Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I have a top down 2d game where the AI spawn at the edges of the map and run towards the center.

I'm using A* and a node mesh to do the pathfinding.

Right now, the AI spawn at a point on the edge of the map and all take the same path which is the shortest route to the center.

Now I want them to be more surprising and interesting and take different paths to each other.

I can immediately think of two ideas for doing this but wanted to know if there are other ways or better ways that people often use?

  1. When one enemy spawns and generates a path to the center, temporarily increase the cost of all the nodes on that path, then slowly decrease them back down over time. Then the enemy AI that spawn later will be forced to take a wider path.

  2. The above approach will lead to AI just taking a wider and wider path though and still be very predictable. So I thought I'd also introduce a number of intermediate goal nodes around the map. When the AI spawn they randomly pick one of the intermediate goals and head there first before heading to the center of the map. Combining this with the above approach of increasing the costs might look pretty good?

What approaches have people found work best to getting the AI to vary the paths they take, look convincing and surprising?

share|improve this question

6 Answers 6

up vote 7 down vote accepted

Your second option hints at a more fundamental approach: ensuring enemies approach your player from different directions. The question is, how far do they have to travel to in order to get "around" your player? The ideal to this would be a mix of

  • dynamically generating points that closely surround (i.e. follow) the player's position;
  • what Nevermind has suggested in terms of randomising paths to these surrounding points, to a greater or lesser degree.

In this way, you can ensure that AI's won't take unecessarily lengthy detours just to get realistic path variation when converging on the player.

Collaborative diffusion does what you want implicitly as part of the algorithm. But it's non-trivial to implement.

share|improve this answer
    
Collaborative diffusion is just a flood fill with some weighting. It's trivial to implement, maybe easier than A*. It just requires a different view of your world - a non-trivial conceptual shift, maybe, but no implementation problem. –  user744 Oct 5 '11 at 17:56
    
It's still non-trivial to implement as a result of it being a non-standard viewpoint in terms of managing AI entities :) –  Nick Wiggill Oct 5 '11 at 18:37
    
Thanks Nick. I think setting up some waypoints that surround the player in the center of the map is going to be the main way to go. Not sure at this stage whether they'll be dynamically generated or some hand crafting involved for each level for my particular situation. Thanks again! –  TerryB Oct 10 '11 at 22:40

As a first idea, try adding a small random value to each node's weight when pathfinding. This way, every agent will look for a path in a slightly different environment. I'm not sure if this will work in your case, but it should be really easy to try.

share|improve this answer
    
The enemies will end-up running like chickens, and in a fine-grained environment the paths will not be so different anyway. It's a good addition to other solutions, but not a solution in itself –  Coyote Oct 5 '11 at 10:41
    
@Coyote This depends a lot on nav-mesh structure, and relations between node weights, speeds and random component. That's why I framed the answer as a suggestion to try, not as a definite answer. –  Nevermind Oct 5 '11 at 14:15
    
Indeed :) I'm usually a fan of entropy. But the final result is rarely great. –  Coyote Oct 5 '11 at 17:34
    
I actually believe Nick Wiggill's answer is way better than mine. But somehow it isn't getting the upvotes it deserves. –  Nevermind Oct 6 '11 at 6:42
    
It is... But yours is first and simpler... we could try to down vote it :P –  Coyote Oct 6 '11 at 9:20

I like Nevermind's answer, however, given the limitation described in the comments this is what I would try:

  1. The algorithm for a single unit to the center, record the total distance travelled.
  2. For each subsequent unit allocate it a distance that is a random and small amount longer than this.
  3. While doing the A* for each unit add extra weight based on how close you are and how far you 'want' to travel. This would probably be something like (distanceToGoal) + Max(0, desiredDistance - distanceTravelled)).

This would make the units attempt to go further, which is probably a different path, which would result in them possibly taking different paths.

You could also just add it to your starting huerestic for each unit, but the random range would probably have to be quite a bit larger.

share|improve this answer

Your problem here is essentially that A* is an algorithm for finding the quickest route to a target. If that is your primary criteria for a 'good' path, then it's unsurprising that all your actors make the same decisions.

What you need to do is modify your quality criteria for the path, so that 'shortest-is-best' isn't the only factor. The element of randomness is key in this, but not so much that it detracts from the path-finding intelligence (i.e. actors take stupidly roundabout paths to the target).

A* pathfinding is innately naive, as it usually assumes that the actor has perfect knowledge of the entire route before it starts out. That's always going to look unrealistic. The solution suggested that picked intermediate goals is a step away from that - the AI is trying to get closer to the target, but only tries to navigate in small sections at a time (this is analogous to real life where you can only navigate as far as you can see, and as you traverse more of the path, you can see further ahead).

I'd perhaps recommend a simpler way of looking at it. When you're pathfinding, don't just maintain a single best-path-I've-found-so-far. Instead, collect a set of the best 5 or 10 paths. Use a threshold to discard obvious outliers. E.g. if the best path traverses 20u to get to the target, the next best traverses 21u, and the next one after that traverses 50u. Set a threshold of 20% larger than the best path, and so discard the 50u path because it's stupidly longer. Now you have several paths to choose from, and by randomly selecting from that set of paths, your actors will make different decisions.

However you won't get this sort of information with standard A* searching, so I think you'd have to modify the algorithm or use something else to gather the set of possible paths.

share|improve this answer

As pointed by Nick Wiggill the simplest approach would be to get a circle surrounding the objective.

  • randomly assign a point close to this circle as a waypoint.
  • eliminate all paths in the circle from the initial path (or increase dramatically the value of these points)
  • then from that waypoint get the path to the objective.

The important part is to eliminate all paths in the circle for the original waypoint as you would probably end-up with enemies crossing the circle to get to their initial waypoint.

From that you can get any variant by playing with multiple values adding secondary waypoints in the circle close to the initial one etc.

share|improve this answer
    
if your map supports it, find 'interesting' locations around this circle (doorways, cover, trees, rocks, buildings; any node with some tactical advantage) and have your enemies head for those locations first if they are available and only come out in the open if they have to. This will look much smarter than just hitting a random spot on the edge of the circle. –  DampeS8N Oct 4 '11 at 15:19
    
Thanks Coyote, yep I'm probably going to go with Nicks solution and as suggested by DampeS8N some key locations of interest as waypoints. To avoid the problem of the AI "crossing the circle" I'm just going to greatly increase the cost of the nodes in the circle so A* should route around it hopefully :) –  TerryB Oct 10 '11 at 22:41

If you have a small set of recurring enemies (or enemy types), you might try to give them personalities that affect their movements. They don't have to be big things, just things that come up every now and then. A good example of this are the ghosts from Pac-Man. Have your A* broken into several intermediary goals. Maybe one enemy is really stupid and gets lost easily, heading in a random direction every third node (other than directly backward). Be creative.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.