1. Part 1: Introduction / graphs / applications
1.1. possible problems
1.1.1. limited CPU and memory resources
1.1.2. real time computing
1.1.3. many units to compute paths for / multiagent pathfinding
1.1.4. paths should look realistic
1.1.5. dynamic changes in the environment
1.1.6. heterogeneous terrain and mobile units
1.1.7. incomplete information
1.2. key elements of the baseline approach
1.2.1. graph representation of a map
1.2.1.1. grid maps
1.2.1.2. triangulation map decomposition
1.2.2. search algorithm
1.2.3. heuristic function to guide the search
1.3. map representations
1.4. graph generation
1.4.1. nodes
1.4.2. edges
1.4.3. directed / undirected
1.4.4. weights
1.5. applications
1.5.1. commercial
1.5.2. search & rescue
1.5.3. domestic
1.5.4. route-planing
1.5.5. games
1.5.5.1. Tic-tac-toe
1.5.5.2. Go
1.5.5.3. Chess
2. Part 3: ideas?
3. Part 2: algorithms
3.1. Depth First Search
3.2. Breadth First Search
3.3. Dijkstra's algorithm
3.4. Best First Search
3.5. A*
4. eventuell auslassen
4.1. more algorithms
4.1.1. IDA* (Iterative Deeping A*)
4.1.2. Jump Point Search
4.1.3. grid-based representations
4.1.3.1. TA* (Triangulation A*)
4.1.3.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*