4 ms·
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
by ThreeToZero 4y ago
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.
- thethirdone 4y agoThat 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`
- laserbeam 4y agoIt 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.
- anonymoushn 4y agoCounterexample: ...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.
- ThreeToZero 4y agoHaha good counter example. Well played