Implementation FlexibleMovement and FlexiblePathfinding

kaen

The Bug Whisperer
Contributor
Architecture
Logistics
#1
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.
 

manu3d

Pixel Forge Artisan
Contributor
Architecture
#2
I just wanted to say 1) cooool! 2) the capacity to do testing by (repeatably) moving a character through a world is something that would be useful for benchmarking rendering performance - something to keep in mind.

Are those tests done in headless mode? Could they be done with a full client, with the user inputs disabled so that the player character just goes through the world on autopilot while the world is visible on screen? I don't want to change the topic of this thread though. I'm just connecting some dots here...
 

kaen

The Bug Whisperer
Contributor
Architecture
Logistics
#3
In theory, yes. In practice, ModuleTestingEnvironment needs a bugfix for testing with a connected client. It works in the isolated test suite within the MTE itself, however it bugs out when loading the Core module making testing real modules impossible atm.

Here's an example in the testing module:
https://github.com/Terasology/Modul...ogy/moduletestingenvironment/ExampleTest.java

It specifically includes logic to disable the renderer for the Client engines, so it should be possible to do this with a full client. I have not done any testing in this vein yet.

http://forum.terasology.org/threads...-testing-with-in-process-engine-objects.1884/
 

Cervator

Project Lead and Community Wizard
Contributor
Design
Logistics
SpecOps
#4
Still haven't had a chance to really dig into this one, but I did come up with what might be a variant move mode that would be interesting: ceiling walking ;)

Essentially regular walking, but on ceilings. Only able to slide "down" one block increments (or configurable / dynamic based on size, of course). Maybe some wall walking again. Unsure how that might mesh with climbing, could that perhaps simply be a subset?

Edit: As a special action while ceiling "walking" allow the creature a pounce attack on something below it. I may have something specific in mind here ... ;)