funcoder

Hallo Leute,

ich programmier grad an meinem ersten 2D Spiel.
Als Benutzer hat man quasi eine art Draufsicht von oben auf eine Karte mit vordefinierten Wegen. Auf den Wegen stehen fahrzeuge die der Benutzer anklicken kann und dann einen belieben Zielpunkt auswählen kann.

Jetzt mein Problem. Wie realisiere ich so eine Wegfindung. Die Anfangs X,Y und End X,Y Koordinaten weiß ich mir fehlen nur noch die Koordinaten dazwischen...

Im Anhang habe ich eine Grafik die das Problem besser beschreibt.

Mir geht es letzendlich nur um Anregungen und Ideen da ich soetwas noch nie gemacht habe und im Internet bisher auch noch nichts passendes gefunden habe...

Danke

MfG

C0DER

Miniaturansicht angehängter Grafiken

 

ko5tik

Dein Spielraum ist sicherlich diskret - dann hast du einen Graph, auf dem du Pfad suchen kannst.
Wenn due schnell eine Lösung haben willst - macht du Tiefensuche, wenn du den Kurzesten Weg suchst - machst du Breitensuche. Am Liebsten besorg dir ein Paar Klassiker wie Knuth / Dijkstra - da steht viel
interessantes und anregendes drin.

HIer kommt zum Beispiel Breitensuche zum Einsatz:
http://www.yook.de/getlines

Dantel

Hmm, einfach so Schnipp-Schnapp wirst du das nicht machen können - zumindest nicht so, dass du selbst verstehst was du da tust. Ich würde das auch mithilfe eines Graphen realisieren. Aber da muss man natürlich einbisschen Graphentheorie büffeln.

Folgendes könntest du mal lesen:
Graphentheorie ? Wikipedia
Graph (Graphentheorie) ? Wikipedia

Breitensuche ? Wikipedia
Tiefensuche ? Wikipedia

Und dann spezieller für dein Problem:
Bellman-Ford-Algorithmus ? Wikipedia
Dijkstra-Algorithmus ? Wikipedia

Und andere...

Shinigami

Hi,

als kleine Ergänzung zu dem bereits genannten:
A*-Algorithmus ? Wikipedia

Dazu gibt's auch ne Menge Beispiel-Implementierungen im Web. Durfte mich im Rahmen einer Studienarbeit damit befassen. Allerdings spielten damals die Limitierungen eines mobilen Geräts keine Rolle (insbes. RAM-Verbrauch) - A* ist dahingehend nicht optimal.

Gruß,
Shini

ko5tik

Das halte ich für ziemlichen Overkill In meinen Kugelspiel gehe ich so vor:
- Feld ist 9x9, also keine Heuristiken oder Alpha/Beta-Pruning oder dergleichen notwendig

Suchzustand wird in einen 9x9-Array gespeichert. ( als Entfernung von Startpunkt , 0 - noch nicht geprüft )

Da wir Breitensuche machen ( finde den kurzesten Weg) wird eine Queue verwendet ( für Tiefensuche nimmt man ein Stack )

Ablauf:
- platziere Startpunkt in die Queue
{
- nehme ersten Punkt aus der Queue
- falls es der Zielpunkt ist , höre auf mit der Schleife
- nehmen die Nachbarpunkte, die noch nicht bearbeitet sind (0 in dem Status-Array), klatsche in der Status dert von dem aktuellen Punkt + 1, und stelle die an der Ende der Queue
}

Nachdem wir den Letzeten Punkt erreichet haben, gehen wir von dem Zielpunkt zuruck, indem wird die Nachbarpunkte mit dem niedrigsten Wert nehmen.
Kutzeste Weg ist somit gefunden.

Wenn die Queue zwischendurch leer geworden ist , bedeutet es daß es kein Weg gibt.