Jump to content
  • Advertisement
Sign in to follow this  
mortiz01

Chasing

This topic is 4227 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

What's a good way to implement chasing? Using steering behaviors (especially for evasion) has it's caveats if you want your entities to be on rails. If they're in a narrow maze for example and you want your entities to stick to the path steering behaviors wouldn't really be all that suited. I'd prefere it to implement chasing using a path-finding algorithm of some description, minimin is one option although the entities can get stuck in infinite loops. I've also implemented rta* but with the destination node consistently changing in reality it ends up almost the same as minimin.

Share this post


Link to post
Share on other sites
Advertisement
Certainly A* for your path planning. Probably the best solution would be to re-plan either every 1 second-ish or re-plan whenever the target has moved more than X meters from where you pathed to last (whichever comes first).

-me

Share this post


Link to post
Share on other sites
If the target is consistently moving I would not spend my time executing a costly deliberative search every n time steps of the game loop (you can choose n anyway you like, I still wouldn't take that approach! ;) ). Recall that there is always a tradeoff between storage (due to offline computation) and time (due to online computation). If you have a problem that requires excessive online computation, first look at a pre-computation and storage option before looking for complex online solutions.

It's a game, so you're allowed to give your game agents any information that you desire to make them effective. How you hide this cheating is the key to immersion! ;)

If you're doing a pursuit problem in a maze, then precompute for the maze the connectivity of intersections. If your maze has say 50 intersections, then you end up with a 50x50 array. For each intersection pair, compute offline (i.e., during development) the shortest path between the intersections. If they are connected by a set of open corridors, place an entry in the array at the element corresponding to the intersection pair, where the entry is the first intersection to travel to along that path. Do this for every intersection pair. You can perform this search offline using Dijkstra's all-pairs algorithm. What you've stored is a pathing connectivity map.

Now, at each iteration of your AI, simply find the closest intersection to the target (prey) and the pursuer (predator). Look up the corresponding entry in the array and have the predator move toward that intersection.

You can enhance this basic idea in many ways. For example, you can update the prey's nearest intersection at a different rate to the lookup of the predators next intersection to travel to (so the predator will chase a position the prey used to be at, or perhaps it always knows where the prey is heading before the prey does... or perhaps only with a probability less than 1). Or, you can only update the predator based on sensory information they obtain. Perhaps they hear the rough location of the prey only occasionally, or they have a movement sensor they can look at occasionally to work out where their prey is.

There is a lot of potential here that enables you to hide the fact that you precomputed the solution to this problem and that your game agents have access to this sort of information (where the players presumably dont).

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!