Hi,

ich programmiere grad für www.sneady.de eine KI für eine Schlange ... jetzt habe ich ein Labyrinth, wo meine Schlange drin ist und wo auch unterschiedlich viele Goodies drin sind!
Wo ich die Goodies finde bzw ob ich sie erreichen kann, finde ich ja per Backtracking heraus, was auch keine Sache ist.
Jetzt möchte ich aber gerne den kürzesten Weg von der Schlange zu einem Goodie wissen. Wie kriege ich sowas heraus? Habe mir überlegt schon beim backtracking den Weg zu speichern, die Sache ist ja aber die, dass das Backtracking nicht unbedingt den idealsten Weg zum Goodie findet! Welchen Algorithmus muss ich anwenden, damit ich den idealsten Weg finde
Wäre für eine Lösung echt mehr als dankbar!

Ein Standardalgorithmus für singel source shortest path Probleme ist der Dijkstra Algorithmus. Es gibt noch Erweiterungen, aber für die Grundlagen ist das schon sehr brauchbar: http://de.wikipedia.org/wiki/Dijkstras_Algorithmus