Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
41 Cards in this Set
- Front
- Back
|
What is a navigation grid |
2D grid representing the world Simple but intuitive Each cell can have flags/weights Objects occupy one or more cells |
|
|
Advantages of a navigation grid |
Fast lookup Easy acces to neighbouring cells Complete representation of the world |
|
|
Pathfinding Evaluation Criteria |
Quality of final path - distance, speed, safety Resource consumption during search - CPU (complexity), RAM (memory) Is it complete? (Guaranteed to find a path if there is one) |
|
|
Random Walk |
Take a step in random direction If goal is reached, stop search Repeat until goal reached |
|
|
Random Trace |
Move towards the goal If goal is reached, end search If obstacle encountered trace around obstacle until a free path in goal's direction is found Repeat until goal reached |
|
|
Evaluate Random Trace |
Unlikely to be at all optimal Not complete Can get stuck in infinite loops Uses very little memory |
|
|
A* Pathfinding |
F = G + H F = cost of moving through node G = cost of path from start to current point H = estimated cost to target from current node |
|
|
Evaluate A* |
Will find shortest path Uses lots of memory - problem with large maps Complete algorithm Can affect cost of traversal with terrain cost, influence maps etc Quality of path depends on quality of heuristic |
|
|
Dijkstra's |
Variation of A* - just misses the heuristic H cost Finds shortest path for each node until end is reached then traces back |
|
|
Seek and Flee |
Seek = steer towards target Desired velocity - vector from character to static target Flee = steer away from target Desired velocity = opposite of seek |
|
|
Pursuit |
Similar to seek but with a mobile target Predict future position to use as target for seek Evasion - uses flee |
|
|
Path steering |
Pathfinding algorithm gives path Use nodes as targets Set next node as target When target reached update target until goal reached |
|
|
Path smoothing |
Give each node a radius When entity is within radius update path |
|
|
Tactics |
Units - AI and human players Terrain - what positions have influence over other positions e.g. high ground Specific tactical locations - safe fall-back positions |
|
|
Terrain analysis |
Extract useful data from structure of terrain Either offline (cheap but static terrain) or real-time (expensive but dynamic terrain) Traversal difficulty, location visibility, degree of shadow, ease of escape, choke points |
|
|
Influence Maps |
Objects have influence over areas of the map Own units have positive influence Enemy units have negative influence Aids decision making |
|
|
Unit influences |
Strength of unit Range of fire of unit Speed of movement Less influence further away from unit |
|
|
Total influence map |
Compute total of influences - positive and negative Results might not be realistic - do lots of low-strength units == one high-strength unit? Other alternatives may be slower to compute |
|
|
Tactical Locations |
Retreat/rally points - prevent routs Cover points - marked locations behind barrels/crates etc to hide/cover a player Shadow areas - hide a player in a stealth game Sniper locations Minefields/chokepoints/ambush locations etc |
|
|
Tac Loc principles |
Generate locations - procedural or manually by designer Assign types e.g. cover point, rally point etc Can use as destinations Can use as waypoints for pathfinding (or influences for places to avoid) |
|
|
Bird-oids/BOIDS |
Useful for modelling animal behaviour (flocks, herds etc) Each boid is a particle with orientation Behaviour of one particle depends on others STEERING - usually limited options (steer left/right and speed up/down) |
|
|
BOIDs steering |
Single BOID - maneuvers based on positions and velocities of flock-mates Flocking is emergent behaviour Separation - avoid crowding Alignment - steer toward average heading Cohesion - move towards average position |
|
|
BOIDs algorithm |
For each BOID in list: vector1 = calc from separation rule vector2 = calc from cohesion rule vector3 = calc from alignment rule totVel = initVel + vec1 + vec2 + vec3 pos = initPos + totVel * deltaTime |
|
|
Cohesion Rule |
Calculate centre of mass of flock Add pos of each boid and divide by number of boids Move towards this |
|
|
Alignment Rule |
Calculate average velocities and add to each boid |
|
|
Additional Boid rules |
Goal setting - specify location, generate vector towards it Wind/water current - rule just returns a vector for wind/water strength Limiting speed - limit boids to a max speed Bounding positions - specify physical limits Flock scattering - negate cohesion rule Perching - allow boids to be motionless Tendency away from point - vector points away from point |
|
|
Group Pathfinding |
Group of units need to get from A to B Should they arrive together? Formations? Should they take the same route? How? How to get through a narrow gap? Move at speed of slowest unit? |
|
|
Hierarchical Group Formation |
Commander responsible for generating path Unit and formation movement handled within group |
|
|
Crowd Simulation |
Particle systems - thousands of individuals, no intelligence, respond to global forces only Flocking systems - limit int, collision avoidance, local control Agent-based and Social Force - intelligent individuals, rule-based social behaviours Cellular automata - world is a grid, one entity per cell, simple states govern movement from cell to cell |
|
|
Vector Field Pathfinding |
Create distance map (scalar field) Create velocity map (vector field, gradient of dist map) Move entities vel_vec = vector_field(x,y) * desired vel |
|
|
Social Forces |
Describes social attractions/repulsions Used to affect movement of individuals Entities try to move as efficiently as possible to destinations Pedestrians want to move quickly and avoid others Maintain comfortable distance from obstacles May be attracted to other peds or signs, posters etc |
|
|
Scripting |
Dynamic language Compiled at run time Simpler language Rapid development but slow execution Glue language - unify system components and writing game code |
|
|
Advantages of scripting |
Game-specific code goes in scripts Don't have to recompile engine every time Easier to roll out updates/DLC Non-programmers can use it easier |
|
|
Typical language properties |
Natively supports high level concepts that programming languages don't - time, state, properties Pointlerless - auto garbage collection No worries about memory leaks or seg faults Safe client-side execution - harder to break things and easier to fix |
|
|
Language properties 2 |
Enables rich, high level programming in terms of game objects and interactions rather than worrying about bits and pixels Slower than native languages but doesn't need to be fast |
|
|
Initialisation Scripts (ST1) |
Executed at program start-up to init subsystems and set parameters |
|
|
Trigger-Only Induced Scripts (ST2) |
Event Handler Scripts - scripts executed when event is triggered Event Oriented Scripts - scripts that define events as well as event handlers |
|
|
Traditional Program Scripts (ST3) |
Looping Scripts - repeatedly executed (e.g. once per frame) Regular Scripts - execute once, run in parallel to host application |
|
|
How is script executed? |
Compiler part translates high-level script program into intermediate low-level language (interpreter code) A program that emulates functionality of virtual computer with desired features interprets and executes interpreter code |
|
|
Defining a Language |
Set of rules (or formulas) that define formally correct sentences Allows us to determine grammatical correctness of a sentence Provides structure necessary for understanding its meaning Syntax (structure) and semantics (meaning) are inextricably linked |
|
|
Backus-Naur Form notation (BNF) |
Non-terminal symbols Terminal symbols Meta-symbols |
