A* Pathfinding

Newbie & Debugging Questions
#1

Hello evryone,

I was couple of days ago working on the Villagers-system. For example: I made a villager that is going to chop a tree and then going back to his home. But for this I needed first some sort of pathfinding. I tried to do something with this tutorial:
A* pathfinding tutorial.
So I coded in what he said (atleast how I think it must be):
[spoiler]

public class FindPath {
	private boolean isFindingPath = false;
	private List<Point> openList = new ArrayList<Point>();
	private List<Point> closedList = new ArrayList<Point>();
	private List<Point> path = new ArrayList<Point>();
	
	public List<Point> findPath(Point start, Point end) {
		isFindingPath = true;

		openList.clear();
		closedList.clear();
		path.clear();
    	
		checkNodesAroundPoint(start);
    	closedList.add(start);
    	closedList.add(searchLowestF(start, end));
    	
    	while(isFindingPath){
			checkNodesAroundPoint(searchLowestF(start, end));
	    	closedList.add(searchLowestF(start, end));
    	}
    	for (Point p : closedList) {
    		Game.level.alterTile((int)p.getX(), (int)p.getY(), Tile.POSIONGRASS);
    	}
    	
    	return path;
	}
	
	public void checkNodesAroundPoint(Point search){
    	for(int x = (int)search.getX() - 1; x <= (int)search.getX() + 1; x++){
        	for(int y = (int)search.getY() - 1; y <= (int)search.getY() + 1; y++){
        		if(!openList.contains(new Point(x,y))){
	        		if(Game.level.isTileWalkable(x, y)){
	        			openList.add(new Point(x,y));
	        			Game.level.alterTile(x, y, Tile.ROCK);
	        		}
        		}
        	}
    	}
	}
	
	public Point searchLowestF(Point start, Point end){
		Point lowestF = new Point(10, 10);
		int lowestFInList = -1;
		int g = 0;
		int h = 0;
		int f = 0;
		
		for (Point p : openList) {
			if(p.getX() == start.getX() || p.getY() == start.getY()){
				g = 10;
			} else {
				g = 14;
			}
			if(p.getX() <= end.getX() && p.getY() <= end.getY()){
				h = (((int)end.getX() - (int)p.getX()) + ((int)end.getY() - (int)p.getY()))* 10;
			} else if(p.getX() > end.getX() && p.getY() <= end.getY()){
				h = (((int)p.getX() - (int)end.getX()) + ((int)end.getY() - (int)p.getY()))* 10;
			} else if(p.getX() <= end.getX() && p.getY() > end.getY()){
				h = (((int)end.getX() - (int)p.getX()) + ((int)p.getY() - (int)end.getY()))* 10;
			} else if(p.getX() > end.getX() && p.getY() > end.getY()){
				h = (((int)p.getX() - (int)end.getX()) + ((int)p.getY() - (int)end.getY()))* 10;
			}
			
			if(h == 0){
				isFindingPath = false;
			}
			
			f = g + h;
			
			if(lowestFInList == -1){
				lowestFInList = f;
				lowestF = p;
			} else if(f < lowestFInList){
				lowestFInList = f;
				lowestF = p;
			}			
		}
		return lowestF;
	}
}

[/spoiler]
I wrote the code myself, only I think I’ve done many things wrong but atleast I tried it.

The things I had no idea to do was how you can see wich “g” it is (for diagonal 14 and for horizontal, vertical 10.)
and how you can return the good path. (I am now altering the tiles to see what the code is actually doing.)

If someone can explain it to me, how I can reach my 2 goals, then tell it! Don’t send the code if you can explain it. I am still learning java, by writing and thinking myself I learn more then copying other peoples work.

Already thanks!
-RoseSlayer

#2

ArrayList is the wrong data structure to use: people may talk about “open list” and “closed list”, but you should be using a priority queue to represent the open list, and probably HashSet for the closed list.

But more importantly, you don’t use closedList for anything, so I expect that your main loop never terminates. No point should ever be in both the open and the closed list.

#3

The second part I was already thinking of, the game was just stuck because he is repeating the same Point, the whole time. so I made an extra void:

	private void changeToClosedList(Point change){
		closedList.add(change);
    	openList.remove(change);
	}

But the code sometimes crashes. It is then making so much Points in closedList (and it isn’t making anymore points in openList). after a couple of seconds it is at 1.400.000 Points in the closedList. But still exactly the same amount in openList. I made a small screenshot so you can see what’s wrong:


http://img163.imageshack.us/img163/3049/4ft.png

The code.
(I now got somesort of the g-part, and that the code isn’t shortcutting around corners.)

in the right upper corner there is a minimap on what’s happening. the gray colour is openList, the purple colour is closedList and the white colour is an unwalkableTile.

If anyone of you can see what I did wrong in my code, just tell me!

@pjt33, I will research a little bit about HashSset and Priority queue when I am done with like this (slower, not the best) script. If it is working, I can always make it perform better etc.

Thanks for your help
-RoseSlayer.

#4

Did you also change checkNodesAroundPoint to not add a point to the open list if it’s in the closed list?

#5

The way I managed to implement A* pathfinding into my game was, I would get the tile the player is currently on, have an array of tiles that contains all the tiles (not including un-walkable tiles)adjacent to the tile the player was current on. I then calculated (for each tile around the player) how many ‘moves’ it would take in total to move from the current tile to the target tile. From that I added the cost of moving from the current tile to the tile I’m currently looking at (I used a similar method to that of that article everyone always seems to link people to :P), once I found the tile with the lowest cost I simply moved the player/npc to that tile and simply repeated this process until I was on the target tile. It worked perfectly for what I wanted, just spend a bit of time on it, don’t give up easily because that won’t get you anywhere, keep working at it and suddenly something will click in your brain and you will figure it out :slight_smile:

#6

Uhm… WOW, how could I miss that. I added that single if-statement and the code works! The only thing I now need to do is: making a path from the Point end to the Point start on the closedList and return it.

Also a smart idea, but I think I will stick to the way I think it will work atm. When the game is about to finish (or when it has a huge performance drain) I will look at all my scripts and see what I can change to let it work faster and better.

[EDIT:]
I thaught by doing it backwards I just switch the openList to closedList and Point start to Point end. But it didn’t worked for some reason?