Released: Orestis 3D Pathfinding


#1

Navigation mesh generation inside the PlayCanvas editor in seconds and a 3D pathfinding runtime to animate any entity on a path. Get it here!

Easily create navigation zones, find paths and animate your entities on them. Play with it on our playground here!

Features:

  • Navigation mesh generation inside the PlayCanvas Editor using Recast, all settings are exposed to tweak.
  • The source .obj of each navigation mesh is added to your project. You can easily download and further edit it.
  • Parse any number of selected entities or even the whole scene.
  • Easily manage your pathfinding zones, simple API to switch active zone on runtime.
  • Pathfinding runtime API to find paths and animate entities on them.
  • THREE-Pathfinding is used as the pathfinding solver.

View the documentation here.

By subscribing to this product you get access to an editor extension that can easily generate navigation meshes inside the PlayCanvas editor.

In addition you get full source code access to all run-time scripts and the THREE-Pathfinding solver.

All navigation meshes generated are yours to keep, even after your subscription has ended.


#2

you are an abolute trooper churning out so many high quality assets


#3

Does it include Detour integration? Or just a navmesh query with the genreated navmesh object? How did you manage to run some RecastCLI thing remotely in the backend and auto-upload/drop the OBJ file into editor?

I currently run my RecastCLI OBj generation remotely from my Playcanvas runtime scene to localhost nodeJS server (on certain browsers requiring to run in http protocol and not https to connect to it) than manually upload the generated .obj file on hard-drive to editor.

It appears that the navmesh is generated from visual geometry itself and not from the collision components itself? Or a way to decide between the two? Or exclude certain entities in the scene graph from the static navmesh generation query via tagging?


#4

The navmesh is generated from the visible geometry that is passed to the extension. You can pass a single entity, a hierarchy of entities or your whole scene. All entities that are enabled at that instant will be used to generate the navmesh, so you can easily control what goes in and what not.

The navmesh is being generated on a remote server and the output obj is saved automatically in your project as an .obj (which you can also download separately and further edit it) using the PlayCanvas editor API.

Generation is very fast ( < 1s) so you can change your settings, regenerate and see the updated navmesh.

Regarding the pathfinding solver we are still doing R&D but most likely we won’t be using Detour as we plan in using a native JS solution.


#5

For path determination, I’m currently using https://github.com/Glidias/three-altern-pathfinding based off the THREE Pathfinding repository which delivers. THREE Pathfinding and Babylon pathfinding are both similiar in that they both use tri-polygon nodes for the navmesh graph instead of N-gons (which is what Detour uses.). Also, centroid to centroid based nodes might deliver sub-standard results compared to a midpoint edge-to-edge node structure, but so far i haven’t seen any notable 3D navmesh solver javascript library that uses midpoint-edge based nodes, short of modifying existing javscript codebases.

It’s going to be quite a lot of work doing everything that Detour had done for the crowd simulation (from nearly 2 decades ago) and dynamic obstacle navmesh-regeneration aspect (which typically uses tile caches and therefore requires recast tiles to be used instead for generation) . I do have a working playcanvas script that even does fast realtime navmesh cutting with moving dynamic convex obstacles hovering/moving over a navmesh, albeit because the mesh isn’t re-gegenerated/recalculated within tiles but temporarily cutting existing geometry, it might end up with less optimal graphs due to that. This does allow paths to be calculated around dynamic obstacles easily on the fly in real time, though.

When it comes to crowds like what Detour does,. local avoidance constrained within navmesh is one aspect from a general perspective, another aspect is (note: just an idea i thought off but have not proven) actually combining it with something like flowfields like in this paper when it comes to flocking a bunch of units across the funnel of navmesh polygons towards a given destination… http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.68.875&rep=rep1&type=pdf and then maybe using something like https://howtorts.github.io/ (but uses navmesh to define flowfields rather than grid…). (. Again, this is something that is veering more towards app-specific territory since not all apps would need crowd flocking within navmesh either.). To also implement something like that on a detour-crowd like scale, would also requiring managing of agents, their paths, and their destinations themselves, and thus a system must be set up like:
Managing groups of moving units within a stipulated navmesh path funnel also means that a crowd agent might end up being pushed out of the given funnel route towards his destination node (due to other forces like seperation/alignment) and finds himself “dislodged” into another new node outside of the funnel, he will have to retrieve from cache/recalculate+store in cache, a new flowfield starting branch path to the same destination from the new node he finds himself in. Thus, a structure of reusable flowfield branches (of diverging and converging flowfields) must be created. Purpose of flowfield caches is to ensure no duplicate navmesh polygon flowfields are duplicated unless they differ within each agent’s starting to ending location path context. Thus, a flowfield within a current node polygon is defined by it’s unique ID of: (From Node) to (Current Node) to (Next Node)" and the stipulated movement direction vectors at each vertex of the Current Node polygon in relation to From Node and Next Node. The flowfield force of the agent is defined by the barycentric weight of the agent’s location in relation to those directional vectors at each of the navmesh’s Current Node polygon vertices. I think combining local navmesh polygon flowfield forces (for the navmesh constraints) + local avoidance (to prevent agents from bunching up) might allow agents to flock fairly properly within a navmesh.


#6

Thanks @Glenn_Ko for your detailed reply and the links provided, much appreciated. It seems you have done a lot research and work in the subject.

We are using THREE Pathfinding in projects of ours and we find it adequate and performant for most basic pathfinding needs.

Initially with Orestis we plan to deploy a basic pathfinding library (find shortest path inside geometry) that is easy to setup and use in both desktop and mobile. So yes, no crowd simulation or dynamic obstacle avoidance.

When WASM really becomes a thing we sure want to explore a more complex solution and feature set (along with navmesh generation in the browser). This is a great example:
http://www.visualiser.fr/page.php?id=Crowd_simulation_EMSCRIPTEN_JS


#7

Btw, there is already a (rather old, but working nicely) EMScripten port of Recast+Detour on https://github.com/vincent/recast.js , but i couldn’t really get it to work on Playcanvas though. Expect a big JS file of course. I ran this on localhost and it runs smoothly, albeit the web demo framerate appears laggy for some unknown reason on my Chrome browser.

Currently, I’ve seen most other libraries (like Haxe armory), stripped out the Detour part and only used the Recast navmesh generation part. Because, it appears that in order to use Detour, you’ll have to use the entire blob of Recast+Detour and all it’s dependencies, which doesn’t make it ideal in various cases.


#8

We share the same findings, indeed the Emscripten port of Detour didn’t work as expected for us.

At some point I believe Web Assembly, given large adoption, will solve that. But for the moment it is too much of a big, hard to maintain, block of code that I would avoid using in the web unless an app explicitly requires it.


#9

Currently in beta, we are working in exposing a clean API and providing robust docs.

Here is a demo of our playground:

All nav meshes were generated inside the PlayCanvas editor.


#10

Released! See initialy post on top of the page for details.