[syntheweave]

The problem is, indeed, that Mr. Glaiel did not know the category of problem he was dealing with.

A correct statement would be: "Given a solution set containing both the shortest path through fire and the shortest path avoiding fire, select the solution that fits within six tiles of movement, preferring the solution that avoids fire where possible."

It's a constraint optimization problem in disguise: generate a solution set, then filter and rank the set to return a canonical result. That describes most of the interesting problems in gameplay code: collision and physics can use that framing, and so can most things called "AI". They just all have been optimized to the point of obscuring the general case, so when a gamedev first encounters each they seem like unrelated things.

The specific reason why it seems confusing in this case is because while pathfinding algorithms are also a form of constraint optimization, they address the problem with iterative node exploration rather than brute forcing all solutions. And you can, if you are really enterprising, devise a way of beefing up A* to first explore one solution, then backtracking to try the other. And it might be a bit faster, but you are really working for the paycheck that day when the obvious thing is to run the basic A* algorithm twice with different configuration steps. You explore some redundant nodes, but you do it with less code.

[rjmunro]

Can you not do A* where it normally costs one point per tile, 10 points for a fire tile but 1000000 points for > 6 tiles, so you never explore the > 6 options unless you have run out of shorter routes?

[wrsh07]

If the parent's description of the problem is correct, then imagine this:

You have a solution of length 6, no fire; Solution of length 4, one fire; Ok sure you prefer the no fire one.

the score for the paths is 6 and 13, respectively

Your algorithm works! But as soon as you have a solution of length 10 (or some length bigger than the length you want), a* still prefers that to the solution without fire - but the answer must be less then or equal to six steps

You can modify to make fire cost 1.1. Now if you find a solution of length 6, you know it must be correct (it minimized the number of fire squares and ended up with a length six solve). But if it's not length 6, you need to increase the cost of fire and run again if there was any fire in your solution.

[syntheweave]

At a glance, it might be OK that way, and I would give it the gold star. It's just unintuitive to make the leap to "apply a cost to the total length of the path" as a way of expressing preferences among distinct categories of path.

Implementation of the categories as completely independent paths falls out of the clarified problem definition directly. It's really in nailing the specification that the problem is hard, i.e., even with GPT we're still programming.

[dureuill]

> And it might be a bit faster, but you are really working for the paycheck that day when the obvious thing is to run the basic A* algorithm twice with different configuration steps.

Pretty much this. Attempt to find a path to the target destination with a first A* run that disregards fire tiles, and if that fails due to limited movement, then do a second run with the fire tiles. I like that this mirrors the decision making a human would follow, too: I won't cross the fire tile unless I'm absolutely required to.

[JamesSwift]

Yeah, I'm not really that familiar with pathfinding, but my naive take is that you actually want 2 scores to rank on rather than making everything implicit in a single cost factor. You have a movement cost and a preference cost. The path needs to suffice the movement budget, but you want to optimize based on preference score.