Solved

# PacMan Style Pathfinding

Posted on 2010-08-12
1,083 Views
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!!

Thanks.
0
Question by:iPete
• 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.

Thanks
0

Author Comment

ID: 33425791
Anyone...
0

LVL 62

Accepted Solution

☠ MASQ ☠ earned 500 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.

or

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.
0

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 :)
0

LVL 62

Expert Comment

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.
0

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.
0

LVL 62

Expert Comment

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.
0

Author Closing Comment

ID: 33437912
Tricky question, good response.
0

## Featured Post

Question has a verified solution.

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

### Suggested Solutions

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 …
Performance in games development is paramount: every microsecond counts to be able to do everything in less than 33ms (aiming at 16ms). C# foreach statement is one of the worst performance killers, and here I explain why.
This Micro Tutorial demonstrates using Microsoft Excel pivot tables, how to reverse engineer competitors' marketing strategies through backlinks.
Nobody understands Phishing better than an anti-spam company. That’s why we are providing Phishing Awareness Training to our customers. According to a report by Verizon, only 3% of targeted users report malicious emails to management. With compan…