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). The pathfinding algorithm will usually follows the shape given by the Perlin noise, giving a nice wiggly shape to the river. 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. Here is the result with a factor of 2 (meaning I add an edge if it cut in half the distance):įinally, for the last issue, I followed an idea I saw somewhere, but I don't remember where. 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). 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. Usually, the way it work is by removing all edges, and then try to add them back, starting with the shortest one and increasing. The solution I came up with was to use a modified version of Kruskal's algorithm. The second issue is a bit more tricky to solve. It looks decent, and gives funny path going nowhere (which I think is fine, you could easily remove them if you don't like): 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 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. Finally, the path are all straight lines. But we don't want to add edges randomly, because it can lead to very ugly results. Secondly and more important, the topology of the path graph is poor since it's a tree. First, there are no crossings (except at the point of interests themselves), which is a bit sad. It's a good start, but I can see three issues here. My initial solution for this was to generate a minimal spanning tree, by using Kruskal's algorithm.
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).
Of course, this gives way too many edges.
Then, I add an edge between each pair of nodes, with weight given by the Euclidean distance. 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). It also means my path should be given by a vector of coordinates corresponding to tile elements in my grid. Here, I will do dirt path, so that I simply draw path by using the dirt layer. 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). 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.īefore starting explaining how I generate paths, I want to tell you how I draw them.
0 kommentar(er)
