Vagabond – City Generation

15 Mar 2020 by pierre

Hi everyone!

Last month, I had been working on city generation. The goal was to use buildings generated by my building generator, to place them on the map and to link them using roads.

In this post, I will share with you the main ideas and techniques I used to achieve that.

Here is an animation showing the overall process:

Building Placement

To place the buildings I use an algorithm inspired by Bridson’s algorithm for Poisson Disk Sampling. The idea is to place buildings one by one, and to place a new building next to an already placed building. The already placed building are tried from oldest to newest, this way, the cities have a concentric shape that is more organic.

Contrary to the original algorithm for Poisson Disk Sampling, I do not use a grid to check for collisions because the bounding box of each building is different, instead, I use a quadtree.

Road Network Generation

For road generation, I decided to reuse the algorithm I have already developed for roads between cities described here: pathfind each door to each door using A* algorithm with a discount for already used road segments.

The problem is that contrary to the problem with cities where I had a dozen cities, here I may have several dozens buildings and as the number of pathfinding runs is quadratic with the number of buildings, it makes a huge difference. Moreover, for roads between cities, the graph was small, but for roads between buildings, the graph is a grid, it has a lot more nodes and edges.

For a city with 40 buildings, it took 200ms to compute the roads. I thought it was too much.

My solution to reduce the time spent is to reduce the number of pathfinding runs done. The idea is to find paths only between a building and its direct neighbors. To find the neighbors of buildings, I compute the Delaunay graph (I use my library to compute it, you can read more about it here). Here is the Delaunay graph of a set of buildings:

Now, I only have a linear number of pathfindings to perform. For a city with 40 buildings, it now took only 20ms, that is a big improvement!

We now have a road network but it lacks structure and it is a bad navigation mesh. To fix that, I modified the cost function of A* to penalize turns. Consequently, the paths are more straight and simpler as you can see:

Currently, the edges are all of length one: they link two cells of the grid. But as the graph is composed of long straight lines, we can compress the graph by retrieving these lines. I achieve that using a DFS:

This graph is way more suitable as a navigation mesh.

The final step is to represent these roads as tiles. I simply rasterize a disk of random radius and with a random offset on each cell of the road network to have something a bit chaotic:

And here is the final result with buildings displayed:

Conclusion

Let us look at some cities generated by the generator to conclude this blog post:

The results are still a bit monotonous but it will be better when the buildings will be more distinct and new types of structures such as market places, wells or castles will be added.

The next step is to populate the cities with villagers.

All the assets used in this post were made by OpenGameArt artists, you can find them there.

See you next time for more!

If you are interested in my adventures during the development of Vagabond, you can follow me on Twitter.

Tags: vagabond pcg