Comments (4)
Studying a little more I ended up finding this video from GDC that talks about Getting off the NavMesh: Navigating in Fully 3D Environments:
URL: https://www.gdcvault.com/play/1022016/Getting-off-the-NavMesh-Navigating
from yuka.
I find it strange that the video talks about spares voxel octrees. SVO is a rendering technique and always includes some sort of raycasting or tracing. Pathfinding in 3D is totally unrelated to rendering.
The first presentation outlines the steps for an algorithm:
- Generate an Octree from the environment. The Octree might become sparse since depending on the scenario most parts of the data space will be empty and thus not subdivided.
- Generate a graph by processing the corner points/edges of certain cells of the Octree.
- Query the graph with (lazy) Theta*.
Yuka already provides a graph class but no Octree and Theta* implementation. Since Theta* is just an enhancement of A* (which is implemented by the engine), the real challenge is the development of an Octree class and the logic that brings all components together in order to implement the above algorithm.
from yuka.
It's not yet clear to me how to handle game entities with different size.
The above algorithm basically only works when the game entity is a point and thus infinitely small. However, game entities usually have a spatial extension.
In context of navigation meshes, the maximum bounding radius of a game entity is honored when the nav mesh is generated by a tool. A similar approach needs to be used for 3D pathfinding when computing the Octree. Otherwise a too big game entity will intersect obstacles. Consider this image from the first post:
If the agent is bigger, it can't use the blue path through the cube, sphere and cone. It probably has to go outside.
from yuka.
@Mugen87 First thank you very much for responding.
This unreal engine plugin is one of the most used because it is very complete and free.
https://github.com/VSZue/DonAINavigation
About the size of object starts on 23:00
This image is from this repo for unreal engine plugin -> https://github.com/darbycostello/Nav3D
I was trying to take a look and even testing these plugins in the unreal engine and they work very well.
In the first case it is the best of all because it works even in the form of infinite worlds, it uses the same octree for all entities so it can avoid collisions between them, it regenerates the octree in a time that is controllable and can be in all frames or at longer intervals, thus being able to map objects that move and re-calculate paths.
from yuka.
Related Issues (20)
- WanderBehavior within Navmesh HOT 2
- Efficient way to find an intersection HOT 2
- jsdoc contradiction to code in GameEntity HOT 16
- Steering handling in `Vehicle.update()` ignores `GameEntity.maxTurnRate` HOT 4
- how to judge arriveBehave over HOT 1
- how to set initial mesh HOT 1
- Yuka and Babylon.js HOT 5
- Building navmesh HOT 2
- Question: Best Practices HOT 2
- Question: NavMesh HOT 8
- Non-terminating while loop HOT 5
- Is there any way to add obstacles dynamically on a 2D grid? HOT 3
- Building with webpack and es6 modules HOT 5
- SteerBehavior - Vehicle facing the wrong direction HOT 3
- How to generate NavMesh automatically? HOT 3
- NavMeshLoader for Typescript throw reference error for fetch HOT 1
- need explanation for this formula HOT 4
- YUKA findPath is not detecting any collisions in Babylon.js HOT 3
- Pursuit Behavor duplicate gltf model HOT 3
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
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.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from yuka.