Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win


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.
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.


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

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

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 …
Artificial Intelligence comes in many forms, and for game developers, Path-Finding is an important ability for making an NPC (Non-Playable Character) maneuver through terrain.  A* is a particularly easy way to approach it.  I’ll start with the algor…
In this video, Percona Solution Engineer Rick Golba discuss how (and why) you implement high availability in a database environment. To discuss how Percona Consulting can help with your design and architecture needs for your database and infrastr…
This lesson discusses how to use a Mainform + Subforms in Microsoft Access to find and enter data for payments on orders. The sample data comes from a custom shop that builds and sells movable storage structures that are delivered to your property. …

610 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