dynamic geometry means dynamic graphs
a change to the geometry need to be applied to the graph or the graph has to be partially re-generated
changing the graph potentially requires recalculation of all paths relying on it
dynamic | modified or generated at runtime |
navmesh | set of polygons representing navigatable surface |
geometry | the world the player can see |
NPC | non-player-character (alias: agent, bot, character) |
AI | all npcs, includes those without visual representation |
dynamic geometry means dynamic graphs
a change to the geometry need to be applied to the graph or the graph has to be partially re-generated
changing the graph potentially requires recalculation of all paths relying on it
big paying target group is more important than a good game
fun for the target player group is good
multiplayer is more fun than "bad" AI
multiplayer is cheaper than "good" AI
lots of time pressure for the release
the world is covered in connected convex polygons
each point inside a polygon is walkable space
the center points of the polygon edges are the nodes in the graph used by A*
each node is connected to all other nodes of both polygons
cells contain polygons representing static geometry (1:n)
cells keep track of overlapping dynamic geometry (m:n)
on moving geometry the cells it is overlapping are updated
reset cell to base state
project objects convex hull onto navmesh plane
clip object hull aginst cell hull to get part inside the hull
clip object hull inside the cell hull with the non-hull edges of the polygons within the cell
update the mesh
graph used by A* is updated for the cell
cannot introduce new walkable terrain
needs all polygon within a cell to be within one plane
no multi-floor geometry
start with the agent at a seed position
move the agent systematically through the world using all of his movement capabilies
let the game engine handle interaction with the geometry
graph edge costs are calculated base on the result returned by the game engine
supports almost any ability that can affect movement
complexity greatly increases with amount of capabilies
seed positions affect the quality
places the characters bounding box at every position and checks for validity
determine edge cost for two adjacent valid positions using predefined rule set
edge cost are calculated on another rule set
rule sets need to be changed when movement is changed within the engine
use of heightmaps can greatly reduce the amount of collision checks required
example of basic dynamic use: Left 4 Dead Infected Climbing (Slide 29ff)
no collision checks
connect verticies of the collision model with direct line of sight to each other
world is segmented so only parts changing are recalculated
walkable surfaces are determined using orthogonal projection on the collision model
movement-based expansion is used to stich walkable surfaces together
a self-building dictionary keeps track of movement-based expansion results to skip them for future calculations
get all non-small (one or more bounding box axis above a threshold) collision objects for rendering
render a height map from above
determine the highest "floor"
render its "ceiling"
set the maximum render height to just below the height of the "floor"
repeat 2. to 5. until the bottom of the scene is reached
additionally get the previously ignores small objects for further rendering
for each "roof"-"floor" combination
render everything between "roof" and "floor" including the "floor" to get an obstacle heigt map
Finding Graph Nodes
ignore pixels with a "roof"-"obstacle" difference smaller than the character size
extrude "floor" and "obstacle" height by half the characters size
generate nodes for pixels where the character size can fit between extruded "roof" and "obstacle" height for all pixels in his bounding shape
put the remaining places to a movement test to determine validity for a node
with multiple character sizes start with the highest and widest bounding shapes to save time
Connectivity and Cost Filling
adjacent nodes get connected according to the set of rules from the self-building dictionary
the rule with the lowest cost is used for creating the edge between the nodes
also connects "floors" connectable by existing rules
all positions undecidable by the prevoius methods are used as seed positions for movement-based expansion
perfrom movement-based expasion for every agent type at design time
update at runtime whenever movement-based expasion is used to fill gaps
path creation
lazy generation
graph separation
traps
