Randomize AI pathfinding in a game

Question

I'm a C# veteran who's never done a game before. In an attempt to broaden my horizons, I've started teaching myself basic XNA stuff in an attempt to make a simple 2D maze type game with some typical enemy shooting involved. My question involves pathfinding for multiple enemies.

Consider the quintessential example: Pacman.

When you start a round in Pacman, the ghosts come out of the box and take different seemingly random paths with one exception - they are weighted toward finding the player's current position. I thought I could recalculate each enemy's path every time the player moves to achieve a similar effect, but I don't want the enemies to overlap paths too much, so I need to randomly distort each calculated path to give some degree of uniqueness to the enemy. Is there a standard approach to this?

I guess I could look at it as each enemy itself is an obstacle, and thus no enemy's path could involve a route that would collide with another enemy. In cases where there is no new path that would present a free run to the player, I would have the enemy continue on its existing path until either a workable path is found or a collision alters the current path. This may be enough, but am I simplifying it too much?

Answer 1

I would approach it with probability..

Maybe something like if way A takes 20 steps and way b takes 30 steps, then the monster will go way A in 60% of the time and the way B in 40%. Then add some kind of rule that make sure that the monsters always will take a specific route if the route is more than 20% more probable than the other..

this would crate a scenario where the monster always take the closest way if they are close enough, take different similar ways in open areas and takes different ways who takes almost as long time at long ranges...

then you need to add some way to filter out the most strange behaviour to remove thinks like changing direction without reason and configure the actual numbers to the formula :) (btw this isn't tested just speculation)..

Answer 2

Maybe you find useful the potential fields approach...

http://aigamedev.com/open/tutorials/potential-fields/

Each enemy has a positive potential field and player has a negative potential field, if you fill the map, you can get a that enemies does not overlap too much because of the same signed charges... of course the algorithm has is matters... but maybe can help you.

Answer 3

Interesting idea, but it may - for the simple Packman example - cause some enemies to not be able to find a path. For example if packman is in the lower right corner where he can only go north or west. If there is an enemy on each of those paths, no other enemies could find a path to him and would freeze or wander aimlessly.

Perhaps giving the enemies a lower "weight" than the real obstacles in the game would allow them to still find a path and provide for that oh-so-satisfying moment when packman eats a power pellet and there are several ghosts in a row to gobble up.