Jump to content

Photo

Pac-Man ghost AI question


89 replies to this topic

#1 vdub_bobby OFFLINE  

vdub_bobby

    Quadrunner

  • 5,831 posts
  • Boom bam.
  • Location:Seattle, WA

Posted Wed Apr 27, 2005 11:30 AM

Has anyone ever documented exactly what the ghost AI is in Pac-Man? I've been looking a little bit online, and I found lots of places where the ghosts' behavior was described generally, but I'm wondering if more precise documentation exists.

#2 NE146 OFFLINE  

NE146

    Dumbass Atari Fan

  • 13,302 posts
  • Location:Seattle, WA

Posted Wed Apr 27, 2005 12:02 PM

Has anyone ever documented exactly what the ghost AI is in Pac-Man?  I've been looking a little bit online, and I found lots of places where the ghosts' behavior was described generally, but I'm wondering if more precise documentation exists.

View Post


How precise do you want it.. to the point where it's down to the code and what it does? There are a couple of sites with the dissasembly of Pacman code out there.

Otherwise, there's always "Ghost Psychology": http://jongy.tripod....Psychology.html :)

#3 vdub_bobby OFFLINE  

vdub_bobby

    Quadrunner

  • Topic Starter
  • 5,831 posts
  • Boom bam.
  • Location:Seattle, WA

Posted Wed Apr 27, 2005 12:07 PM

How precise do you want it.. to the point where it's down to the code and what it does? There are a couple of sites with the dissasembly of Pacman code out there.

Otherwise, there's always "Ghost Psychology": http://jongy.tripod....Psychology.html :)

View Post


Thanks for the link.

And not quite as precise as code-level, but maybe a little more precise than "Ghost Psychology." Though that was informative. :D

#4 NE146 OFFLINE  

NE146

    Dumbass Atari Fan

  • 13,302 posts
  • Location:Seattle, WA

Posted Wed Apr 27, 2005 12:16 PM

I think it's pretty informative. It breaks down their "scatter" and "attack" modes down to the seconds (since it's determined by a timer). And also it breaks down their speeds, which in Blinky's case is determined by the number of dot's eaten. Very good info :)

ALSO.. if you know their Japanese names/nicknames (Oikake, Machibuse, Kimagure, and Guzuta), it's interesting as well because it does a pretty good job of describing their personalities a little better than their english names do:

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.



#5 vdub_bobby OFFLINE  

vdub_bobby

    Quadrunner

  • Topic Starter
  • 5,831 posts
  • Boom bam.
  • Location:Seattle, WA

Posted Wed Apr 27, 2005 2:04 PM

I think it's pretty informative. It breaks down their "scatter" and "attack" modes down to the seconds (since it's determined by a timer). And also it breaks down their speeds, which in Blinky's case is determined by the number of dot's eaten. Very good info :)

ALSO.. if you know their Japanese names/nicknames (Oikake, Machibuse, Kimagure, and Guzuta), it's interesting as well because it does a pretty good job of describing their personalities a little better than their english names do:

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.

View Post


I agree - that timer stuff was very helpful. Though some of the "Ghost Psychology" stuff contradicts your quote - they claim that Red is fastest while the others are all the same speed.

Pinky, Inky and Clyde always move at the same speed relative to one another so the name Speedy is plainly misleading.

But in any case, what I am looking for is something about how a ghost decides which way to go at an intersection.

#6 jammajup OFFLINE  

jammajup

    Space Invader

  • 35 posts
  • Location:Birmingham UK

Posted Wed Apr 27, 2005 3:56 PM

I think it's pretty informative. It breaks down their "scatter" and "attack" modes down to the seconds (since it's determined by a timer). And also it breaks down their speeds, which in Blinky's case is determined by the number of dot's eaten. Very good info :)

ALSO.. if you know their Japanese names/nicknames (Oikake, Machibuse, Kimagure, and Guzuta), it's interesting as well because it does a pretty good job of describing their personalities a little better than their english names do:

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.

View Post


I agree - that timer stuff was very helpful. Though some of the "Ghost Psychology" stuff contradicts your quote - they claim that Red is fastest while the others are all the same speed.

Pinky, Inky and Clyde always move at the same speed relative to one another so the name Speedy is plainly misleading.

But in any case, what I am looking for is something about how a ghost decides which way to go at an intersection.

View Post




In theory the ghosts should take the shortest route but you find that Blinky and Pinky work as a pair with one chasing and the other heading along side,Inky is said to be a bully and if you head towards him sometimes he turns off down a differant corridor but generally only when he is on his own.Clyde is supposed to be the `Ralph Wigam` of the ghost world he wanders around on his own but still causes problems, if your being chased for example at the top of the maze by Clyde,Pinky and Inky and manage to find an escape route through them as you head downwards through the maze slow clyde is still heading upwards and very often gets in the way (doh"!)
Posted Image

#7 PacManPlus OFFLINE  

PacManPlus

    River Patroller

  • 4,101 posts
  • Atari 7800 Dev
  • Location:SouthWest Florida

Posted Wed Apr 27, 2005 8:40 PM

Ok - Here is what happens with each monster:

Blinky (Red) - He tries to get you by your relative position. He takes the fastest route to find you. I believe he tries to line up with you horizontally first, then vertically.

Pinky (Pink) - He wants to move in the same direction as you, but only when he's close enough to you. In other words, he tries to get to your area first, then when he's close enough, he will try to run in the same direction as you. This can be tested by running right up to him and when he gets right in front of you he will turn away (provided there is a hallway to turn into)

Clyde (Gold) - He seems to want to be in the same general area as you, but doesn't seem to directly chase you. Don't let this fool you; he will not turn away if you are in his path. If you stay in one area, he seems to have a set pattern.

Inky (Teal) - He's the tough one. The only thing I've been able to figure out about him is that he seems to be able to take on the personality of any of the other three at a given point in time.

Of course, all of the above is null and void if the monsters are in 'disperse' mode (which means they go to their perspective corners).

As far as speed, all of the monsters are absolutely the same speed, with the exception of Blinky. He starts out the same speed, but as the board progresses, he speeds up, sometimes considerably in the later boards. Also, he is the only one that can 'break out' of disperse mode. On the much later boards, after the monsters reverse direction and go to their corners, Blinky will continue to persue you.

Hope this helps. :)

Bob

#8 PacManPlus OFFLINE  

PacManPlus

    River Patroller

  • 4,101 posts
  • Atari 7800 Dev
  • Location:SouthWest Florida

Posted Wed Apr 27, 2005 8:52 PM

By the way, the main difference in the Monster AI between Pac-Man and Ms. Pac-Man, is that in Ms. Pac-Man, Blinky and Pinky randomly move about the maze while in the first 7 seconds instead of going into their corners. This was probably done to make patterns almost impossible. Also, there is no more 'disperse mode' (other than the initial 7 seconds). When the monsters reverse direction, they still chase you.

Edited by PacManPlus, Wed Apr 27, 2005 8:53 PM.


#9 vdub_bobby OFFLINE  

vdub_bobby

    Quadrunner

  • Topic Starter
  • 5,831 posts
  • Boom bam.
  • Location:Seattle, WA

Posted Thu Apr 28, 2005 9:11 AM

Hope this helps. :)

View Post

Yes, thanks very much.

I have been able to find the disassembly online, but not one that is well commented. And I don't know Z80 assembly well enough to go through it myself :(

Another question: Which console port of Pac-Man has ghost AI that is closest to the original?

#10 PacManPlus OFFLINE  

PacManPlus

    River Patroller

  • 4,101 posts
  • Atari 7800 Dev
  • Location:SouthWest Florida

Posted Thu Apr 28, 2005 11:08 AM

Other than Opcodes' port to the Colecovision which is dead-on, it looks to me like (believe it or not) the 5200 version is pretty close. A few differences I've noticed:
1) Toward the end of the board, instead of just blinky speeding up in the arcade, all of the monsters speed up.
2) Clyde seems to have a somewhat more random movement than the arcade at times.
3) (This isn't really monster AI related) - you don't 'quickly' turn corners if you move the joystick ahead of time like in the arcade. Therefore the monsters can catch you easier while turning a corner - it's just one thing that's always bugged me (the collision detection).

Bob

Edited by PacManPlus, Thu Apr 28, 2005 11:08 AM.


#11 Dav OFFLINE  

Dav

    Moonsweeper

  • 353 posts

Posted Thu Apr 28, 2005 9:26 PM

blue's ai
27cb  ed4b0a4d  ld      bc,(#4d0a)  red ghost position
27cf  ed5b394d  ld      de,(#4d39)  pac postion
27d3  2a1c4d    ld      hl,(#4d1c)  pac offset
27d6  29        add     hl,hl
27d7  19        add     hl,de  	hl= 2hl+de= 2 spaces in front of pacman
27d8  7d        ld      a,l
27d9  87        add     a,a
27da  91        sub     c
27db  6f        ld      l,a
27dc  7c        ld      a,h
27dd  87        add     a,a
27de  90        sub     b
27df  67        ld      h,a  hl=hl+ hl-red ghost.	
27e0  eb        ex      de,hl
27e1  2a0e4d    ld      hl,(#4d0e)
27e4  3a2e4d    ld      a,(#4d2e)
27e7  cd6629    call    #2966  	get best direction given de as destination.
27ea  22224d    ld      (#4d22),hl  blue offset
27ed  322e4d    ld      (#4d2e),a        blue direction
27f0  c9        ret 

You can see why it's confusing. THe inputs are the red ghost x,y coordinates and 2 spaces in front of pacman.

#12 PacManPlus OFFLINE  

PacManPlus

    River Patroller

  • 4,101 posts
  • Atari 7800 Dev
  • Location:SouthWest Florida

Posted Fri Apr 29, 2005 4:27 AM

Wow - that is weird :-/

Thanks Dav; I was wondering when you'd be appearing in this thread :D

#13 Dav OFFLINE  

Dav

    Moonsweeper

  • 353 posts

Posted Fri Apr 29, 2005 6:58 AM

Wow - that is weird :-/

Thanks Dav; I was wondering when you'd be appearing in this thread  :D

View Post



Yes, I'm real busy right now or I'd post more on my favorite subject :)

#14 vdub_bobby OFFLINE  

vdub_bobby

    Quadrunner

  • Topic Starter
  • 5,831 posts
  • Boom bam.
  • Location:Seattle, WA

Posted Fri Apr 29, 2005 12:25 PM

blue's ai
27cb  ed4b0a4d  ld      bc,(#4d0a)  red ghost position
27cf  ed5b394d  ld      de,(#4d39)  pac postion
27d3  2a1c4d    ld      hl,(#4d1c)  pac offset
27d6  29        add     hl,hl
27d7  19        add     hl,de  	hl= 2hl+de= 2 spaces in front of pacman
27d8  7d        ld      a,l
27d9  87        add     a,a
27da  91        sub     c
27db  6f        ld      l,a
27dc  7c        ld      a,h
27dd  87        add     a,a
27de  90        sub     b
27df  67        ld      h,a  hl=hl+ hl-red ghost.	
27e0  eb        ex      de,hl
27e1  2a0e4d    ld      hl,(#4d0e)
27e4  3a2e4d    ld      a,(#4d2e)
27e7  cd6629    call    #2966  	get best direction given de as destination.
27ea  22224d    ld      (#4d22),hl  blue offset
27ed  322e4d    ld      (#4d2e),a        blue direction
27f0  c9        ret 

You can see why it's confusing.  THe inputs are the red ghost x,y coordinates and 2 spaces in front of pacman.

View Post


Wow, thanks! I'd love to read more :)

#15 kisrael OFFLINE  

kisrael

    HMBL 2600 coder

  • 3,970 posts
  • Location:Boston Burbs, MA

Posted Thu May 12, 2005 2:42 PM

Dang, missed this thread before.

I've always been blown away by the psychology of the ghosts, ever since I read that piece in "Programmers at Work". My question is, does it really matter that much? It seems like some Pac-clones that pay much less attention to that detail seem to play about the same. I could be wrong though.

#16 vdub_bobby OFFLINE  

vdub_bobby

    Quadrunner

  • Topic Starter
  • 5,831 posts
  • Boom bam.
  • Location:Seattle, WA

Posted Thu May 12, 2005 2:59 PM

Dang, missed this thread before.

I've always been blown away by the psychology of the ghosts, ever since I read that piece in "Programmers at Work". My question is, does it really matter that much? It seems like some Pac-clones that pay much less attention to that detail seem to play about the same. I could be wrong though.

View Post

Which Pac-clones do you have in mind? And, just offhand, it seems the most important thing is preventing the ghosts from bunching up.

#17 scotty OFFLINE  

scotty

    Chopper Commander

  • 166 posts
  • I have, but have **YOU** played Atari today?
  • Location:North Olmsted, Ohio

Posted Wed Jan 17, 2007 11:55 PM

I wanna blow the dust odd this topic and bring it back too life. I am planning on a wo player Pac-Man game in Blitz and wanted more information on the Ghost's AI

#18 Dav OFFLINE  

Dav

    Moonsweeper

  • 353 posts

Posted Thu Jan 18, 2007 9:22 AM

I wanna blow the dust odd this topic and bring it back too life. I am planning on a wo player Pac-Man game in Blitz and wanted more information on the Ghost's AI



I'm still here and I'll still answer questions. :) I've done 2 player pac 2 different ways. I've hacked inputs into the red ghost so player 2 could drive him, and i've added a second pac. To do that I just swap out the variables for the pacmen every frame. It means that the collision detection happens every other frame so they will occaisionally get into a wall but it works fine otherwise.

#19 JamieVegas OFFLINE  

JamieVegas

    Combat Commando

  • 9 posts

Posted Mon Apr 2, 2007 6:42 PM

I have documented exactly what they do, except the blue ghost! I've been fascinated by the AI for a while. Nearly the all of the information you find on the web is entirely wrong.

It's all deceptively simple, and I'm very happy that Dav provided some assembly to make the solution definitive. I knew the blue ghost was seeking a destination two spaces ahead of Pacman, but it was also clear that the red ghost proximity was having some effect. Exactly what the effect was, I couldn't tell for sure. From the code, it appears that the blue ghost is always finding away to be nearer to two spaces ahead of Pacman, plus the difference between the red ghost and that spot. That is to say, if the red ghost is getting closer, so is the blue. This sort of makes sense along with the "personality" which is supposed to be exhibited by the blue ghost, which is that he is "bashful" and only directly attacks if the red ghost is around. If you're going towards him while the red ghost is far away, his destination is way ahead of you, and that's why he seems to "go in the opposite direction" sometimes.

If anyone wants to discuss disassembly or ghost AI information, please e-mail me!

Edited by JamieVegas, Mon Apr 2, 2007 9:09 PM.


#20 JamieVegas OFFLINE  

JamieVegas

    Combat Commando

  • 9 posts

Posted Wed Apr 4, 2007 11:37 AM

Breakthrough!

I've just disassembled and completely documented the entirety of the ghost AI.

It's incredibly simple, guys!

I'll post a link to the website I'm preparing as soon as it is ready.

#21 Dav OFFLINE  

Dav

    Moonsweeper

  • 353 posts

Posted Wed Apr 4, 2007 2:55 PM

Breakthrough!

I've just disassembled and completely documented the entirety of the ghost AI.

It's incredibly simple, guys!

I'll post a link to the website I'm preparing as soon as it is ready.



I've dissassembled them all before years ago. I don't know if I kept it around. Yes it is extemely simple compared to how complex the results seem. I'll be interested in seeing your webpage. If you haven't gotten around to doing the blue time it's just a psuedo random number generator using the program code to generate random bits, I always thought that was pretty neat.

#22 JamieVegas OFFLINE  

JamieVegas

    Combat Commando

  • 9 posts

Posted Thu Apr 5, 2007 1:02 AM

Dav,

I wish I'd known you'd disassembled all of it! I might have just wasted a ton of time. It seemed like from the last post about the blue ghost in this thread that there was at least still some confusion about the exact math and logic taking place.

Anyway, yes, I did get around to the blue time -- today, actually. I found the same thing -- it reads anywhere from 0000 to 1FFF in the ROM. Very strange.

I assume that if you got the wandering ghost path routine analyized that you got the best-direction function analyzed, too.

Did you find the AI for the attract mode demo Pacman? I found that today, as well. He is simply headed towards the destination point that is directly opposite the midpoint between the pink ghost and pacman. The demo seemed pre-recorded to me. It just goes to show how something simple can create the illusion of intelligence.



Breakthrough!

I've just disassembled and completely documented the entirety of the ghost AI.

It's incredibly simple, guys!

I'll post a link to the website I'm preparing as soon as it is ready.



I've dissassembled them all before years ago. I don't know if I kept it around. Yes it is extemely simple compared to how complex the results seem. I'll be interested in seeing your webpage. If you haven't gotten around to doing the blue time it's just a psuedo random number generator using the program code to generate random bits, I always thought that was pretty neat.



#23 Dav OFFLINE  

Dav

    Moonsweeper

  • 353 posts

Posted Thu Apr 5, 2007 8:41 AM

Dav,

I wish I'd known you'd disassembled all of it! I might have just wasted a ton of time. It seemed like from the last post about the blue ghost in this thread that there was at least still some confusion about the exact math and logic taking place.

Anyway, yes, I did get around to the blue time -- today, actually. I found the same thing -- it reads anywhere from 0000 to 1FFF in the ROM. Very strange.

I assume that if you got the wandering ghost path routine analyized that you got the best-direction function analyzed, too.

Did you find the AI for the attract mode demo Pacman? I found that today, as well. He is simply headed towards the destination point that is directly opposite the midpoint between the pink ghost and pacman. The demo seemed pre-recorded to me. It just goes to show how something simple can create the illusion of intelligence.




Breakthrough!

I've just disassembled and completely documented the entirety of the ghost AI.

It's incredibly simple, guys!

I'll post a link to the website I'm preparing as soon as it is ready.



I've dissassembled them all before years ago. I don't know if I kept it around. Yes it is extemely simple compared to how complex the results seem. I'll be interested in seeing your webpage. If you haven't gotten around to doing the blue time it's just a psuedo random number generator using the program code to generate random bits, I always thought that was pretty neat.



No, I never did the demo movement. I assumed it was random like the blue time. that explains some things :)

I've dissassembled it but I didn't neccessarily keep it. I usually work on scraps of paper when I'm working on something like the 2 player simultaneous mods I've done. Sometimes I'll type stuff into my dissassembly but not too often. I've been through the code enough times in the last 8 years I just know what most of it does.

The cool thing about the blue time is it random but it repeats every time. Much easier for tracking down bugs in development than in e.g. ms pacman where they use the R register a lot.

#24 JamieVegas OFFLINE  

JamieVegas

    Combat Commando

  • 9 posts

Posted Mon Apr 9, 2007 3:56 PM

Dav,

You did Ms. Pacman as well? What did they do to the ghost logic, exactly?

Are they still using the same algorithm to get a direction based on a source and destination grid point? Where exactly does the randomness come into play?

What about the "personalities"? How much different are they from the original Pacman?

#25 Dav OFFLINE  

Dav

    Moonsweeper

  • 353 posts

Posted Mon Apr 9, 2007 5:05 PM

Dav,

You did Ms. Pacman as well? What did they do to the ghost logic, exactly?

Are they still using the same algorithm to get a direction based on a source and destination grid point? Where exactly does the randomness come into play?

What about the "personalities"? How much different are they from the original Pacman?



I did. I seem to remember the randomizing element was to randomize their home quadrant. There may be more too. There's a dissassembly on the net that has some notes in it. If you look though it at the ai part any jumps/calls to 8000-9800 is stuff that got changed. Ms pac is pacman with some jumps overlayed on top of the pacman code. I'll try and look for my notes on it.


I did a little bit on pac plus. They have added a little section of a few seconds of random behavior to the cycle of behaviors. It's a complete recompile so it's a little harder to figure out, and not as interesting as it's too hard for me.

Also I did the pacman harder set that namco put out. Fortunetly I put that in pacman.c in the mame driver so I don't have to worry about losing that one :)

Pacmod Harder compared to Pacman
pacmanh.5E
erase tiles $25:"." $28-$2e:"NAMCO" $5c:copyright C

program code
pacman/pacmod
0843: 14 0F Table of when ghosts come out of house.
0844: 1E 14
0845: 46 37
0846: 00 04 pink, level 1
0847: 1E 18 blue
0848: 3C 34 orange
0849: 00 02 level 2
084A: 00 06
084B: 32 28
084c: 00 00 level 3
084D: 00 04
084E: 00 08
0FFF: 36 54 checksum
2795: 29 00 pink ghost ai, points target to 2 tiles in front of pac instead of 4.
281F: 40 24 orange ghost ai, change close/far breakpoint from $40 to $24.
2FFF: 4C 91 checksum
37F8,3d28,3d43: change 1980 to 1981
Notice the harder upgrade was 2 roms only. 6e,6h. The others are from a newer set.




0 user(s) are browsing this forum

0 members, 0 guests, 0 anonymous users