automatisches Wegfinde-Script

[jmc]

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.

[onemorenerd]

PHP: Datastructures - Manual

Zwischenergebnisse niemals in der DB speichern!

[Besth]

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

[unset]

un wie ordne ich das nun nach f?

Zur not mit usort.

[Besth]

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

[onemorenerd]

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

usort($deinArray, "fsort"); 

[Besth]

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

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

[onemorenerd]

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"); 

[jmc]

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.

[PHP-Desaster]

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!

EDIT:

---

Ah hier: http://en.wikipedia.org/wiki/Optimiz...en_to_optimize

---

[Besth]

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

[jmc]

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.

[PHP-Desaster]

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.