About obstacles
Any visible game objects on the game scene can act as obstacles. Nav3D uses their meshes. Obstacles can be any game objects with any number of transforms in the hierarchy that meet the following requirements:
Among the transform hierarchy, there is at least one object that has a MeshFilter with a Mesh assigned among its components
Transform.scale > 0 in x,y and z
Nav3D handles obstacles as follows:
From the transform hierarchy of the game object, objects containing the MeshFilter with the assigned Mesh are selected
For each Mesh, the set of triangles that make up it is taken
For each triangle, scaling, rotation and translation are performed in accordance with the parameters of the transform from which the Mesh is taken
For all transformed triangles, a passability graph is constructed based on the octree
Our use of an optimal graph based on an octree gives a significantly higher pathfinding speed than the use of a classical grid graph.
For your convenience, there are three main operations for managing obstacles:
Add an obstacle. The obstacle is added to the Nav3D obstacle store and will be taken into account when finding the path. In this case, the already found paths will be updated. It is advisable to use for obstacles that appear on the stage.
Update Obstacle. The passability graph will be updated according to the changed transform characteristics of the obstacle. It is advisable to use if the obstacle has changed its position or size, or rotation.
Remove an obstacle. The obstacle will be removed from the Nav3D Obstacle Storage and will no longer be considered when pathfinding agents.
About pathfinding
To search for a path in the game space, a modification of the A* algorithm is used.
The resulting path goes around all the obstacles that are in a straight line between A and B. At your discretion, the path can be smoothed.
About local avoidance
Any game objects moving in space along found paths or in an arbitrary direction can use the local avoidance mechanism to avoid collisions with each other, as well as to avoid collisions with obstacles during avoidance maneuvers.
Local avoidance in our implementation is based on the ORCA algorithm.
When using local avoidance, a sphere of a given radius is taken as the geometric shape of a moving object. We will call such objects spherical agents. On each frame, the algorithm tries to find a suitable velocity vector so that the agent does not collide with other agents and obstacles on the game scene in the next few frames.
Agent's movement and perception systems
Each agent has its own perception system, allowing it to take into account nearby agents and nearby obstacles when performing a collision-free movement.
When moving along the found path and performing local avoidance, each agent has several vectors for movement:
The motion vector along the found path
Avoidance vector from nearby agents
Avoidance vector from nearby obstacles
The resulting velocity on each frame is calculated from these three velocities, taken with different weighting factors, which you can manually adjust to achieve the desired motion characteristics. Thus, each agent can give a different degree of preference to each of the listed velocities.
Yielding agents
Our use of ORCA as a local avoidance algorithm allowed us to create an unusual style of behavior for agents, which can be useful in some game scenarios. We call them “yielding agents”. They do not have their own movement target and simply try not to interfere with the movement of other agents.
Commands for agents
To use agents in your game scenarios, you have three options for orders:
- Move to the point; The agent will interrupt the current order (if any) and begin pathfinding and moving towards the point
- Chase a moving Transform (be it another agent, or any other moving object in the game). The agent will interrupt the current order and start chasing the moving target
- Move to the point in turn. The agent will start moving to the specified point immediately after reaching the current pursued point. If the agent follows the order to chase the moving Transform, then it will interrupt it and start following to the point. Any number of points can be put in the queue of movement to the point.
