5 ms·

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 t

by scg 4y ago

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)

kenjackson 4y ago
I agree. That description of the problem was horrible. Maybe ChatGPT could write a better description and then people could code up the algorithm.
deleted 4y ago
[deleted]
syntheweave 4y ago
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 4y ago
  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?
  - syntheweave 4y ago
    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.
  - wrsh07 4y ago
    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.
- dureuill 4y ago
  > 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.
tinco 4y ago
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.
- jobstijl 4y ago
  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?
- PeterisP 4y ago
  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.
- TylerGlaiel 4y ago
  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 4y ago
    Solve once for each number of fire tiles n.
underanalyzer 4y ago
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 4y ago
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 4y ago
  it had 4 movement as its base, the numbers over its head were a bonus movement status effect (used for testing this stuff)

by scg 4y ago

kenjackson 4y ago

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

deleted 4y ago

[deleted]

syntheweave 4y ago

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 4y ago
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?
- syntheweave 4y ago
  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.
- wrsh07 4y ago
  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.
dureuill 4y ago
> 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.

tinco 4y ago

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.

jobstijl 4y ago
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?
PeterisP 4y ago
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.
TylerGlaiel 4y ago
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 4y ago
  Solve once for each number of fire tiles n.

underanalyzer 4y ago

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 4y ago

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 4y ago
it had 4 movement as its base, the numbers over its head were a bonus movement status effect (used for testing this stuff)