koobas.hobune.stream
Astar Pathfinding - do not use last visited node
I want to achieve, that the last moved to node is not taken in consideration on the next created path.
Once a node has been reached i recreate the path. Move to next node and so on.
The problem is, the goal node is moving, so it can happen the enemy creates a path backwards, which i want to avoid.
The enemy should always take the optimal way but never backwards/where he came from. How is that possble?
The enemy should always take the optimal way but never backwards
Well those two conditions may collide. If there's a way right around an obstacle or left around A* will always find the shortest path. If the shortest path is the left way it will go left. However if you re-calculate the path when the target has moved more to the right it's possible that the right way is shorter. Just excluding the last node will not help with this problem. Even when you exclude the last node the right path might still be shorter, just with an extra side step.
One solution is to simply avoid recalculating the path each step if the path is still relatively long. So for example calculate a path to the target. If it's 20 nodes long you may recalculate the path once you moved 20%, 30% or 40% of the path. That means after about 4-8 blocks it recalculates a new path.Now the new path might be only 15 nodes long. That means as closer the enemy gets the more often it recalculates the path. This should eliminate such edge cases i've mentioned above. Of course if you want an instant reaction when a previously walkable path gets blocked, you can still trace the path each step to check if all nodes are still valid. If the path gets blocked just do an immediate recalc.
Such an approach is also greate to minimize recalculation overhead. Especially when an enemy is far away A* can get quite expensive in some edge cases.
Hi Bunny,
thanks alot for that indepth info. Since i only check 4 dirs i excluded the search for the diagionals. Somehow i just can't exclude the "back" direction, it always seem to stop after 1 step and can't find another optimal way after that step.
I also tried to create the optimal path and somehow store an alternate pass, with excluding the last node. But it doesn't work properly, because it may end in a "deadend". But was close to what i thought of.
The % approach is an interesting idea, but still can end up in a situation the enemy turns backwards and moves to the last visited node.
I already notice excluding the last node directly doesn't work properly as well.
Somehow i think to store the "best path" and override it with a maybe not so optimal but excluded back node anyhow is the way it could work. Do you have an idea to such approach?
