5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What if we take the A* heuristic and subtract it from the path cost we want, then absolute value it and sort the priority queue ascending by the result? \$\endgroup\$ – Spinnernicholas Jan 11 '14 at 0:54
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ That could work, but there has got to be a way to modify the search so it will trend towards cost x. \$\endgroup\$ – Spinnernicholas Jan 11 '14 at 0:48
  • \$\begingroup\$ @Spinnernicholas: What do you mean "trend towards cost x"? You can always terminate the Dijkstra's at a chosen upper cost limit. \$\endgroup\$ – Pieter Geerkens Jan 11 '14 at 0:50
  • \$\begingroup\$ Sorry, that wasn't a good way of describing it, but I couldn't think of a better way to say it at the time. \$\endgroup\$ – Spinnernicholas Jan 11 '14 at 23:48
  • \$\begingroup\$ Search algorithms like Dijkstra and A* use a priority queue sorted by a heuristic in ascending order. That makes it search for the lowest cost path, or the path with cost closest to zero. I want to change it so that is searches for the path with cost closest to x. \$\endgroup\$ – Spinnernicholas Jan 11 '14 at 23:51
  • \$\begingroup\$ @Spinnernicholas: Exactly; That's why I suggested use of Dijkstra rather than A*. If your goal is cost N plus/minus 3, Dijkstra will find all N-3, then all N-2, then all N-1, etc., until finding all N+3. At that point you can make a random selection, possibly weighted, from all suitable candidates. \$\endgroup\$ – Pieter Geerkens Jan 12 '14 at 2:34
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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).
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.