[scg]

As a human programmer I didn't quite understand the problem statement until I read the whole article and the tests.

I believe the goal is to find a path with the fewest possible "fire" cells and the minimum cost as a tie breaker. The cost of a path is the sum of its cells' cost and it can't be greater than 5.

If I understood the assignment correctly, I don't think the problem statement is equivalent to what's included in the prompt. Specifically, the prompt doesn't clarify what happens if you have to cross through multiple "fire" cells.

> Fire tiles cost 1 point to move through, but they should avoid pathing through them even if it means taking a longer path to their destination (provided the path is still within their limited movement range)

[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.

[tinco]

By the time you've formulated the problem as: "Give me the shortest route with a cost of 5 or lower that doesn't go through fire, and if that doesn't exist, the shortest route with a cost or 5 or lower that goes through fire." Then you've basically formulated the algorithm as well.

That's also precisely where one of the programmer's greatest challenges lies, to carefully translate and delineate the problem. I agree it's a bit steep to ask the GPT to come up with a precise solution to an imprecise question, but it's also fair to say that that's basically what the job of a programmer entails, and if you can't do that you're not really able to program.

[TylerGlaiel]

thats also not a correct formulation of the problem, as it needs to minimize the number of fire tiles it passes through. which is where a lot of the complication comes from.

[syntheweave]

Solve once for each number of fire tiles n.

[PeterisP]

The difficult parts and time-consuming parts are not the same.

Since I have experience in both programming and the domain of my tasks, formulating the steps that need to be done for some task is very quick, and they are "good" steps that avoid various potential pitfalls - but then I need half a week to actually make and debug them; so if some tool (or a junior developer) can do the latter part, that's a big benefit.

[jobstijl]

Wouldn't a better formulation be: "Give me the shortest route with a cost of 5 or lower with the minimum fire tiles in the path necessary" Since your formulation doesn't care about the amount of fire tiles in case there is no other solution?

[kenjackson]

I agree. That description of the problem was horrible. Maybe ChatGPT could write a better description and then people could code up the algorithm.

[underanalyzer]

Since this is the comment thread talking about the algorithm I'm gonna add my 2 cents here:

Here's the problem statement as far as I see it: Each tile has a number of move points to spend to go through it (1 for regular and 2 for water). Each tile also has a cost associated with it. Given a max number of move points find the lowest cost path between two tiles or return none if no such path exists.

I'm gonna say this is still modified dijkstra with a small twist. The fire has cost 1, the other tiles have cost 0. However instead of pathing on a 2d grid (x, y) we path on a 3d grid (x, y, moves). All "goal" tiles within (goal_x, goal_y, moves < total_move_points) have a 0 cost edge which brings them to the true goal node. The implementation difference is that the get neighbors function queries neighbors in later grid layers (x+..., y+..., moves + 1 or 2)

[mannykannot]

Note that water tiles have cost 2, so the tile-crossing limit cannot be expressed simply as a maximum total cost.

Looking at the two examples in the paragraph after "And there’s a lot of complication to it beyond the simple cases too", I can't figure out how the movement value is defined, as I can only see 10 and 8 moves respectively, not the 14 and 10 movement value claimed in the following text (and only one water tile on each path.)

[TylerGlaiel]

it had 4 movement as its base, the numbers over its head were a bonus movement status effect (used for testing this stuff)