Well, I know i know that pacman is a cliche, but the last few days was the first time I actually bothered learning linked lists and trees... and it also lead me thinking to the A* path finding algorythm. So what I'm thinking is this: Each ghost has a focus point on the map that "activates" them. After activated, each ghost follows a "path". Red finds the shortest path to the top-right "power pill", after that, the bottom-left, top-left, bottom right, ETC.. UNLESS! pacman passes Red's line of site, then red keeps on calculating the shortest path to pac. Blue is similar, but finds the longest path to a different sequence of "power pills", unless pac passes line of site, then he searches for the longest path to catch pac. Green? Well.. if it is green .. he calculates a path somewhere inbetween. And the same applies. Now for Pink, he is a little "slow" and "random" and needs a leader. So I rate he finds the longest path to Red. ALWAYS! It doesnt change if pac passes his line of sight. If he does find red he changes his state, finds his "activation point" and then searches for Red again. This is just some random method that crossed my mind while playing with binary trees, dunno why, but it did. So NOW... Any comments on this method? [edited by - o_Silver_Serpent_o on September 24, 2002 2:51:18 PM]

Me an a few members from my IGDA chapter are making a Pac Man clone in SDL, and I''m in charge of the AI. Wheee

Anyways, one of the team said that this is how it was done in the original game:

- 1 ghost would follow pac man
- 1 ghost would try and head off pac man
- 1 ghost would travel around at random
- 1 gohst would travel around at random until it saw pac man, than give chase until pac man got too far away, at which point it would revert to random movement

Now I''m not sure about that last one, and I have no clue which color ghost does what, but that''s prob the way I''m gonna go about doing it.

As for your method, what''s the focus point and what does "activate" mean? Does it mean until they hit that point they aren''t deadly to pac man? Like the inside of the ghost box?

And you should be careful about the longest path idea. The way it sounds now Blue will never catch pac man. This is because as soon as he''s right next to pac man, the longest path leads him in the opposite direction! Sure, he may do a decent job of herding the pac man towards the other ghosts every now and then, but that''s about it. Same deal with Pink chasing Red.

The only way around this would be to plot the longest path once, and then add nodes following the target as it moves, this way at least the ghost will hit the target by chance. Of course now the path just gets longer and longer till the ghost "bumps" into the target.

_________________________________________________________________

Drew Sikora
A.K.A. Gaiiden

ICQ #: 70449988
AOLIM: DarkPylat

Blade Edge Software
Staff Member, GDNet
Public Relations, Game Institute

3-time Contributing author, Game Design Methods , Charles River Media
Online column - Design Corner at Pixelate

Unnoficial IGDA chat! [polaris.starchat.net -> #igda]
NJ IGDA Chapter - NJ developers unite!! [Chapter Home | Chapter Forum]

"Real programmers don''t work from 9 to 5. If any real programmers are around at 9am it''s because they were up all night."
-Anon.

I wrote the AI for "Pac-Man: Adventures In Time", for Hasbro Interactive, and so studied the original Pac-Man game in quite some detail. Namco, as license holders, are very protective of all the Pac-Man characters, including the ghosts, and so the behaviours had to be exactly right.

The most useful resource publicly available is actually for Ms Pac-Man. The Ghost behaviours are very similar to that of the original and so this should be of some use. The document can be found at http://www.cheatplanet.com/gbstrategy/ms_pac_man.htm

I think Pac-Man is a great exercise in AI. It contains pathfinding, strategy and personality all in one simple game.

Have fun!

Cheers,
John

John Reynolds
Creative Asylum Ltd
www.creative-asylum.com

Yeah, i thought about the longest path idea too. Does indeed sound a bit silly.

By activation points I mean like a spot on the map that sets them in "HUNT MODE".

And thanx John, I''ll have a look at that site.

So what do you do when the pacman gets the pill, scatter randomly? Or are they doing some kind of a clever distribution such that each ghost both runs away and tries to maximize the distance to closest of other three ghosts? Just curious.

Oztan

Hmmm... that is quite a different story. Havn''t thought of that, maybe i should get back to coding trees again and wait for another wierd brainy mission

But as with most things in life.... "Every man for himself" sounds like a reasonable solution

That''s a coincedence that this topic comes up. Last week a course started for students that has to prepare them for their final graduation project. They have to learn things like formulating the problem, looking for information and see how literature can help them solve them problem. Because more students showed up than anticipated some where assigned to me, while i was away. When reading my mail i found questions about a project i didn''t know i was involved so i had to come up with a project idea very fast. I came up with pacman ai . (Note that this project is not about implementing the game. It''s about abstracting the problem (which they have to do) and investigate which existing solution techniques can be applied or have to be modified to solve it. Only in the end i will allow them to implement stuff, hehehe)

Because i want the game (the problem framework) to be the original pacman (but then without the ghost ai) i have to refresh my memory a bit. Is it correct that:
- Pacman and the ghost move with the same speed.
- The ghost only can change direction at the corners while pacman can turn any time the player wants.
- All the dots are on a regular grid (and the walls are just gaps in that grid).
- When pacman eats the invulnerability dot the ghost will always turn in the opposite direction even if they are not in some corner.

Hey John this doc looks awesome, thanks a bunch.

And yea, I would make it every man for himself too.

Hey,

My last game was actually pacman, so if you want any help w/ how to do the AI I could help.. I also studied the original pacman so I incorporated the different personalities for each of the ghosts.. imo it turned out pretty well. I used A* for the red and blue ghosts, and then some ad hoc techniques for the other 2.

Well if you want to talk feel free to e-mail me at Rajs20@aol.com

Good luck,
Raj

I remember reading a book and the original programmer of Pac Man was featured in it and I cannot for the life of me remember the name of either.

But I do remember him saying that each ghost had a certain personality. And more importantly the ghost''s attacked in waves and eased off you now and then.

He felt that you should not stress the player out too much as that would destroy the stress/relief element which would have made it less fun.