1
\$\begingroup\$

I understand how A* works, but I don't understand how movement is implemented, e.g. creating a list of directions and then going through that list until every direction is empty. How does that work?

EDIT: Node based.

\$\endgroup\$
7
  • \$\begingroup\$ It really depends on the type of game you are working on. Is it cell-based? Is movement not restricted by your cells (you can move half a cell, stopping whenever you want)? Can you only move whole cells? You should specify, since if you don't the question will be considered too bread, and probrably won't be answered. \$\endgroup\$
    – Leo
    Jul 29, 2017 at 18:14
  • \$\begingroup\$ @Leo Node/cell based, I guess. Movement isn't restricted. \$\endgroup\$
    – Merle
    Jul 29, 2017 at 18:17
  • \$\begingroup\$ You described the core idea: use pathfinding to find a path consisting of a list of intermediate points/moves/directions, then each frame/turn take a step according to the next instruction in that list until it's completed and you progress to the next one, until ultimately you've performed every intermediate step in the path and have arrived at the destination. What specific part of this do you need help with, or what particular problem have you encountered in trying to implement it? \$\endgroup\$
    – DMGregory
    Jul 29, 2017 at 18:22
  • \$\begingroup\$ @DMGregory Like I said, movement isn't restricted. For example, you might move 6px each update instead of one node, but the problem is the node width (e.g. 64) isn't divisible by 6, so I need to adjust that. Also, how would you handle other things moving the player/enemy, like knockback? How would you get back on track? \$\endgroup\$
    – Merle
    Jul 29, 2017 at 18:31
  • \$\begingroup\$ How does that pose an issue? If I know I want to get to (A, B), I move my 6px per update toward that point from wherever I happen to be (even if I was knocked around since last update). When I'm less than 6px from that point I can start moving to the next intermediate point in line. (Or if you want to be really precise, you could move the last 4px to this point, before moving your remaining 2px budget toward the next one). For a big knock you might need to re-plan the path (eg if you get kicked off a bridge) but none of that fundamentally changes the strategy. \$\endgroup\$
    – DMGregory
    Jul 29, 2017 at 18:42

2 Answers 2

1
\$\begingroup\$

Assuming for the moment that you want simple linear motion with 0-time turns and constant speed, the basic method is to generate the points along the path that you are going to move through and follow the lines between the points using linear interpolation (AKA Lerping).

At each movement phase you find the vector to the next point in your path and move towards it by whatever fraction of your movement speed you can. If you reach it then you discard that point, pull the next one from the queue and repeat until you have moved the full allotment. Once you reach the final position - with or without movement left over - you can signal that you are done moving.

This should handle minor changes in position from outside forces - being knocked back by an attack, pushed around by environmental factors, etc - as long as the movement doesn't put you in a position that will require a whole new path.

The actual movement calculations are reasonably easy. Get the difference between your current point and the target as a vector, scale it to be no longer than your movement speed, change position and check to see if you have movement left over.

I whipped up some code:

public class Mobile
{
    public Point2D Position { get; set; }

    private Point2D _lastMoveDir = Point2D.Up;
    public Point2D LastMoveDir { get { return _lastMoveDir; } }

    public double Speed { get; set; }
    public readonly Queue<Point2D> MoveQueue = new Queue<Point2D>();

    private Point2D? currMove = null;

    // Process move queue, updates Position
    public bool DoMove()
    {
        // check current move target
        if (currMove == null)
        {
            // if no more moves then exit, else get next move
            if (MoveQueue.Count == 0)
                return false;
            currMove = MoveQueue.Dequeue();
        }

        // total distance to move is the same as speed
        double distance = Speed;

        // Use as much movement as possible
        while (currMove != null && distance > 0)
        {
            // Find next position along the path
            Position = CalculateMove(Position, currMove.Value, distance, out distance, out _lastMoveDir);

            // Get next move if any movement left over
            if (distance > 0)
            {
                if (MoveQueue.Count == 0)
                    currMove = null;
                else
                    currMove = MoveQueue.Dequeue();
            }
            // test if at target (with error margin)
            else if (Math.Abs(currMove.Value.Subtract(Position).LengthSquared) < 1E-10d)
                currMove = null;
        }
        // return true if still moving
        return currMove != null || MoveQueue.Count > 0;
    }

    // Move in the direction of the target point as far as we can
    private static Point2D CalculateMove(Point2D ptFrom, Point2D ptTo, double distance, out double remaining, out Point2D moveDir)
    {
        remaining = 0;
        // get direction of movement as unit vector
        moveDir = ptTo.Subtract(ptFrom).Unit();
        // get available movement length
        var dirlen = moveDir.Length;
        // if less available length, update vars for this move
        if (distance > dirlen)
        {
            remaining = distance - dirlen;
            distance = dirlen;
        }
        // find location to move to relative to current position
        var offset = moveDir.Multiply(distance);
        // return it 
        return ptFrom.Add(offset);
    }
}

Apart from the inconsistent naming conventions (I know, I'm terrible) and some sloppy techniques, this does produce the kind of movement I describe above. It's supported by a fairly simple Point2D struct which should be easy enough for you to replace with your own preferred variant.

The code above also tracks the last move direction so that you can rotate your game object to face the direction of movement if desired.


If you want a more interesting motion than linear interpolation there are a whole range of curve generators out there that you can use. My preference for this kind of thing is the Catmull-Rom algorithm. It - and several others - generates path segments that vary in length depending on the tightness of the curve. Tighter curves have shorter segments and you can use that to control speed to simulate slowing down for turns and accelerating down the straighter sections.

The downside in this instance is that it requires a fair amount of calculation to get right, so pre-calculation is a very good idea. Unfortunately that means it won't handle nudges anywhere near as well as the simple linear interpolation code.

\$\endgroup\$
0
\$\begingroup\$

Create a list of directions and go through them. If you get knocked off course, just adjust slightly. Readjust completely if there's a bigger unexpected obstacle.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Your answered your own question by basically reiterating what you said in the question? And it's not even correct, in normal A* there will never be an "unexpected obstacle" because the graph shouldn't change. If the graph changes, that's a different question. If the graph changes as you move through it, you may want to look into D*-lite. \$\endgroup\$ Jul 31, 2017 at 1:15
  • \$\begingroup\$ @BlueRaja-DannyPflughoeft I needed confirmation, and somebody confirmed it. Besides, I implemented it and it works fine. I'll look into it though. \$\endgroup\$
    – Merle
    Jul 31, 2017 at 4:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .