Reconstruct A* path

Newbie & Debugging Questions
#1

Hey guys,

So I’ve made an implementation of an A* algorithm for my AI class, and the algo runs blazingly* fast, it has no trouble founding a path in a 256*256 grid, however the reconstructPath method I’ve made is slow and subject to run out of heap space. :frowning:

So the question is, how the heck can I improve this piece of code:


private static List<Node> reconstructPath(Node start, Node goal) {
	List<Node> path = new ArrayList<>();
	start.came_from = null; // Reset the came_from
	Node current = goal;

	while(current != null) {
		path.add(current);
		current = current.came_from;
	}

	return path;
}
  • That’s my claim, and I’m sticking with it!
#2

On a 256x256 grid, there is no way that piece of code can run out of heap space (as the longest possible path has 64K nodes), unless there is a bug (cyclic references).

#3

Hrmph, care to look at my code then? Because I’ve stared myself blind on it xD

Here’s the entire A* algo: http://pastebin.java-gaming.org/5a331617b43
The Node: http://pastebin.java-gaming.org/a33117b7340
And my super epic awesome cough Runner: http://pastebin.java-gaming.org/3311b837044

Edit:
Actually, nevermind. I just fixed it myself. xD Or at least it isn’t crashing anymore. Added “neighbor.came_from = null;” inside the if statement on line 46. xD

Though other feedback would be welcome. The assignment is to make pathfinding(what I’ve done now) and then be able to easily change it to be able to perform “logical deduction in propositional logic on clause form.” I’m hoping that all I have to change is the Node, the way I’ve done it. :slight_smile:

Edit edit:
Actually, I still think there’s a bug in it, because it shows waaay too many nodes as being visited, compared to what I’d expect of A*. :confused:

Edit edit edit:
There is a bug in it. :frowning: Searching for a path from (0,2) to (0,7) in a grid of 20x20, it doesn’t find the shortest path. :frowning: Time to debug.

#4

There are three steps in debugging pathfinding and finding good heuristics:

  • Visualize it
  • Render it
  • Draw it
#5

Well, I fixed the bug that made it choose a weird route. But It’s searching way to many nodes, compared to what it should. I think I might’ve screwed up in the compareTo function, in the node, and that causes the ordering if the TreeSet to be weird.

#6

If you render every step in the path-finding algorithm, you’ll see what happens, and when/why it touches specific nodes.

#7

Hm, I fixed it when changing the openSet from a TreeSet to an ArrayList, and then doing Collections.sort(openSet).

Though the runtime likely is worse, because it’s O(n) to use contains, vs. O(log(n)) in the TreeSet.

But I suppose the conclusion is that I seem to have no clue of how to use TreeSet. xD

#8

Here’s your problem:


class Node {
   @Override
   public int compareTo(Node node) {
      return this.f - node.f;
   }
}

If compareTo returns zero, the Node is considered to be equal to the other node, as per the spec of Comparable. Never return zero, unless this.equals(that).

#9

Hm, then what should I return if their distance is the same?

#10

Literally anything but zero.

#11

I’ve tried that, but it still results in a lot more nodes being visited, compared to using an arraylist. :confused: And it’s kind of silly that it searches in the opposite direction of the goal, when it has the choice to search towards it.

#12

Well, I’m lost for a solution as to how to use a TreeSet in my algorithm.

Any suggestions on how to fix the issue would be awesome!

#13

If the value of ‘this.f’ changes after the node is inserted into the tree, it will break all logic.

#14

Well, I did try to remove the node, before updating the this.f value and then reinserting it, but the search pattern still searches in a diamond shape, far bigger than the box it should search.

Edit:

And I’m a complete and utter idiot. I removed the node and inserted it before i changed the f value… -.-