Jump to content
  • Advertisement
Sign in to follow this  
Sean_Seanston

Pacman AI: A* or something simpler?

This topic is 3674 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've got my Pacman clone up to the point where the ghosts are implemented and can find their way from the starting box to their home corners. Using the same process to chase Pacman doesn't work in many situations and definitely isn't sufficient for any kind of reasonably good AI. So I'm wondering: Should I just try to implement an A* system or is there an easier way? I know I'll have to learn A* some day but this is my first project with AI so maybe it could wait, or maybe I should just jump into it right now, I dunno. What might NAMCO have used for pathfinding in the original Pacman?

Share this post


Link to post
Share on other sites
Advertisement
I don't think the ghosts actually chased Pacman. If they did, they probably just went towards Pacman and picking a random direction when hitting a wall. But A* should be ok, if you wish the ghosts to home in on Pacman. It's not particularly difficult to implement, so you shouldn't worry about that.

Share this post


Link to post
Share on other sites
I think the OP wanted to know how to control the ghosts... pacman with no ghosts would be a pretty dull game... Sorry I don't have any more to contribute on the AI bit though...

Share this post


Link to post
Share on other sites
Pacman certainly doesn't require an A* implementation -- simply picking a random direction at an intersection, perhaps occasionally biased towards the direction the player is relative to the ghost, will be sufficient.

As I recall from an interview I stumbled across a while back, the original ghost AI used purely random movement for two ghosts, 'move towards the player' movement for one, and 'move towards where the player is going' for another. Since the game world is rather rigid in Pacman, it is perfectly feasible (and fast) to implement this by simply making a decision at every path junction.

That said, it wouldn't be a terrible way to get some experience with the A* routine, either.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sean_Seanston
So I'm wondering: Should I just try to implement an A* system or is there an easier way?


Depends what you want from the game...

Quote:
What might NAMCO have used for pathfinding in the original Pacman?


They didn't do 'pathfinding' at all. Mostly it was just a case of picking the most appropriate direction to move in when they reach a junction. It's trivial to see which direction Pac-Man is, or indeed where he's likely to be in the near future, and you only ever have 1, 2, or 3 choices at each junction anyway.

If you're patient, read through this thread for elucidation.

Share this post


Link to post
Share on other sites
Quote:
Original post by jpetrie
As I recall from an interview I stumbled across a while back, the original ghost AI used purely random movement for two ghosts, 'move towards the player' movement for one, and 'move towards where the player is going' for another. Since the game world is rather rigid in Pacman, it is perfectly feasible (and fast) to implement this by simply making a decision at every path junction.


This great article describes the AI in the original Pacman. In my pacman game I followed a similar strategy. I made one ghost go towards the player if they could, the second ghost go in the direction the player was going in and the third ghost (I cut one out for some reason) go aimlessly. It seemed pretty good, and was very easy.

Share this post


Link to post
Share on other sites
I once read about this. A* will be an overkill for pac-man plus it will make the game imposible. It works something like this;

(4) Ghosts:

* Ghost: 1 only follows pac-man if on same row, else picks a random dir on corners.

* Ghost: 1 only follows pac-man if on same column, else picks a random dir on corners.

* Ghost: 3 always follows pac-man.

* Ghost: 4 never follows pac-man always picks a random dir on corners.

Hope this helps.

Share this post


Link to post
Share on other sites
PacMan, or more specifically Ghost, AI has been discussed a lot in the AI forum. Search the forums and you'll find numerous references. One explanation I found with a quick Google search is:

Quote:

Red - Blinky: Oikake - "Akabei" (oikake-ru = to run down/to pursue/to chase down). Or of course the english "Shadow".. the guy is literally on your tail and can be thought of as your shadow

Pink - Pinky: Machibuse (machibuse = performing an ambush). Or in the english "speedy". He is indeed just as fast as Blinky and works with him to ambush and cut you off.

Blue - Inky: Kimagure - "Aosuke" (kimagure = fickle/moody/uneven temper). Or in english "Bashful". He is unpredictable. Sometimes he follows you, sometimes he goes away from you.

Orange - Clyde: Otoboke - "Guzuta" (Otoboke = Pretending Ignorance). The nick "Guzuta" means someone who lags behind). Or of course "pokey" in english. The guy is slow. He's always going somewhere on his own. But he does sometimes successfully cut you off, but almost never outright chases you.



One implementation that I saw which was very good would move the ghost in either a random direction or toward the PacMan on the shortest path to PacMan. The decision between random and toward had higher probability of toward the PacMan at more difficult levels, and also each ghost had a different probability. This helped keep the ghosts from bunching up.

Shameless plug
If you're interested, check out my PacMan AI evolver. At this point the ghosts use the random probability method I mentioned above, and PacMan's AI is evolved over time. http://sourceforge.net/projects/aipac/

-Kirk

EDIT: Holy cow! There were only 4 posts in this thread while I was typing my response!!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!