2
\$\begingroup\$

I've noticed after implementing A* pathfinding into my game, that there is exploitable/unrealistic behavior that goes on when the player moves between two nodes that alter the path of the AI trying to reach them. I have made a few images to demonstrate this problem.

Pathfinding to a static target

This image above shows how the pathfinding in my game would behave if the player stood on the opposite side of a wall than my AI. If the player doesn't move it will take this single path to reach them. Assume that the red icon is the AI (enemy) and the blue icon is the target (player).

pathfinding to a moving target

Now, if the player in this image above moves along the white arrows up and down, and the AI is constantly finding the optimal path to the player (ignore the performance costs of doing that), then the AI will also get stuck moving up and down because the optimal path will constantly shift between going above the wall and going under the wall. Is there a way to modify a standard A* implementation to remedy this? I will include my pathfinding code for clarity, but it's pretty much a standard top down implementation. The "Node" object is a node on my grid, and the grid is an object that holds a list of nodes, with a few functions to find a node from a world point.

public class Pathfinding : MonoBehaviour
{

public Transform seeker, target;
AstarGrid grid;

void Awake()
{
    grid = GetComponent<AstarGrid>();
}


public List<Node> FindPath(Vector3 startPos, Vector3 targetPos)
{
    Node startNode = grid.NodeFromWorldPoint(startPos);
    Node targetNode = grid.NodeFromWorldPoint(targetPos);

    List<Node> openSet = new List<Node>();
    HashSet<Node> closedSet = new HashSet<Node>();
    openSet.Add(startNode);



    while (openSet.Count > 0)
    {
        Node node = openSet[0];
        for (int i = 1; i < openSet.Count; i++)
        {
            if (openSet[i].fCost < node.fCost || openSet[i].fCost == node.fCost)
            {
                if (openSet[i].hCost < node.hCost)
                    node = openSet[i];
            }
        }

        openSet.Remove(node);
        closedSet.Add(node);

        if (node == targetNode)
        {

            return RetracePath(startNode, targetNode);
        }

        foreach (Node neighbour in grid.GetNeighbours(node))
        {
            if (!neighbour.walkable || closedSet.Contains(neighbour))
            {
                continue;
            }

            int newCostToNeighbour = node.gCost + GetDistance(node, neighbour);
            if (newCostToNeighbour < neighbour.gCost || !openSet.Contains(neighbour))
            {
                neighbour.gCost = newCostToNeighbour;
                neighbour.hCost = GetDistance(neighbour, targetNode);
                neighbour.parent = node;

                if (!openSet.Contains(neighbour))
                    openSet.Add(neighbour);
            }
        }
    }
    return null;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ So is the pathfinding function called every frame? A* is doing it's job perfectly well. One option would be a path weighting scheme. Another would be noting the angular distance between first steps in each path. \$\endgroup\$ – Qfwfq May 30 at 5:03
  • \$\begingroup\$ The AI calls the FindPath function every frame for several seconds in order to "track" the player once they have left line of sight, so it is being called every frame in this example. I thought about about weighting it towards the first path it finds but I couldn't think of an admissible way to do that. Could you describe your second approach in more detail? I have a bit of an idea what you mean but I'm not sure. \$\endgroup\$ – Morgan May 30 at 5:21
1
\$\begingroup\$

Doesn't feel like a problem with your implementation but a problem of A*. Leave A* as it is, change when you let it run.

Assume the player will try to confuse his/her pursuer, by doing zigzags for example, and make the pursuer run A* once, then let it move a random number of frames, it can be constant but random is more like trying to catch the player in its own game.

For example:

  • Pursuer runs A* and also decide in advance the next time it will run A* again, random is recommended, between reasonable bounds like 2 tiles min and 6 tiles max. But the max number of tiles must not be greater than the distance to the player, or the following situation may happen: pursuer go pass the player's tile and have to turn back because player moved when the pursuer was 2 tiles away and the next time A* was scheduled to run resulted in 3.

  • Player is aware of A* and tries to exploit it, but he/she cannot predict the next time A* will run. As a result, the pursuer is more believable.

If for some reason a non believable pursuer behavior is wanted, then you can begin doing the random schedule strategy when you detected that you haven't shortened the distance to the target in a given number of frames, and stop after three or four runs and resume A* every frame behavior, to enter random schedule strategy again if you detect at some point you are not shortening your distance to the target.

This may result in the pursuer acting "impatient" when the target isn't reachable, if such situation can occur in your game. And this may or may not be a good thing, depending on the game you imagined. But sure it will make the pursuer look alive. Also, this can be prevented with an extra if to detect when no path was found in addition to just check distance to target after or before A* runs.

Note: I didn't try to run your A* to see if it is correctly implemented, as I don't notice anything wrong in the code at a first glance, and you are already using it, I assuming it is correct.

\$\endgroup\$
  • \$\begingroup\$ I haven't implemented your solution yet but I can see how it works and it sounds like it would solve my issue. Thanks for making the note about the max tiles being less than the total tiles away, I may not have caught that. \$\endgroup\$ – Morgan May 30 at 13:55
  • \$\begingroup\$ @Morgan, glad it helped. \$\endgroup\$ – Hatoru Hansou May 31 at 2:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.