Binary Heaps Pathfinding

Unity Engine
1

Hey all,

So my pathfinding code isn’t fast enough and so I optimized as much as I could, and went to our trusty friend Google to see what else I could do when I happened upon Binary Heaps… again. And so, I decided to give it another shot. First I tried creating a separate script just dedicated to binary heaps just to see if I could get it to work. And I did, which was great. So then I just translated the script over to my Pathfinding code and…

…didn’t turn out so well. Now through debugging, I noticed that the binary heaps were working except for a little problem. In the function that adds the adjacent nodes to the open list, it adds all of the adjacent nodes at the exact same time, so since the binary heap requires that the added node be compared with the f-costs of the existing nodes, it couldn’t possibly work since they all get inserted at the same time.

Well, why they’re being inserted at the same time is beyond me since they’re all sequential and come after one another so technically, some should be inserted first, before the others. But for whatever reason, they all get inserted at the same time (I used Debug.Break() to stop the code whenever ONE node was added to the open list and when I checked the open list, ALL of the nodes had been inserted, and thus, were out of order). So not sure what’s going wrong here, but here’s the basic of code:

Find Adjacent Nodes

	if(column > 0){
			if(row < nodes[column-1].nodeCount){
				Node left = nodes[column-1].nodes[row];
				if(left.node.gameObject.layer.Equals(0)  !closedTransforms.Contains(left.node)){
					if(!open.Contains(left)){
						BinaryInsertion(left); //Left
						Debug.Break();
						left.nodeParent = current;
						left.g = left.nodeParent.g + 10;
						left.h = Mathf.RoundToInt((end.position - left.node.position).sqrMagnitude);
						left.f = left.g + left.h;
					}else{
						if(current.g + 10 < left.g){
							left.g = current.g + 10;
							left.f = left.g + left.h;
							left.nodeParent = current;
						}
					}
				}
			}

This code finds which nodes are adjacent to the current node. This code is duplicated a couple times so that it finds nodes on all sides of the node, not just on the left. So like this:

    if(column > 0){
			if(row < nodes[column-1].nodeCount){
				Node left = nodes[column-1].nodes[row];
				if(left.node.gameObject.layer.Equals(0)  !closedTransforms.Contains(left.node)){
					if(!open.Contains(left)){
						BinaryInsertion(left); //Left
						Debug.Break();
						left.nodeParent = current;
						left.g = left.nodeParent.g + 10;
						left.h = Mathf.RoundToInt((end.position - left.node.position).sqrMagnitude);
						left.f = left.g + left.h;
					}else{
						if(current.g + 10 < left.g){
							left.g = current.g + 10;
							left.f = left.g + left.h;
							left.nodeParent = current;
						}
					}
				}
			}
			if(row > 0  row < nodes[column-1].nodeCount){
				Node upLeft = nodes[column-1].nodes[row-1];
				if(upLeft.node.gameObject.layer.Equals(0)  !closedTransforms.Contains(upLeft.node)){
					if(!open.Contains(upLeft)){
						BinaryInsertion(upLeft); //Up-Left
						Debug.Break();
						upLeft.nodeParent = current;
						upLeft.g = upLeft.nodeParent.g + 14;
						upLeft.h = Mathf.RoundToInt((end.position - upLeft.node.position).sqrMagnitude);
						upLeft.f = upLeft.g + upLeft.h;
					}else{
						if(current.g + 10 < upLeft.g){
							upLeft.g = current.g + 10;
							upLeft.f = upLeft.g + upLeft.h;
							upLeft.nodeParent = current;
						}
					}
				}
			}
		}

…but a few more. So as you see, the code breaks after each node insertion which means that if it found that the left node was adjacent, then the entire code should stop before the rest of the comparisons execute. But, when I check, all of the nodes have been inserted. So not sure what to do here.

I don’t know if this will help at all but this is the BinaryInsertion() code:

	void BinaryInsertion (Node addedItem) {
				
		open.Add(addedItem);
		int aNodePos = open.IndexOf(addedItem);

		while(true){
			int comparer = Mathf.RoundToInt(aNodePos/2);
			if(open[aNodePos].f < open[comparer].f){
				open = Swap(aNodePos, comparer, open);
				aNodePos = comparer;
			}else{
				break;
			}
		}
	}

Thanks in advance!

2

Only thing i can up with is step debugging and target the list that the items get added to.

http://docs.unity3d.com/Documentation/Manual/Debugger.html

And set a debugdot on the variable or such so every time it gets affected program will stop.

3

Tried that as well, get the same results.

4

Also, is the method I’m using to find the adjacent nodes efficient?

5

These are the lines i use to look through all adjacent nodes.

 for (int i = y - 1; i < y + 2; i++)
 {
        for (int j = x - 1; j < x + 2; j++)
        {
               //Do all checks you need in here
        }
}
6

And make sure the first check is for ylargestY … continue, or you’ll get out-of-bounds errors

7

Ofcause i do that. Thats why i wrote do all checks here.

8

What does the code in the Swap function look like?