Support Forum

Binary Heap Size Really Large

Hi! This is the first time I had this error and I don’t know what caused this. What would be the possible causes for this? Thank you!

Could you provide some more context about your setup?

We are using Unity version 2019.3.14f1. It is a 2D game. We are using Grid Graph with small node size (see attached image for the setting).


This means that 1 tile = around 9 nodes (see attached image for reference).

Tile

We are also using the ABPath and AILerp for pathfinding, although we created custom scripts for each one to hold specific data that we want. We are using a custom traversal provider to get additional penalty costs for specific agents. We are also utilizing the IsPathPossible and AstarPath.GetNearest function to check if an agent can do the path before doing so. I don’t know if this is helpful but we also just recently upgraded our Unity version. Our previous version is 2019.3.1f1. Ever since we upgraded to 2019.3.14f1, we’ve been also getting this error.

But this particular error does not affect our game. I think this only happens every time we pause Unity Editor.

I think that’s all about it. Is this info enough?

Hi

Would you mind showing the code for your ITraversalProvider? You should ensure that it only outputs positive penalties. Negative penalties can cause underflow and weird things can happen then.

Hello
Here is the code of our GetTraversalCost in our custom ITraversalProvider. The useCanTraverse is always set to false right now.

As for the GetNodePenaltyForSettlements, here is the code for it.

As you can see it only returns 10000 or 0. Is it possibl because we are using a high penalty cost? Should we adjust it to a lower value. The thing is, when we tried lowering it, the agent does not avoid the settlements anymore.

Hmm. One thing I notice is that you seem to be accessing global objects inside that function.
Is it possible for the innerMap.worldPos (or some other accessed position) to change while the path is being calculated? Keep in mind that paths are calculated on a separate thread asynchronously. The GetTraversalCost should return a consistent value for the same node for each path request. If it changes during the calculation then bad things can happen since some assumptions are broken.

The innerMap.worldPos does not change. It is set when the map is created (which is after loading the scene), as well as the other values being accessed in that code. We are also having a rough time replicating the error, because it does not happen every time. But the 1 thing we are almost certain is that it happens when the agent’s path is very long. But we are still not sure if this is really the culprit. I also encountered this error 1 time, when I put the agent at the edge of the map “Probable infinite loop. Over 1,000,000 nodes searched”. But I also couldn’t replicate this. Are these two connected somehow?

What about IsPartOfHumanElevenSettlement() can that change?
Do you get the error if you for example always return 10000?

Yes, the IsPartOfHumanElevenSettlement() can change. But its value is only if the tile has a settlement or not, so it’s either null or has a value. Yes, I still get the error if the additional penalty is always 10000. But the error is “Probable infinite loop. Over 1,000,000 nodes searched”. Is it somehow connected to the Binary Heap Size problem? And I already found a way to replicate the 1,000,000 node search error.

Is it because my graph is too big and has too many nodes?

If that changes at the same time as path is being calculated then it could possibly cause the error you are seeing since the method would not return a consistent result.

I don’t think so… Your graph doesn’t even have 1000000 nodes.
Are you manipulating the node connections of the graph in any way?

I’m guessing you do not get this error if you just return 0?

The error: “Probable infinite loop. Over 1,000,000 nodes searched” happens even if the penalty is 0. I also tried it with no traversal cost whatsoever, meaning the GetNodePenaltyForSettlements function is not being called. It still happens, the over 1,000,000 nodes search. It happens if I set my agent so far away from the destination. I attached a screenshot of my graph.

Below is the overview of the graph. Those blue squares that you are seeing are not the nodes.

These are the nodes. Those small blue squares inside the big blue squares are the nodes.

But until now I could not replicate the Binary Heap problem. Only the 1,000,000 nodes search.

Hmmm… I cannot replicate this at all. I tried with a 500x500 grid graph (larger than yours) and everything works with no errors there.
Which version of the package are you using?

4.2.2 Pro version. But my node size is only 0.3. So does that mean that the number of nodes in my graph is higher than yours?

No, your graph is 396x466 nodes which is less than 500x500 nodes.

Do you think you could upgrade to the latest version of the package? I don’t think anything related to this has changed, but 4.2.2 is about 2 years old at this point so it is possible that some bugs have been fixed.

I checked. Around 441 nodes are inside the large blue squares, so if I have around 660 large blue squares in this map, that means I only have around 300,000 nodes.

Alright, I’ll try upgrading.

Hi! Upgrading worked. I no longer get the 1,000,000 searched nodes error, but since I still couldn’t replicate the binary heap size error, I couldn’t tell if it is also fixed when I upgraded. I will post updates in this thread if it still happens. Thank you!

Hi! Upon further testing, it appears that the 1,000,000 searched nodes still persists. Upon my first few tries, it did not happen but right now it happens, there are only times that it does not happen. I even removed my custom traversal provider and it still persists. I also tried to remove my custom ABPath and just used the seeker.StartPath(start, end). It still persists depending on how far I put my agent. Sometimes, the error pops up, sometimes Unity freezes and I have to close it using the task manager. Is there something wrong with my settings? Attached here are my settings after the upgrade. Also in the Optimization part, all sections are unchecked.