Page 1 of 1

### A* Pathfinding Algorithm help.

Posted: 27 Nov 2017, 06:44
I'm having some issues with my implementation of the A* Pathfinding algorithm and was wanting to chat with somebody who was familiar with it. I understand it completely, it's just my implementation of it works 90% of the time, but for some reason, when the player is in a certain location on the map (location changes depending on map layout and it seems the hidden locations are completely arbitrary and unpredictable) my algorithm just completely fails to find the player.

I'm completely stumped........

Now, keep in mind, that I only work on this game for about 3 hours at a time late at night before bed, about once or twice throughout the week sporadically. Everytime I go into the code to write more, I completely forget what's going on in the code, so the code is incredibly sloppy and the variable names are really hard to follow. So I honestly don't expect anybody to be able to help that much simply because the code probably won't make sense to anybody and I don't blame you for not putting in the time to learn it.

The issue on the current map file happens within the cells ranged 5,2 - 11,2. The tooltip that is displayed by the mouse while the game runs is the player's current coordinates. Use the arrow keys to move the player around. The A* Algorithm code starts on line 100 and ends on line 184.

Map file placed in "testmap.dat" exactly as is:

Code: Select all

``````********************
*------------------*
*------------------*
*------------------*
*----------*-------*
*----------*----e--*
*----m-----*-------*
*----------*-------*
*----------*-------*
*----------*-------*
*---********-------*
*------------------*
*****************--*
*------------------*
*--*****************
*------------------*
*****************--*
*------------------*
*------------------*
********************``````
The script requires no outside resources other than the map file in the same directory:

Code: Select all

``````SetBatchLines, -1
map:=A_ScriptDir . "\testmap.dat"
nodeNum:=g_index1:=fps_flag1:=g_index2:=fps_flag2:=start1:=start2:=keys:=mobCount:=pathList:=0
sidebarText=`n`n`n`n`nKeys = %keys%`n`nLife = 100
{
F_Index:=A_Index
{
GW:=A_Index
tile_%A_Index%_%F_Index%_type:=A_LoopField
}
GH:=F_Index
}
x:=y:=MARGIN:=5
w:=10 + (30 * GW)
h:=10 + (30 * GH)

Gui, Color, 000000
Gui, Font, s18

loop %GH%
{
B_Index:=A_Index
loop %GW%
{
nodeNum++
if (tile_%A_Index%_%B_Index%_type = "*")
Gui, Add, Edit, x%x% y%y% w30 h30 vtile_%A_Index%_%B_Index%  Disabled -VScroll +Center
else if (tile_%A_Index%_%B_Index%_type = "-")
Gui, Add, Edit, x%x% y%y% w30 h30 vtile_%A_Index%_%B_Index%  Disabled -VScroll +Center -Background
else if (tile_%A_Index%_%B_Index%_type = "k")
Gui, Add, Edit, x%x% y%y% w30 h30 vtile_%A_Index%_%B_Index%  Disabled -VScroll +Center -Background, k
else if (tile_%A_Index%_%B_Index%_type = "m")
{
mobCount++
mobX_%mobCount%:=A_Index
mobY_%mobCount%:=B_Index
Gui, Add, Edit, x%x% y%y% w30 h30 vtile_%A_Index%_%B_Index%  Disabled -VScroll +Center -Background, m
}
else if (tile_%A_Index%_%B_Index%_type = "l")
Gui, Add, Edit, x%x% y%y% w30 h30 vtile_%A_Index%_%B_Index%  Disabled -VScroll +Center -Background, L
else if (tile_%A_Index%_%B_Index%_type = "e")
{
Gui, Add, Edit, x%x% y%y% w30 h30 vtile_%A_Index%_%B_Index% Disabled -VScroll +Center -Background, E
playerX:=A_Index
playerY:=B_Index
}
tile_%A_Index%_%B_Index%_node:=nodeNum
node%nodeNum%_X:=A_Index
node%nodeNum%_Y:=B_Index
x+=30
}
y+=30
x:=5
}

wx:=w + 3
w+=60
hh:=h - 10
Gui, Font, White s8
Gui, Add, Text, x%wx% y5 w50 h%hh% vsidebar -Background, `n`n`n`n`nKeys = %keys%`n`nLife = 100

Loop %GH%
{
y1:=A_Index
Loop %GW%
{
x1:=A_Index
Loop %GH%
{
y2:=A_Index
Loop %GW%
{
x2:=A_Index
tile_%x1%_%y1%_%x2%_%y2%_h:=Abs(x1 - x2) + Abs(y1 - y2)
}
}
}
}

Gui, Show, w%w% h%h%, E-dventures
SetTimer, game_loop, 30
return

game_loop:
Gui, Submit, NoHide
if !g_index1
start1:=fps_flag1:=A_TickCount
g_index1++
StringTrimLeft, movements, movements, 1
iMovements:=movements
loop, parse, iMovements, "|"
{
playerX:=A_LoopField = "left" ? moveEd(playerX, playerY, "left") : (A_LoopField = "right" ? moveEd(playerX, playerY, "right") : playerX)
playerY:=A_LoopField = "up" ? moveEd(playerX, playerY, "up") : (A_LoopField = "down" ?  moveEd(playerX, playerY, "down") : playerY)
}
tooltip %playerX%`, %playerY%
loop %mobCount%
{
curMob:=A_Index
curTileX:=mobX_%A_Index%
curTileY:=mobY_%A_Index%
curNode:=aStarN(curTileX, curTileY)
tile_%curTileX%_%curTileY%_P:=curNode
mob_%A_Index%_path:=node%curNode%_F:=tile_%curTileX%_%curTileY%_G:=player:=playerFound:=0
oList:=curNode
cList:=""
Sort, oList, F sortByF D
if (aStarN(playerX, playerY) != lastPlayerNode)
{
Loop
{
player++
if (player >= 400) ;I had to add this otherwise when the player can't be found, the loop will never break. 400 is the maximum amount of squares to check.
break
if playerFound
break
StringSplit, oList_, oList, `,
curNode:=oList_1
curNodeX:=node%curNode%_X
curNodeY:=node%curNode%_Y
Loop 4
{
foox:=A_Index = 1 ? 1 : (A_Index = 3 ? -1 : 0)
fooy:=A_Index = 2 ? 1 : (A_Index = 4 ? -1 : 0)
{
continue
{
player++ ; Completely useless debugging variable
playerFound:=1
break
}
}
}
cList:=!cList ? curNode : cList . "," . curNode
fixList:=strLen(curNode) + 1
StringTrimLeft, oList, oList, %fixList%
Sort, oList, F sortByF D,

;;;;;;;;;;Debugging code. Uncomment this section to watch the A* algorithm in action.

;~ gui, font, s8
;~ guicontrol, font, tile_%curNodeX%_%curNodeY%
;~ guicontrol,, tile_%curNodeX%_%curNodeY%, %pp%
;~ sleep 500
lastNode:=curNode
}
loop, parse, pathList, `, ;Erases the previous path drawn for debugging.
{
loopX:=node%A_LoopField%_X
loopY:=node%A_LoopField%_Y
guicontrol,, tile_%loopX%_%loopY%,
}
pathList:=""
while (cNode != aStarN(curTileX, curTileY))
{
pathList:=!pathList ? aStarP(cNodeX, cNodeY) : aStarP(cNodeX, cNodeY) . "," . pathList
cNode:=aStarP(cNodeX, cNodeY)
cNodeX:=node%cNode%_X
cNodeY:=node%cNode%_Y
guicontrol,, tile_%cNodeX%_%cNodeY%, %player% ;Displays the current found path to the player. Varible "player" is equal to the number of squares checked. Don't bother asking why I named it "player", I honestly don't even know.
}
}
mob_%curMob%_path:=pathList
}

fpsCalc1:=A_TickCount - fps_flag1
if ( fpsCalc1 > 1000)
{
fps1:=g_index1
fps_flag1:=A_TickCount
g_index1:=0
}

movements:=""
lastPlayerNode:=aStarN(playerX, playerY)
;~ tooltip Player FPS:%fps1%
return

up::
movements:=movements . "|up"
return
down::
movements:=movements . "|down"
return
left::
movements:=movements . "|left"
return
right::
movements:=movements . "|right"
return

moveEd(x, y, dir)
{
global keys
playerTile :="tile_" . x . "_" . y
xx:=dir = "left" ? x - 1 : (dir = "right" ? x + 1 : x)
yy:=dir = "up" ? y - 1 : (dir = "down" ? y + 1 : y)
if (tile_%xx%_%yy%_type = "-")
{
%playerTile%_type:="-"
guicontrol,, %playerTile%,
guicontrol,, tile_%xx%_%yy%, E
}
else if (tile_%xx%_%yy%_type = "k")
{
keys++
%playerTile%_type:="-"

guicontrol,, sidebar, `n`n`n`n`nKeys = %keys%`n`nLife = 100
guicontrol,, %playerTile%,
guicontrol,, tile_%xx%_%yy%, E
}
else if (tile_%xx%_%yy%_type = "l")
{
if (keys >= 1)
{
keys--
%playerTile%_type:="-"
guicontrol,, sidebar, `n`n`n`n`nKeys = %keys%`n`nLife = 100
guicontrol,, %playerTile%,
guicontrol,, tile_%xx%_%yy%, E
}
else
{
xx:=dir = "left" ? xx + 1 : (dir = "right" ? xx - 1 : xx)
yy:=dir = "up" ? yy + 1 : (dir = "down" ? yy - 1 : yy)
}
}
else
{
xx:=dir = "left" ? xx + 1 : (dir = "right" ? xx - 1 : xx)
yy:=dir = "up" ? yy + 1 : (dir = "down" ? yy - 1 : yy)
}
return dir = "left" ? xx : (dir = "right" ? xx : (dir = "up" ? yy : yy))
}

aStarGetTile( node , w)
{
if (w = "x")
return
foo:=tile_%ax%_%ay%
return foo
}

aStarAdjNode( cx, cy, ax, ay )
{
bx:=cx + ax
by:=cy + ay
return aStarN( bx, by )
}

aStarN( nx, ny)
{
return tile_%nx%_%ny%_node
}

aStarH( sx, sy, tx, ty)
{
return tile_%sx%_%sy%_%tx%_%ty%_H
}

aStarG( gx, gy )
{
return tile_%gx%_%gy%_G
}

aStarP( px, py )
{
return tile_%px%_%py%_P
}

sortByF(a1, a2)
{
return node%a1%_F > node%a2%_F ? 1 : node%a1%_F < node%a2%_F ? -1 : 0
}

ESC::
GuiClose:
ExitApp``````

### Re: A* Pathfinding Algorithm help.

Posted: 27 Nov 2017, 22:11
Humpty bumpty sat on a wall.
Humpty bumpty had a great fall.

### Re: A* Pathfinding Algorithm help.

Posted: 30 Nov 2017, 03:40
Didn't really study your code much just saw the title and thought it would be fun to write a A* Pathfinding function.

Here is my version.

Code: Select all

``````Grid =	; Easier to create with monospace text
(Join`n
**********
* A      *
*    *   *
*******  *
*        *
*   * ****
* **     *
*   **   *
**  Z*   *
*        *
**********
)

; Create Array from Grid data
Closed := {}
for Y, Line in StrSplit(Grid, "`n")
for X, val in StrSplit(Line)
if (val = "*")
Closed[X,Y] := true
else if (val = "A")
X1 := X, Y1 := Y
else if (val = "Z")
X2 := X, Y2 := Y

; Find Path
Path := Astar_Grid(X1, Y1, X2, Y2, Closed)

; Display Grid and Path
Display := ""
for Y, Line in StrSplit(Grid, "`n")
for X, val in StrSplit(Line "`n")
{
for index, Cell in Path
if (Cell.X = X and Cell.Y = Y and index > 1 and index < Path.MaxIndex())
{
Display .= "+"
continue 2
}
Display .= val
}
Gui, font, s16, courier new
Gui, Add, Text,, % Grid "`n`n" Display
Gui, Show

; Astar_Grid and supporting functions
Astar_Grid(X1, Y1, X2, Y2, Closed := "")
{
if !IsObject(Closed)
Closed := {}
Open := {}, From := {}, G := {}, F := {}
Open[X1, Y1] := true, G[X1, Y1] := 0
F[X1, Y1] := Estimate_F(X1, Y1, X2, Y2)
while Open.MaxIndex()
{
Lowest_F_Set(X, Y, F, Open)
if (X = X2 and Y = Y2)
return From_Path(From, X, Y)
Open[X].Delete(Y)
if !Open[X].MaxIndex()
Open.Delete(X)
Closed[X, Y] := true
for index, Near in [{"X": X, "Y": Y-1},{"X": X-1, "Y": Y},{"X": X+1, "Y": Y},{"X": X, "Y": Y+1}]
{
if (Closed[Near.X, Near.Y] = true)
continue
Open[Near.X, Near.Y] := true, tG := G[X, Y] + 1
if (IsObject(G[Near.X, Near.Y]) and tG >= G[Near.X, Near.Y])
continue
From[Near.X, Near.Y] := {"X": X, "Y": Y}
G[Near.X, Near.Y] := tG
F[Near.X, Near.Y] := G[Near.X, Near.Y] + Estimate_F(Near.X, Near.Y, X2, Y2)
}
}
}

Estimate_F(X1, Y1, X2, Y2)
{
return Abs(X1-X2) + Abs(Y1-Y2)
}

Lowest_F_Set(ByRef X, ByRef Y, ByRef F, ByRef Set)
{
l := 0x7FFFFFFF
for tX , element in Set
for tY, val in element
if (F[tX, tY] < l)
l := F[tX, tY], X := tX, Y := tY
return l
}

From_Path(From, X, Y)
{
Path := {}, XY := {"X": X, "Y": Y}
Path.InsertAt(1, XY)
while (IsObject(From[XY.X, XY.Y]))
Path.InsertAt(1, XY:= From[XY.X, XY.Y])
return Path
}

Esc::ExitApp
``````
A good portion of the script is just about getting the map data into an array and displaying the map and result.

At its heart is the function Astar_Grid(X1, Y1, X2, Y2, Closed := "") which only really needs the XY of two end points and an Array where all the nodes that cannot be traveled through are defined.

Code: Select all

``````Closed := {}
Closed[1,3] := true
Closed[2,3] := true
Closed[3,3] := true
Path := Astar_Grid(2,2,4,4,Closed)``````
This would return an array holding the path between node 2,2 and node 4,4 if you cannot travel through 1,3 or 2,3, or 3,3.

It would be pretty easy to modify the function to allow other options like diagonal movement or different movement cost to go through different nodes.

This is also based around a grid where each node has 4 directions that can be moved to. It could be changed something more like airplane routes from city to city where one city might have 2 places to fly and another might have 15 places it connected to.

The algorithm is very similar just harder to get data like that into and organized in an array to pass to the function.

FG

### Re: A* Pathfinding Algorithm help.

Posted: 30 Nov 2017, 12:12
Everytime I go into the code to write more, I completely forget what's going on in the code I would take FanaticGuru's implicit advice, start from the beginning.
Good job FanaticGuru, it seems to work great! . Scripts and Functions.
I had a better viewing experince with the courier new font.
Spoiler