automatisches Wegfinde-Script

**onemorenerd** · 13.06.2009, 19:37

Wegsuche Algorithmus - Google Search

**Hopka** · 13.06.2009, 20:04

Mit der Google Maps API kannst du sowas machen. Vorausgesetzt natürlich es geht um die reale Welt.

**PHP-Desaster** · 13.06.2009, 23:54

Schau dir - falls du die Google Api nicht verwenden kannst/willst - mal den Dijkstra- bzw. den A*-Algorithmus an.

**admin** · 14.06.2009, 08:58

Graphentheorie! Lang lang her

**onemorenerd** · 14.06.2009, 09:49

Er meldet sich gar nicht. Haben wir ihn etwa verschreckt? Nun gut, ich versuche es mal einfacher darzustellen.

2D-Karten wie diese sind meist Felder von Quadranten. Jeder Quadrant hat irgendwelche Eigenschaften, z.B. Typ "Strasse" oder "Baum". Start und Ziel sind Paare (x,y) im Feld. Zur Wegsuche schaut man alle Felder rings um den Startpunkt an. Ist ein Feld begehbar, nimmt man es in den Weg auf und führt die Suche von dort aus fort.
Dieser rekursive Algorithmus kann verschiedene Taktiken verfolgen (Breitensuche, Tiefensuche, ...) und Informationen berücksichtigen (Himmelsrichtung zum Ziel, ...) und bekommt dann einen entsprechenden Namen, damit jeder gleich weiß was gemeint ist. A*, Dijkstra und Greedy sind solche Namen.
Hier kannst du dir anschauen wie diese Algorithmen arbeiten. (Auswahl des Algorithmus durch Klick auf den Button A*)

Wenn man nach Graphentheorie googelt, findet man meist Darstellungen aus Punkten und Verbindungslinien - sog. Graphen. Auf den ersten Blick haben die nichts mit einer 2D-Karte gemeinsam. Doch die Darstellung täuscht. Eine 2D-Karte ist auch nur ein Graph. Das sieht man leicht ein, wenn man die Quadranten durch Punkte austauscht und zwischen benachbarten (begehbaren) Punkten eine Linie zieht.

**admin** · 14.06.2009, 10:39

5 Semester Informatik ?

**onemorenerd** · 14.06.2009, 10:48

icke? mehr

**Besth** · 14.06.2009, 13:07

ne verschreckt nicht - ich bin erst jetzt wieder hierzu gekommen ^^
Es war doch Freitag abend

Da muss man doch nicht immer vorm PC hocken *g*

Also um nochmal klar zu stellen: Ich suche kein Suchsystem ala Google für die Weltkarte. Meine karte ist etwas einfacher.
Ich hab eine 2D Karte wie wahrscheinlich

Zitat von onemorenerd

2D-Karten wie diese sind meist Felder von Quadranten

meinte. (Leider kann man den Link nicht aufrufen.)

EDIT:
ja genau so sieht meine karte aus (bisschen einfacher)

Also es gibt auf jeder Koordinate entweder ein Haus, Wald, Gras, Wasser oder eben Straße.

Also rein vom logischen hab ich mir schon gedacht das ich sozusagen jedes angrenzende Feld untersuchen muss ob dort ein Weg möglich ist. Nur meine Frage ist eher wie ich die Priorität mit einbaue.
Sonst findet er ja bestimmt irgendwann nen Weg aber der ist auf jedenfall nicht der kürzeste.
Aber wahrscheinlich ist dieser A* das was ich suche oder?

Zitat von onemorenerd

Hier kannst du dir anschauen wie diese Algorithmen arbeiten.

Ist bei der Seite das was gerade ausgewählt ist das was oben links in der Ecke steht? Oder wenn ich drauf klick spirngt er zu dem jeweiligen?
Die Seite ist echt gut.

Mir haperts grad noch wie ich das dann in PHP umsetz ^^
Und ist die Ladezeit dann nicht enorm?

**onemorenerd** · 14.06.2009, 14:19

Du kennst die Koordinaten von Start und Ziel, also kannst du vom Start aus bevorzugt in Richtung Ziel gehen, Feld für Feld. Wenn ein Feld nicht begehbar ist, nimmst du das Nachbarfeld, was noch am ehesten in Richtung des Ziels liegt.
Rennst du in eine Sackgasse, machst du Backtracking. Eine Sackgasse erkennst du daran, dass du alle Felder um deinen Standort bereits erkundet hast (bis auf das von dem du gekommen bist natürlich) und nirgendwo einen Weg fandest. Also gehst du einen Schritt zurück auf das Feld von dem du gekommen bist und probierst dort eine Alternative, also ein Feld, das du bisher noch nicht probiert hast. Auch hier gilt wieder: Wähle zuerst das Feld, welches am meisten Richtung Ziel liegt.

Wahrscheinlich kannst du dir den Ablauf des Algorithmus inzwischen ganz gut vorstellen (falls nicht ...), aber du weißt nicht wie du das in Code gießen kannst. Nun, ich würde mit einer 10x10 Felder großen Karte beginnen, auf der zunächst alle Felder begehbar sind.
Du brauchst eine Repräsentation dieser Karte (Klasse oder Array), falls du das noch nicht hast. Außerdem brauchst du eine Repräsentation des aktuellen Standorts und des Ziels (Koordinatenpaare x,y) und Hilfsfunktionen wie istBegehbar(x,y), istAufDerKarte(x,y), geheNach(x,y) usw.
Wenn das alles steht kannst du anfangen:

Standort = geheNach(Start);
Nachbarfeld = ermittleBestesNachbarfeld(Standort, Ziel);
wenn istBegehbar(Nachbarfeld) Standort = geheNach(Nachbarfeld);

Das funktioniert bereits, weil die Karte überall begehbar ist.
Nun fügst du eine Wand zwischen Start und Ziel ein und passt den Algorithmus so an, dass er einen Weg drumherum findet. Dabei sind nur zwei Dinge zu beachten:
1. Code wiederverwenden! So entsteht die Rekusion.

2. Keine Annahmen über die Umwelt (Größe der Karte, Zielpunkt, Form der Wand) im Code verankern.

**Besth** · 14.06.2009, 17:56

Ja das Prinzip hab ich verstanden. Danke für deine anschaulichen Erklärungen.
Ich mein eher wie rechne ich denn zb aus welches das beste nachbarfeld ist ^^
muss ich da die luftlinie nehmen zwischen dem zu ermitteltem feld und dem ziel - und wenns am kleinsten ist - ist das das beste feld?
ich test es mal so

**onemorenerd** · 15.06.2009, 00:27

Nehmen wir mal an dein Standort ist (2,1) und das Ziel (4,5). Das Feld sieht also so aus:

Code:

---------------------------
5 |   |   |   |   | Z |   |
---------------------------
4 |   |   |   |   |   |   |
---------------------------
3 |   |   |   |   |   |   |
---------------------------
2 |   |   |   |   |   |   |
---------------------------
1 |   |   | S |   |   |   |
---------------------------
0 |   |   |   |   |   |   |
---------------------------
  | 0 | 1 | 2 | 3 | 4 | 5 |

Du bildest die Differenzen der x-und y-Werte (Schritt 1)
x = 4-2 = 2
y = 5-1 = 4
halbierst diese Werte und rundest das Ergebnis (Schritt 2)
x = round(2/2) = 1
y = round(4/2) = 2
und addierst sie zu den Koordinaten deines Standortes (Schritt 3).
So erhältst du den Punkt (3,3), der auf der Hälfte des Weges zwischen Standort und Ziel liegt:

Code:

---------------------------
5 |   |   |   |   | Z |   |
---------------------------
4 |   |   |   |   |   |   |
---------------------------
3 |   |   |   | P |   |   |
---------------------------
2 |   |   |   |   |   |   |
---------------------------
1 |   |   | S |   |   |   |
---------------------------
0 |   |   |   |   |   |   |
---------------------------
  | 0 | 1 | 2 | 3 | 4 | 5 |

Solange nicht beide Ergebnisse aus dem zweiten Schritt 1 sind, wiederholst du das ganze, nimmst aber immer den Punkt P als Ziel an.

Code:

---------------------------
5 |   |   |   |   | Z |   |
---------------------------
4 |   |   |   |   |   |   |
---------------------------
3 |   |   |   |   |   |   |
---------------------------
2 |   |   |   | P |   |   |
---------------------------
1 |   |   | S |   |   |   |
---------------------------
0 |   |   |   |   |   |   |
---------------------------
  | 0 | 1 | 2 | 3 | 4 | 5 |

Wenn beide Ergebnisse 1 sind erhältst du durch Addition zum Standort die Koordinaten eines Nachbarfelds.

Dahinter steckt die Idee eines rechtwinkligen Dreicks SZR mit R = (xZ, yS) und dessen Verkleinerung Richtung S durch Hypthenusenhalbierung.

Code:

---------------------------
5 |   |   |   |   | Z |   |
---------------------------
4 |   |   |   |   |   |   |
---------------------------
3 |   |   |   |   |   |   |
---------------------------
2 |   |   |   |   |   |   |
---------------------------
1 |   |   | S |   | R |   |
---------------------------
0 |   |   |   |   |   |   |
---------------------------
  | 0 | 1 | 2 | 3 | 4 | 5 |

Die Komplexität der Schleife mit den o.g. drei Schritten ist logarithmisch in der Größe des Feldes. Bei 1000x1000 Felder wird sie also nur maximal 10 Mal durchlaufen. Schick, aber gaanz großer Käse! Es geht nämlich auch in O(n). Denn es gibt auch eine Möglichkeit das Nachbarfeld direkt aus den Koordinaten von Standort und Ziel abzuleiten. Dazu betrachtet man die relative Lage der Punkte zueinander. Liegt Z rechts von S, kommen auch nur die rechten Nachbarfelder von S in Betracht. Liegt Z zudem über S, kommen nur Nachbarfelder rechts über S in Frage. Davon gibt es nur eins. Rums bums Nikolaus.

**Besth** · 15.06.2009, 10:19

Also das klingt für mich jetzt doch etwas verwirrend

ich habs etwas anders gelöst.
ich hab diese formel genommen:

damit rechne ich immer den weg der luftlinie zwischen den nachbarfeldern meines standortes und des ziels aus.
wo der wert am kleinsten ist, ist das beste feld.

sackgassen hab ich auch rausgefiltert. sollte einmal ein weg eingeschlagen werden wo es nicht weiter geht - wird ein feld zurück gegangen und nach alternativen gesucht.

mein prob is derzeit noch das er nur eine route findet aber es ist NICHT die kürzeste

muss das mit den kosten da noch reinbekommen.
naja ich bau mal noch weiter

EDIT:
bei deinem beispiel ist aber das problem wenn nun eine wand (hier die X) so ist:

Code:

--------------------------- 5 | | | | | Z | | --------------------------- 4 | | X | X | X | X | X | --------------------------- 3 | | X | | | | | --------------------------- 2 | | X | | S | | | --------------------------- 1 | | X | | | | | --------------------------- 0 | | | | | | | --------------------------- | 0 | 1 | 2 | 3 | 4 | 5 |

dann rennst du ja nur nach norden und dann wirds mist, weil er irgendwann nich mehr weiter kommt.

**onemorenerd** · 15.06.2009, 13:19

Ja klar gehe ich erstmal nach Norden.

Code:

---------------------------
5 |   |   |   |   | Z |   |
---------------------------
4 |   | X | X | X | X | X |
---------------------------
3 |   | X |   | S |   |   |
---------------------------
2 |   | X |   |   |   |   |
---------------------------
1 |   | X |   |   |   |   |
---------------------------
0 |   |   |   |   |   |   |
---------------------------
  | 0 | 1 | 2 | 3 | 4 | 5 |

Nun würde ich gern auf (4,4) gehen. Dieses Feld ist aber nicht begehbar. Erst jetzt erkenne ich, dass ich auf ein Hindernis zugelaufen bin.
Ich versuche (3,4), weil es ebenso gut Richtung Z führt. Aber auch dieses Feld ist nicht begehbar.
Nun versuche ich (4,3), das ist begehbar, also mache ich diesen Schritt.

Code:

---------------------------
5 |   |   |   |   | Z |   |
---------------------------
4 |   | X | X | X | X | X |
---------------------------
3 |   | X |   |   | S |   |
---------------------------
2 |   | X |   |   |   |   |
---------------------------
1 |   | X |   |   |   |   |
---------------------------
0 |   |   |   |   |   |   |
---------------------------
  | 0 | 1 | 2 | 3 | 4 | 5 |

Jetzt würde ich gern nach (5,4), aber das geht nicht. Ich erkenne, dass mich jeder andere Schritt weiter von Z wegbringen würde (lokales Optimum) und beginne, das Hindernis zu umgehen. Hindernisumgehung bedeutet "gehe so lange an der Wand entlang, bis es günstiger wäre, Richtung Z zu gehen, statt weiter an der Wand lang". Ich starte Richtung Osten.

Code:

---------------------------
5 |   |   |   |   | Z |   |
---------------------------
4 |   | X | X | X | X | X |
---------------------------
3 |   | X |   |   |   | S |
---------------------------
2 |   | X |   |   |   |   |
---------------------------
1 |   | X |   |   |   |   |
---------------------------
0 |   |   |   |   |   |   |
---------------------------
  | 0 | 1 | 2 | 3 | 4 | 5 |

Am Rand der Karte ändere ich die Richtung - ich gehe nun andersrum an der Wand lang. Hier der Weg, den ich schließlich zurücklege.

Code:

---------------------------
5 |   | S |   |   | Z |   |
---------------------------
4 | . | X | X | X | X | X |
---------------------------
3 | . | X | . | . | . | . |
---------------------------
2 | . | X | . |   |   |   |
---------------------------
1 | . | X | . |   |   |   |
---------------------------
0 |   | . |   |   |   |   |
---------------------------
  | 0 | 1 | 2 | 3 | 4 | 5 |

Ab diesem Moment ist es günstiger, wieder direkt auf Z zuzulaufen. Deshalb höre ich auf an der Wand entlang zu gehen.

**Besth** · 15.06.2009, 21:48

jojo is schon klar soweit

aber mal noch ne andere sache. bei den seiten die du gelinkt (zb hier) hast reden die immer von einer offenen liste und einer geschlossenen liste.
gibt es sowas in php? also listen?
oder muss man das über mehrdimensionale arrays lösen? oder gar direkt über die db? was geht denn am schnellsten bei der verarbeitung?

automatisches Wegfinde-Script