Moving target path finding

In working on implementing better pathfinding than “which way is it? ok go that way.” I decided to start with A* as I’ve heard it mentioned before. A* might be a bit overkill for a grid-based game where you can only move in four directions, but oh well. Unfortunately after getting it working I discovered that a basic A* implementation doesn’t work very efficiently when the target is moving around. So, I’m trying to figure out a better way to get my enemies to find their way to the player with out getting stuck. If anyone has suggestions, or experience with doing something like this I’d love to read it ;D

What I did for Guardian II is this:

  1. Check if target is alive. If not, cancel.
  2. If target is targetable with simple AI, switch to simple AI. Otherwise, continue:
  3. Check if path to target has been found. If not, find a path.
  4. Check if you are on the path. If not, try to get on path. If still not, find new path.
  5. Check if target is within a certain distance of the path’s end point. If not, find a new path.
  6. If at end point and target not targetable with simple AI, find new path to target.

By ‘simple AI’ I mean, if target is left, go left. If target is right, go right etc.

Little tips, you should separate entities into separate lists based on its type (alive, movable, etc) so it can reduce the looping time, since you need to perform this a lot.

Are you setting the actual “moving target” as target or some sort of simple prediction? (Like p.e. x tiles into the direction the target is walking, where x is the distance between the chasing entity and the target now)

Depending on how much cpu you can afford to waste and how you want your entities to “react”, you can get some neat looking “behaviour” by just messing around a little with the way the fake/prediction-target gets chosen or even comparing multiple fake targets (doing pathfinding from target to its potential goals first + choosing something on that path as target instead of the actual target itself can have neat results too).

If something like that makes sense can depend a lot on exactly how your game / levels look though, so maybe you should post a screen-shot or something in the hope that someone who’s more experienced that me can give you more specific advice. :wink:

Thanks for the tip. I’ve already done this in the way that path finding for each entity is done.

Currently I’m just setting the “moving target” to the target’s actual location. I’ll play around with estimating where the target would be after x number of moves though, thanks for the suggestion :slight_smile: I’m not sure how helpful a screenshot would be, as I don’t have any of the final level designs done. I’m currently in the process of implementing features.

I hadn’t thought about separating it out into a simpler AI and a more complex one. However, I’m worried that determining if simple AI will work and then having to resort to complex AI would just worsen the performance problems. Perhaps I’m misunderstanding your explanation though.

With ~200 goblins and ~19 heroes running around using the AI it seems to work fine. :slight_smile:
Not to mention the heroes are switching targets between enemies and following the player every few seconds.

I’ll give you a snippet of the code in an hour or so.