> Reference Database

Artificial Intelligence/Path finding

.NET  7
Artificial Intelligence  7
  Group behavior  2
  Path finding  16
    A* and its derivatives  6
  Pattern recognition  1
  Steering behavior  2
  World interaction  4
Audio  0
  DirectX  8
  DSP  5
  Ogg Vorbis  2
  OpenAL  1
  Windows  1
Computer Science  2
  Algorithms & data structures  12
    BSP trees  8
  Encryption  12
  Randomness & noise  11
Data storage  4
  File formats  14
    Image  10
  Resource files  2
Game Development  20
  Cheat & crack prevention  10
  Input  3
  Timing  4
Graphics  27
  Character animation  6
  DirectX  24
    Optimizing  8
  Illumination  5
    Deferred lighting  7
    Global illumination  8
    Lighting models  6
    Screen Space Ambient Occlusion  4
    Shadow maps  18
    Shadow volumes  15
  Image processing & synthesizing  19
  Non-polygonal rendering  3
    Ray tracing  3
  OpenGL  12
  Particle systems  7
  Shaders  32
  Simulation  4
    Cloth  2
    Clouds & sky light  7
    Fire & smoke  4
    Liquids  12
  Surfaces & Meshes  7
    Implicit surfaces  6
    Parametric curves & surfaces  7
    Polygon reduction & LOD  3
    Subdivision surfaces  7
  Terrain  7
    Continuous LOD  12
    Generating data  4
    Voxel engines  2
  Text  6
  Transparency  1
  Visibility determination  16
Languages  5
  Assembler  20
  C & C++  25
    C++ exceptions  5
    Calling conventions  11
    Debugging  5
    Memory management  7
    Optimizations  6
  C#  4
  Creating your own language  13
    Garbage collection  7
  D  2
  Java  4
  Scripting  3
    JScript & VBScript  1
    Lua  6
    Other languages  8
    Perl  2
    Python  5
    Ruby  4
Mathematics  3
  Fourier transform  4
  Geometry  6
  Linear algebra, vectors & matrices  9
  Wavelet transform  5
Object design  3
Physics  5
  Body dynamics  8
  Collision detection  10
    Polytopes  6
Platform  2
  Linux  1
  Mac  2
  Windows  13
    COM, ATL & WTL  8
    Dynamically loaded libraries  6
    Hooks  5
    Input  2
    Networking  6
    Screensavers  3
    Services  1
    Shell  2
    Small executables  3
    Windows  8
Web Technologies  8

AI Madness: Using AI to Bring Open-City Racing to Life
December 2000 - Joe Adzima
The title pretty much says it all for this interesting article.

An optimal pathfinder for vehicles in real-world digital terrain maps
Markus Jönsson

Pawn Captures Wyvern: How Computer Chess Can Improve Your Pathfinding
Mark Brockington

Smart Moves: Intelligent Path-Finding
Bryan Stout

Polygon Soup for the Programmer's Soul: 3D Pathfinding
April 2002 - Patrick Smith
This article describes how the data needed for path-finding algorithms can be automatically generated from an arbitrary 3D level. It also goes on to explain how to use this data to find shortest paths for both human entities and vehicles. All in all, a good article with several good ideas explained.

Path Planning from Start to Finish
2002 - Alex Champandard
This article discusses advantages and disadvantages as well as implementations of various path-finding algorithms. Examples are Dijkstra, A-Star, All-Pairs-Shortest-Path, etc.

The Quake III Arena Bot
June 2001 - Jean Paul van Waveren
This article explains how the Q3A bots work, including path finding, decision making, chat bot, team work, etc.

Minimax explained
July 2002 - Paulo Pinto
This is a good article that explains the Min-Max algorithm, as well as discussion of optimizations, for example Alpha-Beta cut-offs.

Emergent Intelligence
Aug 2002 - Danilo Benzatti
This article discusses the intelligence of ants and how it can be used to model an AI capable of finding the shortest path.

Amit's Thoughts on Path-Finding
Nov 2001 - Amit J Patel
This page has plenty of interesting tips and ideas on how to improve your path-finding algorithm.

Amit's Game Programming Information

Fixing Pathfinding Once and For All
Jul, 2008
A very good article showing the advantages of navigation meshes over other types of path info.

Recast & Detour
A tool kit for pathfinding. Includes a tool for building navigation meshes as well as a library to do pathfinding in it.

Navigation Mesh Reference
This article explains briefly how the navigation mesh in the Unreal 3 engine works, and how it is constructed.

Fixing Pathfinding Once and For All
July, 2008 - Paul Tozour
This article gives strong arguments as to why navigation meshes is better than waypoint graphs. It doesn't go into technical detail on either implementation but do offer references to other related articles that do.

Study: Navigation Mesh Generation
2010 - Stephen A. Pratt
This article and source code explains how navigation meshes can be automatically generated from 3D world meshes.