Pathfinding, Navigation & Obstacle Avoidance

 TODO .... Just a draft yet, EXPERIMENTAL

• Search Space Representations
  • Waypoints
    • Waypoints with radius
    • Corner placed waypoints
  • Navigation Meshes
    • N sided polygons
    • Triangular mesh
    • AxisAligned rectangles (used by CounterStrike bot ai)
  • Navigation Volumes
    • Axis Aligned Boxes (NoOneLivesForever)
    • Convex Volumes/Meshes

• Extension of Search Space Representations
  • Hierarchical Pathfinding
  • Portals

• Auto generation of Space Representation scheme

Most auto generation algoritms work on Polygon soups of level but flags and data may be attached to categorize things like floors, small objects, walls etc

• Delaunay Triangle (edge constrained) / Voronoi Diagrams for navigation meshes
• Portal Extraction from polygon soup (like Sinbad's WorldMinion)
• Different algorithms, for auto placement of Waypoints
• Voxelization of polygon soups (article @gamasutra), for AAB Boxes&Rectangles.

• Pathfinding Algoritms
  • A* ...

• Dynamic Obstacle Avoidance
• ...

• Path Postprocessing
  • StringPulling / Path simplification
  • Smoothing paths

• Path following techniques
  • Use stringpulling ...
  • Visibility/Reachability tests
  • Add some kind of inertia effect to moving characters

• Misc Problems
  • How to do Ladders, Stairs, Elevators, Doors etc.

There are various possible solutions to implement these.