2d World Wrapping

General Grid graph
#1

Hello! The AStar package is brilliant, but I’m coming up against a real challenge involving “stitching” the edges of my grid to the opposite edges. I’m using the free version, but perfectly happy purchasing the package if the best solution is only available with Pro. (I’ll probably purchase it either way to show support, but I digress…)

I’m making a 2d RTS game with maps of arbitrary sizes. This world repeats infinitely when panning the camera, and pathfinding should be able to navigate around the map edges as well. I actually came up with a “solution” very similar to the answer posted in Wrap paths around plane, but that answer is 5 years old (!) and I’m wondering if there’s a better way!

Ultimately, I’m using this to stitch together the edges of my world:

node.AddConnection(neighbor, 0);
neighbor.AddConnection(node, 0);

There’s still a a couple problems with my solution, and I’ve ordered them here from highest to lowest priority:

  1. The GridGraph doesn’t seem to understand areas connected to far edges. Calls to ABPath.Construct(from, to) will fail as expected when trying to navigate to these areas, but I can’t use PathUtilities.IsPathPossible when they’re all considered one area. This makes it problematic to narrow down a potentially large search space of in-area targets. See:


(You can see my extra connections overlayed on top of the standard ones here)

All of the areas in dark purple are considered the same, even though the single island that bridges all four corners is technically in a separate area. The nodes on that island are not reachable from the larger purple area (ABPath.Construct fails). I’ve tried making calls to FloodFill() and FloodFill(node) @ (0,0), but they silently fail to detect these separate areas.

  1. Disabling heuristics was the only way to get the units to accept the stitched paths. They will begrudgingly follow it if I make the area behind them unwalkable. I set a zero cost, but I can’t seem to get it to treat my AddConnection()s as neighboring nodes. It really wants to use (node1.position - node2.position), and since they are physically far away, that cost is calculated as being very high.

  2. I’ve had to implement my own “teleport” logic when a unit approaches one edge and intends to traverse to the other. I do this by looking ahead at path.vectorPath[currentWaypoint+1] to detect and big, suspiciously world-sized jumps in the X, or Y (or both) directions. Is there a better way?

I’m not exactly sure what NodeLink2 does - is that my answer?

I’m also willing to use proxy pathfinding geometry (torus, perhaps?) that exists separately from the scene entirely. I could write a translation layer that converts Game (X,Y) to Clever Pathfinding Shape (X, Z)… but I didn’t want to commit to that just yet.

Thank you for any help you can give!

#2

Hi

That’s strange… Which version are you using?
Could you try adding only some connections until you find which one is causing the two separate areas to be joined together?

(2) About heuristics. Yeah. You need to disable that for it to work. Making those long connections invalidates some assumptions made by the A* algorithm (see https://en.wikipedia.org/wiki/Admissible_heuristic).

(3). Not really I think… That’s probably the easiest way to do it.

NodeLink2 will do some additional things. It will add a point graph and add two nodes to it (say C1 and C2) and position them at the endpoints of the link. Now lets say the closest nodes in the grid graph to the start and end points of the link were A and B, then it will connect the nodes as A <-> C1 <-> C2 <-> B. This is done so that agents can know the exact endpoints of the link, and also more reliably detect that it is actually a link.
I don’t think this is something you should do however, it will probably just make things more complicated.

#3

The connections all appeared to be correct when drawing them with debugging lines. I was using 4.1.16 but upgraded to 4.2.2 to see if that would help. And it did help! Here’s an updated screenshot with a … slightly more complicated test :slight_smile:

Everything in pink, green and blue are contiguous areas. I think if I combine this with PathUtilities.BFS(node, radius) I can accomplish what I was hoping for! (I can live without using a heuristic, and I can manage my own teleport code…) There’s just one more small problem…

When loading a level, the GridGraph only seems to correctly detect the areas in this maze test level once. Subsequent loading of the same data makes the areas in the corners (teal) appear connected to the main maze section (pink). They would also behave strangely when first making grid updates in the corner areas:

Note the orphaned teal area inside the purple area. They would appear connected until I made a meaningless graph update (setting an already-walkable node to walkable again), then appear disconnected but with the glitch. Removing the glitch re-connected the areas.

However! I noticed that loading levels of different sizes made the area detection work correctly, so now I have this in the middle of my level reload code:

// HACK: Resizing workaround to force pathfinding to rebuild the graph
Grid = AstarPath.active.data.gridGraph;
Grid.SetDimensions(1, 1, 1.0f);
AstarPath.active.Scan();

// Resize the GridGraph as normal
Grid.SetDimensions(Width, Height, 1.0f);
AstarPath.active.Scan();

And that seems to successfully trigger… something :slight_smile: My test levels with Very Complicated Areas™ now load correctly every time! Any thoughts on the area glitch + resizing workaround?

I also noticed that my “custom” connections still show up with node.GetConnections() even when its far-side neighbors are unwalkable, but I’m not too worried about that as long as my levels work! Thank you very very much for… well, telling me to upgrade. Haha, and for putting so much work and improvements into the project!

#4

Hi

Yeah, connections are exactly what you set them to. However all code that uses the connections check (if appropriate) if the adjacent node is walkable. Grid graphs do as a performance optimization remove all grid-connections to unwalkable nodes (to avoid even having to access that memory just to see that the node is unwalkable).

Huh. That is odd. Would it be possible for you to make a simple test scene that shows this bug and that you could share with me?