Longest path algorithm for roguelike maze generation

Question

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.

Answer 1

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.

Answer 2

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 #     | #
  #########

Answer 3

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.

Answer 4

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

Answer 5

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.