A* Pathfinding Project

4.0.6 AstarWorkItem


#1

I’ve just upgraded to 4.0 and am having trouble with how to implement work items, what with the changes. Specifically, your example on runtime updates using work items uses the deprecated floodfill. It is unclear to me what I should do inside the IWorkItemContext.QueueFloodFill() method when I instantiate my own WorkItemProcessor : IWorkItemContext. Please explain and I respectfully request you add examples for 4.0.

Edit: I tried using your WorkItemProcessor implementation but its private so I assume I have to create my own, but what do I do inside the required Interface methods?


#2

Hi

Good catch. I need to fix that link.
There is an up-to-date example in the dosc for the AddWorkItem method however: https://www.arongranberg.com/astar/docs/class_astar_path.php#afbf8b247f7dd33c59c8bb90e6752c513

I will paste it here to save a click (this one is actually slightly more updated than the one in the current documentation)

AstarPath.active.AddWorkItem(new AstarWorkItem(ctx => {
	var node = AstarPath.active.GetNearest(transform.position).node;
	node.Walkable = false;
	ctx.QueueFloodFill();
}));

Also. Last week I started to move all code snippets in the documentation to actual code files instead of having been included in the documentation files. It will look almost identical in the online documentation but the benefit is that the code snippets can be checked for compile errors and warnings and they can also be formatted to a consistent style. I have already found a few typos in some snippets.


#3

Thanks for the clarification.

Now I’m finding something has changed with the optimizeForSparseGraphs lookup table. I’m using AddToLookup(node), aka lookupTree.Add(node) and I’ve confirmed that each node added is a separate instance.

When I use the nodes in the lookup tree to start making connections, I get the candidateNodes with lookupTree.GetInRange(nodePosition, sqrdMaxDistance, buffer) which fills the empty buffer I provide. However, every candidateNode that is returned in the buffer is the same node instance as the node whose position was used for nodePosition. Since every candidateNode for a connection is the same instance as the node I want to connect to, no connection is made.

This worked in my previous 3.8.6 implementation, but something seems to have changed in the lookup tree.


#4

Huh. That seems odd. I have looked over the code but I cannot find anything that looks off so far.
You verified that you did not add any nodes multiple times, right?

Do you think you could post the complete code that you are using?

You are right that the lookup tree implementation has changed. It has been completely rewritten as a KDTree instead of some kind of 3D-cell-based structure. It should be a lot faster for most uses cases (especially when the closest node is far away).


#5

My Bad: Did a bit more investigation into GetInRange. I was using maxDistance^2 for the GetInRange sqrDistance value when I should have been using (maxDistance * Int3.Precision)^2. Accordingly, the only node in range was always limited to the original node.

Probably worth a mention in the method’s parameter comments.

Follow-on: During runtime, if I make existing nodes unwalkable or add additional walkable nodes, do I have to rebuild the lookup table? Your notes only mention rebuilding when you move nodes.


#6

Ah. I see.
I have added a comment about that in the docs in my dev version now.

The tree does not care about if nodes are walkable or not so you do not have to update the lookup if you change the walkability.
If you add another node then it should automatically update the lookup tree (at least if you are using the PointGraph.AddNode method, but you seem to be doing some more in depth stuff with the point graph so I am not sure if you are using it).


#7

You are correct that I was using my own method to add nodes rather than AddNode(). However, I’ve now modified it to use AddNode which should make it easier to maintain.

IAfter doing so, I think I see an issue in PointGenerator. AddNode increases the size of the nodes array when it needs to which means nodes.Length can be larger than nodeCount. However, you use nodes.Length when you iterate through nodes to make connections. Doesn’t this approach attempt to access a node that is not present in the array, aka shouldn’t you be using nodeCount instead?

In my own implementation derived from PointGenerator, I’m getting NREs when using nodes.Length to make connections as some of the nodes returned are not present. I can certainly fix this myself, but I’m unclear as to why you wouldn’t have seen this error before, so I must be missing something?


#8

I think the code that assumes that nodeCount == nodes.Length can only ever be called when scanning the graph and then it is known that nodeCount is in fact equal to nodes.Length (unless one has modified the PointGraph code). You are right however that for clarity it should use nodeCount and node nodes.Length. I have changed it in my dev version now.