Point Graph and Optimize for sparse graph

Now for my real question, now that I can post.

Optimize for sparse graph really helps my connection creation time, and I’m hoping it will reduce my graph update time too. However, I’m getting an exception when using it - it doesn’t like any point node already having a next assignment, aka already linked in a linked list. As I look at the code, I see no place where next will be nulled once assigned. The docs say call RebuildLookupTable, and it does clear the lookup table in prep for re-adding nodes, but it doesn’t null each node.next which I would expect it to do before calling AddNodeToLookup. Any insights?


Try the latest beta. I recently rewrote the implementation for that to reduce code size improve performance.
(I cannot guarantee that it is fixed, but I think it is likely).

I’ll give it a try soon but I can’t right now, what with all the other changes I’ve got underway.

Does nulling next make sense in the short term in RebuildNodeLookup()? Can you take a quick glance at that?

Yes, I think that makes sense.

That nulling change appears to have worked. Continuing on the ‘optimize for sparse graphs’ vein, can you explain your algorithm for selecting far fewer nodes to compare? I’ve spent some major time trying to derive it myself, but I must admit failure - its pretty arcane, albeit effective. I can clearly see its about finding neighboring nodes from the lookup and using those to look for connections, but how does the linked list play into this? aka What is the criteria for being a linked node?

When doing a Runtime Graph Update using a GUO, the time spent looking for changed connections in UpdateArea() is enormous O(n^2) as I have a lot of nodes, albeit sparsely populated in an enormous map. I’m thinking that rather than look for changed connections, why not just reconnect the nodes using MakeConnections() which uses ‘optimize for sparse graphs’? In my implementation, I really don’t care about whether the connection line segment intersects the GUO bounds. Is there any reason you can think of why that’s not a good idea? If I understood the ‘optimize’ algorithm I could answer this question myself.

Thanks for bearing with me.


In your version what it did was to divide the world into cells with a size of maxNodeDistance (I think…), and then it inserted all nodes into those cells. If multiple nodes were in the same cell, they would be stored as a linked list (using the .next field). When searching for a node, it would search the cells in an outward pattern. When connecting them, it could just check a few cells around each node.

In the newer version I rewrote it to use a self balancing KD-tree instead. That will also perform a lot better when searching for the nearest node to a point which is far away from all nodes (previously it would have to search a lot of empty cells).

Yeah, the UpdateArea code hasn’t been optimized to take that into account yet.
It’s a bit tricky since users may create arbitrary connections between the nodes that do not necessarily follow the same distance constraints.

I see it now. Thanks for the explanation.

Yes, as a user of point graphs, they could use a little love… :slight_smile:

I’ve changed from using the GraphUpdateObject to using individual WorkItems as its a bit clearer to me what I am doing. The WorkItems add nodes, change node walkability and reconnect all nodes when I add/subtract certain gameObjects. I’ve got a couple of questions about this approach.

Using the above approach, I don’t call UpdateGraphs(guo).

  1. Is there any reason now to do a floodfill following the workitems? aka is floodfill unique to GUOs or is it reqd any time you change anything in a node?
  2. Since I’m not using UpdateGraphs(), I never see IsAnyGraphUpdatesQueued = true. Makes sense. Is there any replacement for this with my approach, aka any way to ‘register’ I’m doing an update, just not with a GUO?
  3. Related to 2, the GraphUpdateComplete Callback no longer fires. Makes sense. Is there any replacement for this that would tell me when my ‘update’ is complete? I expect I will eventually want to replot my paths when I know the graph has changed.