A* Pathfinding Algorithm help.

[Eedis]

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

[Eedis]

Humpty bumpty sat on a wall.
Humpty bumpty had a great fall.

[FanaticGuru]

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

[Helgef]

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

Tested on this:

Code: Select all

**********             ***
* A      *             *Z*
*    *   *             * *
*******  *             * *
*        *             * *
*   * ****             * *
* **     *             * *
*   **   *************** *
**   *                   *
*    *   **** ************
**** *****  * *
   *          *
   ************

[manehscripts]

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

Hey bro, I'm grateful for your code. It's being useful for some jobs. Thanks.
Btw, have u performed any updates to the code over the years? Although it's working, maybe it may have been improved.

Thank you again!

[SpeedMaster]

Although it's working, maybe it may have been improved.

It would be pretty easy to modify the function to allow other options like diagonal movement ...

Hello,
Some time ago, I made a slightly modified version to also support 8 directions (diagonals)

Astar_Grid(X1, Y1, X2, Y2, closed, alldirs:=false)

Set alldirs to " True " to have diagonal path.

Code: Select all

; Astar_Grid and supporting functions by FanaticGuru 
;topic: https://autohotkey.com//boards/viewtopic.php?p=185714#p185714
Astar_Grid(X1, Y1, X2, Y2, closed, alldirs:=false)  
{

	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 (alldirs) ? [{"X": X, "Y": Y-1},{"X": X-1, "Y": Y},{"X": X+1, "Y": Y},{"X": X, "Y": Y+1},{"X": X-1, "Y": Y-1},{"X": X+1, "Y": Y-1},{"X": X-1, "Y": Y+1},{"X": X+1, "Y": Y+1}]
        : [{"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 := {}, pb := [], 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	
}

Cheers

[Qhimin]

Although it's working, maybe it may have been improved.

It would be pretty easy to modify the function to allow other options like diagonal movement ...

Hello,
Some time ago, I made a slightly modified version to also support 8 directions (diagonals)

Astar_Grid(X1, Y1, X2, Y2, closed, alldirs:=false)

Set alldirs to " True " to have diagonal path.

Code: Select all

; Astar_Grid and supporting functions by FanaticGuru 
;topic: https://autohotkey.com//boards/viewtopic.php?p=185714#p185714
Astar_Grid(X1, Y1, X2, Y2, closed, alldirs:=false)  
{

	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 (alldirs) ? [{"X": X, "Y": Y-1},{"X": X-1, "Y": Y},{"X": X+1, "Y": Y},{"X": X, "Y": Y+1},{"X": X-1, "Y": Y-1},{"X": X+1, "Y": Y-1},{"X": X-1, "Y": Y+1},{"X": X+1, "Y": Y+1}]
        : [{"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 := {}, pb := [], 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	
}

Cheers

Hello SpeedMaster,
Thank you very much for your scripts, they are simply awesome! And with this last update you gave exactly what I wanted.

I have been trying to create a path from the blue pixel to the green pixel in the image.



But sometimes, the function is returning me a strange path, as in this another image, in which it deviates from some points instead of maintaining a straight line.



I'm trying to make the path look like the following image.



Do you know how I can improve the accuracy to achieve this result?

Thank you again!

[FanaticGuru]

But sometimes, the function is returning me a strange path, as in this another image, in which it deviates from some points instead of maintaining a straight line.



I'm trying to make the path look like the following image.



Do you know how I can improve the accuracy to achieve this result?

In the algorithm's logic they are both the same number of steps and it is somewhat arbitrary which directions it check first. Could probably add a preference to always check first the same direction as last step to keep it going straight if possible. In theory this would make the algorithm slight less efficient but in practice it might actually be faster because straight probably is the most likely direction to succeed for something like solving typical mazes.

@SpeedMaster like the 8 directions I always meant to add a variable number of directions and a movement cost in each direction. Then you could do things like airplane routes. Or other move complex decision making processes. The algorithm part is not that hard. The how to structure the data array and get information into the array efficiently was the harder problem that needed some thought.

FG

[manehscripts]

Hello,
Some time ago, I made a slightly modified version to also support 8 directions (diagonals)

Astar_Grid(X1, Y1, X2, Y2, closed, alldirs:=false)

Set alldirs to " True " to have diagonal path.

Cheers

Hey bro! I forgot to thank you! Thank you very much !!

[matt4068]

But sometimes, the function is returning me a strange path, as in this another image, in which it deviates from some points instead of maintaining a straight line.



I'm trying to make the path look like the following image.



Do you know how I can improve the accuracy to achieve this result?

In the algorithm's logic they are both the same number of steps and it is somewhat arbitrary which directions it check first. Could probably add a preference to always check first the same direction as last step to keep it going straight if possible. In theory this would make the algorithm slight less efficient but in practice it might actually be faster because straight probably is the most likely direction to succeed for something like solving typical mazes.

@SpeedMaster like the 8 directions I always meant to add a variable number of directions and a movement cost in each direction. Then you could do things like airplane routes. Or other move complex decision making processes. The algorithm part is not that hard. The how to structure the data array and get information into the array efficiently was the harder problem that needed some thought.

FG

How did you get this working on a pbitmap image? Can you share your code?

[Geralt from Tibia]

Hi there,

thank you so much guys for your contribution to the topic. I've also decided to play with it for a little while and came up with an idea to apply Pythagorean theorem to the Estimate_F function:

Code: Select all

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

That way I no longer get weird paths as shown on the left side of the attached screenshot

updated.PNG (9.42 KiB) Viewed 223 times

I also wanted it to only step diagonally when it absolutely has to (eg. it would have to make more than 2 steps). First thought was adding a condition when looping through all dirs:

Code: Select all

if (index > 4 )
	tG := G[X, Y] + 2.1
else
	tG := G[X, Y] + 1

however, I still ocasionally get unnecessary steps, any thoughts of possible solutions to the issue?