Pathfinding Search for Path of Specific Length

Question

I am creating a roguelike. This question applies to random map generation.

First, I generate areas using a BSP algorithm, where I randomly divide the map into areas. Then, I generate a graph of the areas so that I can use search algorithms to generate paths through the map. It is easy to find the shortest path between two areas, but I would like to find a path with a specific number of steps(or path cost).

So, my question is: What is an algorithm that I can use to find a path that has a specific cost or cost range?

An Example of why I think this is useful: Say that I randomly choose two areas(start and end for example). These area might be next to each other, they might be on the opposite sides of the map. I want to force the player to travel through a minimum number of areas before reaching the end, let's say 5. I should be able to be like:

path = startArea.findPathMinimumCost(endArea,5);

And it will return a path of cost 5, or the shortest path, whichever has the greater cost.

Thank you.

Answer 1

Try this on for size: Always choose a specific corner of the generated map as the origin, then perform a Dijkstra's path-finding and randomly select a destination from those areas which meet the minimum distance criteria. Finally, rotate the map according to some algorithm to imply random start location to the user.

Answer 2

I would suggest to incrementally make your shortest path worse. Start with the shortest path and incrementally block some random edges within your path, and search again. If no path is available anymore, choose a different edge.

Answer 3

In graph theory terms, you want to find a simple path (path with no repeated vertices) from A to B with a certain length. One approach is to find all simple paths from A to B, then choose the right one from among that list.

This SO question covers the first part (finding all paths from A to B). In summary, you can do this:

• Use a modified BFS to find all paths starting from A, keeping the ones that get to B and discarding the ones that don't.
• You need to modify BFS so that instead of updating a node's predecessor if you find a shorter path to it, you keep a list of possible predecessors (as well as lists of visited nodes to keep the paths simple)
• Finally, backtrack from B through all the possible predecessors to build the list of paths; select the best path using some criterion (e.g. closest length to target).