Thank you for sharing your dive into the A* algorithm :)
I always like to think about and discuss algorithms and unfortunately don't find enough time during my regular work.
I'd just like to add one note to what you said: A* will always give the best route (given its constraints) and is like a Dijkstra where the cost function reruns the same value for each estimate. It's important though that the estimated cost has to be equal to or larger than the actual path. This usually is guaranteed by the Manhatten distance, but can bite you in a game where you can teleport (i.e. move to steps in the opposite direction and then skip 10 steps, this will kill the heuristic and can lead to pseudo-optimal paths).
But apart from that: thanks for sharing this (maybe I am repeating myself here ;) )
That is an interesting situation I hadn't thought about before.
A* usually is good enough, but it has these situations where it's just too Greedy, that it misses better options. That is exactly why there are multiple different algorithms out there to explore their trade-offs. This is why developers should work shoulder to shoulder with their level designers, to anticipate these situations and make the better choice.
Either way, a lovely comment Philip, hope to hear from you more!
Nice comment but with one minor issue. A-star's(tree version) optimality is guaranteed when using an admissible heuristic, which means the h value never overestimates the actual cost for any node. So, it is important that the estimate has to be equal to or smaller than the actual cost. With no heuristic function given, that's equivalent to h(x)=0 for all x, it will downgrade to Dijkstra.
So the A* algorithm is asking for "some" information about the distance to the goal, but not too aggressive information.
But the author's code is actually a graph version of A*(because there is a closed list maintained), so admissibility is not enough in some situation to guarantee optimality. We need to ensure another property of the heuristic: consistency, which means h(x) <= cost(x,y) + h(y) should be true for all node x.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Thank you for sharing your dive into the A* algorithm :)
I always like to think about and discuss algorithms and unfortunately don't find enough time during my regular work.
I'd just like to add one note to what you said: A* will always give the best route (given its constraints) and is like a Dijkstra where the cost function reruns the same value for each estimate. It's important though that the estimated cost has to be equal to or larger than the actual path. This usually is guaranteed by the Manhatten distance, but can bite you in a game where you can teleport (i.e. move to steps in the opposite direction and then skip 10 steps, this will kill the heuristic and can lead to pseudo-optimal paths).
But apart from that: thanks for sharing this (maybe I am repeating myself here ;) )
That is an interesting situation I hadn't thought about before.
A* usually is good enough, but it has these situations where it's just too Greedy, that it misses better options. That is exactly why there are multiple different algorithms out there to explore their trade-offs. This is why developers should work shoulder to shoulder with their level designers, to anticipate these situations and make the better choice.
Either way, a lovely comment Philip, hope to hear from you more!
Nice comment but with one minor issue. A-star's(tree version) optimality is guaranteed when using an admissible heuristic, which means the h value never overestimates the actual cost for any node. So, it is important that the estimate has to be equal to or smaller than the actual cost. With no heuristic function given, that's equivalent to h(x)=0 for all x, it will downgrade to Dijkstra.
So the A* algorithm is asking for "some" information about the distance to the goal, but not too aggressive information.
But the author's code is actually a graph version of A*(because there is a closed list maintained), so admissibility is not enough in some situation to guarantee optimality. We need to ensure another property of the heuristic: consistency, which means h(x) <= cost(x,y) + h(y) should be true for all node x.