pac man ghost ai
Author
i'm thinking about making a tile game similar to packman where you get chased by enemies. i read an article here pointing out that the ghosts in pacman had specific jobs, like one follows shortest path to chase you, one tries to hang out in the middle of the map to cut off your escape, one randomly moves around one part of the map to make life difficult when you gotta go to that area, stuff like that
i was wondering about what would be the best way to go about making the one that actively follows shortest path to catch you.
i'm thinking the level will be made up of an array of tiles, you can move from tile to tile unless a barrier is between the two tiles. this array of tiles could be reppresented as a graph with each vertex having a path to all adjacent vertices unless theres a wall between the vertices (the wall would only exist on the bitmap, the only thing the graph knows is that there is no path to the blocked tile).
its been a while since i last did anything with algorithms, the only thing i remember is dijkstra's algorithm is used to find a minimum spanning tree which can be looked at to find a shortest path. is the best solution to run dijkstra's algorithm once for each square on the map before the game starts and each time the ghost wants to move, he looks at his position and pac man's position and looks up what would be the shortest path and makes his move accordingly?
or is that overkill? should the ghost just know his coordinates and pac man's coordinates and try to move in a direction that reduces the distance?
or is there another really cool shortest path algorithm that i'm forgetting?
A-star is usually used for path finding. You can think of it as a flood fill, directed by a heuristic. Dijkstra's for a single cell isn't all that different, really.
So, just decide whether you want to re-run it from the cell the ghost is in every so often (say, once every 10 frames or whatever), or whether you want to spend the memory to pre-calculate. Either will work.
So, just decide whether you want to re-run it from the cell the ghost is in every so often (say, once every 10 frames or whatever), or whether you want to spend the memory to pre-calculate. Either will work.
First: http://jongy.tripod.com/GhostPsychology.html
Now, there's a particularly easy way to do distance determination and path-finding in a 2D tile array. Make a 2D array the size of your level. Initialize all the empty (non-wall) squares to some large number (like 9999) and all the wall squares to -1. Set the square the player is located in to 0. Then you can easily determine how many squares away each square is from the player. This is done by traversing the array twice; once starting at the upper-left and going down/right and once starting in the lower-right and going up/left. For each square that isn't a wall, you look at its neighbors that aren't walls. If that neighbor's distance value + 1 is less than the square's distance value, make the square's value the neighbor's value + 1. Example: The player's square is 0. When you're at the square next to the player's square, your value will be 9999. You'll see that the player's square + 1 (1) is less than your value (9999) so you make your value 1. The next square over will be 2 (as 1+1 is less than 9999 again), etc. A couple of easy optimizations are that you don't have to check every neighbor (just the ones up/left when you're traveling down/right, and down/right when you're traveling up/left) and you don't have to reset the distance array every frame.
When it's time to move the ghosts, just have them look at the distance value for the square they're in and the neighors' distance values and they can always make the best move. Not necessarily the best or fastest method, but it's easy to program and it's guaranteed to find the fastest path (in a 2d tile-based level).
Now, there's a particularly easy way to do distance determination and path-finding in a 2D tile array. Make a 2D array the size of your level. Initialize all the empty (non-wall) squares to some large number (like 9999) and all the wall squares to -1. Set the square the player is located in to 0. Then you can easily determine how many squares away each square is from the player. This is done by traversing the array twice; once starting at the upper-left and going down/right and once starting in the lower-right and going up/left. For each square that isn't a wall, you look at its neighbors that aren't walls. If that neighbor's distance value + 1 is less than the square's distance value, make the square's value the neighbor's value + 1. Example: The player's square is 0. When you're at the square next to the player's square, your value will be 9999. You'll see that the player's square + 1 (1) is less than your value (9999) so you make your value 1. The next square over will be 2 (as 1+1 is less than 9999 again), etc. A couple of easy optimizations are that you don't have to check every neighbor (just the ones up/left when you're traveling down/right, and down/right when you're traveling up/left) and you don't have to reset the distance array every frame.
When it's time to move the ghosts, just have them look at the distance value for the square they're in and the neighors' distance values and they can always make the best move. Not necessarily the best or fastest method, but it's easy to program and it's guaranteed to find the fastest path (in a 2d tile-based level).
I second the vote for A*. I have developed my own PacMan clone and used A* to find shortest paths. Very fast, and quite easy to implement. Also, I used AI Game Programming Wisdom as my guide for implementing A*.
-Kirk
-Kirk
i can get to the 11+ board so i know what this site above it talking about. Blinky will chase you and/or seek you out after the first scatter mode. the scatter mode is still important when you want to get up as many dots as possible.. especially when the power pellets dont work anymore. i am always been a pac man king -- getting to like the 3 junior acts(on ms pac man) where the pellets dont turn them blue anymore -- they just turn in the opposite direction. but sometimes i have died when i have gotten the power pellet to turn them around but unknown to me they were just about to go to scatter mode, which then in turned turned them back around on me again and this is not cool. i would interested in someone having some theories about Junior and Super Pac Man -- the ghosts have different personalities in those games. Ms Pac Man is different as well.
I made a pacman game once and every character had different AI....
A very simple thing you could do is detect when a turn is possible, and then if so, calculate the difference in the ghost's position and the character's position. So something like:
dx = pacman.x - ghost.x
dy = pacman.y - ghost.y
So, say you can turn either left or right and dx is negative, then you should turn left... etc
This actually works fairly well... The other thing I used in my game was A* pathfinding. Using this, you can forge a straight path, but beware as this may make your AI *too* clever.
Another devious thing I did was, the blue ghost would calculate where you were *going*, and then try to cut you off by getting there first.
Good luck!
roos
A very simple thing you could do is detect when a turn is possible, and then if so, calculate the difference in the ghost's position and the character's position. So something like:
dx = pacman.x - ghost.x
dy = pacman.y - ghost.y
So, say you can turn either left or right and dx is negative, then you should turn left... etc
This actually works fairly well... The other thing I used in my game was A* pathfinding. Using this, you can forge a straight path, but beware as this may make your AI *too* clever.
Another devious thing I did was, the blue ghost would calculate where you were *going*, and then try to cut you off by getting there first.
Good luck!
roos
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
