Table of Contents
The server can move entities via either navigation functions, or a simple moveToPoint.
Navigation provides full path finding using special mesh data generated by NavGen, while moveToPoint simply moves the entity in a straight line, without taking obstacles or terrain into account.
This is the simplest movement system available — taking a destination, it moves the entity in a straight line until that point is reached.
An example of an entity that uses this mechanism is the MovingPlatform , which follows a series of patrol nodes, using moveToPoint at each one to move to the next.
self.moveToPoint( self.patrolNode[1], self.travelSpeed, 0, self.faceDirection, True )
cell/MovingPlatform.py
Note
For details on the MovingPlatform entity,
see the document How To Build a Server-Controlled Moving Platform.
Navigation is a path-finding service available to entities running on the CellApps. Navigation uses a heuristically guided breadth first search (A*), initially across the chunks, and then in the navigation mesh within the chunks.
For detailed information on all functions below, see the CellApp Python API.
Before using any navigate function, you should check that the destination can be reached. The function canNavigateTo finds the nearest point to the destination that can be reached by traversing the navigation mesh or None if no path can be found. If navigation is attempted to a point that cannot be reached, then an exception will be raised by the navigateStep function.
This function creates a movement controller that moves the entity toward the destination. Each time the entity enters a new navpoly, or travels the specified maximum distance, the controller stops and calls the onMove callback.
Note
The paths generated by calling navigateStep are cached, making subsequent calls to the same destination inexpensive.
To reach the destination, you will have to re-call navigateStep each time the entity stops.
self.controllerId = self.navigateStep( destination, velocity, maximumMovement )
cell/Guard.py
NavigateFollow is an older function for navigating relative to another entity's current position. New code should use navigateStep.
To demonstrate the navigation mechanism, we have constructed a simple example. The example entity randomly picks a location around its current position, then navigates to it. Upon arrival, it chooses a new destination and continues.
The entity could be created before the rest of the chunk data is loaded. If you use navigation immediately in the __init__ method, then the start location might be unresolved, causing an exception. Instead, we wait for the navigation mesh to load, using a timer and testing with canNavigateTo.
def __init__( self ): BigWorld.Entity .__init__( self ) self.destination = self.position self.addTimer( 5.0, 0, RandomNavigator.TIMER_WAITING_FOR_NAVMESH ) def onTimer(self, timerId, userId): if self.canNavigateTo( self.position ) == None: self.addTimer( 5.0, 0, RandomNavigator.TIMER_WAITING_FOR_NAVMESH ) else: self.navigateStep( self.destination, 5.0, 10.0 )
cell/RandomNavigator.py
Example navigation during chunk data load
Calling the first navigateStep will result in the onMove callback being triggered. At this time, the entity may or may not have reached its destination, so we check how close the entity is. In this example, we require it to be within 0.1 metre of the target before picking a new destination.
Note the use of canNavigateTo — this function clamps the destination to the point closest to the destination, and that is accessible via the navigation mesh. The entity then perpetually follows this cycle of picking a destination, running to it and then picking another.
def onMove(self, controllerId, userId):
if ( self.position - self.destination ).length > 0.1:
self.navigateStep( self.destination, 5.0, 10.0 )
else:
self.destination = None
while self.destination == None:
randomDestination = (
self.position.x + random.randrange(-400, 400, 1.0),
self.position.y,
self.position.z + random.randrange(-400, 400, 1.0) )
self.destination = self.canNavigateTo( randomDestination )
self.navigateStep( self.destination, 5.0, 10.0 ) cell/RandomNavigator.py
To be able to correctly display the entity on the client machine, we require two things:
-
A model.
-
The correct filter.
The default filter is DumbFilter, which simply places the entity at the location most recently received from the server, thus producing a stuttering motion as it moves about the world. You might also notice that its height above the ground appears to go up in steps — this is the movement of the entity on the server as it traverses the navigation mesh covering slopes.
Instead, we will use AvatarDropFilter, which
produces fluid movement for the Action Matcher, with the addition that
it locks the entity to the ground. For details on
AvatarDropFilter, see AvatarDropFilter.
def onEnterWorld( self, prereqs ): self.model = BigWorld.Model( RandomNavigator.stdModel ) BigWorld.addShadowEntity( self ) self.filter = BigWorld.AvatarDropFilter() def onLeaveWorld( self ): BigWorld.delShadowEntity( self ) self.model = None
client/RandomNavigator.py
To show the method of converting an entity using either navigate or navigateFollow to use navigateStep, we have provided a simple example. It has two behaviours, gated by a think method: A patrol behaviour, which moves between two UserDataObjects using navigate and a follow behaviour, which follows a supplied entity ID, but stops and waits if it gets too close, using navigateFollow.
navigateFollow was used to path to a point relative to an entity. Here is a simple example of using navigateFollow to follow an identified entity around.
# Follow brain def follow( self ): # If self.targetID doesn't exist, switch to patrol mode if not BigWorld.entities.has_key( self.targetID ): self.stopFollow() return # If target isn't in this space, switch to patrol mode target = BigWorld.entities[ self.targetID ] if target.spaceID != self.spaceID: self.stopFollow() return # If we've arrived, wait here for target to move away if self.closeEnoughToTarget(): self.cancel( "Movement" ) self.addTimer( 5 ) return # Follow our target target = BigWorld.entities[ self.targetID ] try: self.navigateFollow( target, FOLLOW_ANGLE, FOLLOW_DISTANCE, VELOCITY, 500, 500, True, 0.5 ) except ValueError, e: # No path found self.cancel( "Movement" ) self.addTimer( 5 ) def closeEnoughToTarget( self ): target = BigWorld.entities[ self.targetID ] return distance( self.position, target.position ) <= FOLLOW_DISTANCE def onMove( self, controllerID, userData ): self.think()
cell/ElPolloDiablo.py - Before
Since navigateFollow and navigateStep share the same controller internally, the changes are quite simple. We replace the block of code marked # Follow our target with the following block of code:
# Follow our target yaw = target.yaw + FOLLOW_ANGLE offset = ( FOLLOW_DISTANCE * math.sin( yaw ), 0, FOLLOW_DISTANCE * math.cos( yaw ) ) dest = self.canNavigateTo( target.position + offset, 500, 0.5 ) if dest is None: # No path found self.cancel( "Movement" ) self.addTimer( 5 ) return self.navigateStep( dest, VELOCITY, 500, 500, True, 0.5 )
cell/ElPolloDiablo.py - After
The new calculation of dest is the same as that performed by navigateFollow on the supplied entity. We've also made use of the canNavigateTo method to ensure that we attempt to navigate to a reachable spot, now that we have access to the destination point.
As should be clear here, navigateStep is a more flexible interface to navigateFollow's existing behaviour, giving more control over movement behaviour and exposing the intended destination to Python scripting code.
navigate was used to start an entity moving to a target point, pathing along the navigation mesh, and would callback to the entity when either the target point was reached, or if the navigation mesh was unable to find a suitable path. Here is a simple example of using navigate to path between two points.
# Patrol brain def patrol( self ): # If we haven't got any nodes, find a pair if self.nextNode is None: self.setupNodes() if self.nextNode is None: # If we can't find a pair of nodes, wait 5 seconds and try again self.cancel( "Movement" ) self.addTimer( 5 ) return # If we've arrived, turn around if self.closeEnoughToNode(): self.swapNodes() # Navigate to slightly closer than self.closeEnoughToNode() self.navigate( self.nextNode.position, VELOCITY, True, 500, 0.5, PATROL_DISTANCE * 0.8 ) def closeEnoughToNode( self ): target = self.nextNode return distance( self.position, target.position ) <= PATROL_DISTANCE def setupNodes( self ): self.prevNode = None self.nextNode = None closest = None dist = 500 for i in BigWorld.userDataObjects.values(): if i.__class__.__name__ != "PatrolNode" or len(i.patrolLinks) == 0: continue if distance( self.position, i.position ) < dist: closest = i dist = distance( self.position, i.position ) if closest is not None: after = closest.patrolLinks[ 0 ] while distance( closest.position, after.position ) < PATROL_DISTANCE * 3: after = after.patrolLinks[ 0 ] if after is None or after.uuid == closest.uuid: after = None break if after is not None: self.prevNode = closest self.nextNode = after def swapNodes( self ): temp = self.nextNode self.nextNode = self.prevNode self.prevNode = temp def onNavigate( self, controllerID, userData ): # Arrived. Turn around. self.swapNodes() self.think() def onNavigateFailed( self, controllerID, userData ): # Can't get there. Turn around self.swapNodes() self.think()
cell/ElPolloDiablo.py - Before
Similarly to replacing navigateFollow, we can replace the use of navigate very simply. We replace the block of code marked # Navigate to slightly closer than self.closeEnoughToNode() with the following block of code:
# Navigate towards self.nextNode.position dest = self.canNavigateTo( self.nextNode.position, 500, 0.5 ) if dest is None: # No path found self.cancel( "Movement" ) self.addTimer( 5 ) return self.navigateStep( dest, VELOCITY, 500, 500, True, 0.5 )
cell/ElPolloDiablo.py - After
We use the canNavigateTo method to identify a waypoint position on the navigation mesh that matches our desired destination, and then attempt to navigate towards it. This is similar to what navigate does internally, except that we receive an onMove callback every time we enter a new navpoly, or have travelled the specified maximum distance.
These more frequent callbacks allow the script-level code to control navigation at a finer level, dealing with changed priorities or moving targets without needing to either be triggered by an external event or wait until the previously-selected destination is reached.
At this point, the onNavigate callback is unused, and can be removed. onNavigateFailed can be renamed to onMoveFailure. onMove remains unchanged, and simply calls self.think() as seen in the above navigateFollow example.
If navigateStep is called again during the onMove callback, the existing Controller will be reused if possible. This helps to ensure that calling navigateStep more frequently than navigate would be for the same navigation activity does not cause extra load on the CellApp through repeated Controller object creation.