Comment by ThreeToZero | Hacker News Reader

Comment by ThreeToZero | Hacker News Reader

A modified A* that solves the fire routing problem (less efficiently than OP's I think).

Each A* location stores where it comes from, how long it takes to get to it, and how many fires it passed through to get there. The algorithm only considers fire cells neighbors if the current number of fires passed through is less than the current fireWillingness global.

1. count fire tiles within movement range

2. run A* from src to dst completely avoiding fire

3. if we can reach then that's the solution

4. if we can't reach, increase fireWillingness to 1, re-run A* on the board

5. keep increasing fire-willingness until the A* results don't change, or we can now reach the dst.

This works because a low fire path is always better than a high fire path. And increasing fire-tolerance will only shorten the paths from src to dst.

Counterexample:

  ...XX
  SF.FD
  ...XX
  
  S = start
  F = fire
  X = wall
  D = destination

The cat can to the destination in 6 moves passing through 1 fire. In the fireWillingness=1 pass, the middle tile is reached after passing through fire, so the destination appears unreachable. The proposed algorithm will pass through 2 fires instead of 1.

Haha good counter example. Well played

That algorithm (implemented efficiently) is just A* using a different concept of distance.

The distance specifically would be `fire*episilon + steps if steps < max else inf`

It doesn't work if you just change the distance. Having implemented similar variations of A* I agree with Tyler. You need to change more than distance to get this to work.

Usually you need to change the search space and increase the number of states you go through to get the algorithm to differentiate between things you want and things you don't want to happen in your final result.

Reply on news.ycombinator.com