pathfinding in video games

Get Started. It's Free
or sign up with your email address
Rocket clouds
pathfinding in video games by Mind Map: pathfinding in video games

1. Part 2: algorithms

1.1. Depth First Search

1.2. Breadth First Search

1.3. Dijkstra's algorithm

1.4. Best First Search

1.5. Jump Point Search

1.6. A*

2. Part 1: Introduction / graphs / applications

2.1. possible problems

2.1.1. limited CPU and memory resources

2.1.2. real time computing

2.1.3. many units to compute paths for / multiagent pathfinding

2.1.4. paths should look realistic

2.1.5. dynamic changes in the environment

2.1.6. heterogeneous terrain and mobile units

2.1.7. incomplete information

2.2. key elements of the baseline approach

2.2.1. graph representation of a map

2.2.1.1. grid maps

2.2.1.2. triangulation map decomposition

2.2.2. search algorithm

2.2.3. heuristic function to guide the search

2.3. map representations

2.4. graph generation

2.4.1. nodes

2.4.2. edges

2.4.3. directed / undirected

2.4.4. weights

2.5. applications

2.5.1. commercial

2.5.2. search & rescue

2.5.3. domestic

2.5.4. route-planing

2.5.5. games

2.5.5.1. Tic-tac-toe

2.5.5.2. Go

2.5.5.3. Chess

3. Part 3: ideas?

4. eventuell auslassen

4.1. more algorithms

4.1.1. IDA* (Iterative Deeping A*)

4.1.2. grid-based representations

4.1.2.1. TA* (Triangulation A*)

4.1.2.2. TRA* (Triangulation Reduction A*)

4.2. heuristics (self-discovery approach)

4.2.1. Manhattan

4.2.2. Octile

4.2.3. ALT admissible heuristic

4.2.4. ALTBest-p

4.2.5. dead-end heuristic

4.2.6. gateway heuristic

4.2.7. canonical heuristic

4.2.8. portal heuristic

4.2.9. true distance heuristics ("family of heuristics that store exact distances between pairs of selected nodes")

4.3. hierarchical abstraction on grid maps

4.3.1. HPA*

4.3.2. PRA* (Partial Refinement A*)

4.3.3. HAA*

4.3.4. Block A*