Flight Navigation
R

Publisher

revolnoom

Flight Navigation

3D
Flight Navigation Voxel Pathfinding A* 3D Collision Exploration

This package provides flying/swimming navigation in free 3D space. It builds a Sparse Voxel Octree representing the solid/empty state, and then applies Greedy A* algorithm for path finding. Currently in development. Please see README.md for a more detailed list of features and limitations, as well as how to use.

Download Latest (1.1.0)
Source Repository

Godot Flight Navigation 3D

/In development. Buggy?/

This package provides flying/swimming navigation in free 3D space. It builds a Sparse Voxel Octree representing the solid/empty state, and then applies Greedy A* algorithm for path finding.

General Information

  • Tested on Godot versions:
    • v4.2.1.stable.official.b09f793f5

Features

  • Multi-threading voxelization on CPU

  • Upto 9 layers of voxelization (512 x 512 x 512) on 8GB RAM

  • Works with all primitive collision shapes and some complex shapes:

    • BoxShape3D
    • SphereShape3D
    • CapsuleShape3D
    • CylinderShape3D
    • ConcavePolygonShape3D
    • ConvexPolygonShape3D

How To Use

  • Set up your scene with collision objects you want to voxelize, and reserve a collision layer for them. (Note that all voxelize targets should be objects that never move, because of "No runtime update" limitation. See below.)

Collision objects setup

  • Create a FlightNavigation3D, set its collision mask to include the voxelize objects' mask, and set $Extent.shape.size property. For the size property, you can do it either in code or in editor (recommended) by right-click FlightNavigation3D object > Enable "Editable children".

FlightNavigation3D object setup

  • Call FlightNavigation3D.voxelize() or voxelize_async() with the depth you want.

    • Two voxelize methods must not be called at your root scene's _ready(), because they need a physic frame or two to detect all overlapping bodies and areas.

    • Voxelization might take a long time depending on host machine. It's recommended to use voxelize_async(), which uses multithreading at low priority.

  • Call find_path() anytime to get a connected path between two points inside FlightNavigation3D space. Here's an illustration of the result. The boxes are drawn with debug methods FlightNavigation3D.draw_svolink_box() (draw an arbitrary box) and FlightNavigation3D.draw_debug_boxes() (draw all leaf voxels of the SVO)

Result illustration

Warning

To be able to voxelize a map right in the editor, PhysicsServer3D is set active for the FlightNavigation3D to detect overlapping bodies and areas. It could cause you editor-wide problems, like objects set afloat in the scene suddenly drop to the ground.

There are some ways you can try to work around this problem:

  • Make sure you don't save the ill-affected scenes if it happens.
  • Try to open only the scene of map you need to voxelize and nothing else.

Write your own pathfinding algorithm

/TODO/

Limitations

  • No runtime update

By design, the SVO packs data tightly to save space and quick neighbor lookup. Thus, addition/removal/transformation of objects inside the navigation space cannot be updated trivially, and you must re-voxelize the space every time.

  • No inside/outside state.

The SVO doesn't store information or provide a way to figure out whether a position is inside an object. This could be a future improvement.

Future Improvements

  • Save/load SVO into Resource file and voxelize in the editor. (UI is ready, but implementation for ResourceFormatSaver/Loader encounters error).

  • Implement some tips and tricks from paper to speedup voxelization.

  • GPU voxelization (? uhhhh I'll figure this out later).

Credits

Modifications From Papers

/TODO/