Fast path finding for pacman game

Hi there

I have been reading all the posts about path finding and still not sure what is the best solution for a pacman style game.

Basically there will be a maximum of 4 baddies at any time, each which may need to call a path finding function to enable them to chase the player

I have programmed the basic game but currently the baddies just move randomly.

Here is the current version
http://www.mediakitchen.co.uk/chomper1.html

I would like to make it a bit more interesting and challenging by making the baddies chase the player.

What path finding algorithm would you suggest for this game? It has to be programmed in AS1 for Flash Player 7.

Many thanks

Don't use a pathfinding algorithm - as such.

There's no point calculating the path from baddie to pacman if pacman has moved by the time baddie gets there, best just to have the baddies make navigation decisions at key points, such as corners and intersections, and base that decision on the position of the pacman. MUCH much quicker.

Also try and find some info in the AI in the original pacman games, if i remember each ghost had its own peculiar style of AI, depending on its colour, and only one of them was 100% aggressive.

Here's how I would approach it:

First, the baddies would not use path finding, but normal maze navigation (ie: Baddy encounters a wall. Which directions are unobstructed? Pick random direction and go)

Second, then to add more "intelligence" I would modify the direction choice based on: Which direction is available, and where is the player in relation to the baddie? Is he to the right, left, up or down of baddy?

You can then make the baddy ALWAYS choose a direction that will head towards the player (for a super smart, agressive baddy) or weight the choice with some randomness. For example, make it so one baddy ALWAYS heads toward the player, make one who is completely random, make one who chooses to head toward the player 70% of the time, etc.....

Thanks lesli

I have implemented a path finding algorithm based on http://proto.layer51.com/d.aspx?f=998 however I agree with what you are saying and think if I take your suggested approach the game will run alot smoother.

The link for the latest version of game with one intelligent baddie is

http://www.mediakitchen.co.uk/chomper2.html

Thanks

Thanks Ray Beez

I did originally try to add intelligence by comparing the player location with the baddie location but I found in certain circumstances the baddie got stuck if for example player was directly above the baddie - but that may have been errors in my code:)

By the way, one flaw in my method above is that decisions only occur when baddie hits a wall. You need to add an invisible tile at all intersections and make your baddie re-evalluate their path decisions when they hit intersections (thus allowing them to turn if appropriate).

I gave this topic aswell a thought:

if you need pathfinding (the could be valid reason if for example you want to let the bot go to a certain spot as quick as possible, or spawning obstacles/ enemies as nasty as possible [always on the shortest path],...) i´d be smart to first analyze your environment.

imagine given this map
http://mitglied.lycos.de/mmvr1/flash...cman_ai_01.gif
there are already some dead ends,- finding those should be an easy task (fields that have only 1 accessble neighbour- or that have a dead end)
http://mitglied.lycos.de/mmvr1/flash...cman_ai_02.gif

the conventional way finding a path would be solving this with a grid as way points
http://mitglied.lycos.de/mmvr1/flash...cman_ai_03.gif
to decrease however the loops you need to perform within the finding algorithm you can already exclude those fields who have only 2 openings (I still included edges in this illustration but you could leave them as well)
http://mitglied.lycos.de/mmvr1/flash...cman_ai_04.gif
like I said you can even leave out the edges wich would give you ~ 4 nodes on that path to check [all the fields who have at least 3 accessable neighbours]. This way you can simplify and reduce the needed way points/ fields alot and the pathfinding should already run a lot better


a little sidewalk:
like others already mentioned I would make the enemies all knowledgeable on where you are,- just like human beeings they only should know where the pacman went if they saw him passing them. If pacman for example hides behind a wall...
http://mitglied.lycos.de/mmvr1/flash...cman_ai_05.gif
... all the enemy then knows is that pacman is somwhere behind that corner- nothing more- so after the enemy reached the backside of that corner he still needs to search (look) again for pacman.

Smart enemies are not always interesting to play with. For example, how would they know where PacMan is if they cant see it? You could build it so they try to follow PacMan only if it is visible, allowing to hide behind the corners.

Pathfinding spoils pac-man games. In the old ones only one baddie used path finding, then 2 were dumb and one only chased you went it could see you.
Render, even those example drawings look really good, Me = Jealous once again.

Path finding isn't needed for pacman, it's a simple case of working out where the player is in relationship to the ghost, and then working out the best possible method to get there ( I'm currently using this in a game, also used it in Souq Chase in DiS, albeit the other way around so the baddie was running away ).

So the ghosts move a tile at a time, even if it's smoothed out, it's still a tile. When they've moved that whole tile it's then that you let them think.

If playerXPos<ghostXPos then the ghost's preferred horizontal move is left, and if playerYPos>ghostYPos then the best vertical direction for it is down.

Next check all the possible directions the ghost can move in, ie check the tiles around it.
Then just compare. Using the examples above, we want to go left and down. If any of the possible moves allow either of these favourites then we're on to a winner, and he moves in that direction.
If on the other hand he can't move in either of these directions, so he can only move up or right, just pick one of those at random.

Also with pacman ghost ai they can't double back, so that random choice is made even easier, as you remove the chance of it doubling back on itself.

Check Neave's pacman open source, it does it this way too ( Got a hefty chunk of inspiration from that a while back :) ).

Squize.

Neave hadda remove his pacman stuff i think. forkin lawyers eh?

Quote:

---

Originally Posted by Squize

If playerXPos<ghostXPos then the ghost's preferred horizontal move is left, and if playerYPos>ghostYPos then the best vertical direction for it is down.

---

This is basically my implementation of Pacman pathfinding, with 4 enemies, it got really hard to avoid them.

If you feel like sprucing it up a bit, make a couple work like this, and then a couple work simply by going a random direction. Adds some zest :)

Iopred: Yup. And hence why my description includes some randomness. IN the real pacman, only 1 ghost (the red one) is smart and seeks you out 99% of the time. He's also a slight bit faster than Pacman.

The rest will occasionally head toward you but occasionally head in other directions, thereby at least giving you a chance to escape. And one of them is kind of dumb and rarely heads in Pac's vicinity.

i wouldn't mind seeing bitmapData pacman, blow your own way through the maze by destroying the walls.

or maybe health conscious pacman, avoid the fatty sausages and eat the health celery... nah, eat the sausages avoid the celery, much cooler

I also remember reading a tutorial or something teaching how each gosth was "programmed". I believe the red one was the "evilest". I can´t find it.

Same thinking as lesli_felix.

Edit: If you try to make the pathfinding too perfect then player won't have a chance to win at all.

Quote:

---

Originally Posted by iopred

Quote:

---

Originally Posted by Squize

If playerXPos<ghostXPos then the ghost's preferred horizontal move is left, and if playerYPos>ghostYPos then the best vertical direction for it is down.

---

This is basically my implementation of Pacman pathfinding, with 4 enemies, it got really hard to avoid them.

If you feel like sprucing it up a bit, make a couple work like this, and then a couple work simply by going a random direction. Adds some zest :)

---

I would only do that if every tile in between pacman and ghost were walkables. Given the fact that they are "walls", the ghost can't see pacman.

This is going off-topic, but one of the original pathfinding ideas I have read was scent-based. Basically the character smells and his smell spreads aound him in every direction (not through walls of course). The smell is also left behind him and it slowly fades away after he has moved away. Now the enemies have nose and can detect which way the scent of char is stronger to move that way. Have not seen that idea in action, but still liked it because it is more realistic then simply finding path through invisible walls.

Tony how do you think up stuff like that... sheesh lol. It takes me 3 months to think stuff up. I've always been a fan of line-of-sight based pathfinding, but I usually add in the visible distance such that some baddies can "see" farther than others.

Quote:

---

Originally Posted by tonypa

....The smell is also left behind him and it slowly fades away after he has moved away. Now the enemies have nose and can detect which way the scent of char is stronger to move that way.....

---

Wow, that's a pretty good idea Tony.

And it actually sounds pretty east to implement, if the maze is tilebased for example, you just run a loop through all of the tiles and reduce the amount they smell. The ghosts just move onto the adjacent tiel that smells the strongest.

If not using tiles, you could even apply smell to a bitmapdata object as a particular colour, and fade the whole thing to reduce the smell each frame.

I'm gonna have to try that one sometime...

its called swarm intelligence and not so unknown in the AI science. Scientists copied the idea from the ants as a single one of them is not intelligent but in a large group they can do pretty much everything- same goes for bees.

Swarm intelligence is a bit broader than that, and doesn't always involve smell, although in the case of ants it does.

Boids are a better example of swarm intelligence AI, in fact any system that produces seemingly intelligent emergent behaviour from a few simple rules could be said to exhibit swarm intelligence.

Hmmm, I had an idea for pacman type game A.I movement last night at my way home in train. How about when we press a key for directing pacman(type) on a corner in a direction, how about registering that value at the corner tile, which will provide a roadmap for the A.I. for reaching till pacman(or anyone like him).

the smell idea could potentially take up some CPU if your going through all the tiles. Would it be feasible that when the player enters the tile he leaves a smell, a time stamp and a smell strength

when something else needs smell information of the tile, it gets the correct strength based on the current timer - tile timer * smell strength. Would that work to speed up the proccess. Just thinking as i type

Quote:

---

Originally Posted by mr_malee

the smell idea could potentially take up some CPU if your going through all the tiles. Would it be feasible that when the player enters the tile he leaves a smell, a time stamp and a smell strength

when something else needs smell information of the tile, it gets the correct strength based on the current timer - tile timer * smell strength. Would that work to speed up the proccess. Just thinking as i type

---

I thought too it would be probably lots of work for CPU. Your idea is much faster, but it ignores the part where smell is spreading out from your current position. Even if you stand still, you send out scent signals into every direction (with some imagination you could even include wind, making possible to sneak past the enemies using wind blowing from their position to you).

I said already its not my idea, I read about it somewhere. Cant remember right now where exactly...