Today I started working on a Pac-man clone, which is my first attempt at a game with AI (albeit simple AI). Some wise man on this message board once named 3 classic games that beginners should try to clone in order to get a good grasp on the essentials of game programming. I think he said a Tetris clone should be made for learning good structure/logic in a game, a Breakout-type game should be made for learning how to model basic physics, and lastly Pac-Man for learning AI. He was a wise man, but I must be a damn sucker. My first two games (in C/C++ and DirectX) were a Pong game and a Worms/Scorched Earth type game, so I''m not too experienced yet. Today I started Pac-Man and everything was going alright (I got tiles and some graphics on the screen), but then I got to the ghosts and the AI and now I''m stuck. I have no idea what I''m doing. I can''t the ghosts to do anything reasonable (they just get stuck in walls -maybe that''s what ghosts really do). I''ve read articles and lots of stuff about AI theories, but I never seen any source code. How the hell I am supposed to how to code behavior states and pathfinding and all that good stuff? The way I made my first real game (Pong) was by looking at the source of a Breakout game and reverse engineering it. It worked very well (and I added the option for playing with an AI controlled opponent). For my second game (Extreme Guerrillas), I looked at the QBASIC source code for Gorillas (without remembering any BASIC from 5 years ago) and then converted most of it to C and heavily modified it to run in DOS. After a while I learned DirectX and converted the game to Windows. BTW, did you know Microsoft used a quadratic equation in their physics algorithm for trajectory? It used exponents and square root stuff... not too clever. The way I modeled the trajectory just used addition. It worked just as well, and it was certainly faster! What can you expect from Microsoft? Anyway, I''m completely stuck trying to code Pac-Man. Like I said, I''ve read about theories, but they don''t really help me. If I had the source code to a Pac-Man game or something similar I''d be a happy man and I think I''d learn just as much. But maybe I''ll figure something out after I pull my hair out... wait a minute, I don''t have hair. Al

Now, I don''t know much about AI or anything, but I can say that if you just started Pac-Man today, you probably shouldn''t be on the ghosts yet... I know Pacman is a simple game, but if it''s one of your first you should probably be spending a little more time on planning...

------------------------------
Jonathan Little
invader@hushmail.com
http://www.crosswinds.net/~uselessknowledge

Warning, this describes a AI technique. It is just a short term solution that I through together. The reason I am saying this is, if you are begining, you need to be able to figure out what is going on. But I give it to you because I am nice, and after you see, you''ll say why didn''t I think of that.

You want Pac Man AI. There are 2 things you can do. Make the ghost always know where Pac Man is, or make the ghost have to see Pac Man. Making them always no is the easiest. First check Pac Man''s x-y coordinates and see if he is to the left, right, above or below the ghost. Before you move the ghost, check for a wall. If the is a wall blocking it any direct path, send it off in the opposite direction. The ghost should have 3 states: direct chase, flee, and indirect chase.
For direct chase, the ghost will follow the above algorithm
Flee is used when Pac Man Eats one of the big pelets and is just the opposite of the above.
Indirect chase is when the ghost is chasing, but can''t find Pac Man because there are too many walls blocking its path. Indirect chase will have some random elements to it. You''ll have to figure out the rest for your self. I''m sure there are easier ways, but that''s the first thing that came to mind. I''ve never written a Pac Man Clone.

Domini

Your in luck, I've got the source code to a pacman clone i did, email me and ill send you the source code if you want. I'm not sure the way i did it is easier than the method described by Domini, but it works and it works well. It took me a just over a week to finish pacman, and 90% of my time was spent on the AI part. I only have one level in it so thats why it took such a short time but the way i did it was write out all the places in the level where the paths intersect, then write down all the paths that can stem from those intersections. I made it into a sort of database of paths. Then to calculate the ghosts next move i just used the path that would take it closer to it's destination or away from pacman if he has eaten a power up. The ghosts job wasn't only to chase pacman, one ghost chases pacman another moves towards the nearest juction to pacman, another the second nearest junction to pacman and the last ghost picks a random direction at every intersection. So they work as a team to try and catch him. Later.

Edited by - Chris F on 2/12/00 10:22:41 PM

Thanks for your advice. I already know some AI basics, like simple chasing, evading, random motion, and patterns, but I''m just confused about avoiding obstacles. You mentioned if the ghost hits a wall he''ll go in the opposite direction. I understand that, but if the ghost is supposed to always know where the player is, wouldn''t changing his direction in one frame have no effect? Here''s what I mean: Since the player''s always moving, wouldn''t the ghost have to update the player''s position every frame? If so, if I told the ghost to go in the opposite direction, the next frame he would just turn back around and hit the wall again if he knew the player was in the opposite direction. Do you understand what I mean? I don''t know how I could prevent that. I was thinking maybe if I only updated the ghost''s knowledge at certain intervals.. so if the ghost found a new crack in the wall he wouldn''t turn around and hit the wall again. Am I even on the right track?

Al

I think you should look into AI pathfinding. There is an excellent article on Gamasutra that describes a lot of algorithms that you can use for your game.

I see if I can find it for you... please wait =)

Found it: Smart Move: Path-finding by W. Bryan Stout.

Edited by - Spellbound on 2/13/00 5:10:35 AM

Heya,

A few years back I wrote a game ("Interchange" on the Amiga, in case you were interested) that had almost exactly that sort of problems with the baddie AI. I found that the baddies were making decisions every frame and often they contradicted each other from frame to frame and they just seemed to get stuck or they homed in on the player so quickly that the player stood no chance at all.

My game had a similar layout to PacMan (Ie, it was a maze game) and the solution I used was to cut down the frequency of the decision making for the baddies. The only time they could make a decision is when they came to a junction and would never go back they way they came unless they were in a dead end. This worked remarkably well, despite its simplicity, and once you had 3 or 4 baddies on screen, you had a tough time staying out of thier way. Of course in your pacman game, you will have to have them change state whenever PacMan eats a pill.

Anyway, hope that helped.

--== Rapier ==--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Save the whales, feed the hungry, free the mallocs!

As for the frame question, AI doesn''t have to occur at every frame. Collision detection does(even that is debatable) but AI doesn''t. Pick a direction for the ghost and send it that way checking for a collision. When the ghost collides with a wall, then run the decision making routine to decide a new direction. It is this decision where the AI techniques mentioned above come into play.

What I mentioned here is pretty easy to figure out as a player and will make the game boring fast, but it illustrates the difference between collision detection and AI. If you noticed in the arcade game everything was pretty symetrical. The game was built on a grid of tiles neatly organized into the maze. You could extend the decision point model above to include every time the ghost coordinates correspond to the center of each tile in the maze, meaning that everytime it moves one tile you decide if it should continue in the same direction or change directions using AI. Lastly you could add to the tile checks to look for pac man in the immediatly adjacent tiles and give those directions priority over other available decisions.

PacMan''s AI was pretty elegantly done for its time. Using a combination of Domini''s and Chris'' ideas you should be able to faithfully reproduce the game.

Kressilac

ps Once you get this far you will realize that you can eliminate the need for collision detection every frame by dealing with the center of the tile and the center of a ghost image. Animate the ghost for tile center to tile center and incorporate this with your AI. *smile*