Giter Club home page Giter Club logo

dotsnav's Introduction

Video (v0.1)    Video (avoidance)    Demo    Discord    Sponsor

Table of Contents

Introduction

DotsNav is a fully dynamic and robust planar navmesh Unity package built on DOTS. It is fast enough to add and remove many obstacles each frame, supports agents of any size, and can be used through monobehaviours without prior knowledge of DOTS.

To support further development consider becoming a sponsor.

Getting Started

Installation

If OpenUpm is not installed, ensure Node.js is installed so you have access to npm and run:

npm install -g openupm-cli

To add DotsNav to a Unity project, open a prompt in the project root and run:

openupm add com.bassmit.dotsnav

Planes

Attach a DotsNavPlane behaviour to a gameobject. Its border will be drawn in the scene view.

To create a navmesh attach a DotsNavNavmesh behaviour. The value of ExpectedVerts determines the size of initial allocations.

To enable local avoidance attach a DotsNavLocalAvoidance behaviour. This behaviour does not require a navmesh.

Pathfinder

To enable path finding attach a DotsNavPathfinder behaviour to a gameobject. The pathfinder manages the resources required to search for paths on any number of threads, and only one pathfinder is allowed at any time.

Obstacles

To create an obstacle add a DotsNavObstacle behaviour to a gameobject and assign the Plane field. When spawning obstacle prefabs make sure to assign the Plane immediately after instantiation.

Add DotsNavNavmeshObstacle and DotsNavLocalAvoidanceObstacle behaviours as appropriate.

Add a few vertices and move them around using the position handle. The edit mode colors can be set in the DotsNav tab in Preferences.

Alternatively an obstacle's Vertices array can be populated through script. Obstacle gameobjects can be scaled, rotated and used as prefabs. Obstacles are projected on to their respective planes when inserted.

Agents

To create an agent attach a DotsNavAgent behaviour to a gameobject and assign the Plane field. When spawning agent prefabs make sure to assign the Plane immediately after instantiation.

Add DotsNavPathfindingAgent and DotsNavLocalAvoidanceAgent behaviours as appropriate.

Note that DotsNavPathfindingAgent and DotsNavLocalAvoidanceAgent have Direction and Velocity fields respectively. Currently no steering behaviours are provided, but a basic example can be seen in the avoidance sample scene.

Conversion to DOTS

Attach a Convert to Entity component all to planes, agents, obstacles and the pathfinder. When using monobehaviours to develop a project choose “Convert and Inject”. Obstacles and agents can then be removed by destroying the associated gameobject. Planes can be disposed of similarly.

Renderer

To draw the navmesh while playing, add a DotsNavRenderer component to a gameobject. If the renderer is attached to the camera it can draw in the game view as well as the scene view.

Path Queries

Path queries can be enqueued using DotsNavAgent.FindPath.

Next navmesh update a path will be calculated.

Using the default settings, invalidated paths are recalculated automatically.

For multiple agents, path finding is performed in parallel.

Creating obstacles from code

Obstacle prefabs are automatically enqueued for insertion when spawned. Alternatively obstacles can be inserted by calling InsertObstacle and providing a list of vertices.

Obstacles can be removed by destroying a previously spawned gameobject, or by calling RemoveObstacle providing an id returned by InsertObstacle.

Getting Started with DOTS

Conversion

When using monobehaviour conversion use “Convert and Destroy”.

You can use the DOTS Editor to inspect the entities in the sample scenes to get a better understanding of the components involved.

API

All public APIs expose read-only operations. Write operations are triggered by creating entities with appropriate archetypes, or updating component data.

Planes

Navmeshes are created by adding a NavmeshComponent to an entity. Local avoidance requires an ObstacleTreeComponent and a DynamicTreeComponent. Destroy the entity to dispose of its resources.

PathFinder

When adding a PathFinderComponent to an entity, use the constructor so it is initialized properly. Destroy the entity to dispose of its resources. There should be only one PathFinderComponent at any time.

Obstacles

There are two types of obstacles:

  • Dynamic, these obstacles are associated with an entity through which they can be identified and removed
  • Static, these obstacles can not be removed or identified beyond being static, but can be inserted in bulk

The following archetypes trigger obstacle insertion:

  • Dynamic
    • ObstacleComponent, DynamicBuffer<VertexElement>
    • ObstacleComponent, VertexBlobComponent
  • Static
    • DynamicBuffer<VertexElement>, DynamicBuffer<VertexAmountElement>
    • ObstacleBlobComponent

Note that any obstacle requires a NavmeshObstacleComponent and or a ObstacleTreeElementComponent. Entities with static obstacle archetypes are destroyed after insertion. To destroy dynamic obstacles destroy their associated entity.

Agents

General components:

  • RadiusComponent

Pathfinding related components:

  • NavmeshAgentComponent
  • PathQueryComponent
  • DynamicBuffer<PathSegmentElement>
  • DynamicBuffer<TriangleElement>
  • DirectionComponent (optional)
  • AgentDrawComponent (optional)

Local avoidance related components:

  • DynamicTreeElementComponent
  • ObstacleTreeAgentComponent
  • VelocityObstacleComponent
  • RVOSettingsComponent
  • MaxSpeedComponent
  • PreferredVelocityComponent
  • VelocityComponent

To trigger a path query set PathQuery.State to Pending.

Accessing the triangulation

The NavmeshComponent provides access to the triangulation through the following methods, allowing for traversal of the triangulation and development of additional algorithms:

  • Edge* FindTriangleContainingPoint
  • Vertex* FindClosestVertex

Technical Information

DotsNav uses a Local Clearance Triangulation which reduces path finding using an arbitrary agent radius to a single floating point comparison per expanded edge. It uses a quadedge to represent the triangulation, and a bucketed quadtree for point location.

DotsNav's insertion and removal algorithms are guaranteed to succeed and guarantee closed polygons remain closed, no matter how many intersecting obstacles are inserted or removed. In short, intersections use an existing point chosen to converge on the destination in the rare case no valid point can be created due to the density of the navmesh. When points chosen in this way are not connected directly, A* is used to determine which edges need to be constrained.

Due to the nature of the algorithms involved exact geometric predicates are required for a robust implementation. DotsNav relies on adaptive predicates, only when regular floating point calculations do not provide sufficient precision is the costly exact calculation performed. The predicates are available separately.

DotsNav provides locally optimal search. First, a channel of connected triangles with enough clearance is found using A*. The optimal path given this channel is then found using the funnel algorithm. While channels found are often optimal they are not guaranteed to be. An algorithm to find the optimal channel exists, but can easily require several orders of magnitude more time to execute and is not currently implemented.

DotsNav uses the RVO2 algorithm to implement local avoidance. While the triangulation accepts any sequence of inputs, RVO2 only supports closed and counter clockwise wound obstacles.

Known Issues

  • Performance appears to be significantly worse and less consistent from frame to frame in a build as compared to in the editor.
  • As globally optimal path search is not implemented the quality of the cost function can not easily be determined.
  • Local avoidance agent settings are fragile and require trial and error to find configurations yielding acceptable results.
  • Synchronizing gameobjects and entities can almost certainly be improved, as no research has gone in to the intended mechanisms for doing so.
  • Summary comments have not been thoroughly checked, please raise an issue or create a pull request to correct any errors you may find.

Contributing

Contributions to DotsNav are very much appreciated and pull requests will be considered promptly. To develop the package while using it in a different Unity project clone a fork of DotsNav, check out the dev branch, and add the package using the "from disk" option in your main Unity project. Changes made to the package will then trigger a reimport in the main project automatically. Once pushed you can open a pull request against DotsNav.

Bibliography

Acknowledgements

I would like to thank Marcello Kallmann for describing the local clearance triangulation including robust and dynamic insertion and removal algorithms, Jonathan Shewchuk for placing his geometric primitives in the public domain, Govert van Drimmelen for porting them to C#, and Jamie Snape for making available a C# implementation of RVO2.

dotsnav's People

Contributors

bassmit avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

dotsnav's Issues

Would this be suitable for dynamically growing world?

I am doing some research on the state of pathfinding in DOTS, and I just came across this projects which looks amazing.

I have a couple of questions, if you dont mind me asking.
Would this project cater for a world that is generated dynamically at runtime and will potentially grow in size? Based on the demo and the docs, it seems the world is limited to a certain area only.

If that's the case, can we generate multiple areas and link them to each other somehow? Think of a chunked world approach that generates tiles as the player moves around.

Thank for you amazing work!
Cheers!

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.