The Crowd - MeFisto94/jme3-recast4j-demo GitHub Wiki

The jme3-Recast4j-demo has a Crowd Builder GUI with which you can test every setting for an agent or Crowd.

Basic Usage

Create the CrowdManager.
Instantiate the CrowdManagerAppstate with the CrowdManager and add it to the AppStateManager.
Load a NavMesh
Create a Query object for path finding.
Create a Crowd.
Set avoidance parameters for the Crowd.
Add agents to the Crowd.
Set a target for the Crowd.
React when target reached.

CrowdManagerAppstate and CrowdManager

CrowdManagerAppstate is the starting point for Crowd management. This wrapper extends BaseAppState to give you full interactivity with the jMonkeyEngine. To use it, you configure and pass it a CrowdManager object. The CrowdManager object handles updates for the crowd and can be one of two threading types, CrowdUpdateType.SEQUENTIAL or CrowdUpdateType.PARALLEL.

SEQUENTIAL - Update one Crowd after another.
PARALLEL - Update all Crowds in Parallel using the Java 8 Stream API. This is not always the best solution and in most cases might perform worse than SEQUENTIAL.

Startup

CrowdManager cm = new CrowdManager();
cm.setUpdateType(CrowdUpdateType.PARALLEL);
CrowdManagerAppstate crowdManagerAppstate = new CrowdManagerAppstate(cm);
this.getStateManager().attach(crowdManagerAppstate);

There is no limit on the number of Crowds you can add to the CrowdManager. Increasing Crowds has the added benefit of increasing performance, especially when using PARALLEL mode, because you are dividing the workload between multiple cores and the CrowdManager has smaller crowds to manage.

Note	PARALLEL only makes sense with many active crowds and can’t fix the fact that large crowds are straining the performance.

Crowd Example

try {
    //Read in saved MeshData and build new NavMesh.
    MeshDataReader mdr = new MeshDataReader();
    MeshData savedMeshData = mdr.read(new FileInputStream("myMeshData.md"), 3);
    NavMesh navMeshFromData = new NavMesh(savedMeshData, 3, 0);
    //Or read in saved NavMesh.
    MeshSetReader msr = new MeshSetReader();
    NavMesh navMeshFromSaved = msr.read(new FileInputStream("myNavMesh.nm"), 3);

    //Create the query object for pathfinding in this Crowd.
    query = new NavMeshQuery(navMeshFromSaved);
    //Start crowd.
    crowd = new Crowd(MovementApplicationType.DIRECT, 100, .3f, navMeshFromSaved);
    //Add to CrowdManager.
    getState(CrowdManagerAppstate.class).getCrowdManager().addCrowd(crowd);

    //Add OAP.
    ObstacleAvoidanceParams oap = new ObstacleAvoidanceParams();
    oap.velBias = 0.5f;
    oap.adaptiveDivs = 5;
    oap.adaptiveRings = 2;
    oap.adaptiveDepth = 1;
    crowd.setObstacleAvoidanceParams(0, oap);
    oap = new ObstacleAvoidanceParams();
    oap.velBias = 0.5f;
    oap.adaptiveDivs = 5;
    oap.adaptiveRings = 2;
    oap.adaptiveDepth = 2;
    crowd.setObstacleAvoidanceParams(1, oap);
    oap = new ObstacleAvoidanceParams();
    oap.velBias = 0.5f;
    oap.adaptiveDivs = 7;
    oap.adaptiveRings = 2;
    oap.adaptiveDepth = 3;
    crowd.setObstacleAvoidanceParams(2, oap);
    oap = new ObstacleAvoidanceParams();
    oap.velBias = 0.5f;
    oap.adaptiveDivs = 7;
    oap.adaptiveRings = 3;
    oap.adaptiveDepth = 3;
    crowd.setObstacleAvoidanceParams(3, oap);
} catch (IOException | NoSuchFieldException | IllegalAccessException ex) {
    LOG.info("{} {}", CrowdBuilderState.class.getName(), ex);
}

Load NavMesh

Each Crowd needs a navigation mesh. These are explained in the NavMesh Generation topic.

Create Query Object

//Create the query object for pathfinding in this Crowd.
query = new NavMeshQuery(navMeshFromSaved);

Provides the ability to perform pathfinding related queries against a navigation mesh. These are explained in the Path Finding topic.

Create Crowd

//Start crowd.
crowd = new Crowd(MovementApplicationType.DIRECT, 100, .3f, navMeshFromSaved);

Each Crowd must know how to apply the movement to an agent, how many agents it must manage, their radius, the navigation mesh to use for path finding and the path finding filter to apply to the agents.

Each Crowd can contain both active and inactive agents. You can remove agents or add agents at will. Removing an agent will free its slot up for reuse. After you create the crowd, you will typically add all your agents, which will set them as active but not path finding, and just set new targets for them as desired. You can poll the agents to know when they have reached their targets and react to the event. You can reset, i.e. cancel, the target at any time.

Crowd Constructors

//Constructor #1
public Crowd(MovementApplicationType applicationType, int maxAgents, float maxAgentRadius, NavMesh nav)

//Constructor #2
public Crowd(MovementApplicationType applicationType, int maxAgents, float maxAgentRadius, NavMesh nav, IntFunction<QueryFilter> queryFilterFactory)

There are two constructors used to build crowds, and sixteen query filters are created during initialization of any crowd. The difference between the two is constructor #1 will create the query filters and set every filter to default settings while constructor #2 lets you create and set the filters and settings. See the Crowd Filters topic for details on filters while the Crowd constructor parameters are explained below.

MovementApplicationType - There are four movement application types which address the different needs for movement. The way Path Finding works for the crowd is you supply the crowd with a start location and target for the agent to travel to. The crowd will calculate a path to the target and every update either supply you with the new position and velocity to use for that frame, move your agent, or do nothing, depending on the type used.
- BETTER_CHARACTER_CONTROL - Physics agents are the only type allowed for this Crowd. Each agent will have a BetterCharacterControl. The crowd will setWalkDirection and setViewDirection for the control every update.
- DIRECT - No controls are needed for movement. The crowd will setLocalTranslation and setLocalRotation for the agent every update.
- CUSTOM - With custom, you implement the applyMovement() method from the ApplyFunction.java interface for your agent. This will give you access to the agents CrowdAgent object, the new position and the velocity of the agent.
- NONE - No movement is implemented. You can freely interact with the crowd and implement your own movement solutions.
maxAgents - The maximum number of agents the crowd can manage. [Limit: >= 1]
maxAgentRadius - The maximum radius of any agent that will be added to the crowd.
NavMesh - The navigation mesh to use for planning.
QueryFilter - Defines polygon filtering and traversal costs for navigation mesh query operations. At construction: All area costs default to 1.0. All flags are included and none are excluded. If a polygon has both include and exclude flags, it will be excluded. The way filtering works, a navigation mesh polygon must have at least one flag set to ever be considered by a query. So a polygon with no flags will never be considered. Setting include flags to 0 will result in all polygons being excluded.

Crowd Filters

Every crowd has sixteen query filters and each Crowd Agent uses one of these filters for its path finding. The first Crowd constructor accepts no filter. This constructor will create and fill the first slot with a BetterDefaultQueryFilter.java. The remaining slots will be filled with DefaultQueryFilter.java. Each filter will be called using the empty query constructor.

Empty Query Constructor

public DefaultQueryFilter() {
    m_includeFlags = 0xffff;
    m_excludeFlags = 0;
    for (int i = 0; i < NavMesh.DT_MAX_AREAS; ++i) {
        m_areaCost[i] = 1.0f;
    }
}

The filter will have both include/exclude flags (Ability Flags) set as well as area costs if you use the empty DefaultQueryFilter constructor. The include flags are set to All, the exclude flags to None and all area costs are 1.0f. There are potentially 64 different custom Area Types and 16 Ability Flags you can create.

Custom Filter Setting

//Create crowd using filters from list.
 IntFunction<QueryFilter> filters = (int i) -> myFilterList.get(i);
 //Create the crowd.
 crowd = new Crowd(applicationType, maxAgents, maxAgentRadius, navMesh, filters);

When you supply your own filters to crowd constructor #2, as we did above, you can dictate the area cost associated with each Area Type and the custom Ability Flags. You create the Area Type and Ability Flag like is done in the example SampleAreaModifications.java file that is included with jme3-recast4j.

public DefaultQueryFilter(int includeFlags, int excludeFlags, float[] areaCost)

Agents will prefer the path that has the lowest area cost when path finding. You do not have to supply area costs for all 64 Area Types but any unset cost will be defaulted to one.

float[] areaCost = new float[] {1f, 10f, 1f, 1f, 2.0f, 1.5f};

So if you only have six Area Types, like is used in the SampleAreaModifications.java file, you can just set those and everything else will be set to one.

Filter Update

filter.setIncludeFlags(getIncludes());
filter.setExcludeFlags(getExcludes());

Once the Crowd has been instantiated, you can only update the filters include and exclude flags, not the area costs.

public BetterDefaultQueryFilter(int includeFlags, int excludeFlags, float[] areaCost)

A note about the BetterDefaultQueryFilter. As has been mentioned, a navigation mesh polygon must have at least one flag set to ever be considered by a query. So a polygon with no flag will never be considered. When a polygon has no flag and the filter is set to include all (which is the default case most of the time), the BetterDefaultQueryFilter will accept the polygon instead of rejecting it. Otherwise, this leads to useless code setting the flag to 0x1 when you build the NavMesh, just so that the filter accepts them, as is done with RecastTestMeshBuilder.java.

This only applies if you do not set any flags during the NavMesh generation process. In our examples, we set the flags, so its not mandatory to use the BetterDefaultQuerryFilter.

Add to Crowdmanager

//Add to CrowdManager.
getState(CrowdManagerAppstate.class).getCrowdManager().addCrowd(crowd);

Add the Crowd to the CrowdManager after intitialization. Your crowd is now fully configured and awaiting agents to be added. Remember, there is no limit on the number of Crowds you can create.

ObstacleAvoidanceParams

//Add OAP.
ObstacleAvoidanceParams oap = new ObstacleAvoidanceParams();
oap.velBias = 0.5f;
oap.adaptiveDivs = 5;
oap.adaptiveRings = 2;
oap.adaptiveDepth = 1;
crowd.setObstacleAvoidanceParams(0, oap);

This is the shared avoidance configuration for an Agent inside the crowd. After initialization, you can create your own customized ObstacleAvoidanceParams based on your needs. You can change these at anytime and the Agents who have this as their type will be affected immediately.

When first instantiating the crowd, you are allotted eight ObstacleAvoidanceParams objects in total. All eight slots are filled with the defaults listed below.

Defaults	Description
velBias(0.4f)	Describes how the sampling patterns is offset from the (0,0) based on the desired velocity. This allows tightening the sampling area and culling a lot of samples. [Limit: 0-1]
horizTime(2.5f)	Time horizon, this affects how early the agents start to avoid each other. Too long horizon and the agents are scared of going through tight spots, and too small, and they avoid too late (closely related to weightToi).
weightDesVel(2.0f)	How much deviation from desired velocity is penalized, the more penalty applied to this, the more goal oriented the avoidance is, at the cost of getting more easily stuck at local minima. [Limit: >= 0]
gridSize(33)
weightCurVel(0.75f)	How much deviation from current velocity is penalized, the more penalty applied to this, the more stubborn the agent is.
adaptiveDivs(7)	Number of divisions per ring. [Limit: 1-32]
weightSide(0.75f)	In order to avoid reciprocal dance, the agents prefer to pass from right, this weight applies penalty to velocities which try to take over from the wrong side.
adaptiveRings(2)	Number of rings. [Limit: 1-4]
weightToi(2.5f)	How much penalty is added based on time to impact. Too much penalty and the agents are shy, too little, and they avoid too late.
adaptiveDepth(5)	Number of iterations at best velocity.

Adding Agents to the Crowd

This is a simplistic example for adding an agent, you may want to have a more robust method, depending on your Crowd type.

Basic flow

Set update flags.
Set parameters.
Create the agent.
Optional - set the Spatial for the agent. (Depends on Crowd Type)

Helper Method

private void addAgent(Vector3f location) {

    //Load the spatial that will represent the agent.
    Node agent = (Node) getApplication().getAssetManager().loadModel("Models/Jaime/Jaime.j3o");
    //Set translation prior to adding controls.
    agent.setLocalTranslation(location);
    //If we have a physics Crowd we need a physics compatible control to apply
    //movement and direction to the spatial.
    //agent.addControl((new BetterCharacterControl(0.3f, 1.5f, 20f)));
    //getState(BulletAppState.class).getPhysicsSpace().add(agent);

    //Add agent to the scene.
    ((SimpleApplication) getApplication()).getRootNode().attachChild(agent);

    //Set update flags.
    int updateFlags = CrowdAgentParams.DT_CROWD_OPTIMIZE_TOPO | CrowdAgentParams.DT_CROWD_OPTIMIZE_VIS;

    //Build the params object.
    CrowdAgentParams ap = new CrowdAgentParams();
    ap.radius                   = 0.03f;
    ap.height                   = 1.5f;
    ap.maxAcceleration          = 8.0f;
    ap.maxSpeed                 = 3.5f;
    ap.collisionQueryRange      = 12.0f;
    ap.pathOptimizationRange    = 30.0f;
    ap.separationWeight         = 2.0f;
    ap.updateFlags              = updateFlags;
    ap.obstacleAvoidanceType    = 0;
    ap.userData                 = new UserDataObj();

    //Add agent to the crowd.
    CrowdAgent createAgent = crowd.createAgent(agent.getWorldTranslation(), ap);

    //Set the spatial for the agent.
    crowd.setSpatialForAgent(createAgent, agent);
}

Update Flags

Flag	Description
ANTICIPATE_TURNS
OBSTACLE_AVOIDANCE
OPTIMIZE_TOPO	Attempts to optimize the path using a local area search. Inaccurate locomotion or dynamic obstacle avoidance can force the agent position significantly outside the original corridor. Over time this can result in the formation of a non-optimal corridor. This function will use a local area path search to try to re-optimize the corridor.
OPTIMIZE_VIS	Attempts to optimize the path if the specified point is visible from the current position. Inaccurate locomotion or dynamic obstacle avoidance can force the agent position significantly outside the original corridor. Over time this can result in the formation of a non-optimal corridor. Non-optimal paths can also form near the corners of tiles. This is not suitable for long distance searches.
SEPARATION

CrowdAgentParams

Before you add the agents to the Crowd you set the parameters for the agent. These parameters dictate the behaviour of the agent within the Crowd and are required.

See CrowdAgentParams.

Parameter	Description
float radius; `[Limit: >= 0]`	The radius of the agent. When presented with an opening they are too large to enter, pathFinding will try to navigate around it.
float height; `[Limit: > 0]`	The height of the agent. Obstacles with a height less than this (value - radius) will cause pathFinding to try and find a navigable path around the obstacle.
float maxAcceleration; `[Limit: >= 0]`	When an agent lags behind in the path, this is the maximum burst of speed the agent will move at when trying to catch up to their expected position.
float maxSpeed; `[Limit: >= 0]`	The maximum speed the agent will travel along the path when unobstructed.
float collisionQueryRange; `[Limits: > 0]`	Defines how close a collision element must be before it’s considered for steering behaviors.
float pathOptimizationRange; `[Limit: > 0]`	The path visibility optimization range.
float separationWeight; `[Limit: >= 0]`	How aggressive the agent manager should be at avoiding collisions with this agent.
int updateFlags;	See Update Flags
int obstacleAvoidanceType; `[Limits: 0 ⇐ value < 8]`	This is the Obstacle Avoidance configuration to be applied to this agent. Currently, the max number of avoidance types that can be configured for the Crowd is eight. See ObstacleAvoidanceParams
int queryFilterType;	Query filter the agent uses for path finding. See Crowd Filters
User Data	User defined data attached to the agent.

The User Data object is a custom object you can attach to the agent. It can be used for any purpose you deem necessary.

This is intended as an example only.

//Custom UserDataObj
public class UserDataObj {
  private String name;

  /**
  * @return The name to return.
  */
  public String getName() {
    return name;
  }

  /**
  * @param name The name to set.
  */
  public void setName(String name) {
    this.name = name;
  }
}

Add it to the CrowdAgentParams userData slot.

ap.userData                 = new UserDataObj();

Then just grab the object from the CrowdAgent, cast the object and use it.

UserDataObject userData = (UserDataObject) crowdAgent.params.userData;

if (userData.getName().equals("Boss Mob")) {
  //example use only
}

Create Agent

//Add agent to the crowd.
CrowdAgent createAgent = crowd.createAgent(agent.getWorldTranslation(), ap);

You add agents to the crowd by creating the agent. This is a jme3-recast4j specific method that will convert the Vector3f position to a float that Recast4j requires. The Crowd needs to know the starting position (agents current translation) for path finding and the CrowdAgentParams. When you create your agents, the Crowd will calculate the nearest start reference and position on the Polygon from the supplied position. If successful, the CrowdAgent will have an index number >= 0. If it fails, it will be -1. This is the index of that agent inside the crowd. You can use this index to get your CrowdAgent but most Crowd methods use the CrowdAgent.

Optional

//Set the spatial for the agent.
crowd.setSpatialForAgent(createAgent, agent);

The Crowd needs to know the spatial that represents the agent so it can apply movement if your Crowd type is DIRECT or BETTER_CHARACTER_CONTROL. Typically, you use a Node and add your model and any controls to the node.

Set Target

Basic flow

Pick a target.
Set the path finding query extents.
Set path finding filter.
Determine the closest Polygon to target.
Set the target for the crowd.

Helper Method

/**
 * Set the target for the crowd.
 *
 * @param target The target to set.
 */
public void setTarget(Vector3f target) {

    //Get the query extent for this crowd.
    float[] ext = crowd.getQueryExtents();

    //Locate the nearest poly ref/pos.
    FindNearestPolyResult nearest = query.findNearestPoly(DetourUtils.toFloatArray(target), ext, new BetterDefaultQueryFilter());

    if (nearest.getNearestRef() == 0) {
        LOG.info("getNearestRef() can't be 0. ref [{}]", nearest.getNearestRef());
    } else {
        //Sets all agent targets at same time.
        crowd.requestMoveToTarget(DetourUtils.createVector3f(nearest.getNearestPos()), nearest.getNearestRef());
    }
}

Getting Target

It’s up to you to determine the target Vector3f. Use any method you deem appropriate for the situation.

Query Extents

This is the search distance along each axis. [(x, y, z)]. You can pick any numbers you deem appropriate or get them from the crowd.

//Get the query extent for this crowd.
float[] ext = crowd.getQueryExtents();

Filtering

Filtering is explained in these topics so there is no need to re-invent the wheel.

FindNearestPolyResult

//Locate the nearest poly ref/pos.
FindNearestPolyResult nearest = query.findNearestPoly(DetourUtils.toFloatArray(target), ext, new BetterDefaultQueryFilter());

This is a standard path finding technique and explained in detail under the Path Finding topic. To give the short version, path finding requires a valid start and end reference. A reference is the id of the Polygon and position is a point on that Polygon. When you set the target, you provide the end reference. To get that reference you query your NavMesh to find the nearest Polygon by passing the target, extents for the search, and Filter the movement costs.

Setting target

if (nearest.getNearestRef() == 0) {
    LOG.info("getNearestRef() can't be 0. ref [{}]", nearest.getNearestRef());
} else {
    //Sets all agent targets at same time.
    crowd.requestMoveToTarget(DetourUtils.createVector3f(nearest.getNearestPos()), nearest.getNearestRef());
}

If the findNearestPoly search does not intersect any polygons, the search will return #DT_SUCCESS, but nearestRef will be zero. So always check for nearestRef before using getNearestPos().

The getNearestPos() method will return an array. Use DetourUtils.java to create the Vector3f for the jme3-recast4j requestMoveToTarget method.

public boolean requestMoveToTarget(Vector3f to, long polyRef)

When using jme3-recast4j, this method will set targets for all members of the crowd at one time. You can use the other available methods to move individual agents.

Reacting

As the agent moves towards its target, you can poll it using these jme3-recast4j specific methods. These can be used to implement your own behaviors.

Method	Description
isMoving(CrowdAgent crowdAgent)	When the Agent is ACTIVE and moving (has a valid target set).
hasNoTarget(CrowdAgent crowdAgent)	When the Agent is ACTIVE and has no target.
isForming(CrowdAgent crowdAgent)	When the Agent is ACTIVE and moving into a formation. (which means he is close enough to his target) Any agent that reaches its destination will move into a forming pattern where it will start to circle the target it reached.

If your agent is returning false to all of these methods, then something is wrong. In this case, you would reset the agent.

public boolean resetMoveTarget(int idx)

This will zero out the target reference, target position, velocity, invalidate the path and set the agents target state to none. You can also do this when the agent reaches its destination. This will have the effect of making the agent idle so it can then be pushed out-of-the-way by other agents. Agents that are not reset will continue their forming pattern and will always attempt to get back to their Crowd defined positions prior to being moved out of position.