Sign in to follow this  

Best way to follow a moving object

This topic is 1101 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello everyone,

 

I have implemented an A* algorithm to find the shortest path between two static none moving points, and that works great. However if I use the same algorithm to find the shortest path between one point and another moving point(example of that is an enemy and a moving player) for multiple enemies, my FPS tanks from ~2000+ to 15 FPS or lower and the game starts to freeze every once and a while.

 

So what am I doing? and What is the problem?

 

Well, what i'm doing is I'm re-calculating the shortest path using A* every time the player moves from one node or cell to another. (I have a grid that contains 100X100 cells or nodes where each node or cell is 32x32 pixels). So each time the player moves by 32 pixels I re-calculate the path, which is very taxing and unnecessary. 

 

So that's what I am doing.

 

I did find one possible solution which is, I would only calculate the path from the enemy to the player once, and then whenever the player moves one node or cell I just add that node or cell to the already existing way point list. However that solution has one problem. Imagine if the player is not walking in a straight line, imaging he is walking in a zig-zag motion, if I add the same way points to the enemy path, the enemy will do the same zig-zag motion and will not walk in the shortest possible path which would be a straight line.

 

Like so:-

 

W4HrCY7.jpg

 

 

 

 

So Here is my question, What is the best possible way to make an enemy follow a player using the shortest path possible? And does it work on more than one enemy? by that I mean will your solution work in case of 10 enemies that are all following the player? will there be no massive FPS drop?

 

 

Thank you.

Share this post


Link to post
Share on other sites

A* is know to be accurate but somewhat slow.

 

possible fixes:

 

1. re-calc A*  less often.   re-calc when player moves 2 squares, instead of one, for example. pros: processing is cut in half. cons: unit path changes are 1/2 as responsive to changes in player location.  

     

2. re-calc A* in a round robin fashion. when its time to re-calc A*, do it for one or a few units per frame unit all are updated. pros: only one or a few units update A* per frame, IE fewer A* re-calcs per frame on average. cons: units have to wait for their turn (A* update) to change path, you must re-calc enough units per frame to keep up with player movement in a sufficiently timely manner. 

 

3. a combo of re-calc'ing less often, AND in a round robin fashion. pros: less A* re-calcs per frame on average. cons: less responsive to player movement.

 

4. abandoning A* for a fatser algo such as line-of-sight: relative heading = heading to player - unit's heading. limit relative heading to +/- unit's max turnrate. turn unit by relative heading. move unit. pros: runs really fast. cons: you lose collision avoidance, and must implement some sort of collision recovery such as "bang and turn". line-of-sight with bang and turn only works well for sparsely distributed obstacles, such as trees on a grassy plain, and doesn't work well for walls, and doesn't work at all for concave obsacles unless you add heuristics. fast heuristics can be used to implement pretty good collision avoidance, wall following, etc, but the better it gets, the more complex its rule set (and therefore code) becomes.

 

5. jump A* is a modified A* that works faster with large open areas. pros: a faster A*. cons: only helps in special cases.

 

6. limit the number of units that use A* to what the processor can deal with. this is a common design trade-off gamedevs must make.  A* and rendering hi-rez skinned meshes are the two things that keep shooters from having lots of hostiles on screen at once.  pros: units use A* and game runs fast enough. cons: the number of active hostiles must be low to prevent slowdowns. This is why an encounter in a shooter may have perhaps 6 hostiles vs 60 hostiles.  They cant draw and pathfind 60 hostiles without slowdowns.

 

7. increase the size of a "square" used by A*. pros: bigger squares = fewer squares to test in A* = faster A*. cons: lower resolution, perhaps too low. for example: if you use 32x32 pix tiles for walls etc, A* squares of 64x64 pix won't work, you need 32 pix resolution accuracy, which means a square size no bigger than 32x32 pix..

 

8. some other method that hasn't occurred to me. maybe some else here has additional options to provide.

 

in my own quest for large numbers of active hostiles, i've gone to method 4 (line-of-sight with bang and turn collision recovery) for path finding, and rigid body animation for rendering. i can have ~125 hostiles active onscreen at once before i experience slowdowns. the line-of-sight path finding is so fast that pathfinding is no longer the bottleneck in AI. the bottleneck in AI is now target selection which requires iterating though the lists of active player and non-player entities.

 

fast accurate pathfinding is still one of the holy grails of game development. but line-of-sight + advanced heuristics and collision recovery can give A* a good run for its money. 

Edited by Norman Barrows

Share this post


Link to post
Share on other sites
The canonical solution to this involves steering behaviors - there are numerous references available for free on the web.

The simple pathfinding-based solution to your problem is to do incremental path searches. When the player is at Point A, find a path to Point A. When he has moved on to Point B, find the shortest path from Point A to Point B. By sampling the player position periodically instead of constantly, you smooth out the "zig-zag problem" and also save on computational cost. The search from A to B is likely a lot shorter than the search from the enemy's position to the target, as well.

There are plenty of other tricks you can try just on the pathfinding level. For example, for distant units, you can use hierarchical A* and just find a path to the player's current "zone" if your world geometry is well subdivided. You can use the ratio of (distance to player) vs (distance between current target point and player location) to decide when to re-path, i.e. don't bother searching for a new path if the destination is only a short distance from where you're already heading. Some minor modifications to your A* heuristic can give you "find me a path that gets me in range of the player" if your units can interact with the player over a reasonable distance.

Ultimately the best solution depends on a combination of factors: what your world geometry looks like, how fast units move, whether there are additional constraints on the path search such as minimum radius, and so on. Most of the solutions will involve something that looks like steering behaviors anyways, so that's a good tool to have on your belt.


Contrary to what some people believe, a good A* implementation is blazing fast and should have zero problems handling the situation you've described when used correctly. There do exist some modifications and adjustments to A* to make it faster in special cases, but again, that depends a lot on the world you're doing path searches in. The tricky part of A* is that it's very easy to write a correct but horrifically slow implementation, and amateurs and the inexperienced are often fooled into thinking that the algorithm is to blame.

Share this post


Link to post
Share on other sites

The simple pathfinding-based solution to your problem is to do incremental path searches. When the player is at Point A, find a path to Point A. When he has moved on to Point B, find the shortest path from Point A to Point B.

 

first of all I would like to thank you, that really helped ^_^

 

However one problem comes to mind using this strategy. lets say the enemy unit movement speed is really low, and the player movement speed is high. what if the player and the enemy are sitting at point A, and the player moves to point B. The enemy will find the shortest path between point A and point B and starts moving, while the enemy is moving to point B the player then moves back to point A. keep in mind the enemy is really slow moving unlike the player who is really fast.

 

The problem that occur here is the enemy will start moving to point B while the player already moved to point B and back to point A. which means at some point both the player and the enemy have met at some point in that path but the enemy will just keep walking to point B without making a path correction to stop and start moving back to point A.

 

So how do you fix this problem?

 

Q01upBD.jpg

Share this post


Link to post
Share on other sites

You could modify it to check whether the new square of the player is close to the previous destination.  If it's close, just pathfind from current destination to new destination.  If it's not, redo the whole path.

Share this post


Link to post
Share on other sites

If you only have 100x100 grid it would propably be faster to just floodfill from the player. That way you only have to calculate ~10 000 distances once after the player moves from a node to another and every node knows what is the fastest direction to go to reach the player. No matter how many enemies you have the pathfinding time is constant as they only have to look the next direction from the grid. If it still isn't fast enough you can spread the floodfill to multiple frames of say 1000 nodes per frame. The additional lag of the further away nodes shouldn't be very noticeable as the path far away would stay the same most of the time.

Share this post


Link to post
Share on other sites

Adding to ApochiPiQ's suggestion, you can obtain better incremental pathfinding at a higher cost by discarding the last part of the old path and extending the chaser's path from there, with increased opportunity to take shortcuts against the target's meanderings. At most, you can discard the whole previous plan, going back to non-incremental pathfinding. The amount of discarding can vary adaptively (e.g. according to how much of the last discarded path portion is reconstructed without change).

Share this post


Link to post
Share on other sites

This topic is 1101 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this