Luki hat mir vor kurzem einen interessanten Link über Navigation Meshes geschickt: http://www.ai-blog.net/archives/000152.html

Der Unterschied zu den meisten herkömmlichen Verfahren ist, dass keine einzelnen Wegpunkte gespeichert werden, über die der kürzeste Weg berechnet wird, sondern Polygone, die angeben, welche Flächen begehbar sind. Dadurch kriegt man im Allgemeinen glaubwürdigere Ergebnisse.

Da ich momentan selbst wieder an einem Spiel arbeite, das auf zuverlässige Wegfindung angewiesen ist, werde ich das wohl in Betracht ziehen. Leider scheint es aber noch keine wirklich gute Referenzimplementierung zu geben. Was im Artikel verlinkt ist, kostet alles und ansonsten habe ich bis jetzt nur den Quelltext von Bitfighter gefunden, der das alles sehr stark vereinfacht und dadurch ziemlich sicher keine optimalen Ergebnisse bekommt.