Procedural Voxel/Cube Wold Pathfinding (no colliders)

General
#1

Hello,
I am using a new procedural voxel/cube system (like Minecraft) called VoxelPlay and am trying to find the best solution for pathfinding given that the system doesn’t use colliders for each cube. Actually, what it does is only toggle on the colliders within a small distance from you (a 3x3x3 cube around the player.).

I am trying to adapt the mechanics of a 2-d turn-based tactical grid/tile game I have been working on into a 3-d voxel style. I had been using a grid graph, and units moved one cell at a time (1cell = 1 unit) on their turn. I hadn’t been using colliders then either, but the maps were a set width and height, so I would manually set each node to walkable/non-walkable during level generation. If a tile changed, I would toggle that node accordingly.

In the new scenario, the character is moving over very large areas which vary on the y-axis. Because there aren’t full colliders per cube, I can’t use a layered grid graph and scan. My alternative approach was to use the point graph. I made a pool of empty gameObjects(nodes) and positioned one on the surface of each cube within N distance from the player (their API includes a method to find the Y position for the highest cube that falls directly below a given Vector3). This works, but it takes about 500ms altogether with placing each node (~100 nodes) and generating connections (the reported Astar scan time is small ~7ms). This won’t work because I need to refresh once I move a certain distance away (every few units I move I get a 500ms freeze).

I am trying to brainstorm the best way to make this work. My thoughts so far:

  1. Manually setting the nodes for the layered grid graph?
  2. Instead of repositioning all empty gameobjects, only move a row of them from the back to the front (stratify as I move) and rescan the point graph?
  3. Add new points and selectively update the point graph, only occasionally wiping all points and starting anew.

Sorry for the deluge of text. Any ideas or suggestions? If I can provide an array of Vector3’s where a node should be, what is the most efficient way to manage this?

Thanks

#2

Hi

If you have the whole voxel data, maybe it is possible for you to modify the LayerGridGraph.SampleCell method? The layered grid graph gets all information about the rest of the world using physics in that method.