# Longest path algorithm for roguelike maze generation

I have a simple grid-based map composed of rooms, like this (A=entrance, B=exit):

```   0 1 2 3
#########
0 #B# #####
#########
1 #   ### #
#########
2 # #     #
# #     #
3 # #     #
#########
4 # ###   #
#########
5 ###A    #
###     #
6 ###     #
#########
```

And I'm stuck trying to make a suitable algorithm to create a path of doors between the rooms, in such a way that the player has to explore most of the map before finding the exit.

In other words, I'm trying to find the longest possible path from A to B.

(I'm aware that this problem can be solved for acyclic graphs; however, in this case there can be cycles.)

EDIT: Another example where rooms are connected using floodfill, and the exit is chosen as the farthest room from the entrance:

```   0 1 2 3
#########
0 #B#     #
# #-#####
1 # | #   #
### #   #
2 ### #   #
###-#-###
3 #   | ###
#-#######
4 #A|     #
# #     #
5 # #     #
# #     #
6 # #     #
#########```

Note that the path to the exit is not the longest possible path at all.

-
If you force the player to take the longest path possible, you are actually building a straight path that pretends to be complex. This is bad. – o0'. Nov 6 '10 at 13:31
It's not bad (it's the basis of the rail shooter genre, for example), but you need to be aware you're doing it and design the rest of your game to work well with it. – user744 Nov 6 '10 at 18:07
It's also easier to control the pace of the game when the levels are mostly linear. It makes it possible to add, for example, a recovery room after a particularly difficult monster room. If there wasn't a main path, the distribution of challenges and rewards would be random. – jSepia Nov 7 '10 at 17:51

I believe you already have great answers, but here is my \$0.02 of theoretical solution to the problem.

What you want is NOT the longest path, but longest shortest path. You want the room that is the farthest away, given you are considering the shortest path to the room. This probably sounds confusing, but it is very easy to calculate.

1. Start at your starting room. Mark each of its neighbors 1. They are distance 1 away from the starting room.
2. For each room marked 1, visit each of its UNMARKED neighbors and mark them 2. They are 2 distance away from the start.
3. Continue until you have covered all the rooms. The room with the maximum number is farthest away from the start.

Computing an actual longest path (wont take too long for say 10 rooms) will not work because you cannot make the player take that longest path. So putting the entry and exit in two rooms farthest away from each other is your best bet. To find this, calculate the farthest room from a random room. Then, from that room, find the farthest room. This is called finding the diameter of a Graph, please Google it.

-

2 Stack Overflow posts similar to this one: graph longest path, reference from same post .

-

A possible alternative would be to create a (maximum?) spanning tree using Prim/Kruskal (in order to eliminate cycles) and apply a traditional longest path algorithm on the spanning tree.

However, I'm worried that the spanning tree algorithm will tend to create dead-end branches, forcing the player to backtrack constantly.

EDIT: Result of using a Kruskal-based algorithm and placing the exit at the end of the longest branch:

```   0 1 2 3
#########
0 #A|     #
# #####-#
1 # #     #
###     #
2 ###     #
###     #
3 ###     #
###-#####
4 #   |   #
#-#####-#
5 # ###   #
#-#######
6 #     #B#
#     #-#
7 #     | #
#########```
-
I was going to suggest Primm too :-), +1 , I think backtrack is an important part of a lot of games too... check diablo 2. – Mr.Gando Nov 5 '10 at 11:39

Here's something to fiddle with:

``````Connect each room with a door to another room.
N = 0.75*TotalNumberOfRooms
Until (pathSize > N) {
Use A* pathing to get a path from A to B. (G being size of room, or # of monsters)
if (pathSize < N) remove a connection/door
if (noPath) choose a different door/connection
if (room.doors < 1) choose a different door/connection
}
``````

I'd remove doors randomly along the path, otherwise you end up with 1 door at the exit, and tons of doors at the start.

I think this is `O(n^2)` so not great for large maps.

-
A very elegant solution in principle. Next time I should try to think of something like this before going for convoluted techniques. – jSepia Nov 6 '10 at 4:47
Well, elegant maybe but it's going to be a processor hog. O(n^2) won't scale well with large maps. – Stephen Furlani Nov 8 '10 at 14:53

I think you're going about this the wrong way. Maximal path in a graph with cycles is technically undefined because it's infinite if the cycle lies between the start and end. There are probably clever ways you can extend/restrict the definition of maximal path, but I don't think that's the best approach here.

You're not trying to model an actual long path (e.g. a robot trying to explore as much area in a map as possible). You're just trying to get the player to explore many rooms.

So, make the chance the player finds the exit proportional to the percentage of the map explored so far. Let's say there's X rooms on a level, and the player character has explored Y. Next time the character enters a room, place the exit there with f(Y, X) probability. A trivial example of f might be (Y*Y)/(X*X) - e.g. for 10 rooms, there's a 100% chance the exit in the last room, 81% chance it's in the next to last room - and only a 1% chance it's in the first room.

You can tweak the equation however you want to make the game feel right, and maybe even give the player some abilities to make it more likely to generate. The key part is, don't generate the exit until the character actually enters the room. This method is also immune to player knowledge of the dungeon generation algorithm; even if the player has strange movement patterns like the knight's jump in NetHack or teleportation, they're going to have to explore more rooms to find the exit.

If you must statically generate the exit, you can use the same idea with a virtual character. Imagine a flood fill starting from the character's position, moving once cell each iteration. The last room to be filled is the room where the exit belongs (in fact, the last cell to be filled is the cell where it's farthest from the player). However, in this case the player has more information about the exit - if they're on the left, it's most likely on the right - and if they can teleport, may actually be able to get there faster than a normal random walk.

Finally, I just finished a roguelike where the exit spawned on the other side of the map from the player character, and then wandered randomly. Some items in the dungeon made it visible on the map, at the expense of getting hungry faster. I didn't do any analysis, but it definitely felt like I had to explore more of the map to find it, and it gave the levels a unique feel.

-
Dynamic generation does seem like a pretty good idea, as long as the player doesn't notice. Otherwise I think they would feel quite cheated. I love the floodfill idea, though. – jSepia Nov 4 '10 at 19:14
Well, your entire proposal is in some sense cheating the player. Don't blame me for refining the math to not require a world model. ;) But you can use design tricks to make it more palatable - for example, the exit is placed a priori, but a key required to use it is generated in the method I described, or placed on a monster that only spawns after exploring X rooms / killing X monsters, or opening the door requires flipping X switches, one in each room, etc... – user744 Nov 4 '10 at 19:19
I tried a floodfill approach. It does a good job of connecting every room and produces short branches, but it doesn't actually produce the longest possible path to the exit even if the exit is the last node visited (or, in my implementation, the farthest one). (example added to my question) – jSepia Nov 4 '10 at 21:43
I'm all for key/switch-based mazes, though. It just seems easier to implement that sort of thing with trees, because then if you have two branches, you can detect which branch leads to the exit, block it, and put the key in the other branch. – jSepia Nov 4 '10 at 21:47
But I do admit that I was wrong in thinking that it was an "A to B" pathfinding problem. I realize it makes more sense to find the exit as a result of the algorithm rather than as a goal. – jSepia Nov 4 '10 at 21:51