This Week In Veloren 31

Thanks to all of the contributors this week, @Timo, @Zesterer, @Slipped, @Pfau, @Muqito, @tommy, @imbris, @yashaslokesh, and @haslersn!

Thanks to @Pfau for this week's Screenshot Saturday. We're excited to see what comes out next week!

Programming

Generating Towns by @Zesterer

We'd like generated towns to have structure. To do this, we generate them in several passes. They look something like this:

Foundation Pass

First, we split the town up into 9x9x9 cells. For each one, we work out whether it sits close to or below the surface of the terrain. If that's the case, we designate that cell a 'foundation'. Foundations are special cells that permit the generation of other structures in later passes.

Road Pass

In this pass, we choose an initial location from which all roads in the towns will be connected. From there, we repeatedly choose a random road cell and extend the road out across the foundation layer by a random number of cells. If we hit another road in the process, or there are any significant changes in altitude, we stop the road. In addition, we make sure that roads never run right next to other roads. The result of this process is a relatively convincing road network for the town with multiple high streets.

Area Pass

The third pass is used to designate specific regions of the town. Here, we choose a random road cell and a neighbouring empty cell. From here, we "grow" a region using a flood fill algorithm until its randomly determined growth energy is expended. Parks, trade districts, and other such areas all have different growth energies with random variations. Once a region is designated, we disallow buildings forming on it in later passes.

Building Pass

This pass generates buildings. Like the previous pass, we choose a random road cell and a neighbouring empty cell. From here, we grow the building from the starting cell. Buildings are also permitted to grow vertically upwards, although they are not permitted to grow out over an empty space to form an overhang (yet). Once the flood fill is complete, we do two things: firstly, we eliminate any cells that don't have enough neighbours (to avoid ridiculously narrow buildings). This can, in rare cases, result in the total elimination of the building. Then, we decide whether to keep the building or throw it out based on its size. The building falls under a given size, we throw it out and try again.

Wall Pass

The final 'high-level' pass is the wall pass. Here, we use a flood fill algorithm to designate external parts of the town by growing inward from the edges. When a non-empty cell is encountered, we don't go further. As a side-effect, we remove unused foundation cells that appear in external cells. After this, we use another flood fill algorithm to probe outwards from the centre of the town, designating any cells it hits as internal cells. Now for the magic: when the flood fill algorithm encounters an external cell, it designates it as a wall. Once completed, we clean up the walls in much the same way as the previous pass, removing walls that have two few (or too many) neighbours. The result is a clean boundary wall around the entire town.

Module Pass

The last pass is used to assign modular components to buildings and walls. In this pass, we go through each wall and building cell and take a look at what neighbours it has. Based on the neighbours, we attempt to match it with a particular pre-built voxel model that is designed to fit certain neighbour conditions. This will then be used for block generation when players approach the town.

There is still a lot of work to do to improve towns, but these are the fundamentals. Stay tuned to later TWiV posts to hear more as they improve!

Other work

@Timo has made great progress on the inventory system, take a look at the videos above. @Sharp has continued work on rivers and drainage. There will be more to come on this in the upcoming weeks.