A*4 pathfinding

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:

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:

Metapher

Mitglied
ich progge derweil ein game in php indem man rumlaufen kann...aber immer zu klicken *laufhoch* *laufrunter* war langsam zu langweilig und jetz wollt ich es über A* machen sodass man auf die karte klickt und das männchen hinläuft


und mein problem isses jetz die Nodes:
1. zu erstellen (um den spieler drumherum)
2. die in diese "to-do-liste" einzutragen