Check out our latest project ✨ OpenChapter.io: free ebooks the way its meant to be 📖

Flight Navigation

An asset by RevolNoom
The page banner background of a mountain and forest
Flight Navigation hero image

Quick Information

0 ratings
Flight Navigation icon image
RevolNoom
Flight Navigation

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.

Supported Engine Version
4.2
Version String
1.1.0
License Version
MIT
Support Level
community
Modified Date
10 months ago
Git URL
Issue URL

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.)

README 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".

README 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)

README 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/

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.

Reviews

0 ratings

Your Rating

Headline must be at least 3 characters but not more than 50
Review must be at least 5 characters but not more than 500
Please sign in to add a review

Quick Information

0 ratings
Flight Navigation icon image
RevolNoom
Flight Navigation

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.

Supported Engine Version
4.2
Version String
1.1.0
License Version
MIT
Support Level
community
Modified Date
10 months ago
Git URL
Issue URL

Open Source

Released under the AGPLv3 license

Plug and Play

Browse assets directly from Godot

Community Driven

Created by developers for developers