Support for 3D grids

[AdamJamesNaylor]

I noticed in your previous versions of this library that it supported 3D pathing.
Is that something you are considering for this version?

If not, I'm wondering if it's something I could 'fake' by connecting 2D grids in layers and adding sensible costings between them. But not sure how best to achieve that?

[roy-t]

Hey Adam,

I'm not planning on adding 3D pathing since it adds a lot of computation complexity really fast. For example a 10x10 grid has 100 cells to check (worst case) while a 10x10x10 grid already has a 1000 cells to check (worst case again). But if you really need A* path finding in 3D, the algorithm is exactly the same. All you have to do is expand the grid into 3d, add a third dimensions to the movement patterns and expand the heuristic here

AStar/Roy-T.AStar/PathFinder.cs

Line 159 in 8a3c6ac

private static float ManhattanDistance(Position p0, Position p1)

to also account for the 3rd dimension.

So I think its easier to fork this library than trying to fake it. However in some scenarios faking it would also be a good idea. For example if your 3D map is a map of a house. Where each floor is 2D grid and there are only a few place where you can go up or down (at the stair cases). In that case you could use this library to path from the current position to a stair case.

[AdamJamesNaylor]

Thanks for the quick reply (and great work on the library).

I'll certainly look into making the modification myself.
As for the faking option, the grids will need to support layouts as complex as this: https://www.reddit.com/r/starcitizen/comments/9wqv0r/lorville_map/
I certainly think there is a way to logically simplify the grid so that it works. Perhaps by scaling sections and modifying the costings so that it works?

[roy-t]

I think you could make that work with 7 2D grids and a few staircases :)

[roy-t]

Closed, No more actions needed