Game Development Stack Exchange is a question and answer site for professional and independent game developers. It only takes a minute to sign up.
Sign up to join this community
I am working on a 2D RTS like game, basic A* works perfectly for moving a unit from point A to point B.
But now I facing the continuous path-finding problem, like A attack a moving object B, call A* at each frame once Object B's position changed seems inefficient.
so what is the standard method to this problem?
From what I know, you could take a look at the D* algorithm which stands for "Dynamic A*". This algorithm is used to compute pathfinding for dynamic environment, here with a moving target.
Here's a paper using D* for moving target path finding : Moving Target D* Lite
One option is to only make a new path once every few frames. If you did it once or twice a second rather than 60+ times a second then the user is unlikely to notice unless they are both two very fast moving objects
You can use the "dog curve" approach which dogs apparently uses when hunting down someone. They calculate where the impactpoint will be "in the future" and sets of straight to that position.
A simple approximative way could be something along the lines :
A = NPC
B = Target
T = time to get to B:s position (B:s initial position)
Calculate where B will be in 'T' time (if B continues at the same speed / angle) and go there instead.
This is not the perfect way as the distance changes but much simpler than making a perfect solution and much better than just trying to get to 'B'.
A agree with Kylotan that there isn't a standard method.
One method I have seen work was to assume the target continues moving in the same direction and change the goal position as you run through your path finding algorithm. This does mean you have to hold two metrics in your A* nodes (cost and time as opposed to just cost).
To do better than that is very difficult. Unless you actually have knowledge about the unwavering path of the target, you're heading into the land of quite hard AI because you'll have AI's second guessing or simulating the target behaviour in order to guess where they will be and path towards that. This kind of AI is a real-time AB-game from game theory, an area that's not standard in any 3D game AI toolkit.
One way to do dynamic path finding is have the entity predict where the target is going and go there.
One way of doing this is using a Taylor series.
I'll call the path of the target over time the function S(t) where S is the position and t is the current time and the approximation to the path is A(f) and f is the date in the future one is approximating.
Then the simplest and most stupid approximation is A(f)=0.
The next simplest is A(f)=S(t) where t is the current time and f is the future. This is predicting the target simply stops in place.
The third simplest is A(f)=S'(t)*f+S(t) where S' is the derivative of S with respect to time. This is predicting the target continues on at a constant speed with no acceleration.
The fourth simplest is A(f)=S''(t)*f^2/2+S'(t)*f+S(t). This is predicting the target is accelerating at a constant speed like a falling ball.
I know this can be rephrased in terms of change in time which is probably more convenient for a game. Now S can be anything. It could be an X coordinate, it could be a Y coordinate, it could be the distance between the objects, it could be an angle. Also there's probable better methods of predicting the future path of an object so I'd look around a bit.
If the terrain is reasonably open and the target isn't too far from the pursuer, then you could use the intercept steering behavior. Essentially, you take the position and velocity of the target to calculate a position out in front of the target that isn't too far, and not too close, and you steer the pursuer towards that point (calculated each at regular intervals).
