routing-algorythmus: von AxB nach CxD in 8x8 Matrix, axial oder diagonal, weg finden

[userOne]

Hiho
Folgende Lage:
Ein Spielfeld mit 8x8 Sektoren.
Man kann sich axial und diagonal jeweils um ein Feld bewegen, einzelne Felder sind nicht begehbar (Spielfeld ist in Datenbank hinterlegt).
Der Algorythmus soll jetzt einen Weg von Sektor AxB nach Sektor CxD finden, in möglichst nicht expotentieller laufzeit

Beispiel (von s nach z) in 4x4:
(s,z und 1 sind begehbar, 0'en nicht)
1 s 1 1
1 1 0 0
1 1 0 z
1 1 1 1

Route wäre:
(s) Startpunkt
nach unten,
nach unten,
diagonal nach unten-rechts,
diagonal nach oben-rechts (z) Zielpunkt

Vielleicht habt ihr noch paar Ideen für mich wie man das am besten angehen kann
Ich sehe im Moment keinen anderen Weg als einen Baum aufzubauen mit allen Pfaden wo ich soclhe Pfade entferne die ein Feld was nicht begehbar ist Treffen und solche Pfade, die über Umwege ein Feld erreichen, was man auch zum Beispiel Direkt erreicht. (also Pfad mit 'nach rechts, nach unten' fällt weg, da 'diagonal nach rechts unten' möglich ist und der kürzere weg ist)

mfG
Manuel

[Codeq]

was hast du denn gegen einen minimalen spannbaum und den darin kürzesten weg einzuwenden? ist nach meinem wissensstand auch die effektivste methode, die matrix im array nach einem baum sortieren und dann nach DIJKSTRA den kürzesten weg suchen lassen....
und die zeitkomplexität ist auch leider nicht besser hinzubekommen...

[userOne]

ich mach es jetzt so:


zielpunkt bekommt ne 0, dann mache ich aus allen begehbaren feldern um die 0 herum eine 1, um alle 1en herum eine 2, um diese ne 3 usw., so fülle ich die map..

jetzt gehe ich vom startpunkt immer zur niedrigeren angrenzenden zahl und komme so auf kürzestem weg zur 0, meinem zielpunkt.

mfG
u1

[Codeq]

nennt sich spannbaum ja...
sag ich doch ;)