1. Nimm jetzt an unserem Uhans - 3. ADVENT - Gewinnspiel teil - Alle Informationen findest Du hier!

2D Spiel - Wegfindung, Ideen

Dieses Thema im Forum "Android Spiele Entwicklung" wurde erstellt von funcoder, 23.01.2010.

  1. funcoder, 23.01.2010 #1
    funcoder

    funcoder Threadstarter Erfahrener Benutzer

    Beiträge:
    218
    Erhaltene Danke:
    38
    Registriert seit:
    15.08.2009
    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
     

    Anhänge:

  2. ko5tik, 23.01.2010 #2
    ko5tik

    ko5tik Android-Experte

    Beiträge:
    620
    Erhaltene Danke:
    40
    Registriert seit:
    14.10.2009
    Phone:
    HTC Hero
    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
     
  3. Dantel, 23.01.2010 #3
    Dantel

    Dantel Android-Hilfe.de Mitglied

    Beiträge:
    105
    Erhaltene Danke:
    12
    Registriert seit:
    26.12.2009
    Phone:
    HTC Hero
    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...
     
  4. Shinigami, 24.01.2010 #4
    Shinigami

    Shinigami Fortgeschrittenes Mitglied

    Beiträge:
    436
    Erhaltene Danke:
    69
    Registriert seit:
    08.04.2009
    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
     
  5. ko5tik, 25.01.2010 #5
    ko5tik

    ko5tik Android-Experte

    Beiträge:
    620
    Erhaltene Danke:
    40
    Registriert seit:
    14.10.2009
    Phone:
    HTC Hero
    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.
     

Diese Seite empfehlen