Blog d’un « connard amer »™

I had an epiphany three days ago, and I could not stop thinking about it since. I realized that dungeon was nothing more than a graph. It does seem to say anything like that, but there are a lot of implications.

This is not a new idea. Others have already spoken before me. For example, Steve Segreto (based on an original work of David Adam) assumes that each cell is a node. A cell in the middle of a room is connected to 8 other cells. This representation gives a lot of nodes and edges. I personally find that it gives too much.

Two reasons make me say this. The first is that algorithms who need to travel many times the graph will have their execution time too long to be reasonable. Do not forget that the maps should not put an eternity to generate. The second reason is that we lose information about the structure of the dungeon itself. We lose the concept of rooms/tunnels. But I find her particularly interesting.

Let's take the example of a monster that is somewhere in the dungeon and tried to reach the player. To do this, consider the Dijkstra pathfinding algorithm. It needs to traverse the entire graph to find a solution. As a result, the execution time can quickly become substantial if the graph is immense. Moreover, once in a room, go to the next tunnel, the shortest route proves to be a straight line (with Bresenham example). Dijkstra's no need to know that. It's the same for tunnels. Once in, there is no real surprise to get to the other side. This representation does not take that into account and we will have to run Dijkstra every time the monster will move one cell. We quickly realize how this representation is expensive. And here it is assumed that there is only one monster that follows the player. Imagine with several…

The way I see a dungeon addresses these issues. Rather than from the fact that cells are the nodes of the graph, I consider that the rooms themselves are the nodes and tunnels are edges. This implies several things. First, the graph is greatly simplified. It has indeed many fewer nodes and a lot less edge. Dijkstra will therefore act to a higher level of abstraction and go faster. He does not calculate the path himself inside a room when he wants to go from one edge to another. Just use a simplified version of Bresenham who give us only the next cell where to go (without having to place the algorithm in full). It's the same for tunnels.

It should be noted that unlike the first representation, the one I propose implies that the cost of the edges is not the same whatever the edge. Indeed, the tunnels do not have the same length and the rooms do not have the same size. We must take this into account during the exploration of the graph. We can already count the number of cells in a tunnel to find the cost of an edge. But it does not include the size of the room. I have not yet found a miraculous solution, but the fairest is to consider a tunnel from the middle of a room to go to the middle of another room. It should therefore, in addition to the number of cells in the tunnel itself, add the number of cells needed to reach the middle of each room that the tunnel connects.

We must also pay attention to the case of tunnels that have branches. Such tunnels will not link only two rooms, but a variable number. One solution might be to avoid such tunnels or consider branching points as pseudo-rooms of size 1 × 1.

Whichever representation is chosen, it is pleasing to note that this allows us to do certain things made totally impossible if we just see a dungeon as a 2D matrix. For instance we can manage to put the maximum distance between the player and the exit (to prevent him from having to finish the level seen just a single room). But it can also be used to generate the dungeon. We construct a graph, and there is actually a dungeon in creating the 2D matrix represents. Although for this example, the second representation is more appropriate.

Well… I have yet push the thinking at the end, but I do see advantages to represent the dungeons as graphs where rooms are nodes and tunnels are edges.