I just finished reading an excellent article on how to fix pathfinding in games. The author presents a number of excellent examples of how today's pathfinding can break (with examples from legendary games like Oblivion and Half Life 2), and offers a great solution: use a navigation mesh instead of a waypoint graph. Genius.