Random paths generation between points of interest

posted in ProjectW for project ProjectW

Published August 24, 2020

Ahoy !

Following my two preceding entries on random ground generation and on random distribution of entities and points of interest, I present to you my work on random paths generation.

Before starting explaining how I generate paths, I want to tell you how I draw them. For this, I simply use my ground tiling system, and I draw paths by setting my ground grid with the corresponding ground layer element (see my entry on random ground generation). Here, I will do dirt path, so that I simply draw path by using the dirt layer. It also means my path should be given by a vector of coordinates corresponding to tile elements in my grid.

The starting idea is to generate a graph, where each node is a point of interest we want to connect by a path (this could be random, but in my example I want all the houses to be connected, and the “trees circle” to be not connected). Then, I add an edge between each pair of nodes, with weight given by the Euclidean distance.

Of course, this gives way too many edges. Thus, we need to chose a subgraph. I also want all my points to be connected together, so I want the subgraph to contain all nodes, and it should be connected (meaning there is always a path in the graph between each pair of nodes). My initial solution for this was to generate a minimal spanning tree, by using Kruskal's algorithm. Here is the result:

It's a good start, but I can see three issues here. First, there are no crossings (except at the point of interests themselves), which is a bit sad. Secondly and more important, the topology of the path graph is poor since it's a tree. It would be nice to have some cycles. But we don't want to add edges randomly, because it can lead to very ugly results. Finally, the path are all straight lines. It would be fine for a stone road for example , but it's a bit weird looking for a dirt path in a hill/forest environment. Thus, we would like some wiggles.

The first issue is very easy to address. We can simply throw in some extra nodes in the path graph (verifying they are not too close to a point of interest ; this can be done by simply spawning crossings as point of interests themselves). It looks decent, and gives funny path going nowhere (which I think is fine, you could easily remove them if you don't like):

The second issue is a bit more tricky to solve. The solution I came up with was to use a modified version of Kruskal's algorithm. Usually, the way it work is by removing all edges, and then try to add them back, starting with the shortest one and increasing. For each edge, we check whether adding it would connect two disconnected part of the graph together or not, and add it only if yes. In my modified version, if not, then I also check whether adding the edge would decrease significantly the minimal path length between the two nodes (where significantly is given by a parameter, so that I can control if I want more or less cycles). If yes, then I add it. Here is the result with a factor of 2 (meaning I add an edge if it cut in half the distance):

Finally, for the last issue, I followed an idea I saw somewhere, but I don't remember where. The idea was to generate a river by first generating a virtual relief using Perlin noise, and then use a pathfinding algorithm like A* to navigate through it. The pathfinding algorithm will usually follows the shape given by the Perlin noise, giving a nice wiggly shape to the river. So I did the same for the paths. The cool thing is that this approach already gives me a “rasterized” version of the path (since I'm navigating with A* on the tile grid). Also, I can mark cells as impossible to navigate where there is a point of interest not part the path graph. So that I don't have my path going through something it should not (like a “trees circle”). Also, I can play with the Perlin noise parameters to get interesting different looking result. Here is an example: