Einfaches Pathfinding
lima-city → Forum → Programmiersprachen → C/C++ und D
algorithmus
beispiel
code
karte
knoten
list
point
pos
problem
punkt
queue
roboter
routine
sagen
speichern
start
startpunkt
status
url
weg
-
Hallo,
ich schreibe in letzter Zeit an einem Spiel. Dort brauche ich nun (vorerst einmal) eine möglichst einfache möglichkeit, eine Wegfindung zu realisieren. Also nicht das allereinfachste (einfache Luftlinie ;) ) sondern schon mit ein paar Vorraussetzungen:
Zu beachten:
- Zweidimensionales umfeld
- Der Weg soll sich entlang von bestimmten Marker-Punkten (Beispiel: Straße) entlang schlängeln.
- Zu bevorzugende Wege, von denen nur abgewichen wird, wenn es nicht anders geht. (oder halt das Gegenteil - wege die nur beschritten werden, wenn es gar nicht anders geht.)
- Wege, Biegungen, Gabelungen, etc. sind nur im 90°-Winkel vorhanden.
Idee: Nun habe ich mir dazu natürlich schon so meine Gedanken gemacht. Mein erster Ansatz wäre, mich dabei von Punkt zu Punkt vorzuarbeiten. Ich nehme also erstmal den Startpunkt, bei welchem ich mir anschaue, welche Marker-Punkte in geringster Distanz liegen. Nun wird bei denen jeweils untersucht, welcher die geringste Distanz zum Zielpunkt hat. Zu dem wird sich dann zuerst bewegt. Von dort aus geht es dann weiter im Klartext.
Problematik: Ich weiss prinzipiell nicht, welcher Marker-Punkt ausgewählt wird. Wenn ich also annehme, der Startpunkt liegt auf einer Kreuzung, gibt es 4 Markerpunkte in direkter Umgebung. Alle 4 müssen überprüft werden. Liegt der Startpunkt nun auf einer "Weggabelung", also nur 3 Mögliche Wege, müssen nur noch 3 Wege überprüft werden... etc.
Nun ja, ich habe mir dazu einige Algorithmen angeschaut, bie Beispielsweise den A*-Algorithmus oder den von Dijkstra. Leider sind diese mächtig aufwändig. Ich durchschaue da noch nicht ganz die "Logik" dahinter....
Naja, ich würde mich über Ideen und Umsetzungsvorschläge in C/C++ freuen. Quellcodes wären schön, erwarte ich aber nicht. Eine logisch nachvollziehbare Idee reicht vollkommen ;) -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Schönes interessantes Thema. Da würde ich gerne Code beisteuern, hab aber noch eine Frage:
Ist die Karte diskret oder kontinuierlich (also sind die x,y-Koordinaten integer) ?
-
Ich weiss jetzt nicht genau, was du meinst, aber wenn du mit "diskret" eine endliche Karte meinst, ist sie das prinzipiell.
Wenn ich aber so darüber nachdenke, tut das wenig zur Sache, denn was ich wohl vergaß zu erwähnen: Ich habe keine Möglichkeit, die Karte oder bestimmte Punkte der Karte auf "begehbarkeit" zu prüfen. Ich kann mich auf der Karte nur an den erwähnten "Marker-Punkten" orientieren, welche ich auf der Karte beliebig platzieren und auch mit Eigenschaften belegen kann.
So habe ich mir inzwischen beispielsweise gedacht, dass ich jedem "Marker-Punkt" eine variable zuweise, welche ihm sagt, wie viele Punkte "um ihn herum" anzusteuern sind. Allerdings hat sich dann das Problem von "U"-Wegen ergeben, wo der Start näher an dem Ziel ist, als der Weg an sich. Also auch doof :(
Aber erzähl - vielleicht ist ja an deiner Idee trotzdem was dran, was sich verwenden lässt.
PS: Ich bitte um eine möglichst ausführliche Erläuterung - nur der Code mag manchen vielleicht helfen, aber ich fürchte nicht alle verstehen sofort, was wofür gut ist ;) -
OK, leider hab ich das proggen angefangen, bevor ich dein zweites Post habe lesen können. Ich hoffe es war nicht komplett für die Füße, weil es funktioniert so schön ^^
Das ganze ist nur ein grobes Beispiel und arbeitet auf einer ASCII-Map. Eine Map ist wie folgt aufgebaut:
-erste Zeile: die Breite
-zweite Zeile: die Höhe
-danach das Gelände: x für Berg, Punkt für Straße und Leerzeichen für Acker.
Ein Beispiel:
20 12 xxxxxxxxxxxxxxxxxxxx x xx. x .xx x x xx. x .x x x...... xx .x x x. xxxxx . x x.............xxxxxx x . xxxxx . x x .. . x x ......... x x ...... . x x . .... x xxxxxxxxxxxxxxxxxxxx
Ein Berg hat einen Aufwand von 10, ein Acker von 3 und eine Straße von 1.
Dem Programm übergibst du 5 Parameter: zuerst den Dateipfad der Map, dann die X-Koordinate vom Startpunkt, dann die Y-Koordinate vom Startpunkt, dann die X-Koordinate vom Endpunkt und dann die Y-Koordinate vom Endpunkt.
Als Ausgabe liefert dir das Programm den schnellsten Weg. Es wählt ganz schöne Wege, die den Straßen folgen, außer einmal kurz über den Acker hüpfen ist wirklich viel kürzer.
Den Code kannst du so kompilieren:
gcc -o path path.c -lm
Als Beispiel, wenn ich mit obiger Map (Dateiname "map") wissen will, wie ich von 1/1 nach 18/10 komme, ruf ich es so auf:
./path map 1 1 18 10
Das ganze bringt die Ausgabe:
===gefunden== 18 / 10 17 / 10 16 / 10 15 / 10 14 / 10 14 / 9 14 / 8 13 / 8 12 / 8 11 / 8 10 / 8 9 / 8 8 / 8 8 / 7 7 / 7 7 / 6 7 / 5 6 / 5 5 / 5 4 / 5 3 / 5 2 / 5 1 / 5 1 / 4 1 / 3 1 / 2 1 / 1
Und wenn du dir das Mal auf der Map anschaust (0/0 ist oben links), dann ist das ein sehr sinnvoller Weg.
Voilà der Code:
#include <stdlib.h> #include <stdio.h> #include <malloc.h> #include <math.h> #define UNKNOWN 0 #define OPEN 1 #define CLOSED 2 #define NONE -1 typedef struct { void *prev; void *next; double f; int pos; } item; int* weight; int* type; int* predec; item* firstOpen; item* lastOpen; int width; int height; int start; int target; int targetx; int targety; int max (int a, int b) { return a > b ? a : b; } void loadMap (char* path) { FILE* handle = fopen (path, "r"); int x, y; int values [256]; values [' '] = 3; values ['.'] = 1; values ['x'] = 10; fscanf (handle, "%d", &width); fscanf (handle, "%d", &height); weight = (int*) malloc (sizeof (int) * width * height); type = (int*) malloc (sizeof (int) * width * height); for (x = 0; x < height * width; type [x ++] = UNKNOWN); predec = (int*) malloc (sizeof (int) * width * height); for (x = 0; x < height * width; predec [x ++] = NONE); for (y = 0; y < height; y++) for (x = 0, fgetc (handle); x < width; weight [x ++ + y * width] = values [fgetc (handle) ] ); } void printRoute () { printf ("===gefunden==\n"); int pos = target; while (pos != NONE) { printf ("%d / %d\n", pos % width, pos / width); pos = predec [pos]; } } void addOpenList (item* itm) { item* cur = lastOpen; while (cur) { if (cur->f < itm->f) { itm->prev = cur; itm->next = cur->next; cur->next = itm; if (itm->next) ( (item*) itm->next)->prev = itm; else lastOpen = itm; return; } cur = cur->prev; } itm->next = firstOpen; itm->prev = 0; if (firstOpen) firstOpen->prev = itm; else lastOpen = itm; firstOpen = itm; } item* findOpenList (int pos) { item* cur = firstOpen; while (cur) if (cur->pos == pos) return cur; else cur = cur->next; } void updateOpenList (item *itm) { item* cur = itm->prev; while (cur) { if (cur->f > itm->f) { cur->next = itm->next; if (itm->next) ( (item*) itm->next)->prev = cur; else lastOpen = cur; itm->next = cur; if (cur->prev) ( (item*) cur->prev)->next = itm; else firstOpen = itm; itm->prev = cur->prev; cur->prev = itm; } else return; cur = cur->prev; } } void check (item* itm, int x, int y) { double f; int pos = x + width * y; item *open = 0; if (type [pos] == CLOSED) return; f = itm->f + max (weight [itm->pos], weight [pos] ) + sqrt ( (x - targetx) * (x - targetx) + (y - targety) * (y - targety) ); if (type [pos] == OPEN) { open = findOpenList (pos); if (f > open->f) return; } predec [pos] = itm->pos; if (open) { open->f = f; updateOpenList (open); } else { open = (item*) malloc (sizeof (item) ); open->pos = pos; open->f = f; addOpenList (open); type [pos] = OPEN; } } void relax (item* itm) { int x = itm->pos % width; int y = itm->pos / width; if (x > 1) check (itm, x - 1, y); if (x < width - 1) check (itm, x + 1, y); if (y > 1) check (itm, x, y - 1); if (y < height - 1) check (itm, x, y + 1); } int main (int argc, char** argv) { int x, y; loadMap (argv [1] ); sscanf (argv [2], "%d", &x); sscanf (argv [3], "%d", &y); start = x + y * width; sscanf (argv [4], "%d", &targetx); sscanf (argv [5], "%d", &targety); target = targetx + targety * width; item* itm = (item*) malloc (sizeof (item) ); itm->f = 42.0f; itm->pos = start; addOpenList (itm); while (firstOpen) { itm = firstOpen; if (itm->next) ( (item*) itm->next)->prev = 0; else lastOpen = 0; firstOpen = itm->next; relax (itm); if (itm->pos == target) { printRoute (); return 0; } type [itm->pos] = CLOSED; free (itm); } printf ("===nicht gefunden===\n"); return -1; } -
Hm, klingt interessant. Mag nun einiges an "umdenken" kosten, aber ich denke ich werde es mal ausprobieren.
Ich denke ich könnte das - wenn ich es dann begriffen habe - in etwa umsetzen, indem ich einfach durch 2 Punkte jeweils "Felder" generiere. ihm also sage ein Feld ist alles was zwischen Punkt1 und Punkt2 liegt. Also sozusagen extra dafür ein "Raster" erschaffe. Dann kann ich in dem "Feld" einen "Marker-Punkt" setzen, auf dem ich dann speicher, welches Gelände dort herrscht, etc... Naja, kriege ich schon irgendwie hin.
Nun aber zu deinem Code.- wie genau geht der vor? Da ist nun so viel "drum herum", dass ich irgendwie nicht durchschaue, was der eigentliche "Inhalt" ist ;) -
Errm, da ist nichts "drum herum", außer das Karten einlesen. Das Ganze IST der Algorithmus.
Das ist einfach nur ein A*-Algorithmus:
Die Knoten werden während der Suche in drei verschiedene Klassen eingeteilt:
* unbekannte Knoten: Diese Knoten wurden während der Suche noch nicht gefunden. Zu ihnen ist noch kein Weg bekannt. Jeder Knoten (außer dem Startknoten) ist zu Beginn des Algorithmus unbekannt.
* bekannte Knoten: Zu diesen Knoten ist ein (möglicherweise suboptimaler) Weg bekannt. Alle bekannten Knoten werden zusammen mit ihrem f-Wert in der sogenannten Open List gespeichert. Aus dieser Liste wird immer der vielversprechendste Knoten ausgewählt und untersucht. Die Implementierung der Open List hat großen Einfluss auf die Laufzeit und wird oft als einfache Prioritätswarteschlange (z. B. binärer Heap) realisiert. Zu Beginn ist nur der Startknoten bekannt.
* abschließend untersuchte Knoten: Zu diesen Knoten ist der kürzeste Weg bekannt. Die abschließend untersuchten Knoten werden in der sogenannten Closed List gespeichert, damit sie nicht mehrfach untersucht werden. Die Closed List ist zu Beginn leer.
Jeder bekannte oder abschließend besuchte Knoten enthält einen Zeiger auf seinen Vorgängerknoten. Mit Hilfe dieser Zeiger kann der Pfad bis zum Startknoten rückverfolgt werden.
Wird ein Knoten x abschließend untersucht (auch expandiert oder relaxiert), so werden seine Nachfolgeknoten in die Open List eingefügt und x auf die Closed List gesetzt. Die Vorgängerzeiger der Nachfolgeknoten werden auf x gesetzt. Ist ein Nachfolgeknoten bereits auf der Closed List, so wird er nicht erneut in die Open List eingefügt und auch sein Vorgängerzeiger nicht geändert. Ist ein Nachfolgeknoten bereits auf der Open List, so wird der Knoten nur aktualisiert (f-Wert und Vorgängerzeiger), wenn der neue Weg dorthin kürzer ist als der bisherige.
Falls der Zielknoten abschließend untersucht wird, terminiert der Algorithmus. Der gefundene Weg wird mit Hilfe der Vorgängerzeiger rekonstruiert und ausgegeben. Falls die Open List leer ist, gibt es keine Knoten mehr, die untersucht werden könnten. In diesem Fall terminiert der Algorithmus, da es keine Lösung gibt.
Wikipedia
Beitrag zuletzt geändert: 28.8.2009 0:33:24 von census -
Hm, wie schon gesagt: Den A*-Algorithmus durchschaue ich noch nicht wirklich.
Des weiteren würde ich vermuten, ist der viel zu umständlich.
Also um das ganze Problem nochmal genauer zu spezifizieren:
- Ich habe beispielsweise einen Roboter, ohne Sensoren, welcher lediglich seine eigene Position und die Position von den "Marker-Punkten" kennt.
- Des weiteren kann ich weitere Informationen in den "Marker-Punkten" speichern, welche ich aber so gering halten möchte wie möglich.
- Ich kann dem "Roboter" sagen (Functions und Methoden dafür hab ich schon geschrieben), dass er sich auf "Luftlinie" zu einem Punkt begeben soll.
- Der "Roboter" hat ausser den Punkten keine Möglichkeit, sich informationen über das Terrain oder ähnliches zu holen.
Die Lösung sollte möglichst "Step by Step" sein und so "klein" wie möglich gehalten werden. Ich forsche halt nach einer Möglichkeit, welche das "Ich probiere alle wege durch" möglichst einfach umgeht. (Notfalls geringfügig auf Kosten der "Länge" des Weges.)
Trotzdem Danke, census, für den Beitrag. Ich werde mir das alles mal genauer anschauen und mal schauen, ob ich das ganze irgendwie durchschaue und verwenden kann. -
nerdinator schrieb:
Hm, wie schon gesagt: Den A*-Algorithmus durchschaue ich noch nicht wirklich.
Des weiteren würde ich vermuten, ist der viel zu umständlich.
Wenn du mit umständlich = aufwendig meinst, dann wohl nicht. Der Aufwand ist im worst-case O(n) = n², und linear oder logarithmisch wirst du kein Pathfinding implementieren können. Behaupt ich mal.
Also um das ganze Problem nochmal genauer zu spezifizieren:
- Ich habe beispielsweise einen Roboter, ohne Sensoren, welcher lediglich seine eigene Position und die Position von den "Marker-Punkten" kennt.
- Des weiteren kann ich weitere Informationen in den "Marker-Punkten" speichern, welche ich aber so gering halten möchte wie möglich.
- Ich kann dem "Roboter" sagen (Functions und Methoden dafür hab ich schon geschrieben), dass er sich auf "Luftlinie" zu einem Punkt begeben soll.
- Der "Roboter" hat ausser den Punkten keine Möglichkeit, sich informationen über das Terrain oder ähnliches zu holen.
Das macht das ganze einfacher. A* arbeitet ja auf einem Graphen und dieser Graph ist die Verquickung deiner "Markerpunkte". Ich pass meinen Code mal an.
Nur ein paar Fragen:
- Gibt es unbegehbare Stellen? Wenn ja, wie merkt das der Roboter ohne Sensoren?
- Ist es immer möglich auf Luftlinie die Marker zu erreichen?
- Kannst du mir mal ein Beispiel geben, also eine Start und Endposition des Bots und die Liste der Marker (und alle weiteren Infos zur Map, die man sonst noch bracuht) ? -
> Gibt es unbegehbare Stellen? Wenn ja, wie merkt das der Roboter ohne Sensoren?
Da liegt ein großes Problem. Es gibt durchaus dynamisch unbegehbare stellen, wie beispielsweise Türen. Ich dachte an etwas wie einer bool-variable in den "Marker-Punkten" (Die Marker-Punkte sind Objekte, mit vielen Eigenschafen, wie x, y, usw...) Dass der "Roboter" keine Sensoren hat, heisst ja nicht, dass die Punkte nicht "sehen" können. Oder ich löse einfach die "Löschung" der betreffenden Marker-Punkte aus, wenn die Tür geschlossen wird und erstelle sie neu, wenn die Tür geöffnet wird... Da gibt es viele Möglichkeiten. Im Grunde ist das Problem erstmal zu ignorieren.
> Ist es immer möglich auf Luftlinie die Marker zu erreichen?
Da liegt das nächste Problem: Es ist nicht jeder "Marker-Punkt" von jedem Marker-Punkt zu erreichen. Also praktisch immer nur die "Nächstliegenden". Um die zu ermitteln habe ich eine Funktion geschrieben á la "GetNearestPoint()". Diese ermittelt nach Luftlinie den nächstliegenden Punkt.
> Kannst du mir mal ein Beispiel geben, also eine Start und Endposition des Bots und die Liste der Marker (und alle weiteren Infos zur Map, die man sonst noch bracuht) ?
Oje, prinzipiell sind das unglaublich viele infos ;) Aber ich probier es mal, das so weit wie möglich zu vereinfachen.
Erstmal zur Veranschaulichung ein Bild. Auf diesem sind alle meiner meinung nach notwendigen Marker-Punkte Rot verzeichnet, alle "denke ich notwendigen" Gelb und der Startpunkt Blau. (Fällt nicht sofort ins Auge, er ist oben links.) Der Hintergrund der Karte ist praktisch nur "Dekoration", welche nur der User sehen wird. Aber der "Roboter" soll sich praktisch nur auf der (hier braunen) Straße aufhalten. Aber für ihn gibt es halt nur die Marker-Puntke, die einem anzeigen, wo die Straße überhaupt ist. Die Punkte kann man praktisch mit allen möglichen Informationen füttern. -
Super, das Bild hat mehr erklärt als 1000 Worte. So, ich habe Gefallen an der Sache gefunden und bin schön was am schreiben. Bis Montag kann ich dir einen Vorschlag posten, wie ich das angehen würde und hoffentlich kannst du da was sinnvolles rausziehen.
Könntest du mir bitte die Map ohne bunte Punkte zur Verfügung stellen? Danke. -
Nochmal das Bild ohne Bunte Pünktchen: http://nerdinator.lima-city.de/emb/freepics/map.PNG
Und wie schon gesagt: Die einzigen Orientierungspunkjte sind die Punkte. Und lass dir ruhig Zeit ^^ -
So ich hab mal was geschrieben, was funktioniert. Allerdings kann ich es noch nicht hochladen, weil meine Auktion für Downloadspace noch 2 h läuft. Danach stell ich's online und du kannst dann schauen, ob's dir taugt.
-
Schauen wir mal :) Vielen Dank in Vorraus.
-
Na wie geil, jetzt hab ich extra Downloadplatz ersteigert und bekomme dauernd nur ein:
Status: Verbinde mit 85.25.149.77:21... Status: Verbindungsversuch fehlgeschlagen mit "ECONNREFUSED - Connection refused by server". Fehler: Herstellen der Verbindung zum Server fehlgeschlagen
====================================
EDIT:
Gottseidank gibt's die Konkurrenz:
http://www.speedshare.org/download.php?id=08ECB32A3
VORSICHT: Nicht auf den riesengroßen offensichtlichen Downloadbutton klicken, sondern auf den kleinen versteckten unten.
Das ganze ist in Java geschrieben, wiel ich grad kein C++ zur Hand habe, aber die Idee sollte ja dieselbe sein.
Starten kannst du das ganze mit
java -jar pathfinder.jar
Einfach den Zielpunkt setzen und der Roboter läuft hin. Nicht immer optimaler Weg, aber immer guter Weg.
Ich hoffe das ganze gibt dir brauchbare Denkanstöße.
Beitrag zuletzt geändert: 29.8.2009 16:04:36 von census -
Das sieht ganz cool aus :)
Nun erläutere mal, was genau passiert. Also wir haben den Startpunkt - von dort aus tgeht er nun alle möglichen wege durch, oder wie? Und orientiert er sich an den Punkten, oder an seiner Position? Am besten mal ganz genau beschreiben, damit ich es begreife ^^ Ausserdem wäre ein quellcode schön ^^ -
Klar, klar, kriegste alles. Ich wollt nur wissen ob wir vom selben Reden.
Gib mir etwas Zeit und du kriegst Quellcode mit Kommentaren und Erläuterung. -
Es sieht zumindest sehr gut aus. Ob es nun wirklich "das" richtige ist, weiss ich erst nach der Erläuterung usw... Aber ich denke notfalls muss ich das versuchen so zu übernehmen. Denn ich bekomme sonst auch nirgendwo eine treffende Antwort. Ich glaube deine war bisher die Beste ;)
-
http://rapidshare.com/files/273500379/pathfinder.tar.gz.html
MD5: 21DAC14CAAB07620AF4D344D607E17CB
Bitteschön, hier die Sourcen.
Das ganze funktioniert wie folgt. Deine Map wird als reines Hintergrundbildgeladen. Die Logik der Karte ist in der Datei map.xml wiedergegeben. Hierbei ist darauf zu achten, dass bei einer Transition der Startpunkt weiter links (kleineres x) oder weiter oben (kleineres y) liegt als der Zielpunkt. Das Programm liest beim Start beide Dateien. Hier nun eine kurze Erläuterung, was welche Klasse oder Routine macht. Ist halt Java, weil ich grad kein C++ zur Hand hatte. Wenn du das aber nutzen willst, kann ich dir das gern nach C++ portieren (also das reine Pathfinding) und dir ne Klasse geben, der du halt über Routinen Punkte und Transitionen hinzufügst und die dir dann den Weg zwischen zwei Punkten bestimmen kann. Ist kein Problem, schreib ich dir gern, falls du willst.
public class MainFrame extends JFrame
Uninteressant. Ist nur der Mainentrypoint und das Toplevelfenster.
public class Map implements ImageObserver
Hier passiert die Magie. Zunächst mal die Eigenschaften:
private Image image; - das Hintergrundbild
private Hashtable <String, Point> points; - alle Markerpunkte der Karte
private Hashtable<String, Transition> transitions; - alle Verbindungen zwischen Markern
private Dimension size; - die Größe in Pixeln der Map
private java.awt.Point offset; - das Offset in Pixeln vom Marker an der Position (0/0) bezüglich dem Ursprung des Hintergrundbildes
private Dimension scale; - der Faktor, wieviele Pixel zwischen zwei benachbarten Markern liegen
private Vector <Point> waypoints; - die Wegpunkte, über die sich der Roboter gerade bewegen wird.
private boolean isMoving; - wahr, falls sich der Roboter gerade bewegt
Und hier die Routinen:
private Map ()- Uninteressant: Leerer, geschützter Defaultkonstruktor
public static Map loadFromFile (String path) throws IOException, ParserConfigurationException, SAXException - Uninteressant: Liest das Jpeg und das XML.
public boolean imageUpdate(Image img, int infoflags, int x, int y, int width, int height) - Uninteressant: Implementiert ImageObserver
public Dimension getSize () - Uninteressant: Gibt die Größe zurück.
public java.awt.Point snap (java.awt.Point point) - Uninteressant: Sucht den nächsten Punkt, der auf einer Strecke der Karte liegt.
public void updateTransitions () - Fügt der statischen Transitionsliste vier neue Transitionen hinzu (oder überschreibt bestehende), nämlich die beiden Nachbarn sowohl des Roboters als auch des Zielpunktes.
private boolean findRoute () - Hier wird der Weg gesucht. Eine quick-and-dirty Implementierung von A*.
public void setTarget (java.awt.Point snapped) - Setzt den Zeilpunkt und ruft updateTransitions.
public void tick () - Bewegt den Roboter ein Pixel weiter.
public class MapPanel extends JPanel implements MouseMotionListener, MouseListener
Uninteressant. Macht nur die Darstellung.
public class Point
Ein Markerpunkt.
public class Transition
Ein Übergang von einem Markerpunkt auf einen Nachbarn.
public class StarList
Eine Liste über gewichtete Punkte. -
nerdinator schrieb:
Hm, wie schon gesagt: Den A*-Algorithmus durchschaue ich noch nicht wirklich.
Der ist eigentlich ganz einfach.
Kennst du diesen Link schon? Der erklärt das meiner MEinung nach sehr gut wie man vorzugehen hat.
http://www.policyalmanac.org/games/aStarTutorial.htm -
Klingt interessant - werde ich mir bei Zeiten durchlesen :)
-
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
