PacMan Style Pathfinding

Posted on 2010-08-12
Medium Priority
Last Modified: 2013-12-26
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!!

Question by:iPete
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 3

Author Comment

ID: 33425428
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.


Author Comment

ID: 33425791
LVL 63

Accepted Solution

☠ MASQ ☠ earned 2000 total points
ID: 33426977
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.
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!


Author Comment

ID: 33431488
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 :)
LVL 63

Expert Comment

by:☠ MASQ ☠
ID: 33435748
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.

Author Comment

ID: 33437288
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.
LVL 63

Expert Comment

by:☠ MASQ ☠
ID: 33437338
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.

Author Closing Comment

ID: 33437912
Tricky question, good response.

Featured Post

Will your db performance match your db growth?

In Percona’s white paper “Performance at Scale: Keeping Your Database on Its Toes,” we take a high-level approach to what you need to think about when planning for database scalability.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

What is RenderMan: RenderMan is a not any particular piece of software. RenderMan is an industry standard, defining set of rules that any rendering software should use, to be RenderMan-compliant. Pixar's RenderMan is a flagship implementation of …
Recently, in one of the tech-blogs I usually read, I saw a post about the best-selling video games through history. The first place in the list is for the classic, extremely addictive Tetris. Well, a long time ago, in a galaxy far far away, I was…
This tutorial will teach you the special effect of super speed similar to the fictional character Wally West aka "The Flash" After Shake : http://www.videocopilot.net/presets/after_shake/ All lightning effects with instructions : http://www.mediaf…
In this video you will find out how to export Office 365 mailboxes using the built in eDiscovery tool. Bear in mind that although this method might be useful in some cases, using PST files as Office 365 backup is troublesome in a long run (more on t…

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question