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.

Solution 1

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.

Solution 2

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!

Solution 3

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

Solution 4

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

Solution 5

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

View more solutions

Comments

[TofuBeer]

Pacman does do better than the above algorithm perhaps (especially as the game progresses). A*, etc... is a good starting point... I didn't say it was a good ending point :-)

[coobird]

I actually haven't played Pac-Man in a long time, so I don't quite remember how smart those ghosts became. Actually, I don't think I ever got past level 3 or 4. Hey, I was in 3rd grade ;)

[TofuBeer]

Well it could be due to the speed increase that they are more able to target you... or it could be that they add some randomness that they reduce as you get higher in levels.

[coobird]

That could very well be true!

[gregory boero.teyssier]

I basically did my ownn thing. First i'd calculate the distance between the ghost and the pacman from top, left, right, and bottom. Then based on which distance is shortest i have the ghost move in that direction. Works great, and by giving them different speeds they dont stick together either

[Esteban Brenes]

You might be interested in this for a more detailed look at the Pac-Man Ghost logic: home.comcast.net/~jpittman2/pacman/pacmandossier.html

[Matthew]

right but what happens if there is an obect in the way, your method is flawed. just saying. i am too actually looking at a* logic.