So hallo.
Ich bins mal wieder.
Und zwar hab ich mal wieder keinen Plan wie man folgende Sache erstellen könnte und hoffe ihr könnt mir helfen einen Ansatz zu finden:

Ich möchte auf meiner Karte (mit Straßen, Häusern, Gras, Wasser usw.) ein Script einbinden in der der User 2 Punkte anklickt und dann automatisch eine Route berechnet wird - nur über die Straßen (die kürzeste möglichst)
Nur hab ich noch keine Ahnung wie ich sowas um setzen könnte.
Hat da jemand ne Ahnung? Bzw habt ihr überhaupt verstanden was ich will? :D

Wegsuche Algorithmus - Google Search (http://www.google.com/search?q=Wegsuche+Algorithmus)

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

Schau dir - falls du die Google Api nicht verwenden kannst/willst - mal den Dijkstra (http://de.wikipedia.org/wiki/Dijkstra-Algorithmus)- bzw. den A* (http://de.wikipedia.org/wiki/A*-Algorithmus)-Algorithmus an.

Graphentheorie! Lang lang her :)

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

2D-Karten wie diese (http://www.classic-zone.de/images/artikel/snes-zelda3-map1.png) 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 (http://www.stefan-baur.de/cs.algo.search.html?glstyle=2008) 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.

5 Semester Informatik ? :)

icke? mehr ;)

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
2D-Karten wie diese (http://www.classic-zone.de/images/artikel/snes-zelda3-map1.png) sind meist Felder von Quadranten
meinte. (Leider kann man den Link nicht aufrufen.) 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?
Hier (http://www.stefan-baur.de/cs.algo.search.html?glstyle=2008) 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?

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 ... (http://kik.informatik.fh-dortmund.de/visual/)), 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.

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

Nehmen wir mal an dein Standort ist (2,1) und das Ziel (4,5). Das Feld sieht also so aus:
---------------------------
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:
---------------------------
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.
---------------------------
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.
---------------------------
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.

Also das klingt für mich jetzt doch etwas verwirrend :D
ich habs etwas anders gelöst.
ich hab diese formel genommen:
http://www.hinterseher.de/Diplomarbeit/Abstand.gif
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 :)

bei deinem beispiel ist aber das problem wenn nun eine wand (hier die X) so ist:
---------------------------
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.

Ja klar gehe ich erstmal nach Norden.
---------------------------
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.
---------------------------
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.
---------------------------
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.
---------------------------
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.

jojo is schon klar soweit :)

aber mal noch ne andere sache. bei den seiten die du gelinkt (zb hier (http://www.policyalmanac.org/games/aStarTutorial_de.html)) 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?

Wie du die Daten speicherst ist eigentlich egal. Es muss nur möglichst schnell sein. Mit PHP ist wohl die schnellste Variante das Array, ein DB kommt da wohl aber für den mehrfachen Gebrauch sicher nicht in Frage, ausser die wolltest z.B. alle Züge vorberechnet speichern.
Zwei eindimensionale Arrays sind sehr wahrscheinlich schneller als ein zweidimensionales.

Wenn du nicht den besten Weg findest ist entweder deine Heuristik schlecht oder aber du hast den A*-Algorithmus nicht richtig umgesetzt.
Je nachdem was für eine Karte du has (wie gross und wie kompliziert aufgebaut sie ist) wäre in deinem Fall auch eine Greedy Best First Search sinnvoll.
Wenn du tatsächlich eine sehr grosse und sehr komplex aufgebaute Karte hast, sodass es schwer oder zu aufwändig ist eine genauere Heuristik zu erstellen, dann kannst du bei deinen Weg über Backtracing mit Hilfe des Bresenhams Algorithmus (den kennst du vieleicht vom Linien ziehen in Grafikbearbeitungsprogrammen; es ist das selbe Prinzip, ausser dass du jeweils die Länge der erzeugten Linie + Länge bis zum Ziel + Länge bis zum Start berechnest) noch etwas optimieren, aber der A* alleine sollte eigentlich in den meisten Fällen reichen.

PHP: Datastructures - Manual (http://de.php.net/manual/en/spl.datastructures.php)

Zwischenergebnisse niemals in der DB speichern!

naja das problem ist ja - ich muss ja nach den kosten sortieren. und immer das feld als nächstes untersuchen das die geringsten kosten hat.
mein array sieht ja dann so aus:
array {
[0]=> array {
[x]=> 0
[y]=> 0
[vorgaengerx]=> 0
[vorgaengery]=> 0
[f]=> 0
[g]=> 0
[h]=> 0
}
[1]=> array {
[x]=> 0
[y]=> 0
[vorgaengerx]=> 0
[vorgaengery]=> 0
[f]=> 0
[g]=> 0
[h]=> 0
}
[2]=> array {
[x]=> 0
[y]=> 0
[vorgaengerx]=> 0
[vorgaengery]=> 0
[f]=> 0
[g]=> 0
[h]=> 0
}
}
un wie ordne ich das nun nach f? weil ich brauch ja die ganzen infos von den koordinaten un kosten ...
ach mensch ich weiß grad nich mehr weiter. ich mach ma ne pause bis heut abend ^^
danke trotzdem für die hilfe hätt nich gedacht das ich überhaupt soweit komm ;)

un wie ordne ich das nun nach f?
Zur not mit usort.

ok das versteh ich leider nicht wie das auf mein beispiel passt :(

function fsort($a, $b) {
if ($a['f'] == $b['f']) {
return 0;
}
return ($a['f'] < $b['f]) ? -1 : 1;
}

usort($deinArray, "fsort");

ok danke funktioniert.
ich hatte mir bis eben das hier zusammengereimt:
function sortiere ($a, $b) {
return $a["f"] > $b["f"];
}
usort($meinarray, "sortiere");

aber deins sieht etwas komplexer aus :D

rein interessehalber: wenn ich jetzt noch zusätzlich nach nem 2. feld sortieren wöllte wie müsste denn der code verändert werden?
also wenn zb erst nach "f" un dann nach "g", dann nach "h" usw. (falls f bzw g gleich ist)
hab die funktion usort leider noch nicht 100%ig verstanden udn würde es gern

function fghsort($a, $b) {
if ($a['f'] == $b['f']) {
if ($a['g'] == $b['g']) {
if ($a['h'] == $b['h']) {
return 0;
}
return ($a['h'] < $b['h']) ? -1 : 1;
}
return ($a['g'] < $b['g']) ? -1 : 1;
}
return ($a['f'] < $b['f']) ? -1 : 1;
}

usort($deinArray, "fghsort");

Wenn $a['f'] == $b['f'] und $a['g'] == $b['g'] dann muss $a['h'] == $b['h'] sein ;)

Benutzt du nun A*? Warum nimmst du als Index nicht z.B. ($a << 16 | $b)? Der Zugriff wäre dadurch einiges schneller (die zwei Bitoperationen sind vernachlässigbar im Vergleich).
Sonst müsstest du ja immer alle geschlossenen und geöffneten Knoten durchsuchen, so hast du direkten Zugriff.

Sonst müsstest du ja immer alle geschlossenen und geöffneten Knoten durchsuchen, so hast du direkten Zugriff.

Premature Optimization ist die Wurzel allen Übels oder wie war das Zitat noch gleich!

Ah hier: http://en.wikipedia.org/wiki/Optimization_(computer_science)#When_to_optimize

Benutzt du nun A*? Warum nimmst du als Index nicht z.B. ($a << 16 | $b)? Der Zugriff wäre dadurch einiges schneller (die zwei Bitoperationen sind vernachlässigbar im Vergleich).
Sonst müsstest du ja immer alle geschlossenen und geöffneten Knoten durchsuchen, so hast du direkten Zugriff.
ja ich benutze A*. Bzw versuche ich noch es umzusetzen.
Ich versteh leider nicht was du mit Index ($a << 16 | $b) meinst.
Sry bin nich so der krasse Freak :)
Ich programmier gern ma in meiner Freizeit aber so das es richtig zum Programmierer reicht fehlt mir die Zeit/Lust :D

Damit kannst du folgenden Pseudocode etwas abkürzen:for each neighbour of node
if neighbour in closed
/*du hast einen zufälligen index also musste du alle Element in closed
durchsuchen bis du neighbour findest (oer auch nicht) */
...
else if neighbour in open
/*du hast einen zufälligen index also musste du alle Element in open
durchsuchen bis du neighbour findest (oer auch nicht) */
...
Den Index könntest du aber auch durch x und y bestimmen lassen. Da PHP bei Arrays automtisch maps erstellt haben Index und Reihenfolge im Array nicht viel miteinander zu tun. Das ist normalerweise ein Nachteil bei der Performance, hier aber kannst du das vorteilhaft nutzen.
Du baust deine Nodes in closed und open entweder so auf:
$open = Array();
...
$open[$x][$y] = Array( // Zugriff bei bekanntem x, y über $open[x][$y]
4, // --> g
23, // --> h
27, // --> f
3, // --> parent x
8 // parent y
);
oder so:
$open = Array();
...
$open[($x << 16) | $y] = Array( // Zugriff bei bekanntem x, y über $open[($x << 16) | $y]
4, // --> g
23, // --> h
27, // --> f
3, // --> parent x
8 // parent y
);
Und das oberer Beispiel würde zu:
for each index -> neighbour of node
if exists closed[index] // du hast exakt einen Index zu prüfen
...
else if exists open[index] // du hast exakt einen Index zu prüfen
...

Wenn man nicht optimieren soll warum nicht gleich Dijkstra oder eine IDDFS? Dann brauchst du nicht unbedingt eine genaue Heuristik und der erste Weg den du findest ist auch der nächste.

Wenn man nicht optimieren soll warum nicht gleich Dijkstra oder eine IDDFS? Dann brauchst du nicht unbedingt eine genaue Heuristik und der erste Weg den du findest ist auch der nächste.

Das sehe ich auch so. Wenn ich mich nicht mit dem Thema auskenne, würde ich erstmal vorne anfangen.