Path finding in a Java 2d Game?

Question

Essentially its a pacman clone game I'm working on. I have an Enemy class, and 4 instances of this class created which all represent 4 ghosts of the game.

All ghosts start up in random areas of the screen and then they have to work their way towards the pacman character. As the player controls the pacman, moving it around, they should follow it and take the nearest possible way towards him.

There is no maze/obstacles (yet) so the entire map (400x400 pixels) is open ground to them.

For the player and each Ghost, i can retrieve the X, Y, image width and height attributes. Also, i already have a collision detection algorithm, so not worried about that, just about the ghosts finding their way to pacman.

Answer 1

You could start looking at A* (A star)

And here is a page that has links to other path finding algorithms.

[edit] gah... brain is too slow... forgot about this book, it is C or C++ (I forget which), but you can still get the concepts for Java. It may not be the easiest for you to read, but isn't bad overall. AI for Game Developers by David M. Bourg, Glenn Seemann.

Answer 2

For a good pathfinding algorithm, using A* would probably be a good idea, however, for a simple game that doesn't require sophisticated, efficient, nor effective path searching, simply having the characters move toward a target by finding out the direction of the target should be sufficient.

For example, the decision to make the character move, in pseudocode:

if (target is to the left of me):
    move(left);
else
    move(right);

if (target is above me):
    move(up);
else
    move(down);

Yes, the character is not going to make the most efficient movement, but it will get closer and closer to the target on each iteration of the game loop.

It's also my guess that an arcade game from the early 80's probably wouldn't be using sophisticated pathfinding algorithms.

Answer 3

If you just have a grid of pixels - an "big field" on which pacman and ghost can move about freely - then the shortest path is easy - a straight line between the ghost and the pacman.

But "shortest path" invariably means we're trying to solve a graph-theory problem. (I'm assuming knowledge of graphs, some graph theory, adj. matrices, etc!)

In the case above, consider each pixel to be a node on a graph. Each node is connected to its neighbors by an edge, and each edge has equal "weight" (moving to the node on "above" is no slower than moving to the node "below").

So you have this: ("*" = node, "-, /, \, |" = edge)

*-*-*
|\|/|
*-*-*  ... (etc)
|/|\|
*-*-*

If Pacman is in the center, it can move to any other node very easily.

Something more closer to reality might be this:

*-*-*
| | |
*-*-*  ... (etc)
| | |
*-*-*

Now, pacman cannot move diagonally. To go from the center to the bottom-right requires 2 "hops" rather than one.

To continue the progression:

*-*-*-*
| | | |
| | | |
| | | |
*-*-*-*
| | | |
*-*-*-*

Now, to go from a node in the middle to a node at the top, you need 3 hops. However, to move toward the bottom only takes 1 hop.

It would be easy to translate any game-board setup into a graph. Each "intersection" is a node. The path between two intersections is an edge, and the length of that path is the weight of that edge.

Enter A*. By constructing a graph (use an adjency matrix or a list of nodes), you can use the A* algorithm to find the shortest path. Other algorithms include Dijkstra's. And many others! But first you need to frame your problem in terms of a graph, and then toy with how you'd go from node A (pacman) to node B (ghost).

Hope that helps!

Answer 4

I think go for the shortest path algorithm at every move made by pacman. A very good implementation is Dijkstra's algorithm.

Just to summarize: Visualize the maze as a graph with vertices and edges. Each edge has a wait (in your case all the edges have same weight). The algorithm finds the shortest path from source vertice to target vertice by moving one step down each immediate reachable edge. Then on the next vertice you do the same and keep on doing until to you get to the target. The first path reached is the shortest path. There can be many optimizations done to this algorithm to speed up the things like taking into account where the pacman was in its previous position and in which direction it moved so that you can get some heiristics in the algorithm. I would suggest finding the shortest path from each ghost to pacman on every movement and move the ghost in that direction. Eventually the distance will reduce and you will be able to catch pacman.

Another heuristic that can be used it to find all the immediate edges reachable from pacman and try to cover as many of these vertices as possible by ghosts. So instead of setting pacman as the target vertice we set the vertices immediatetly reachable by pacman as target, the result will be that the available ghosts will try to cover up themajor escape routes of pacman and catch him.

Answer 5

It's been a very long time, but from memory the ghosts in Pac-Man didn't do much in the way of pathfinding. They would do a fairly standard randomized maze traversal until they "spotted" you, which involved finding an unobstructed path along the axis of a corridor towards you, and then they would move directly towards you until you disappeared from their line of sight, whereupon they would resume a random pattern. On higher levels Pac-Man would leave invisible trails behind him for a while that the ghosts would "smell" and sometimes follow.

When Pac-Man got a power up, the only difference in the algorithm is that, when they spotted you, the ghosts would flee you instead of moving towards you.

So, for an authentic experience, you probably don't need a very sophisticated pathfinding algorithm at all. If you want to be fancy, of course, you can implement A*.

Answer 6

Walking directly towards your enemies is a start but when you add a maze you'll want to add a bit smarter pathfinding so your ghosts don't get stuck in bends or dead ends.

The following tutorial is a great lightweight guide to get started with A*, with downloadable examples.

Path Finding on Tile based Maps

Answer 7

Hello

in Pacman all of the ghost had a different chasing algorithm

• Blinky -> Chases. Will usually take the shortest route to you, and tends to follow.
• Pinky -> Ambushes. Tends to take a more roundabout way to pac-man. Deadly. (pinky and blinky tend to make different choice when choosing a direction , often caging the player in a corner)
• Inky -> Freak. This dude acts strangely. He moves about the board fairly randomly, but sometimes chases when he gets in close.
• Clyde -> Idiot. Moves randomly. Not much of a threat.

The ghosts have an interesting pattern programmed into their movements: occasionally, they will simultaneously cease and desist their pursuit of Pac-Man and return to their respective corners of the maze, entering "scatter mode".

there is a full description of the algo at the pacman dossier

regards

Guillaume