Problem bei Pathfinding: Berechnen einer Luftline

[Teflo]

Hallöchen!
Hab ein technisches Problem. Ich hab überlegt, ob ich's nicht doch in's Dev-Comm Forum schreiben sollte, weil's eigentlich relativ wenig mitm Maker gemein hat, bzw. werde ich es vielleicht mal in ner Programmiersprache schreiben. Egal, ich schreib's erstmal hier hin.
Folgendes:
Ich bin dabei ein Pathfinding Skript zu schreiben. Nichts wahnsinniges, aber schon etwas knifflig. Ich dachte, ich fang einfach an und erweitere das evtl.

Im Moment benutze ich Wall-Tracing. Das bedeutet, dass der Held versucht zum Ziel zu gelangen, bis er auf eine Wand trifft. Dann schaltet er in den Wall-Tracing-Modus, in welchem der Held du Wand entlang läuft. Anders gesagt, Wenn der Held nach Rechts ( oder wahlweise auch Links ( Übrigens vom Helden aus) ) kann, geht er nach Rechts. Geht das nicht, dann geradeaus. Geht das auch nicht, dann Links, und ansonsten zurück.

Nun ist die Schwierigkeit daran, wann "Stop" zu sagen. Wann soll der Held aufhören, sich an der Wand "entlang zu tasten"? Die Antwort ist eigentlich ganz einfach:
Man zieht eine direkte Luftlinie von Start- zu Zielpunkt. Passiert der Held nun diese Linie im Wall-Trace Modus, stoppt er diesen und versucht wieder geradeaus zum Ziel zu gelangen. Das ist zwar ganz nett, sieht aber zum Teil unschön aus.
Manchmal ist es besser, eine Luftline von der aktuellen Position zu "zeichnen" und zu schauen, ob diese Linie begehbar, also sichtkontakt zum Ziel besteht. Diese Linie wird auch Libe-of-Sight genannt.
Hier mal ein Bild zum besseren Verständnis:
http://npshare.de/files/37/8155/Wall-Tracing-Prob.png
Das Problem ist jetzt, dass ich nicht weiß, wie ich das umsetzen soll :/
Aufjedenfall istdie Luftline erstmal wichtiger als die LoS!

PS: Mir ist grad eingefallen, dass man den Weg vorberechnen könnte und dabei Breadcrumbing benutzen könnte. Dadurch ließen sich solche unschönen Wege vermeiden.
PPS: Hier noch ein Artikel dazu: hier (http://www.ke.informatik.tu-darmstadt.de/lehre/ss06/se-spiele/slides/PathFinding-Awerbuch.pdf)

€dit: AH! Error 404! O_O

[Dhan]

Also im Wesentlichen arbeitet der Algorithmus mit der Luftlinie da ja so, dass er die direkte Luftlinie berechnet und bei einem Hindernis den Helden solange um das Objekt rumlaufen lässt, bis er wieder auf der Luftlinie ist, anschließend setzt er den Weg fort.
Woran das Implementieren scheitert, versteh ich nicht so ganz. Erstmal einen Algorithmus schreiben, der ohne einen Durchgang zu schaffen berechnen kann, ob man auf Luftlinie ist oder nicht (idealerweise als Funktion x->y, die auch auf y->x umschalten kann für vertikale Linien, je nach Verhältnis der x/y-Abstände), dann ein zwei Switche ("bereitsLuftlinieverlasen" "bereitsmitUhrzeigersinnversucht") und einen Algorithmus für am-Rand-entlanglaufen. (prüfe die 4 umliegenden Felder, Feld vorne zu und Feld neben einem frei -> laufe auf das neben dir, Feld vorne zu und das daneben auch, das hinter einem nicht -> laufe nach hinten etc) und die Sache müsste geritzt sein.
Kann durch dieses "Tracing with line of sight" immer noch leicht erweitert werden, einfach bei jedem neuen Feld prüfen, ob die Sichtlinie frei ist, ist ja ohne weiteres möglich und gut ist.

Wenn du mich fragst, hast du bei deiner Implementierung wahrscheinlich in dem riesigen Codesalat einen winzigen Fehler gemacht, der das ganze ausmacht.

Ansonsten, wie siehts mit Waypoints aus?
Kannst du die Karte vielleicht so in Waypoints aufteilen, dass du einen primitiven Dijkstra verwenden kannst?
An sich könnte ich mir sogar einen Algorithmus vorstellen, der gezielt möglichst große "Kammern" findet (sternförmige Gebiete, d.h. jeder Punkt einer Kammer kann durch eine direkte Linie von einem "Mittelpunkt" aus erreicht werden), in sie einen Waypoint setzt, Wege zu anderen Kammern anlegt und eine Kostenmatrix anlegt, mit der Dijkstra funktioniert... allerdings müsste man sich hier einige Gedanken noch machen (insbesondere weil man ja keine Zuordnung Tile -> Kammer anlegen kann ohne wirklich massiv Variablen zu benutzen und wenn man das macht, kann man gleich tileweise Dijkstra durchführen)
(beschreib am Besten, was du überhaupt machen willst wenn das nicht geheim ist)

[Teflo]

Ja, das Problem ist, dass ich nicht weiß, wie ich die Luftlinie berechne und Abfrage, ob der Held auf dieser Linie steht. Line-of-Sight wäre ja das gleiche, bis auf die Unterschiede, dass der Startpunkt die Aktuelle Position ist und noch zusätzlich abgefragt werden muss, ob die Tiles darauf auch frei sind ( Terrain ).

Ich möchte btw ein Point'n'Click Game machen. Mehr steht dazu noch nicht fest, weil ich erstmal die Engine haben will, bevor ich mich richtig reinlege. ^_^°

[Dhan]

Naja, Luftlinien sind lineare Funktionen.
Erstmal fragst du ab, ob sie eher horiziontal oder eher vertikal verläuft, sprich ob der Abstand Start-Ziel auf der X oder auf der Y-Achse größer ist.
Angenommen, der Abstand ist auf der X-Achse größer, die Linie also eher horiziontal.
Dann willst du die lineare Funktion finden, die die beiden verbindet.
Die Steigung der Funktion ist schonmal leicht zu berechnen, DeltaY durch DeltaX, anschließend den Start einsetzen und du bekommst die genaue Funktion raus, in einer Vorschrift der Art:
f(x) = m*x + c
bzw das m und das c.
Da der Maker nur Integer speichert, denk dran, die Zahlen immer mit 10 oder 100 multipliziert zu halten um eine oder zwei Nachkommastellen speichern zu können.
Daraus kannst du eine Zuordnung x -> y erzeugen wobei du natürlich da du feldweise arbeitest runden musst, wenn du zwei Nachkommastellen gespeichert hättest, würde aus einem 344 also eine 3, denn 3,44 gerundet ist 3.

Die Frage, ob man sich nun auf der Linie befindet, ist zu lösen, indem du die X-Koordinaten des Spielers in das System eingibst und rausschaust, ob es die richtigen Y-Koordinaten ausspuckt. (bzw andersrum bei eher vertikalen Linien)

[Teflo]

Hm, irgendwas hab ich falsch gemacht:


Delta_X = X2
Delta_X -= X1
Delta_Y = Y2
Delta_Y -= Y1
Delta_X_Abs = Delta_X
If Delta_X_Abs < 0 Then Delta_X_Abs *= -1
Delta_Y_Abs = Delta_Y
If Delta_Y_Abs < 0 Then Delta_Y_Abs *= -1
If Delta_X_Abs >= Delta_Y_Abs Then
Steigung = Delta_Y
Steigung *= 100
Steigung /= Delta_X
Else
Steigung = Delta_X
Steigung *= 100
Steigung /= Delta_Y
Endif
Das ist auf einer Seite, die wie folgt aufgerufen wird:


X1 = Start_X
X2 = Ziel_X
Y1 = Start_Y
Y2 = Ziel_Y
Call_Event ( This Site page 1 )
Steigung1 = Steigung
X1 = Held_X
X2 = Held_X
Y1 = Start_Y
Y2 = Ziel_Y
Call_Event ( This Site page 1 )
Steigung2 = Steigung
Steigung_Delta = Steigung1 - Steigung2
If Steigung_Delta < 0 Then Steigung_Delta *= -1
If Steigung_Delta <= Grenzwert Then
Switch Luftlinie = On
Else
Switch Luftlinie = Off
Endif
Jetzt weiß ich nicht, ob das überhaupt so stimmt und welchen Grenzwert ich einsetzen soll :/

€dit: Argh! Ich bin so blöd! xD
Hab die Formel vergessen und falsch verstanden! Mach mich nochmal ran und poste, wenns klappt

€dit²: kk, hab's fast:


Delta_X = X2
[...] bleibt gleich
Endif
Y-Ergebnis = Steigung * X1
zweite Seite:


X1 = Start_X
X2 = Ziel_X
Y1 = Start_Y
Y2 = Ziel_Y
Call_Event ( This Site page 1 )
Y_Start_Ziel = Y-Ergebnis
X1 = Held_X
X2 = Held_X
Y1 = Start_Y
Y2 = Ziel_Y
Call_Event ( This Site page 1 )
Y_Held_Ziel = Y-Ergebnis
Y-Delta = Y_Start_Ziel - Y_Held_Ziel
If Y-Delta < 0 Then Y-Delta *= -1
If Y-Delta <= Grenzwert Then
Switch Luftlinie = On
Else
Switch Luftlinie = Off
Endif


Das einzige Problem ist, das er rumspinnt, wenn Delta_Y = 0 ist, also eine perfekte horizontale Linie

[tarrox]

X1 = Start_X
X2 = Ziel_X
Y1 = Start_Y
Y2 = Ziel_Y
Call_Event ( This Site page 1 )
Y_Start_Ziel = Y-Ergebnis

->Ich frage mich was du ab jetzt machst? Dadurch das du X1 und X2 mit
Held_X besetzt erhaelst du nur die hoehe bis zum Ziel (Y-Abstand) und nicht
die Luftlinien-Steigung. Berechne hier doch einfach die Steigung die der Held
und das Ziel haben. Diese Vergleichst du dann mit der Steigung Start-Ziel ist
der Wert gleich dann ist man auf der Luftlinie sonst nicht. Wenn du hierbei
die Nachkommerstellen nach dem rechnen entfernst, erhaelst du zudem auch
schon einen Akzeptablen Grenzwert, wobei man hier mit den
Nachkommerstellen Spielen kann um noch bessere Ergebnisse zu erhalten
(auf 1 Nachkommastelle runden, auf die zweite etc).

X1 = Held_X
X2 = Held_X
Y1 = Start_Y
Y2 = Ziel_Y
Call_Event ( This Site page 1 )
Y_Held_Ziel = Y-Ergebnis
Y-Delta = Y_Start_Ziel - Y_Held_Ziel
If Y-Delta < 0 Then Y-Delta *= -1
If Y-Delta <= Grenzwert Then
Switch Luftlinie = On
Else
Switch Luftlinie = Off
Endif




Das einzige Problem ist, das er rumspinnt, wenn Delta_Y = 0 ist, also eine perfekte horizontale Linie
Du kannst vorm Rechnen abfragen ob Y-Start = Y Ziel und je nachdem einen anderen Weg zum rechnen verwenden, da man die Luftlinien-Bedingung auf einer horizontalen Luftlinie mit einem If abfragen kann. Ansonsten weiss ich nicht mehr ob der Maker ein Problem damit hat die 0 zu Teilen (oder mit der 0 zu Teilen(vieleicht beides^^)) kanns leider nicht testen.

[makenshi]

Ansonsten weiss ich nicht mehr ob der Maker ein Problem damit hat die 0 zu Teilen (oder mit der 0 zu Teilen(vieleicht beides^^)) kanns leider nicht testen.

Die 0 zu teilen (0 : 10) ist unproblematisch. Nur kannst du durch die 0 selbst nicht teilen. Das kann kein System afaik. Das wären ja unendlich viele Ergebnisse. Der Maker fängt das allerdings bei einer solchen Teilung den Fehler ab. Wenn du beim Maker versuchst durch 0 zu teilen, dann belässt der Maker die Variable einfach bei ihrem alten Wert.

Ergo:

20 / 0 = 2