Actually, if the state A* searches through is not "tile reached" but "tile reached + count of fires on path", then it just becomes regular A*. This solves the A

Actually, if the state A* searches through is not "tile reached" but "tile reached + count of fires on path", then it just becomes regular A*. This solves the A to C doesn't always go through B, because it turns B into multiple distinct states, some with fires, one without. There are a few issues with this. Search state is bigger (performance goes down), might not scale if other search features are needed in the game, you might need to be smart about when you stop the search and how you write your heuristic to not have to reach all combinations of fire counts before you end your search... But the trick to "just use A*" is not in modifying the cost, but changing the search space. PS. I see no reason why you should change your current code, obviously. PPS. I don't think GPT could come up with that insight. It sure didn't in your case.