Minimum spanning tree
« Friday, September 13, 2013 »

game Kruskal Prim

While reading on wikipedia about the Prim algorithm, I found out that minimum spanning tree algorithms could be used to create randomly generated maze. In order to create a maze, we have to generate a grid of edge with random weight.

Passing the edges inside a kruskal or prim function should return a list of edge that can be used.

That said, this kind of algorithm can be used to create dynamic map for online games.

Let say we want to build a map where each node of the graph is a capture point. We'd like to build the map on the client using a seed. The seed is sent to both clients for a 2 team game. The seed has to be the same to generate the random weight on every edges of the map.

Since map should be built randomly, we cannot exactly tell how many capture point will be more or less favorable to a team. For that reason, I came up with the idea of splitting the graph in two while generating the maze. Let say we have 5 special nodes.

  • Node A is the spawn point for team A
  • Node B is the spawn point for team B
  • Nodes P1, P2, P3 are node use as portal between the 2 graphs

We build a graph using n capture point. 15 nodes on one side, and 15 nodes on the other side. Of the 15, there is Node A and nodes P1, P2, P3. in the other graph, Node B and nodes P1, P2, P3.

Pass both edge set to a minimum spanning tree generator and join both sets. You should end up with a set of nodes joining all the 30 nodes. Since more than one node will be shared accross the 2 graphs, the resulting graph will have edge cycles. In other words, multiple possible path to use to get from Node A to Node B. In a game where multiple teams could be created, we could split the graphs into multiple subsets.

I also believe that using those algorithms, could be used to create randomly generated levels. For a game where users have to pass by a particular place, we could use the technic I developped above to share a Node with an other graph. The shared node could be a room where that a player has to cross after killing a boss.

Other important thing to remember is that this algorithm is usefull to generate things that could be much more complicated than a maze. A maze is built on a grid, a game could be built on a set of nodes connecting the closest nodes to each others. The location of the nodes could be in two dimension or even three dimension. Since the algorithm is only connecting 2 nodes by one edge while preventing cycles and making sure that each nodes are accessible. In doesn't really matter how is the graph presented. One room could access an other room with a staircase or a tunnel or even a wormhole.

I will try to create a 3d maze using opengl in the following weeks. My first try should look like a 2d maze with walls.

comments powered by Disqus

Copyright © 2015 Loïc Faure-Lacroix