AStar Problem

Newbie & Debugging Questions
#1

Hello, I made a small game awhile back, and I had an A-Star algorithm used for making the NPC’s follow a particular path. This algorithm worked fine until recently, I’m not exactly sure what i’ve touched. But it never seems to work anymore. I have tried to set up logging so that I can debug it, but I can’t seem to figure out what the problem is. This is the output of the log

With 0 = Unwalkable 1 = Walkable

My code is as follows:

Pathfinder.java http://pastebin.com/KL43FbuD
NodeList.java http://pastebin.com/dqhuTDye
Node.java http://pastebin.com/BZqJgY9j
Movement.java http://pastebin.com/q5jUHJZ3
AStarMap.java http://pastebin.com/UF5h9Ux4

The method gets called like this:


Node startNode = new Node(npc.getX(), npc.getY());
Node endNode = new Node(8, 1); 
		
AStarMap loader = new AStarMap(map);
PathFinder pathMaker = new PathFinder(loader.getMap());
pathMaker.findPath(startNode, endNode);
		
pathMaker.displayPath();

No matter what start and end position it is, it always returns that same path.
There are no exceptions being thrown, there is just a problem with my code. I would be so greatful for any assistance.

#2

Ah, first: You’re missing a few chunks of code that we might need to see. Movement and whatever the main(String[] args) or whatever you’re using to call it is using.

Second: I’m betting that you’re not filling your open list correctly. It seems that you’ve either got a broken method (getSuccessors(…)) or that your iteration through the list returned is broken.


PathFinder.java Lines 53 & 54
if (movement == null)
    break;

That’s my suspect in this. I mean, it’s probably not what’s ending it, however if you need this in there to get your program to work, then you’re obviously having issues with things somewhere (Since there’s no way that movement can be null, unless you’re inserting a null value in there somewhere.

Ah, there could be other issues in there that I just can’t see, 'cause of the way you code (Blame me at this point, I’m exhausted). However, it’s considered bad practice to use ‘cut-and-paste’ coding. This is a quick readability rewrite, and one that’ll let you ensure that you’re not accidentally creating your Movement objects incorrectly.


public ArrayList<Movement> getSuccessors(Node currentNode) {
	ArrayList<Movement> movements = new ArrayList();
	int x = currentNode.xPosition;
	int y = currentNode.yPosition;
	if(isIn(x - 1, y)) { // LEFT
		movements.add(getMovement(nodeMap[y][x - 1], currentNode));
	}
	if(isIn(x - 1, y - 1)) { // TOP LEFT
		movements.add(getMovement(nodeMap[y - 1][x - 1], currentNode));
	}
	/*
	* ...
	* Enter the other six directions
	* ...
	*/
	return movements;
}
	
public Movement getMovement(Node next, Node currentNode, boolean diagonal) {
	int g = currentNode.movementCost + diagonal ? COST_DIAG : COST_NORM;
	int heuristicDistance = calculateHeuristic(node);
	return new Movement(node, g, heuristicDistance)
}

public boolean isIn(int posX, int posY) {
	return posX >= 0 && posX < sizeX && posY >= 0 && posY < sizeY;
}
#3

Thankyou for the readability Advice. It made it easier to find what was wrong, there was a few places I had to fix up in the PathFinder class. One of them was in the getSuccessors methods, so thank you.

It was all really stupid mistakes that I overlooked haha

I really appreciate it :slight_smile: