Pathfinding mal wieder

[faucon]

So, ich habe mich auch mal ein wenig mit Pathfinding beschäftigt, blicke aber noch nicht ganz durch. (Und komm mir jetzt niemand mit Lachsens A*-Teil ^.~)

Die Boardsuche hat diesen und diesen informativen Thread ergeben.

Interessieren würde mich die dort beschriebene Wall-Tracing Methode mit Luftlinie. Was ich glaube verstanden zu haben (Beispiel: Held wird zu Objekt bewegt):

1.) Es wird eine Luftlinie zwischen Startpunkt-Held und Objekt gezogen
2.) Der Held wird auf dieser Linie bewegt, bis er an ein Hindernis stößt
3.) Der Held wird durch das Wall Tracing um das Hindernis herum bewegt, bis er wieder an die Luftlinie stößt
4.) Und so weiter bis er beim Objekt ankommt

Die Luftlinie wird durch die Geradengleichung y=m*x+b berechnet.
m wird folgendermaßen berechnet: m = Delta x / Delta y bzw andersherum, damit keine Brüche rauskommen. b berechnet sich durch Umformung: b = y-m*x (x, y sind hierbei irgendwelche Werte der Geraden, bspw. der Startpunkt) Hier gelingt mir allerdings die Umsetzung nicht.

Beispiel:
Held H will zu Ziel Z am Hindernis vorbei

Dann müsste sich ja ergeben:
X1= 1, Y1 = 4, X2 = 5; Y2 = 2
m = 4/2 = 2
b = 4-2*1 = 2

Also: y = 2*x+2

Das ist allerdings die falsche Gleichung. Liegt wahrscheinlich an der doofen Anordnung des Koordinatensystems und daran, dass ich zu doof bin umzudenken.
Außerdem: Ich bekomme ja wie bei jeder Funktion nur einen X auf einen Y Wert. (Sonst wärs ja keine Funktion) Da dadurch zwangsweise diagonale Felderverbindungen entstehen würde es recht kompliziert werden den Helden ohne diagonale Schritte auf der Geraden entlangzubewegen.

Wäre nett wenn mir jemand helfen könnte.

[noch ein niemand]

Muss Held Z am Hindernis vorbei egal wo er oder Hindernis sich befinden?
Wenn nicht gib es einfach per Move Event ein.
Wenn doch erstelle ein Event das die Position des Helden mit dem Hindernis vergleicht.Lass den Helden jedesmal in eine andere als die normale Laufrichtung laufen wenn er auf eine Wand stoßen würde.

Falls das nicht hilft, zu den Formeln kann ich nichts sagen....hab in Mathe ne 5....

Den Helden kann mann aufgrund des Einzel-Feld-Systems des Makers nicht diagonal bewegen.Du kannst jedoch(falls dir das nicht zu kompliziert ist)anstatt nem char ein picture verwenden.Dessen X bzw. Y wert musst du durch eine Abfrage ob es bewegt wird dauernd ändern.Das Picture durch Tastatureingabe zu bewegen sollte kein Problem sein.Dem Picture eine Position zuzuweisen zu der es gehen sein sollte ebenfalls keine Probleme machen das sich dies einfach über die Move Picture -Schaltfläche machen lässt.

[cilence]

Den Helden kann mann aufgrund des Einzel-Feld-Systems des Makers nicht diagonal bewegen.

...

Wenn du wüsstest.

@Topic:
Nimm doch zum Umgehen die Funktion des Abfragens der Tile ID. Du kannst schließlich für die Felder in der Database eine bestimmte ID festlegen, so wie das z.B. auch bei Laufschritten gemacht wird. Für unbegehbare Tiles gibst du z.B. 5 ein. Frage die nächstliegenden nun ab, danach lässt du den Helden in die nächstbeste Richtung laufen. Kann er da nicht hin, läuft er wie in deinem Bsp. erst nach oben. Dann eben mal wieder neu berechnen. Dürfte ein bisschen Skriptarbeit erfordern, aber es geht schon. Einziges Prob seh ich darin, dass du den Helden mit Wahrscheinlichkeit entweder nur nach oben oder nur nach unten laufen lassen kannst.

[CapSeb]

Argh, bei deinen Berechnungen bekommt man ja Kopfschmerzen!

Also mal ganz von Vorne.
Dein Held bewegt sich von Start nach Ziel. Das Ganze ist zunächst erstmal eine gerade Linie. Daher lässt es sich abstrahieren. Verwendet wird eine lineare Funktion. Die benötigten Informationen erhält man über das Steigungsdreieck und das Umformen nach dem y-Achsenabschnitt.


Steigungsdreieck:
delta-Y durch delta-X ergibt die Steigung m. Dabei musst du aber auch die beiden Delta verwenden, also den Unterschied zwischen Start und Ziel. Delta-Y, d.h. der Y-Unterschied, ist in deinem Beispiel [2-4 = -2] und Delta-X, d.h. der X-Unterschied, ist [5-1 = 4]. Das kann man auch sehr gut bei hingucken erkennen: Zwei nach oben ( =-2, wegen dem umgedrehten Koordinatensystem) und vier nach rechts.
Beim Teilen würde eine Kommazahl entstehen. Daher ist es ratsam das Ganze in Prozenz, also Hundertsteln, auszudrücken: [-200%/4 = 50%]. Die Prozent verfallen im Maker natürlich, wodurch die Formel [-2*100/4 = 50] verwendet wird.


Y-Achsenabschnitt:
Wie richrig erkannt wird die Formel [y = m*x + b] nach [b = y - m*x] ungestellt. Da die Steigung und damit das Produkt m*x in Prozent ist, muss y noch in Prozent (Hundertstel) umgewandelt werden. Das macht erst im Maker Sinn, da dort das Prozentzeichen ignoriert wird. b wäre also [y*100% - m*x], oder im Maker dann [(b in Hunderstel) = y*100 - (m in Prozent)*x].
Das Ergebnis des Beispiels lautet dann bei Verwendung des Startpunktes [4*100 - (-50)*1 = 450].
450 Hunderstel sind 4,5 und somit, wie unschwer mit den Augen am Bild erkennbar, richtig.


Zu den Kästchenübergängen:
Die geraden Zahlen, mit den gerechnet wurde, sind im Grunde die Kästchenmitte. Die Kästchenübergänge sind als genau in der Mitte zwischen zwei Zahlen. Daraus ergibt sich eine Verschiebung um 0,5 - oder in Hundertstel ausgedrückt um 50.
Ein Kästchen kann man an auf der X-Ebene, also durch Links- oder Rechtsschritte, und auf der Y-Ebene, dementsprechend Hoch- oder Runterschritte, verlassen.
Zunächst überprüft man die x-Richtung. Dazu verwendet man wieder die Formel [y = x*m + b] oder nach x aufgelöst [x = (y-b)/m]. Liegt das Ziel weiter rechts, muss der Y-Wert bei einem halben Kästchen weiter rechts überprüft werden, also bei [y = (x+0,5)*m + b]. Durch das Ducheinander mit den Prozent und der fehlenden Kommarechnung muss im Maker die Formel lauten [y = ((x*100 +50)*(m in Prozent)/100 +(b in Hundertstel) +50)/100]. Bei dem Teil "*m/100" muss erst multipliziert und dann geteilt werden, sonst gibt es heftige Rundungsfehler. das Ende ist ebenfalls wegen der Rundung: Man will Wissen in welchem Bereich sich der Übergang befindet. Und Kästchenseiten beginnen und enden immer bei halben Zahlen, zB. 3,5 und 4,5 sind die Ränder von 4.
Ist der Y-Wert gleich dem momentanen Wert, befindet sich der Kästchenübergang also irgendwo rechts auf gleicher Höhe mit dem Held, womit die erste Bewegung getan wird. Ansonsten müsste man stehen bleiben und den y-Wert überprüfen. Ist das Ziel weiter links, wird ein anderer x-Wert überpüft (nicht +50 sondern -50) und dann natürlich nach links gelaufen.
Hier das Beispiel direkt am Anfang, also der erste Schritt (Makerwerte statt Prozente und Hundertstel):

m = 50
b = 450

y(test) = ((1*100 +50)*-(50)/100 + 450 + 50) /100 = (-75 +500)/100 = 5
--> 5 ist die momentan Höhe, also Schritt nach rechts.

Für hoch runter gilt die gleiche Prozedur. Aber eben mit y und x vertauscht. Das musst du dir mal selbst überlegen.


CapSeb

[faucon]

Erstmal danke für die Antworten.

@noch ein niemand:
Nutzt mir leider nichts.

@e.hoff:
Funktioniert leider im Endeffekt nciht so wie ichs gerne hätte.

@CapSeb:
Dankeschön
Wenn mein Zeitplan mal wieder etwas leerer ist werde ich mich da mal dransetzen.