3
\$\begingroup\$

I've written a simple A* path finding algorithm to quickly find a way through a tile based dungeon in which the tiles contain the information of walls.

An example of a dungeon (only 1 path for simplicity):

Example of a dungeon with only 1 path through it

However now I'd like to add a variable amount of "Bombs" to the algorithm which would allow the path-finding to ignore 1 wall. However now it doesn't find the best paths anymore,

for example with use of only 1 bomb it generates paths like these:

Examples of paths through the dungeon using a bomb to break through walls

While the correct shortest path would be this one:

Example of desired shortest path using a bomb

The problem is that "Closed Nodes" now interfere with possible paths. Any ideas of how to tackle this problem would be greatly appreciated!

\$\endgroup\$
1
  • \$\begingroup\$ It would help if you showed what changes you made to the algorithm to represent the use of bombs. \$\endgroup\$
    – DMGregory
    Jan 29, 2017 at 16:40

1 Answer 1

9
\$\begingroup\$

The typical approach here would be to treat your remaining bomb count as an additional dimension in the pathfinding space.

So given this situation

2      ↑
   ──────┐
1   ←  o │ →
         │
0      ↓ 

    0  1   2

Our tile at the o (1, 1, 4 bombs) has the following reachable neighbours in the cardinal directions:

move x y bombs cost
0 1 4 1 step
1 0 4 1 step
2 1 3 1 step + 1 bomb
1 2 3 1 step + 1 bomb

This solves the problem of "closed nodes" interfering with possible paths, because the node you reach by blasting through the wall to the right (2, 1, 3 bombs) is different from the node you reach by walking down past the end of the wall, then right, then up (2, 1, 4 bombs). So marking one as closed doesn't prevent exploration of the other.

To make sure you can still terminate the algorithm, you count every node on the exit tile as a goal node, regardless of the number of bombs left - so a path can be considered complete whether it used no bombs or all 4. A*'s cost minimization will choose the best one according to the parameters you give it.

You can adjust your cost function to decide whether the algorithm should always find the shortest number of steps even if it has to use all the bombs (bomb cost = 0), or give it some trade-off like "use a bomb if it saves more than 3 steps" (bomb cost = 2 x step cost, since a bomb use always comes with one step too)

When your maps or number of dimensions are large, you'd probably want to construct these tiles only as-needed, rather than reserving an array for every conceivable configuration (of which many will never be used). For the case you describe though, an exhaustive collection wouldn't be a problem.

\$\endgroup\$
5
  • \$\begingroup\$ Hi thanks to your answer I was able to make it work, I ended up not just adding a dimension for each bomb-use in fear of having the different paths on the dimensions block each other but creating a "completely new" dimension everytime a bomb is used, that has it's own closedlist (which is a copy of the original closed list until a bomb was used + any new nodes closed on this dimension) if later another bomb is used it creates another closedlist by copying it's parent closed node's list! Thanks for the answer! \$\endgroup\$ Jan 30, 2017 at 13:42
  • \$\begingroup\$ Feel free to add your own answer describing the method you used — it might be useful to other developers in the future. There's no taboo here about answering your own question — our goal is to build up a repository of high-quality gamedev info. :) \$\endgroup\$
    – DMGregory
    Jan 30, 2017 at 13:57
  • \$\begingroup\$ Am I right this won't solve the following problem/question: Say I have 2 bombs but for the optimal (shortest) path I'd need 4 bombs. I can now skip around wall A and B, or around C and D, or B and D, ...the algorithm described above won't find the smartest answer to this problem, correct? \$\endgroup\$
    – Krumelur
    Jan 30, 2017 at 15:00
  • \$\begingroup\$ The algorithm in my answer will find the best path possible with the bombs it has. I haven't deeply investigated the other proposed algorithm, but it seems like it should too, although it may do some redundant searching if, eg. two bomb routes cross (by being in separate universes they can't share info to help rule-out longer paths, so each universe has to find that out for itself rather than delegate to the shortest n-bomb path to reach it) \$\endgroup\$
    – DMGregory
    Jan 30, 2017 at 15:32
  • \$\begingroup\$ @EnslavedTuna it should work, but you'll quickly have a space explosion with this. Each bomb will duplicate the size of the search space, so after 10 bombs you increase the search space by 1024! For performance reasons and to easily constrain the number of bombs, I advise to use DMGregory's answer \$\endgroup\$
    – MrBrushy
    Jan 30, 2017 at 16:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .