Making the AI take different paths to each other

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.