A* Pathfinding Algorithm help.

Get help with using AutoHotkey and its commands and hotkeys
User avatar
Eedis
Posts: 59
Joined: 30 Sep 2013, 11:09

A* Pathfinding Algorithm help.

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
Loop, Read, %map%
{
	F_Index:=A_Index
	Loop, Parse, A_LoopReadLine
	{
		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)
				adjNode:=aStarAdjNode( curNodeX, curNodeY, foox, fooy  )
				adjNodeX:=node%adjNode%_X
				adjNodeY:=node%adjNode%_Y
				if cList not contains %adjNode%
				{
					if (tile_%adjNodeX%_%adjNodeY%_type = "*")
						continue
					if oList not contains %adjNode%
						oList:=oList . "," . adjNode
					tile_%adjNodeX%_%adjNodeY%_G:=aStarG(curNodeX, curNodeY) + 1
					node%adjNode%_F:=aStarG(adjNodeX, adjNodeY) + aStarH(adjNodeX, adjNodeY, playerX, playerY)
					tile_%adjNodeX%_%adjNodeY%_P:=curNode
					if (adjNode = aStarN(playerX, playerY))
					{
						player++ ; Completely useless debugging variable
						playerFound:=1
						break
					}
				}
				else if (aStarG(curNodeX, curNodeY) < aStarG(adjNodeX, adjNodeY))
					tile_%adjNodeX%_%adjNodeY%_P:=curNode
			}
			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%
			;~ pp:=aStarP( adjNodeX, adjNodeY )
			;~ guicontrol,, tile_%curNodeX%_%curNodeY%, %pp%
			;~ sleep 500
			lastNode:=curNode
		}
		cNode:=adjNode
		cNodeX:=adjNodeX
		cNodeY:=adjNodeY
		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
Science is not about answering questions; it's about finding new questions to ask.
User avatar
Eedis
Posts: 59
Joined: 30 Sep 2013, 11:09

Re: A* Pathfinding Algorithm help.

27 Nov 2017, 22:11

Humpty bumpty sat on a wall.
Humpty bumpty had a great fall.
Science is not about answering questions; it's about finding new questions to ask.
FanaticGuru
Posts: 1355
Joined: 30 Sep 2013, 22:25

Re: A* Pathfinding Algorithm help.

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
Last edited by FanaticGuru on 30 Nov 2017, 13:13, edited 1 time in total.
Hotkey Help - Help Dialog for Currently Running AHK Scripts

AHK Startup - Consolidate Multiply AHK Scripts with one Tray Icon

[Function] Timer - Create and Manage Timers
Helgef
Posts: 3844
Joined: 17 Jul 2016, 01:02
Contact:

Re: A* Pathfinding Algorithm help.

30 Nov 2017, 12:12

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

Return to “Ask For Help”

Who is online

Users browsing this forum: Bing [Bot], ForbidInjustice, MannyKSoSo, vsub and 177 guests