DigitalExtinction / Game

A 3D RTS game implemented in Rust.
https://de-game.org
GNU Affero General Public License v3.0
314 stars 25 forks source link

Implement pathfinding #12

Closed Indy2222 closed 2 years ago

Indy2222 commented 2 years ago

After #11 is implemented adapt it to proper object movement.

There are several requirements:

Research available algorithms. Plain A* won't work.

Indy2222 commented 2 years ago

After doing a bit more research, I decided to go with a version of NavMesh in the first iteration:

  1. compute rectangular bounding box around all static obstacles
  2. erode map boundaries & dilate the bounding boxes
  3. compute constrained Delaunay triangulation
  4. create edge visibility graph from -- edges which are part of the same triangle are neighbors in the graph
  5. build an R-tree for use in search for initial and target edges neighboring from/to points
  6. find shortest paths with a modified A* combined with gradual funnel algorithm