Last time, we saw how to use the spanning tree of the logical graph to select which physical edges to use for our mazes. We also saw that not all spanning trees give good results.
As mentioned in the last post, Prim's algorithm and Kruskal's algorithm can be used to find a spanning tree for a graph, but if we apply it to our lattice grids, we get a very un-mazelike result:
What is happening here? These algorithms find a specific spanning tree: the minimum spanning tree. That is, of all possible spanning trees, they will select one of the ones with the lowest possible edge weight sum[1]. For our lattice grid, each edge has the same length, and thus, the output of the algorithm turns out to depend only on the initial vertex selected and the order that edges are added to and removed from a priority queue maintained by the algorithm.
The weight of an edge is not required to be its Euclidean length, however. We can immediately get better results if we simply assign a random value as the weight of each edge. The resulting minimum spanning tree will give us a much more winding result:
We can achieve a lot of interesting effects with clever selection of logical edge weights; more than a single blog post can contain. As one example, start by assigning a random weight between zero and nine inclusive to each edge of a lattice grid. Then, take two lines that split the square lattice in half horizontally and vertically. Any logical edge that crosses one of these two splitting lines has its weight increased by ten.
The result looks like this:
We have created a maze where each 'component' of the original lattice (based on the splitting lines) is self-contained, and only connected to the others by the minimum number of edges required to ensure that the logical graph is spanned. One immediate video game application of this technique is to make each component its own 'biome', for example, each component might be a swamp, a forest, a desert, a mountain, or an ocean, and players can only cross between biomes at a single location, where your maze generator would place boss monsters.
Tune in next time where we look at more advanced strategies for assigning weights to our logical graphs.
[1] It is worth noting that there may be multiple spanning trees for a given graph with a minimal edge weighting.
No comments:
Post a Comment