I’m writing a remake of pacman, and the ghost pathfinding is giving me tons of problems. I can’t get it to work. I’ve studied the astar algorithm untill my head hurt, tried to implement it two different ways, and it still doesn’t work. Any pathfinding advise? Is there a better or quicker way than astar? Am I a complete moron? Help is appreciated.
Well, AStar is about it for easy to do pathfinding. The only other option is to drop AStar and calculate every possible path to the destinatioon. :o
Generating the tree is easy enough. i.e.:
public class Position
{
public int x;
public int y;
public Position(int x, int y)
{
this.x = x;
this.y = y;
}
public Position[] generateMoves(Map map)
{
boolean[] moves = new boolean[4];
int count;
Position[] positions;
if(!map.isWall(x-1, y)) moves[0] = true;
if(!map.isWall(x+1, y)) moves[1] = true;
if(!map.isWall(x, y-1)) moves[2] = true;
if(!map.isWall(x, y+1)) moves[3] = true;
for(int i=0; i<moves.length; i++) count += (moves[i] ? 1 : 0);
positions = new Position[count];
count = 0;
if(!map.isWall(x-1, y)) positions[count++] = new Position(x-1, y);
if(!map.isWall(x+1, y)) positions[count++] = new Position(x+1, y);
if(!map.isWall(x, y-1)) positions[count++] = new Position(x, y-1);
if(!map.isWall(x, y+1)) positions[count++] = new Position(x, y+1);
return positions;
}
}
The only thing that code is missing is a way to generate the heuristic score. Add a score to them, and you can sort the position arrays and follow them in heuristic order. Of course, you may want to just try following the tree first to see if you can make it work. i.e.:
public boolean findPath(ArrayList path, Map map, Position start, Position end)
{
if(start.x == end.x && start.y == end.y) return true;
Positions[] paths = start.generateMoves(map);
for(int i=0; i<paths.length; i++)
{
if(findPath(path, map, paths[i], end))
{
path.append(start, 0);
return true;
}
}
return false;
}
Thanks for the help. That makes sense and it’s not too difficult! I’m not at the computer with my code on it so I can’t implement this until tomorrow, but I’ll tell you how it goes.
Somthing that bothers me about all this pathfinding buisness is that the ghost is calculating the best path to pacman each frame: it gets the ENTIRE path, but only moves a tiny amount (not even one tile in my game) before checking again. Is this over-doing it? I mean, I’m only using a tiny part of the calculated path. Should I only check every once in a while, or at certain times like when it or pacman gets to an intersection? Or is there a different way of dealing with this problem? Is it a problem at all?
edit: spelling
[quote]Somthing that bothers me about all this pathfinding buisness is that the ghost is calculating the best path to pacman each frame: it gets the ENTIRE path, but only moves a tiny amount (not even one tile in my game) before checking again. Is this over-doing it?
[/quote]
On a grid like PacMan you can probably get away with murder for pathfinding and still not notice too much of a performance drop. But with the A*Star heuristics, you can limit the number of branches you check. Theoretically (with the right heuristic) you could simply follow the next cell that has the highest probability of being correct. Again, since the mazes in PacMan are not difficult, (just keep trying to align the X and Y coordinates and you’ll get there) you can probably get away with such a simple implementation.
Another solution is to only update the path as needed. i.e. To reach PacMan, I can calculate a set of waypoints to reach his approximate location in the shortest period of time. Once I complete my manuvers, I then have a much shorter path to chase PacMan, and start using single waypoint paths to hunt him down.
Truth be told, pathfinding is one of the most complex pieces of any video game. Just getting to the destination is not good enough. You want them to get there FAST and intelligently. You may even want the characters to predict where the player is going to go. Sadly, those are very difficult issues to solve and far beyond the scope of simply plotting a path.
Cool. The heuristic function was also giving me problems with pacman, but I am putting it off untill I can actually make the ghost do somthing halfway intelligent. I thought about it a little bit and could only come up with this: The shortest distance between any two points (if I can only move up, down, left, and right; NOT diagonal) is |start.x - end.x| + |start.y - end.y| (the straight lines lining up the horizontal and vertical coordinates). This is never really the best move in pacman, because it is easy to have walls between the start and end points to get around. I figure, the farther away the points are using the above function, the more possibilities of finding a relatively straight path between them (only RELATIVELY straight). What I mean is, the smaller the straight-lines distance described above, the greater descrepancy between the straight-lines distance and the real distance. So my heuristic might be: find the straight-lines distance, and the shorter it is, add more to it. The only problem is that if the distance actually is the straight-lines distance, then it will greatly overestimate the heuristic. I could add another part to the heuristic function which could check to see if it is a straight line to pacman, or even if the straight-lines distance is the exact answer.
I hope I’m explaining my thoughts correctly. Thanks again for the great help.
[quote]I thought about it a little bit and could only come up with this: The shortest distance between any two points (if I can only move up, down, left, and right; NOT diagonal) is |start.x - end.x| + |start.y - end.y| (the straight lines lining up the horizontal and vertical coordinates). This is never really the best move in pacman, because it is easy to have walls between the start and end points to get around.
[/quote]
You can’t know until you try it, but that method should work just fine. Having walls in the way is not a problem, because the path finding algo explicitly eliminates paths with walls. Worst case is that you’ll take a slightly longer path than intended.
Another scoring algo might be:
int shortest = Math.min(endx-startx, endy-starty);
double cost = shortest + (double)Math.max(endx-startx, endy-starty)/shortest/;
If I understand what I wrote, that should favor paths that are shorter in both directions. I have no bloody idea if it will work, but it should generate some interesting numbers. 
Just remember to switch your start and end coords so that the result is always positive.
Some interesting links for you:
http://www.gamedev.net/reference/articles/article1841.asp
http://jongy.tripod.com/GhostPsychology.html
http://www.gamedev.net/community/forums/topic.asp?topic_id=130871&whichpage=1
[quote]Thanks again for the great help.
[/quote]
No problem. I just happened to be digging in this stuff lately, so it’s fresh in my memory.
That Ghost Psycology site is hilarious! Thanks for the links.
Here’s an update on this:
-
You need to keep a list of points previously checked in the path. You then need to prevent the findPath() method from following paths that have already been crossed. I did this by passing a parent into Position, then checking back through the parents to see each value returned by generateMoves() has already been checked.
-
Got the perfect scoring heuristic:
int x = Math.max(startx, endx) - Math.min(startx, endx);
int y = Math.max(starty, endy) - Math.min(starty, endy);
int score = Math.min(x, y);
if(x == 0) score = y;
if(y == 0) score = x;
if(score == 0) return score;
return (score + (double)Math.max(x, y)/score);
You’ll note that it’s very similar to the algo I posted before. It’s merely been perfected.
With the above code, lower values are better. i.e. The end point should have a score of zero, and all points leading away should have higher scores. Just sort the result returned by generateMoves by that score, and you should get the perfect path every time. Err… at least that’s how it has worked in testing.
As I haven’t used any path algorithms yet but have heard about the shortest path alrogithm of Dijkstra in our math course (in the context of graphs) and in our TCP/IP networking course, I was wondering if anybody would know of the performance difference if implemented in a game.
You would actually need to calculate a cost for each vertex but if you consider each square on the field as a point and the vertex has a distance of 1 to it’s neighboors so the weight of the vertex would be 1.
With a field of let’s say 3232, that would give 3232 points and each point is connected to it’s neighboors with a vertex of weight 1.
Any idea ?!
I tried to implement your algorithm jbanes. I made two Classes. One Position Class and a Pathfinder Class with the method from above.
My app is still doing an infinite loop caculating the paths. Did anyone get the code running?
I also have a question about this line of code:
Afaik theres no method “append” to an arraylist . Did you mean “add(int, object)” ? (this didn’t solve my problem)
[quote]My app is still doing an infinite loop caculating the paths. Did anyone get the code running?
[/quote]
Note point 1 in my follow-up. The updated version I have looks something like this:
import com.dnsalias.java.gage.collision.*;
public class Position
{
private Position parent;
private int x;
private int y;
public Position(int x, int y)
{
this(null, x, y);
}
public Position(Position parent, int x, int y)
{
this.parent = parent;
this.x = x;
this.y = y;
if(this.parent == null) this.parent = this;
}
public int getX()
{
return x;
}
public int getY()
{
return y;
}
public Position[] generateMoves(CollisionMap map)
{
boolean[] moves = new boolean[4];
int count = 0;
Position[] positions;
if(map.getValue(x-1, y, 2, 2) == 0) moves[0] = !parent.equals(x-1, y);
if(map.getValue(x+1, y, 2, 2) == 0) moves[1] = !parent.equals(x+1, y);
if(map.getValue(x, y-1, 2, 2) == 0) moves[2] = !parent.equals(x, y-1);
if(map.getValue(x, y+1, 2, 2) == 0) moves[3] = !parent.equals(x, y+1);
for(int i=0; i<moves.length; i++) count += (moves[i] ? 1 : 0);
positions = new Position[count];
count = 0;
if(moves[0]) positions[count++] = new Position(this, x-1, y);
if(moves[1]) positions[count++] = new Position(this, x+1, y);
if(moves[2]) positions[count++] = new Position(this, x, y-1);
if(moves[3]) positions[count++] = new Position(this, x, y+1);
return positions;
}
public double getScore(Position target)
{
int x = Math.max(this.x, target.x) - Math.min(this.x, target.x);
int y = Math.max(this.y, target.y) - Math.min(this.y, target.y);
int score = Math.min(x, y);
if(x == 0) score = y;
if(y == 0) score = x;
if(score == 0) return score;
return (score + (double)Math.max(x, y)/score);
}
public boolean equals(int x, int y)
{
return (this.x == x && this.y == y);
}
public boolean alreadyTraversed(Position position)
{
Position parent = this.parent;
while(parent.parent != parent)
{
if(parent.x == position.x && parent.y == position.y) return true;
parent = parent.parent;
}
return false;
}
public boolean equals(Object object)
{
Position position;
if(!(object instanceof Position)) return false;
position = (Position)object;
return (position.x == x && position.y == y);
}
}
Modifications to findPath():
public boolean findPath(ArrayList path, Position start, Position end)
{
if(start.getX() == end.getX() && start.getY() == end.getY()) return true;
Position[] paths = start.generateMoves(map);
double[] scores = new double[paths.length];
Position temppos;
double tempd;
for(int i=0; i<paths.length; i++)
{
scores[i] = paths[i].getScore(end);
if(i > 0 && scores[i] < scores[i-1])
{
temppos = paths[i];
tempd = scores[i];
paths[i] = paths[i=1];
scores[i] = scores[i-1];
paths[i-1] = temppos;
scores[i-1] = tempd;
}
}
for(int i=0; i<paths.length; i++)
{
if(start.alreadyTraversed(paths[i])) continue;
if(findPath(path, paths[i], end))
{
path.add(0, paths[i]);
return true;
}
}
return false;
}
[quote]I also have a question about this line of code:
Afaik theres no method “append” to an arraylist . Did you mean “add(int, object)” ? (this didn’t solve my problem)
[/quote]
Yes, that was a typo on my part. One of the many dangers of getting advice on forums.
Great, it runs or I should say it stops now. But somehow the coordinates that are stored in the “path” ArrayList are messed up a bit (my character is moving strangely, jumping around)
To make it easy I tested on an map without borders and walls. My map is a simple tilemap stored in a 2dimensional array.
I got a few questions concering this part:
I suppose map.getValue(…) returns some kind of integer where 0 means “not blocked”. Am I right? And why are there 4 parameters?
I have to check the results of path to find out why the coordinates are messed up.
I also have another problem to solve. Because my walls are not as big as my tiles (instead the walls are BETWEEN the tiles) I have to write my own collision-Method that handles tile transitions…havin an idea already, but first I need to fix up the other problems. Some help would be appreciated 
[quote]Great, it runs or I should say it stops now. But somehow the coordinates that are stored in the “path” ArrayList are messed up a bit (my character is moving strangely, jumping around)
To make it easy I tested on an map without borders and walls. My map is a simple tilemap stored in a 2dimensional array.
[/quote]
That’s most likely the problem. The heuristic I use is designed for mazes. It doesn’t fare so well on open spaces.
[quote]I suppose map.getValue(…) returns some kind of integer where 0 means “not blocked”. Am I right? And why are there 4 parameters?
[/quote]
Sorry, that’s from the CollisionMap class of my GAGE2D library. Just replace that with something that gets the value of a given cell, where 0 means empty and non-zero means impassable.
[quote]I also have another problem to solve. Because my walls are not as big as my tiles (instead the walls are BETWEEN the tiles) I have to write my own collision-Method that handles tile transitions…havin an idea already, but first I need to fix up the other problems. Some help would be appreciated
[/quote]
That’s a little tricker. Myself, I used 16x16 cells, where players were 32x32. That’s the reason for the set of getValue() calls. If you aren’t going to do that, then you can remove the getValue() stuff.