World Representations for pathfinding Flashcards
What type of model of space do we need for World Representations for pathfinding?
Discrete (countable) models of space
What do we need to do in respect to representing the Level geometry and character’s limitations?
They need to be translated to nodes/states and connectios/actions
What is Localization?
Process of localizing the coordinates on the game world that corresponds to a node in the Graph
What types of discrete models of space are usually used in games?
Tile Graphs
Points of visibility
Navigation Mesh
What is Quantization?
Translation of a position in the game world into a node of the pathfinding graph
What is Quantization Generation?
Process of dividing a continuous space into regions and connections
What is division scheme validity?
A division scheme is valid if all points in two connected regions can be reached from each other in a direct line (LOS)
How is the world splitted with tile graphs?
The world is splitted into regular regions in the form of squares and sometimes hexagons
What is the division scheme for tile graphs?
A node corresponds to a tile
The connections to responds to the adjacent tiles
Why are Quantization and Localization needed?
Because the pathfinding algorithms work with graphs
What discrete model is easier to implement both quantization and localization
Tile-based Graphs
Define Quantization on Tile Graphs
current_position/number_of_tiles
Define Localization on Tile Graphs
node * number_of_tiles + number_of_tiles/2 (center of the tile)
Define Validity on Tile Graphs
Only empy nodes are connected in the graph
Or partially blocked tiles depending on the shape of the blockage
Advatanges of Tile graphs
Easy to generate
Disadvantages of Tile Graphs
L. Large number of nodes
P. Partial Blockage tiles
P. Plans returned are usually blocky and irregular (we need to usually post process the path and smooth it)
Dirichlet Domains Division Scheme
Set of characteristic points in a level specified by the level designer
How are Connections created in Dirichlet Domains
Manually
By finding intersections of borders of different domains
By applying ray casts between characteristic points
Define Quantization on Dirichlet Domains
Find closes characteristic point
Define Localization on Dirichlet Domains
Position of the characteristic point of node
Defnine Validity on Dirichlet Domains
No way to ensure validity. The designer is responsible for ensuring valid dirichlet domains
Advantanges of Dirichlet Domains
Easy to program and change
High level control over the pathfinding graph
Disadvanteges of Dirichlet Domains
Validity problems
Requires a lot of manual effort
Division Scheme on Navigation Mesh
Polygon-as-node
Connections corresponds to shared edges between polygons
