Embedded Files
Predicts potential collisions by modeling the relative velocity between agents.
A cone-shaped region is computed, and if the agent’s velocity falls inside it, a collision is likely.
Adjustments are made by projecting the agent’s velocity outside the cone to avoid direct paths to other agents.
Extends VO by factoring in both agents' velocities.
Instead of full responsibility falling on one agent, both adjust by averaging their velocities to create a shared “safe” region.
This creates more natural and fair avoidance behavior.
Improves on RVO by using a blend between relative velocity and VO.
Creates a region that biases movement away from the collision while maintaining some alignment with preferred direction.
Removes Jitter or Oscillation.
Uses half-plane constraints to compute a safe velocity space.
It accounts for both static and dynamic agents by building planes the agent must stay on the “safe” side of.
If an agent violates any constraint, it computes alternative velocities by projecting onto these planes and blends based on urgency, speed, and directional alignment.
If there's a heatmap then agent agent will use that as a influence on the direction to avoid so it doesn't avoid and go off the map or into an area where a nav mesh doesn't exist.
A* in this demo requires that a nav mesh is created so each agent can initialize their node data. The concept is the same regardless if its 2D, 3D, nav mesh or tiles, there's only one difference which is neighbor exploration.
Check if the line segment intersects anywhere on the neighboring triangle.
If there's an intersection, check the distance and see if it's the closest to the goal.
Calculate local g Cost (Distance between neighbor point and current node position).
Use local g Cost to calculate the total g Cost (Current node total g + calculated local g).
Calculate the h Cost (Distance between neighbor point and goal point).
Calculate the local f Cost (total g Cost + h Cost) and check if the f Cost is less than the neighbor node f cost.
Neighbor Exploration
Neighbor Exploration
Green sphere is the start point
Red sphere is goal point
Magenta triangle mesh are what was explored
Yellow arrows start from current node to next explored intersection
Purple sphere is next waypoint
A* Optimization:
A* Optimization:
A* does give the most optimal straight path.
It can be optimize by reducing the number of waypoints to get from point A to point B.
This method is called pruning.
Pruning takes the already created path and removes intermediate waypoints if it does not cause the path to go through obstruction:
Step size: The step size is based on the average triangle edge length.
Large: Faster to compute, but it may skip over narrow triangles (Some points may not be pruned).
Small: Slower to compute, but the sample size can be so dense it can result in a path just being start and goal.
Before Prune
Before Prune
After Prune
After Prune
Agents move along their computed path. If an agent comes within another agent's search radius (Green ring) then it computes ORCA to avoid the other agent.
Features
Features
An optimization I made for ORCA.
Filter and prioritize who we should avoid.
Skip what was the next waypoint if it past it after computing ORCA.
Terrain & Nav Mesh Generation
Terrain & Nav Mesh Generation
- Terrain Generation:
Custom HLSL code that allows for the terrain to have 3 different textures blended.
Terrain is procedurally generated based on Perlin noise.
Terrain generates a heightmap of data.
Uses heightmap data from the generated terrain to create triangular meshes.
Has a border where the generation starts based on the max size of an agent so no agent can "fall off the map".
Added randomness so the triangles are uniform, giving a more natural and unique look of the nav mesh.
Uses triangles of the generated nav mesh to generate a heatmap.
Heat:
The higher heat is towards the center of the nav mesh as that's the safest to move toward when avoiding another agent.
The lower heat is towards an edge or a triangle that has no neighbor as that's not safe for an agent to be when avoiding another agent.
Page updated
Google Sites
Report abuse