Metapher
Mitglied
ich mach mich grdae an pathfinding bequem...nur leider wird es oft nur für Basic und C beschrieben...es gibt zwar einige allgemeine versionen aber diese sind schwer zu erklären...
ich fasse mal kurz zusammen...
es gibt ne figur die zu einem ziel gelangen soll, die jedoch auf nichtbegehbare objekte aufpassen muss und dadurch den kürzesten weg suchen soll
soweit so gut...
also soll man der figur einen startpunkt geben (x,y) und nen zielpunkt(x,y)
(alles in 2D)
damit die figur erstmal sieht wo sie hinlaufen muss werden um die figur herum "Nodes" gesetzt.
nodes sind punkte die 5werte enthalten:
x-wert
y-wert
entfernug zum startpunkt (G)
entfernug zum zielpunkt (H)
gesamte entfernung (cost) (F)
(siehe bild)
die figur sucht sich nun die nodes nacheinander heraus, welche die kleinste enfernung zum ziel haben.
diese nodes müssen aber in eine art "to-do-liste" eingetragen werden damit sie abgearbeitet werden können...jedoch fängt man mit den nodes nicht einfach an x=1 und y=1 an sondern wenn die figur nunmal auf x=14 und y=10 steht müssen die nodes sich kreuzförmig um die figur ausbreiten....
und nachdem ein node abgearbeitet wurde müssen kreuzförmig neue nodes erstellt werden um den node der gewählt wurde
und wenn die figur sich den weg zum ziel überlegt hat
kann sie auch dorthin laufen
und hier die englische zusammenfassung:
es gibt auch diverse code varianten für A*4, A*8 und A*8+
hier mal die A*4 variante für blitzbasic:
das ganze hört ich ja nicht schwer an....ist es aber...besonders in PHP
mein problem in php is derzeitig diese "to-do-liste" in der die nodes eingetragen werden! lässt sicheinfach nicht richtig realisieren..
links dazu:
deutschte BlitzBasic Page:
http://www.blitzbase.de/artikel/path_1.htm
englische A* anleitung:
http://www.policyalmanac.org/games/aStarTutorial.htm
ich fasse mal kurz zusammen...
es gibt ne figur die zu einem ziel gelangen soll, die jedoch auf nichtbegehbare objekte aufpassen muss und dadurch den kürzesten weg suchen soll
soweit so gut...
also soll man der figur einen startpunkt geben (x,y) und nen zielpunkt(x,y)
(alles in 2D)
damit die figur erstmal sieht wo sie hinlaufen muss werden um die figur herum "Nodes" gesetzt.
nodes sind punkte die 5werte enthalten:
x-wert
y-wert
entfernug zum startpunkt (G)
entfernug zum zielpunkt (H)
gesamte entfernung (cost) (F)
(siehe bild)
die figur sucht sich nun die nodes nacheinander heraus, welche die kleinste enfernung zum ziel haben.
diese nodes müssen aber in eine art "to-do-liste" eingetragen werden damit sie abgearbeitet werden können...jedoch fängt man mit den nodes nicht einfach an x=1 und y=1 an sondern wenn die figur nunmal auf x=14 und y=10 steht müssen die nodes sich kreuzförmig um die figur ausbreiten....
und nachdem ein node abgearbeitet wurde müssen kreuzförmig neue nodes erstellt werden um den node der gewählt wurde
und wenn die figur sich den weg zum ziel überlegt hat
kann sie auch dorthin laufen
und hier die englische zusammenfassung:
Summary of the A* Method
Okay, now that you have gone through the explanation, let’s lay out the step-by-step method all in one place:
1) Add the starting square to the open list.
2) Repeat the following:
a) Look for the lowest F cost square on the open list. We refer to this as the current square.
b) Switch it to the closed list.
c) For each of the 8 squares adjacent to this current square …
If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.
If it isn’t on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square.
If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.
d) Stop when you:
Add the target square to the open list, in which case the path has been found, or
Fail to find the target square, and the open list is empty. In this case, there is no path.
3) Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.
es gibt auch diverse code varianten für A*4, A*8 und A*8+
hier mal die A*4 variante für blitzbasic:
Code:
Function pathfinding0(startx,starty,endx,endy)
Delete Each node
Delete Each open
Delete Each path
Dim nodemap(mapwidth,mapheight)
If startx=endx And starty=endy Then Return
node.node=New node
node\x=startx
node\y=starty
open.open=New open
open\node=node
nodemap(startx,starty)=1
.again0
node=Null
cost=2147483647
For open=Each open
delta=Abs(open\node\x-endx)+Abs(open\node\y-endy)
If open\node\cost+delta<cost Then
cost=open\node\cost+delta
node=open\node
tempopen.open=open
EndIf
Next
If node=Null Then Return
Delete tempopen
For i=0 To 3
x=node\x+dirx(i)
y=node\y+diry(i)
If x=>0 And y=>0 And x<=mapwidth And y<=mapheight Then
If map(x,y)=0 And nodemap(x,y)=0 Then
tempnode.node=New node
tempnode\parent=node
tempnode\cost=node\cost+1
tempnode\x=x
tempnode\y=y
open.open=New open
open\node=tempnode
nodemap(x,y)=1
If x=endx And y=endy Then finish=1:Exit
EndIf
EndIf
Next
If finish=0 Then Goto again0
While tempnode\parent<>Null
path.path=New path
path\node=tempnode
tempnode=tempnode\parent
Wend
path.path=New path
path\node=tempnode
End Function
das ganze hört ich ja nicht schwer an....ist es aber...besonders in PHP
mein problem in php is derzeitig diese "to-do-liste" in der die nodes eingetragen werden! lässt sicheinfach nicht richtig realisieren..
links dazu:
deutschte BlitzBasic Page:
http://www.blitzbase.de/artikel/path_1.htm
englische A* anleitung:
http://www.policyalmanac.org/games/aStarTutorial.htm
Zuletzt bearbeitet: