Implementation FlexibleMovement and FlexiblePathfinding

Discussion in 'Modules' started by kaen, Sep 11, 2017.

  1. kaen

    kaen The Bug Whisperer

    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.
    • Winner Winner x 2
  2. manu3d

    manu3d Pixel Forge Artisan

    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...
    • Agree Agree x 1
  3. kaen

    kaen The Bug Whisperer

    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/
  4. Cervator

    Cervator Project Lead and Community Wizard Staff Member

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

Share This Page