I've written an alternative pathfinding and movement module.
https://github.com/kaen/FlexibleMovement
https://github.com/kaen/FlexiblePathfinding
simple demo module: https://github.com/kaen/FlexibleMovementTestbed
Motivation
To understand why, you'll need to understand a few things about `Pathfinding` as it exists:
- It uses "offline" analysis (a worker thread analyzing the map to build a navgraph before paths can be served)
- This offline analysis gets partially invalidated when modifying the map (via setBlock) and the analysis must be performed again
- It assumes a fixed 1x2x1 character size
- It enforces a limited set of movement modes (jumping, walking)
Because of these limitations, here are some examples of things you can't implement with that pathfinder:
- Fish
- Birds
- Spiders
- Moles
- Dragons
- Giants
- Ghosts
The goal of this new pathfinder is to support all of these, and to expose a framework for implementing more movement types I didn't think of.
Construction
The pathfinding algorithm is based on 'Jump Point Search'. I found this to be
a good candidate for pathing through largely unobstructed fields while flying,
and it degrades to A* even in the worst case. It uses 100% "online" searching,
so all paths are found on the fly. There's a limited amount of caching done
within each search.
Different movement modes are implemented by different "plugins". There are two
types of plugins: movement, and pathfinding. One for each module. They're
pretty simple to write, and you can write your own and include them in your
own module without modifying the original FlexiblePathfinding module.
Currently I've implemented the following plugins:
Walking
Leaping
Swimming
Flying
Free Movement (Ghosting)
The following are also planned:
Climbing
Digging/Destroying
Testing
Both modules have very complete test coverage. The pathfinding module has a
robust suite of very fast unit tests. The movement plugin uses
ModuleTestingEnvironment to run full (and very slow) integration tests. It
actually moves characters through a real world in the actual engine to verify
everything works end-to-end.
It even has ASCII art
Status
Currently it is "unstable". The public interfaces are still very much subject
to change, especially as modifications are made to implement the remaining
movement types. However I definitely encourage experimentation, feature
requests, and feedback.
More information will be added to the README on github.
https://github.com/kaen/FlexibleMovement
https://github.com/kaen/FlexiblePathfinding
simple demo module: https://github.com/kaen/FlexibleMovementTestbed
Motivation
To understand why, you'll need to understand a few things about `Pathfinding` as it exists:
- It uses "offline" analysis (a worker thread analyzing the map to build a navgraph before paths can be served)
- This offline analysis gets partially invalidated when modifying the map (via setBlock) and the analysis must be performed again
- It assumes a fixed 1x2x1 character size
- It enforces a limited set of movement modes (jumping, walking)
Because of these limitations, here are some examples of things you can't implement with that pathfinder:
- Fish
- Birds
- Spiders
- Moles
- Dragons
- Giants
- Ghosts
The goal of this new pathfinder is to support all of these, and to expose a framework for implementing more movement types I didn't think of.
Construction
The pathfinding algorithm is based on 'Jump Point Search'. I found this to be
a good candidate for pathing through largely unobstructed fields while flying,
and it degrades to A* even in the worst case. It uses 100% "online" searching,
so all paths are found on the fly. There's a limited amount of caching done
within each search.
Different movement modes are implemented by different "plugins". There are two
types of plugins: movement, and pathfinding. One for each module. They're
pretty simple to write, and you can write your own and include them in your
own module without modifying the original FlexiblePathfinding module.
Currently I've implemented the following plugins:
Walking
Leaping
Swimming
Flying
Free Movement (Ghosting)
The following are also planned:
Climbing
Digging/Destroying
Testing
Both modules have very complete test coverage. The pathfinding module has a
robust suite of very fast unit tests. The movement plugin uses
ModuleTestingEnvironment to run full (and very slow) integration tests. It
actually moves characters through a real world in the actual engine to verify
everything works end-to-end.
It even has ASCII art
Status
Currently it is "unstable". The public interfaces are still very much subject
to change, especially as modifications are made to implement the remaining
movement types. However I definitely encourage experimentation, feature
requests, and feedback.
More information will be added to the README on github.
