From BlenderWiki

Path-finding and steering behaviours in Blender

Overview

Path-finding in Blender is based on the concept of navigation meshes. Now you can create navigation mesh for your level geometry directly in Blender and use it in Blender Game Engine (BGE) to get your actors to find path to the target and move along it. Besides path following, there are also a few other steering behaviours which can be assigned to the actor: seek and flee. Path-finding with navigation mesh is effective for big static obstacles. To enable actors to avoid small dynamic objects during their movement local obstacle avoidance can be used. If the obstacle simulation is enabled the actor will try to choose direction which is free of collision with obstacles on each frame during execution one of the steering behaviours.

Automatic generation of the navigation mesh from raw geometry and execution of the path-find queries in BGE is implemented by integrating Recast&Detour library, obstacle avoidance - Project Cane. The author of these projects is Mikko Mononen.

Navigation mesh creation

For using a mesh object in the BGE as a navigation mesh you have to set special physics type "Navmesh" for this object:

1. Select mesh object in Object Mode
2. Move to Physics Panel in the Properties (make sure that active engine is Blender Game)
3. Select "Navmesh" in the Physics Type list

You can create navigation mesh in two ways:

• Manually - create blender mesh object and set physics type NavMesh for it
• Automatically - generate navigation mesh from raw level geometry by Recast library. You have to do following:

1. Select objects you want to generate navigation mesh from
2. Setup parameters on the Navmesh Panel (Properties » Scene » Navmesh)
3. Push the button Build navigation mesh

New object with the name 'Navmesh' will be created. The physics type of this object will be automatically set to NavMesh.

Note: To avoid creation of the new navigation mesh object if you have already one you can add it to selected objects before generation. So if among selected objects there are objects with "NavMesh" physics type, result object will be picked up from them (it will be active or last selected navigation mesh object) and updated with new navigation mesh data.

Parameters for navigation mesh generation

Cell size - rasterized cell size

Cell height - rasterized cell height

Agent height - Minimum height where the agent can still walk

Agent radius - Radius of the agent

Max climb - Maximum height between grid cells the agent can climb

Max slope - Maximum walkable slope angle in degrees

Min region size - Minimum regions size. Smaller regions will be deleted

Merged region size - Minimum regions size. Smaller regions will be merged

Max edge length - Maximum contour edge length

Max edge error - Maximum distance error from contour to cells

Verts per poly - Max number of vertices per polygon

Sample distance - Detail mesh sample spacing

Max sample error - Detail mesh simplification max sample error

Navigation mesh editing

You can edit a navigation mesh using ordinary editing methods or using the following buttons on the Physics panel to handle the NavMesh data which represents the mesh faces owned by the navigation polygons

In Edit Mode:

NavMesh Copy Face Index - to copy the navigation polygon index from the active face to selected faces

NavMesh New Face Index - to add a new navigation polygon index to selected faces

In Object Mode:

NavMesh Reset Index Values - to assign a new index to every faces

NavMesh Clear Data - to remove the navigation data from the mesh

Navigation polygons have following restrictions: they are convex and have a limited numbernumber of vertices (currently it is maximum 6 vertices per polygon). So you should try to stick to these restrictions during navigation mesh editing. Invalid navigation polygons are ignored for constructing KX_NavMeshObject and corresponding faces are displayed as black.

Obstacle avoidance

To set up obstacle avoidance for actors you have to set the proper obstacle simulation type on the Obstacle simulation Panel (Properties » World » Obstacle simulation, engine - Blender Game):

• None - obstacle simulation is disabled, actors aren't able to avoid

obstacles

• RVO_rays - obstacle simulation is based on the RVO method with ray sampling
• RVO_cells - obstacle simulation is based on the RVO method with cell sampling.

The Level height options is used to define minimum margin between obstacles by height, when they are treated as those which are situated one above the other i.e. they doesn't influence to each other. You can turn on the debug rendering of the obstacles activating Visualization check-box.

You have to specify objects which have to be represented in the obstacle simulation. For such objects you have to activate Create obstacle the check-box on the Physics Panel (Properties » Physics » Create obstacle) and set up the radius of the obstacle (such objects are approximated with round collision bounds).

Implementation notes

Recast&Detour library is added to the Blender solution as an external library (ext_recastnagivation). Logically the project implementation is divided into 2 parts:

1. Generation and editing of navigation meshes in the Blender editor
2. Path-finding using navigation mesh in the Blender Game Engine

Generation and editing of navigation meshes in the Blender editor

Navigation mesh generation is implemented as operator (MESH_OT_navmesh_make, editors/mesh/mesh_navmesh.c), which executes such tasks

• creates list of source mesh objects
• builds vertex and index data for these objects, which is suitable for Recast library
• generates navigation mesh using Recast library
• creates mesh object to represent Recast navigation mesh

Faces of the result mesh object corresponds to the triangles of the detailed meshes of the Recast navigation mesh. The index of the navigation polygon the face belongs to stored in the layer CD_RECAST of the face custom data. The visualisation is implemented using Derived Mesh mechanism (blenkernel\intern\DerivedMesh.c). Miscellaneous functions defined in blenkernel\BKE_navmesh_conversion.h are used to build the derived mesh for the visualisation.

Path-finding using navigation mesh in the Blender Game Engine

During the data conversion step to pass blender scenes to the game engine, each blender mesh object which has the physics type "NavMesh" will have a special game object KX_NavMeshObject constructed. KX_NavMeshObject is derived from KX_GameObject class and is used as the wrapper for Detour navigation mesh functionality.

KX_SteeringActuator implements steering behaviours. At each frame, steering velocity for the actor is calculated based on the type of behaviour, location of the target, and physical properties of the actor (parameters of the actuator). Then steering velocity is adjusted by the obstacle simulation in order to provide obstacle avoidance. Adjusted steering velocity is applied to the actor. Facing of the actor is handled based on the actuator parameters.

Obstacle simulation handles obstacles - special representation of the game objects. On each frame, obstacles are updated with the current position of their parent game objects. KX_ObstacleSimulation is the base class for obstacle simulation, it doesn't provide any particular algorithm for obstacle avoidance. It is mainly responsible for the adding, deleting and update of obstacles. KX_ObstacleSimulationTOI is derived class to implement common functionality for two algorithms: RVO based on the ray sampling (KX_ObstacleSimulationTOI_rays) and RVO based on the cell sampling (KX_ObstacleSimulationTOI_cells).

Path-finding API for Blender Game Engine

The brief description of objects which are used to implement path-finding and steering behaviours in Game Engine.

KX_NavMeshObject

This object represents the navigation mesh.

Methods

findPath(start, goal) - finds path from start to goal points

start - vector of start point

goal - vector of goal point

returns a path as list of points

raycast(start, end) - finds first intersection of the ray with navigation mesh walls.

start - vector of ray source point

end - vector of ray destination point

returns hit factor - ratio of the distance from source to intersection point to the ray length (distance between start and goal points)

draw(mode) - visualizes the navigation mesh (for debug purpose)

mode - defines the mode for the visualization. Supports the following modes (constants are defined on GameLogic module):

RM_WALLS - render walls of the navigation mesh. Wall is the edge of navigation polygon, which isn't portal to the next polygon, so it's impassable for an actor

RM_POLYS - render navigation mesh polygons

RM_TRIS - render triangles of the detailed navigation mesh. Detailed navigation mesh is used to represent the surface of the polygons in detail.

rebuild() - rebuilds the navigation mesh based on the object mesh. It can be used to rebuild navigation data after changing in the object mesh.

Note: It works only for manually created mesh object (without using operator for automatic generation of navigation mesh).

KX_SteeringActuator

This actuator implements steering behaviours: seeking, fleeing, path following.

Attributes

behaviour - integer, defines one of the following steering behaviours

1 SEEK - to seek to target object

2 FLEE - to flee from target object

3 PATHFOLLOWING - to move along the path to the target object

target - target object for behaviour

navmesh - navigation mesh object. It's used for finding a path in the path following behaviour. For other behaviours it's used to generate obstacles - the walls for restricting passable area (if obstacle simulation is enabled)

distance - maximum distance at which it's considered that target is reached

velocity - velocity of the actor for current behaviour

acceleration - acceleration of the actor for current behaviour

turnspeed - turn speed of the actor for current behaviour

selfterminated - defines whether the actuator has to be terminated when target is reached.

facingMode - enables automatic facing mode for actor (0 - automatic facing is disabled, 1 - 6 - automatic facing with X, Y, Z, -X, -Y, -Z axis, respectively)

normalUp - enables calculation of the actor "UP" vector based on the normal of the underlying navigation mesh.

enableVisualization - enable debug visualization

pathUpdatePeriod - the period of time for recalculation the path to target.

-1 - path is recalculated every logic frame

0 - path is calculated only one time at the beginning of the actuator execution

Note: this attribute is important only for the pathfollowing behaviour

Samples

1. Navigation mesh demo: File:Manual-navmesh demo.blend
2. Obstacle avoidance demo: File:Manual-obstacles demo.blend