Huh that’s a neat problem. My instinct was to use a (fire, regular) tuple for cost, but then what A* heuristic can you use…
I guess run it once with no cost for regular tiles and remove fire from any tiles it used. Then run with normal tile costs, but block fire tiles. That doesn’t break ties nicely of course and I’m not convinced the first pass has a good A* heuristic either…
It works but you do it twice when you could do it once
But I expect anyone who’s programmed some pathfinding before to, at the minimum, be able to say “run A* twice”. Somehow AIs never understand the prompt well enough
I think the best option is to make sure to have ‘sorted’ the calls to the fire tiles, you can do that by having them in a separate grid or just stash them to a small local array on stack when you encounter them, and investigate those at the end of the loop
If there’s no result that’s been found under the cost limit without the fire at each point of the algorithm, you do do the recursive calls for the fire as well, and you flag your result as “has fire in it” for the caller on top
When getting a result from your several recursive calls, you take the best non-fire result that’s under 15 tiles long, else you take the best result period
Then once you’re back to the top level call, if there was a non-fire path you will get that result, if there wasn’t you will get that instead
Huh that’s a neat problem. My instinct was to use a (fire, regular) tuple for cost, but then what A* heuristic can you use…
I guess run it once with no cost for regular tiles and remove fire from any tiles it used. Then run with normal tile costs, but block fire tiles. That doesn’t break ties nicely of course and I’m not convinced the first pass has a good A* heuristic either…
It works but you do it twice when you could do it once
But I expect anyone who’s programmed some pathfinding before to, at the minimum, be able to say “run A* twice”. Somehow AIs never understand the prompt well enough
I think the best option is to make sure to have ‘sorted’ the calls to the fire tiles, you can do that by having them in a separate grid or just stash them to a small local array on stack when you encounter them, and investigate those at the end of the loop
If there’s no result that’s been found under the cost limit without the fire at each point of the algorithm, you do do the recursive calls for the fire as well, and you flag your result as “has fire in it” for the caller on top
When getting a result from your several recursive calls, you take the best non-fire result that’s under 15 tiles long, else you take the best result period
Then once you’re back to the top level call, if there was a non-fire path you will get that result, if there wasn’t you will get that instead
Undeniably faster but doesn’t change the big O of course. I wonder how it would benchmark.