PacMan Style Pathfinding

I am attempting to add enemies to a simple game I have developed (in objective c) and am trying to figure out how I should implement the enemy AI or pathfinding.  I do not need anything too advanced or complicated and in my mind the best possible solution would be if I could make my enemies behave the same way the ghosts do in pacman.

Some sample code and explanation would be greatly appreciated!!

Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

iPeteAuthor Commented:
The implementation does not have to be of the A* or BFS or DFS algorithm I am just looking for a simple solution that will provide a similar result to what the player experiences in pacman with the ghosts following and fleeing.  I understand all 4 ghosts have different AI and I am just looking for something fun and basic.

iPeteAuthor Commented:
☠ MASQ ☠Commented:
Programatically there are two choices for the "ghost" AI in PacMan:

1) At junction is target above/below or left/right of ghost if so take that path from the junction - unless there is already a ghost between the target and your location already if so replot an alternate route using the same left/right/up/down rule but ignoring that exit from the junction.


2) At each junction calculate the number of moves to reach the target, take the shortest route (again unless there is already a ghost on that route)

In Pacman there is also a "confounding variable" which determines whether the route chosen is ignored which starts (for example) at 75 on Level 1 and decreases by 5 at each level until it reaches zero. That's the % chance that the ghost will not take the best route using either of the two algorithms above. So the ghosts appear to get cleverer as the game progresses. Ghost 2 starts at 50, ghost 3 = 25 etc. So the final ghost will always take the best route.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
HTML5 and CSS3 Fundamentals

Build a website from the ground up by first learning the fundamentals of HTML5 and CSS3, the two popular programming languages used to present content online. HTML deals with fonts, colors, graphics, and hyperlinks, while CSS describes how HTML elements are to be displayed.

iPeteAuthor Commented:
Thanks so much for posting a comment.  This is exactly the kind of info I was looking for.  If you could just elaborate a little more I would be happy to consider this solved.

I am using a tile map, and the mazes in the tile map are more like a collection of rooms and corridors that could lead to dead ends or to other rooms, objects etc.  With this in mind it would be nice to define junction, as I see it a junction would be a corner of any kind.  I also believe that perhaps I should "mark" the junctions on the map with invisible objects so that when an enemy ghost hits a junction it knows it needs to perform it's AI calculation as opposed to waiting till the ghost has a collision (run into the wall) too perform it's AI functions.

Do you believe this is a good approach, what are your recommendations for implementing this kind of algorithm given the tilemap/object considerations mentioned above?

Again thanks for your insight and attention :)
☠ MASQ ☠Commented:
Without wanting to start throwing in more work for you just a few points about using the "ghost" AI for this:
You'll have a problem using the PacMan ghost concept with dead ends.  The reason PacMan works well is the player always has one other route to escape so tactically can deliberately allow one ghost to get close knowing they can still get away while the game "thinks" it's got you.  Unless you allow for combat of some kind in your game once your player is between your "ghost"  and the dead end and there are no more junctions the game is effectively over.  If you don't have some form of "Radar" to indicate to the player that trouble is coming it could effectively become a game of chance.
You could improve your player's chances by linking all the tiles  so each room has two exits or maybe once a player heads down a dead end you post a warning so they know if there's a "ghost" following potentially heading down a dead end would be a suicide mission.
You might want to add an escape function transporting your player at random to another place in the game that they could use only a few times per level.
iPeteAuthor Commented:
Just about to jump a plane for India so not a lot of time to respond, but I will be allowing combat between player and ghost on a minimal level.  The player also uses a life count so the game would not end unless the player has depleted this count by multiple encounters with the ghosts or other obstacles.

1. I assume my definition of 'junction' was correct?
2. What do you think about the idea of placing invisible 'junction' objects, any ideas as to how the ghosts should behave when they hit a junction?  Pseduo code perhaps...
3. Any other suggestions or heads up you could offer as to potential problems using this behavior model?

Thanks again!! and I will check back in as soon as I land.
☠ MASQ ☠Commented:
Yes, your use of junctions is right.  It's easier to use some form of marker when you actually get to a junction than to check on each move if you've arrived. You could then use them to trigger the AI choice on direction.
Still might be worth some way of indicating ghost proximity to the player otherwise it should work well.
Hope the flight goes/went well.
iPeteAuthor Commented:
Tricky question, good response.
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Game Programming

From novice to tech pro — start learning today.