World Representations for pathfinding

Question 1

What type of model of space do we need for World Representations for pathfinding?

Answer 1

Discrete (countable) models of space

Question 2

What do we need to do in respect to representing the Level geometry and character’s limitations?

Answer 2

They need to be translated to nodes/states and connectios/actions

Question 3

What is Localization?

Answer 3

Process of localizing the coordinates on the game world that corresponds to a node in the Graph

Question 4

What types of discrete models of space are usually used in games?

Answer 4

Tile Graphs
Points of visibility
Navigation Mesh

Question 5

What is Quantization?

Answer 5

Translation of a position in the game world into a node of the pathfinding graph

Question 6

What is Quantization Generation?

Answer 6

Process of dividing a continuous space into regions and connections

Question 7

What is division scheme validity?

Answer 7

A division scheme is valid if all points in two connected regions can be reached from each other in a direct line (LOS)

Question 8

How is the world splitted with tile graphs?

Answer 8

The world is splitted into regular regions in the form of squares and sometimes hexagons

Question 9

What is the division scheme for tile graphs?

Answer 9

A node corresponds to a tile

The connections to responds to the adjacent tiles

Question 10

Why are Quantization and Localization needed?

Answer 10

Because the pathfinding algorithms work with graphs

Question 11

What discrete model is easier to implement both quantization and localization

Answer 11

Tile-based Graphs

Question 12

Define Quantization on Tile Graphs

Answer 12

current_position/number_of_tiles

Question 13

Define Localization on Tile Graphs

Answer 13

node * number_of_tiles + number_of_tiles/2 (center of the tile)

Question 14

Define Validity on Tile Graphs

Answer 14

Only empy nodes are connected in the graph

Or partially blocked tiles depending on the shape of the blockage

Question 15

Advatanges of Tile graphs

Answer 15

Easy to generate

Question 16

Disadvantages of Tile Graphs

Answer 16

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)

Question 17

Dirichlet Domains Division Scheme

Answer 17

Set of characteristic points in a level specified by the level designer

Question 18

How are Connections created in Dirichlet Domains

Answer 18

Manually
By finding intersections of borders of different domains
By applying ray casts between characteristic points

Question 19

Define Quantization on Dirichlet Domains

Answer 19

Find closes characteristic point

Question 20

Define Localization on Dirichlet Domains

Answer 20

Position of the characteristic point of node

Question 21

Defnine Validity on Dirichlet Domains

Answer 21

No way to ensure validity. The designer is responsible for ensuring valid dirichlet domains

Question 22

Advantanges of Dirichlet Domains

Answer 22

Easy to program and change

High level control over the pathfinding graph

Question 23

Disadvanteges of Dirichlet Domains

Answer 23

Validity problems

Requires a lot of manual effort

Question 24

Division Scheme on Navigation Mesh

Answer 24

Polygon-as-node

Connections corresponds to shared edges between polygons

Question 25

Define Quantization on Navigation Mesh

Answer 25

Find the polygon that contains the specified position

Question 26

Define Localization on Navigation Mesh

Answer 26

Use geometric center of the polygon that represents the average position of its vertices

Question 27

Define Validity on Navigation Mesh

Answer 27

Depends on the design of the level designer

Question 28

Advantages of Navigation Mesh

Answer 28

Reuse of the mesh geometry of the floor of a level
Walls and ceilings mesh can be part of the graph
Since navmesh represents the walkable area we can do path post-processing by testing if the resulting path is inside the navmesh

Question 29

Disadvantages of Navigation Mesh

Answer 29

May require additional processing to take into account the agent’s geometry

Question 30

What is an alternative representation for navmesh

Answer 30

edge-as-a-node