Pathfinding in Hexagonaler Karte

'n Abend zusammen.
Ich zerbreche mir jetzt schon seit ein paar Stunden den Kopf darüber, wie ich am schnellsten ein Pathfinding in einer Hexagonalen Karte umsetzen soll.
Alle Felder der Karte sind in einer Datenbank abgelegt mit den jeweiligen 6 zugehörigen Nachbaren. Aktuell sieht die Berechnung so aus:
- Startpunkt und Zielpunkt festlegen
- Vom Startpunkt aus alle benachbarten Felder besuchen und ihnen eine Gewicht zuweisen.
- Vom Endpunkt den Weg des geringsten Widerstandes suchen
Ich hab die Karte mal an den Post rangehängt, damit sich jeder ein Bild machen kann.
Das Problem ist, dass bei einer Entfernung von 6 Feldern die Berechnung der Gewichte schon 2 Sekunden dauert. Was natürlich untragbar ist, wenn das ganze in einem Spiel eingesetzt werden soll. Vielleicht hat ja jemand einen Vorschlag, wie die Berechnung beschleunigt werden könnte...
Das ist der Code, mit dem die Gewichtung berechnet wird.

$done=array();
function calcWeight($id,$depth) {
global $load_fields;
global $weight;
global $done;
$depth++;
if($depth<7) {
$tmp=$load_fields[$id];
for($i=0;$i
if(!in_array($tmp[$i],$done)) {
$w=10;
$tmp2=$load_fields[$tmp[$i]];
for($j=0;$j
if($weight[$tmp2[$j]]<$w && $weight[$tmp2[$j]]!=-1) {
$w=$weight[$tmp2[$j]];
}
}
$w++;
$weight[$tmp[$i]]=$w;
array_push($done,$tmp[$i]);
}
}
for($i=0;$i
calcWeight($tmp[$i],$depth);
}
}
}
$load_fields ist ein array, der für jedes feld einen array der nachbaren enthält. alles andere sollte sich von selbst erklären.
Gruß
meister

de.wikipedia.org/wiki/A-Stern-Algorithmus
Schau dir den mal an, dürfte dir weiterhelfen, gibs sicher auch eine Implentierung in PHP, weiß gerade nicht wo oder ob...
Greetz,
xXx

In der Snippets DB liegt was rum.

danke für die antworten, aber die erleuchtung ging einen anderen pfad
da das spielfeld hexagonal aufgebaut ist, kann man relativ schnell die umgebenden felder errechnen. somit lässt sich das weightmapping einfach auf diese felder anwenden. jetzt bin ich bei 0,06sec. statt vorhin 2sec.