finde den kürzesten weg

lemma245

Grünschnabel
Hallo,

ich arbeite an einen Programmierprojekt
Nun bin ich bei der Programmierung eines Spieles an meine Grenzen gestossen. Das Spiel heisst Atomica.

Ich habe die letzten Wochen über keinen Ansatz für die Probleme "Finde den kürzesten Weg zwischen zwei Feldern auf den Atomica-Feld" oder "Berechne den Streckenzug zwischen dem ausgewählten Feld und dem Feld, worüber sich der Mauszeiger gerade befindet" gefunden. Dieser Zug sollte dann auch graphisch angezeigt werden

Ich dachte zuerst an den Algorithmus von Dijkstra in Bezug auf den kürzesten Weg . Aber: Dieser Algorithmus geht von einer Menge von Knoten aus, die durch Kanten (mit Kosten bewertet) verbunden sind. Dann kann man wunderbar zwischen allen Paaren den kürzesten Weg finden.
Okay, die Knoten sind in diesem Falle die Felder auf dem Atomica-Spielfeld und die Kosten sind die Anzahl der Felder, um von Feld x zum Feld y zu gelangen. Man könnte für diesen Algorithmus alle unbesetzten Felder + das des ausgewählten Atoms betrachten. Aber wie kommt man dann zu den Kosten zwischen den Feldern? Soll etwa jedes Feld mit jedem verglichen und so die Abstände zwischen den Feldern berechnet werden (Achtung: sehr hohe Laufzeit)?

könnte Ihr mir bei der Lösung helfen? Das speilbrett habe ich ersschaffen es besteht aus 10x10 feldern aber die grafische Oberfläche ist mit Java-Swing zu realisieren . Die Entwicklung von grafisch ansprechenden Benutzungsoberflächen ist ausdr¨ucklich erwünscht. Diese dürfen aber nicht auf zusätzliche Bibliotheken (wie z. B. Java3D, OpenGL etc.) zurückgreifen

gibt es jemanden, der mir helfen kann
benni
 

Jey

Mitglied
Hi!

Ich hab da mal ein gutes Tutorial gefunden, in dem die Implementierung eines für Spiele geeingneten Suchalgorithmus gezeigt wird. Der verwendete Algorithmus heißt A* (siehe auch http://de.wikipedia.org/wiki/A*). Da wird das ganze mit den Kosten näher beschrieben. Ist zwar für die etwas exotische Programmiersprache einer 3D-Engine gedacht, der Grundgedanke jedoch sollte rüberkommen!

Das Tut findest du hier, da gibts eine zip namens "PathGuru", da ist unter anderem eine PDF drin, in der der ganze Algorithmus + Implementierung beschrieben wird:
http://www.thekidgame.com/Locoweed3DGS/pathfinding.htm
 

lemma245

Grünschnabel
Ich hab nen Problem der algorithmus ist in C++ und in englisch. kann nur das Wersentliche

lesen.

mir fällt nichts ein.

danke
 

zeja

Erfahrenes Mitglied
Also ein wenig selber suchen sollte wirklich helfen...

A* ist wirklich ein sehr guter Algorithmus dafür und bei Wikipedia ausführlich und auf deutsch beschrieben: http://de.wikipedia.org/wiki/A*-Algorithmus

10x10 ist abgesehen davon nicht wirklich groß. Da sollte so ziemlich jeder Algorithmus recht schnell sein. Eine einfache Tiefensuche sollte da fast schon ausreichen.
 

Jey

Mitglied
Ja, stimmt. Bei 10x10 Feldern sollte eigentlich rekursives Backtracking o.ä. ausreichen.