if your game is like a turn-based game where 1 entity moves at a time then a single path would suffice and you just reuse it for each entity generating a new path each time, but if its like a RTS where each entity would need its own path and several entities move simultaneously then you would use multiple paths or a path for each entity, once a path is generated it remains in memory at the index you used in SearchMap* functions so each unit in your game will be completely independent.
I hope Phaelax does not mind me editing and reposting his lib but I spent some time this afternoon making the whole thing more multi-path friendly after reading your post, I added a few functions to set/get the start and target marks for each path, the original example used the same global start+target I have made it so each path index can have its own set of markers by adding a type array and some functions into the lib
in this example use F1(path 0) to F4(path 3) to set the active path, set start and target markers and generate a path as usual, you will see when switching between paths (F*) that each path is now independent
Modified AStar.agc
/* *************************************************
* Original Author: IanM (DBP)
* Ported to AGK: Phaelax
* Date: June 22, 2013
* *************************************************
* COMMANDS
* ----------------------------------------
* CreateSearchMap(mapwidth, mapheight, cellwidth, cellheight)
* CreateSearchPathList(NumberOfPaths)
* SetSearchMap(x, y, value) (values greater than 0 are not walkable)
* GetSearchMap(x, y)
* GetSearchPathX(path, move)
* GetSearchPathY(path, move)
* GetSearchPathSize(path)
* SetSearchRestrictDiagonals(mode) (1 will avoid diagonals between blocked cells)
* SetMaximumCost(cost)
*
* SearchMapAStar4(path, startX, startY, finishX, finishY)
* SearchMapAStar8(path, startX, startY, finishX, finishY)
* SearchMapFlood4(path, startX, startY, finishX, finishY)
* SearchMapFlood8(path, startX, startY, finishX, finishY)
*
* GetFloodCost(finishX, finishY) (Uses previous Flood4 search to identify cost of specified target)
*************************************************
* Ported to AGK2: PartTimeCoder
* ----------------------------------------
* Date: July 29, 2017
* ----------------------------------------
* Removed: GoSub and Init function requirments
* Fixed: now works with #Option_Explicit
* Added: DrawSearchPath(path, col)
* Added: DrawSearchMap(col)
* Added: DrawSearchGrid(col)
* Added: WorldToGridX(world_x)
* Added: WorldToGridY(world_y)
* Added: GridToWorldX(grid_x)
* Added: GridToWorldY(grid_y)
* Changed: CreateSearchMap() added cell dimensions for draw functions
* Fixed: SearchMapFlood8() Throwing out of bounds error. (Y=-1)
* Fixed: SearchMapAStar8() Throwing out of bounds error when no path found. (Y=-1)
* ----------------------------------------
* Date: June 16, 2018
* ----------------------------------------
* Added: SetPathMarker(Path, marker, x, y)
* Added: GetPathMarkerX(Path, marker)
* Added: GetPathMarkerY(Path, marker)
* Added: DrawPathMarker(Path, marker, col)
* Added: GetSearchRestrictDiagonals()
*/
// ===================================================
type SEARCH_Position_t
x as integer
y as integer
endtype
type SEARCH_TileInformation_t
status as integer
G as integer
H as integer
F as integer
parentX as integer
parentY as integer
O as integer
endtype
type SEARCH_OpenListItem_t
F as integer
x as integer
y as integer
endtype
type SEARCH_Markers_t
startX
startY
targetX
targetY
endtype
// ===================================================
// Initialize search variables
// ===================================================
global SEARCH_MapWidth as integer
global SEARCH_MapHeight as integer
global SEARCH_CellWidth as integer
global SEARCH_CellHeight as integer
global SEARCH_MaxPaths as integer
global SEARCH_CurrentPosition as SEARCH_Position_t
// Used for HEAP format used in A*
global SEARCH_OpenListSize as integer
// Used for flood4 search
global SEARCH_OpenListTop as integer
global SEARCH_OpenListBottom as integer
// Optimization for flood4 search
global SEARCH_PreviousStart as SEARCH_Position_t
// General search parameters
global SEARCH_RestrictedDiagonals as integer
global SEARCH_MaximumCost as integer
global SEARCH_ParametersChanged as integer
global SEARCH_LastSearch as integer
// Initialize flags
global SEARCH_PathsInitialized as integer
global SEARCH_MapInitialized as integer
global dim SEARCH_Map[SEARCH_MapWidth, SEARCH_MapHeight] as integer
global dim SEARCH_TileInfo[SEARCH_MapWidth, SEARCH_MapHeight] as SEARCH_TileInformation_t
global dim SEARCH_OpenList[SEARCH_MapWidth * SEARCH_MapHeight] as SEARCH_OpenListItem_t
global dim SEARCH_SearchPath[SEARCH_MaxPaths, SEARCH_MapWidth * SEARCH_MapHeight] as SEARCH_Position_t
global dim SEARCH_PathSize[SEARCH_MaxPaths] as integer
// ===================================================
//
// ===================================================
#constant PATH_START 0
#constant PATH_TARGET 1
function SetPathMarker(Path, marker, x, y)
if Path >=0 and Path <=SEARCH_Markers.length
select marker
case PATH_START
SEARCH_Markers[Path].startX=x
SEARCH_Markers[Path].startY=y
endcase
case PATH_TARGET
SEARCH_Markers[Path].targetX=x
SEARCH_Markers[Path].targetY=y
endcase
endselect
endif
endfunction
function GetPathMarkerX(Path, marker)
if Path >=0 and Path <=SEARCH_Markers.length
select marker
case PATH_START
exitfunction SEARCH_Markers[Path].startX
endcase
case PATH_TARGET
exitfunction SEARCH_Markers[Path].targetX
endcase
endselect
endif
endfunction -1
function GetPathMarkerY(Path, marker)
if Path >=0 and Path <=SEARCH_Markers.length
select marker
case PATH_START
exitfunction SEARCH_Markers[Path].startY
endcase
case PATH_TARGET
exitfunction SEARCH_Markers[Path].targetY
endcase
endselect
endif
endfunction -1
function DrawPathMarker(Path, marker, col)
if Path>=0 and Path <=SEARCH_Markers.length
markerX as integer
markerY as integer
markerX=GetPathMarkerX(Path, marker)
markerY=GetPathMarkerY(Path, marker)
if markerX<>-1 and markerY<>-1
DrawBox(markerX*SEARCH_CellWidth,markerY*SEARCH_CellHeight,markerX*SEARCH_CellWidth+SEARCH_CellWidth,markerY*SEARCH_CellHeight+SEARCH_CellHeight, col, col, col, col, 1)
endif
endif
endfunction
// ===================================================
//
// ===================================================
Function WorldToGridX(world_x)
Result as integer
Result = world_x/SEARCH_CellWidth
EndFunction Result
Function WorldToGridY(world_y)
Result as integer
Result = world_y/SEARCH_CellHeight
EndFunction Result
// ===================================================
//
// ===================================================
Function GridToWorldX(grid_x)
Result as integer
Result = grid_x*SEARCH_CellWidth
EndFunction Result
Function GridToWorldY(grid_y)
Result as integer
Result = grid_y*SEARCH_CellHeight
EndFunction Result
// ===================================================
//
// ===================================================
function DrawSearchPath(path, col)
i as integer
x as integer
y as integer
for i = 1 to GetSearchPathSize(path)-1
x = getSearchPathX(path, i)
y = getSearchPathY(path, i)
drawBox(x*SEARCH_CellWidth,y*SEARCH_CellHeight,x*SEARCH_CellWidth+SEARCH_CellWidth,y*SEARCH_CellHeight+SEARCH_CellHeight,col,col,col,col, 1)
next i
endfunction
// ===================================================
//
// ===================================================
function DrawSearchMap(col)
x as integer
y as integer
for x = 0 to SEARCH_MapWidth
for y = 0 to SEARCH_MapHeight
if GetSearchMap(x,y) > 0
drawBox(x*SEARCH_CellWidth,y*SEARCH_CellHeight,x*SEARCH_CellWidth+SEARCH_CellWidth,y*SEARCH_CellHeight+SEARCH_CellHeight,col,col,col,col, 1)
endif
next y
next x
endfunction
// ===================================================
//
// ===================================================
function DrawSearchGrid(col)
// draw grid lines
x as integer
y as integer
for x = 0 to SEARCH_MapWidth-1
for y = 0 to SEARCH_MapHeight-1
drawBox(x*SEARCH_CellWidth,y*SEARCH_CellHeight,x*SEARCH_CellWidth+SEARCH_CellWidth,y*SEARCH_CellHeight+SEARCH_CellHeight,col,col,col,col, 0)
next y
next x
endfunction
// ===================================================
//
// ===================================================
function CreateSearchMap(map_width, map_height, cell_width, cell_height)
SEARCH_MapWidth = map_width
SEARCH_MapHeight = map_height
SEARCH_CellWidth = cell_width
SEARCH_CellHeight = cell_height
SEARCH_PreviousStart.X = -9999
SEARCH_PreviousStart.Y = -9999
undim SEARCH_Map[]
undim SEARCH_TileInfo[]
undim SEARCH_OpenList[]
dim SEARCH_Map[SEARCH_MapWidth, SEARCH_MapHeight]as integer
dim SEARCH_TileInfo[SEARCH_MapWidth, SEARCH_MapHeight] as SEARCH_TileInformation_t
dim SEARCH_OpenList[SEARCH_MapWidth * SEARCH_MapHeight] as SEARCH_OpenListItem_t
SEARCH_MapInitialized = 1
endfunction
// ===================================================
//
// ===================================================
function CreateSearchPathLists(Paths as integer)
SEARCH_MaxPaths = Paths
undim SEARCH_SearchPath[]
undim SEARCH_PathSize[]
global dim SEARCH_SearchPath[SEARCH_MaxPaths, SEARCH_MapWidth * SEARCH_MapHeight] as SEARCH_Position_t
global dim SEARCH_PathSize[SEARCH_MaxPaths] as integer
global SEARCH_Markers as SEARCH_Markers_t[]
SEARCH_Markers.length = SEARCH_MaxPaths
path as integer
for path=0 to SEARCH_MaxPaths
SEARCH_Markers[path].startX=-1
SEARCH_Markers[path].startY=-1
SEARCH_Markers[path].targetX=-1
SEARCH_Markers[path].targetY=-1
next
SEARCH_PathsInitialized = 1
endfunction
// ===================================================
//
// ===================================================
function SetSearchMap(X as integer, Y as integer, Value as integer)
if SEARCH_MapInitialized = 0 then exitfunction
if X < 0 or X >= SEARCH_MapWidth then exitfunction
if Y < 0 or Y >= SEARCH_MapHeight then exitfunction
SEARCH_PreviousStart.X = -9999
SEARCH_Map[X,Y] = Value
endfunction
// ===================================================
//
// ===================================================
function GetSearchMap(X as integer, Y as integer)
if SEARCH_MapInitialized = 0 then exitfunction 0
if X < 0 or X >= SEARCH_MapWidth then exitfunction 0
if Y < 0 or Y >= SEARCH_MapHeight then exitfunction 0
V as integer
v = SEARCH_Map[X,Y]
exitfunction v
endfunction 0
// ===================================================
//
// ===================================================
function GetSearchPathX(Path as integer, Move as integer)
if SEARCH_PathsInitialized = 0 then exitfunction -1
if Path < 0 or Path > SEARCH_MaxPaths then exitfunction -1
if Move < 0 or Move > SEARCH_PathSize[Path] then exitfunction -1
x as integer
x = SEARCH_SearchPath[Path, SEARCH_PathSize[Path]-Move].X
exitfunction x
endfunction -1
// ===================================================
//
// ===================================================
function GetSearchPathY(Path as integer, Move as integer)
if SEARCH_PathsInitialized = 0 then exitfunction -1
if Path < 0 or Path > SEARCH_MaxPaths then exitfunction -1
if Move < 0 or Move > SEARCH_PathSize[Path] then exitfunction -1
y as integer
y = SEARCH_SearchPath[Path, SEARCH_PathSize[Path]-Move].Y
exitfunction y
endfunction -1
// ===================================================
//
// ===================================================
function GetSearchPathSize(Path as integer)
if SEARCH_PathsInitialized = 0 then exitfunction -1
p as integer
p = SEARCH_PathSize[Path]
if Path >= 0 or Path <= SEARCH_MaxPaths then exitfunction p
endfunction -1
// ===================================================
//
// ===================================================
function SetSearchRestrictDiagonals(Mode as integer)
if SEARCH_RestrictedDiagonals <> Mode
SEARCH_RestrictedDiagonals = Mode
SEARCH_ParametersChanged = 1
endif
endfunction
function GetSearchRestrictDiagonals()
endfunction SEARCH_RestrictedDiagonals
// ===================================================
//
// ===================================================
function SetSearchMaximumCost(Cost as integer)
if SEARCH_MaximumCost <> Cost*10
SEARCH_MaximumCost = Cost * 10
SEARCH_ParametersChanged = 1
endif
endfunction
// ===================================================
//
// ===================================================
function GetFloodCost(TX as integer, TY as integer)
if SEARCH_MapInitialized = 0 then exitfunction -1
if SEARCH_PathsInitialized = 0 then exitfunction -1
F as integer
F = SEARCH_TileInfo[TX,TY].F
if SEARCH_PreviousStart.X <> -9999 then exitfunction F
endfunction -1
// ===================================================
//
// ===================================================
function SEARCH_SingleStepCost(X as integer, Y as integer)
if X = 0 or Y = 0 then exitfunction 10
endfunction 14
// ===================================================
//
// ===================================================
function SEARCH_EstimateDistance(X as integer, Y as integer, TX as integer, TY as integer)
Distance as integer
Distance = (abs(X - TX) + abs(Y - TY))*10
endfunction Distance
// ===================================================
//
// ===================================================
function SEARCH_InitializeTileInfo(SX as integer, SY as integer)
SEARCH_OpenListSize=0
SEARCH_PopulateTileInfo()
SEARCH_TileInfo[SX, SY].G = 0
SEARCH_TileInfo[SX, SY].H = SEARCH_EstimateDistance(SX, SY, 0, 0)
SEARCH_TileInfo[SX, SY].F = SEARCH_TileInfo[SX, SY].H
SEARCH_TileInfo[SX, SY].Status = 1
SEARCH_TileInfo[SX, SY].ParentX = SX
SEARCH_TileInfo[SX, SY].ParentY = SY
SEARCH_AddToOpenList(SX, SY)
endfunction
// ===================================================
//
// ===================================================
function SEARCH_PopulateTileInfo()
X as integer
Y as integer
for X = 0 to SEARCH_MapWidth
for Y = 0 to SEARCH_MapHeight
SEARCH_TileInfo[X,Y].F = 0
if SEARCH_Map[X,Y] > 0
SEARCH_TileInfo[X,Y].Status = 2
else
SEARCH_TileInfo[X,Y].Status = 0
endif
next Y
next X
endfunction
// ===================================================
//
// ===================================================
function SEARCH_AddToOpenList(X as integer, Y as integer)
Parent as integer
Child as integer
Cost as integer
Child = SEARCH_OpenListSize
inc SEARCH_OpenListSize
Cost = SEARCH_TileInfo[X,Y].F
do
if Child <= 0 then exit
Parent = (Child - 1)/2
if SEARCH_OpenList[Parent].F < Cost then exit
SEARCH_OpenList[Child].F = SEARCH_OpenList[Parent].F
SEARCH_OpenList[Child].X = SEARCH_OpenList[Parent].X
SEARCH_OpenList[Child].Y = SEARCH_OpenList[Parent].Y
Child = Parent
loop
SEARCH_OpenList[Child].F = Cost
SEARCH_OpenList[Child].X = X
SEARCH_OpenList[Child].Y = Y
endfunction
// ===================================================
//
// ===================================================
function SEARCH_GetLowestCostOpen()
Parent as integer
Child as integer
Cost as integer
if SEARCH_OpenListSize <= 0 then exitfunction 0
dec SEARCH_OpenListSize
SEARCH_CurrentPosition.X = SEARCH_OpenList[0].X
SEARCH_CurrentPosition.Y = SEARCH_OpenList[0].Y
Cost = SEARCH_OpenList[SEARCH_OpenListSize].F
X as integer
Y as integer
X = SEARCH_OpenList[SEARCH_OpenListSize].X
Y = SEARCH_OpenList[SEARCH_OpenListSize].Y
Parent = 0
do
Child = (2 * Parent) + 1
if Child >= SEARCH_OpenListSize then exit
if Child+1 < SEARCH_OpenListSize
if SEARCH_OpenList[Child].F > SEARCH_OpenList[Child + 1].F then inc Child
endif
if SEARCH_OpenList[Child].F < Cost
SEARCH_OpenList[Parent].F = SEARCH_OpenList[Child].F
SEARCH_OpenList[Parent].X = SEARCH_OpenList[Child].X
SEARCH_OpenList[Parent].Y = SEARCH_OpenList[Child].Y
Parent = Child
else
exit
endif
loop
SEARCH_OpenList[Parent].F = Cost
SEARCH_OpenList[Parent].X = X
SEARCH_OpenList[Parent].Y = Y
if SEARCH_TileInfo[SEARCH_CurrentPosition.X,SEARCH_CurrentPosition.Y].Status = 2 then exitfunction SEARCH_GetLowestCostOpen()
SEARCH_TileInfo[SEARCH_CurrentPosition.X,SEARCH_CurrentPosition.Y].Status = 2
endfunction 1
// ===================================================
//
// ===================================================
function SEARCH_QueueOntoOpen(X as integer, Y as integer)
inc SEARCH_OpenListTop
SEARCH_OpenList[SEARCH_OpenListTop].X = X
SEARCH_OpenList[SEARCH_OpenListTop].Y = Y
endfunction
// ===================================================
//
// ===================================================
function SEARCH_UnqueueFromOpen()
if SEARCH_OpenListBottom => SEARCH_OpenListTop then exitfunction 0
inc SEARCH_OpenListBottom
SEARCH_CurrentPosition.X = SEARCH_OpenList[SEARCH_OpenListBottom].X
SEARCH_CurrentPosition.Y = SEARCH_OpenList[SEARCH_OpenListBottom].Y
endfunction 1
// ===================================================
//
// ===================================================
function SEARCH_BuildPath(Path as integer, SX as integer, SY as integer, TX as integer, TY as integer)
Moves as integer
X as integer
Y as integer
Moves = 0
X = TX
Y = TY
SEARCH_SearchPath[Path, Moves].X = X
SEARCH_SearchPath[Path, Moves].Y = Y
repeat
inc Moves
SEARCH_SearchPath[Path, Moves].X = SEARCH_TileInfo[X,Y].ParentX
SEARCH_SearchPath[Path, Moves].Y = SEARCH_TileInfo[X,Y].ParentY
X = SEARCH_SearchPath[Path, Moves].X
Y = SEARCH_SearchPath[Path, Moves].Y
until X = SX and Y = SY
SEARCH_PathSize[Path] = Moves
endfunction Moves
// ===================================================
//
// ===================================================
function SEARCH_ClearPath(Path as integer, SX as integer, SY as integer)
SEARCH_SearchPath[Path, 0].X = SX
SEARCH_SearchPath[Path, 1].Y = SY
SEARCH_PathSize[Path] = 0
endfunction 0
// ****************************************************************************
// ****************************************************************************
//
// ****************************************************************************
// ****************************************************************************
function SearchMapAStar8(Path as integer, SX as integer, SY as integer, TX as integer, TY as integer)
X as integer
Y as integer
XOffset as integer
YOffset as integer
NewCost as integer
if SEARCH_MapInitialized = 0 then exitfunction -1
if SEARCH_PathsInitialized = 0 then exitfunction -1
if Path < 0 or Path > SEARCH_MaxPaths then exitfunction -1
SEARCH_LastSearch = 1
SEARCH_InitializeTileInfo(SX,SY)
while SEARCH_GetLowestCostOpen() > 0
for XOffset = -1 to 1
X = SEARCH_CurrentPosition.X + XOffset
if X >= 0 and X < SEARCH_MapWidth
for YOffset = -1 to 1
if (XOffset || YOffset) <> 0
Y = SEARCH_CurrentPosition.Y + YOffset
if (XOffset || YOffset) = 0
Y = -1
else
` Restrict diagonals
if SEARCH_RestrictedDiagonals
if XOffset <> 0 and YOffset <> 0
if SEARCH_TileInfo[X, SEARCH_CurrentPosition.Y].Status = 2
` This bit depends on Y *not* being set to -1
//if Y<>-1
Y = SEARCH_CurrentPosition.Y
if SEARCH_TileInfo[SEARCH_CurrentPosition.X, Y].Status = 2
Y = -1
endif
//endif
endif
endif
endif
endif
if Y >= 0 and Y < SEARCH_MapHeight
if SEARCH_TileInfo[X,Y].Status = 0
SEARCH_TileInfo[X,Y].ParentX = SEARCH_CurrentPosition.X
SEARCH_TileInfo[X,Y].ParentY = SEARCH_CurrentPosition.Y
if X = TX and Y = TY then exitfunction SEARCH_BuildPath(Path,SX,SY,TX,TY)
SEARCH_TileInfo[X,Y].G = SEARCH_TileInfo[SEARCH_CurrentPosition.X,SEARCH_CurrentPosition.Y].G + SEARCH_SingleStepCost(XOffset,YOffset)
SEARCH_TileInfo[X,Y].H = SEARCH_EstimateDistance(X,Y,TX,TY)
SEARCH_TileInfo[X,Y].F = SEARCH_TileInfo[X,Y].G + SEARCH_TileInfo[X,Y].H
if SEARCH_MaximumCost = 0 or SEARCH_TileInfo[X,Y].G < SEARCH_MaximumCost
SEARCH_AddToOpenList(X,Y)
SEARCH_TileInfo[X,Y].Status = 1
endif
else
if SEARCH_TileInfo[X,Y].Status = 1
NewCost = SEARCH_TileInfo[SEARCH_CurrentPosition.X,SEARCH_CurrentPosition.Y].G + SEARCH_SingleStepCost(XOffset,YOffset)
if SEARCH_TileInfo[X,Y].G > NewCost
SEARCH_TileInfo[X,Y].ParentX = SEARCH_CurrentPosition.X
SEARCH_TileInfo[X,Y].ParentY = SEARCH_CurrentPosition.Y
SEARCH_TileInfo[X,Y].G = NewCost
SEARCH_TileInfo[X,Y].F = NewCost + SEARCH_TileInfo[X,Y].H
SEARCH_AddToOpenList(X,Y)
endif
endif
endif
endif
endif
next YOffset
endif
next XOffset
endwhile
n as integer
n = SEARCH_ClearPath(Path,SX,SY)
exitfunction n
endfunction 0
// ****************************************************************************
// ****************************************************************************
//
// ****************************************************************************
// ****************************************************************************
function SearchMapAStar4(Path as integer, SX as integer, SY as integer, TX as integer, TY as integer)
X as integer
Y as integer
XOffset as integer
YOffset as integer
NewCost as integer
if SEARCH_MapInitialized = 0 then exitfunction -1
if SEARCH_PathsInitialized = 0 then exitfunction -1
if Path < 0 or Path > SEARCH_MaxPaths then exitfunction -1
SEARCH_LastSearch = 0
SEARCH_InitializeTileInfo(SX,SY)
while SEARCH_GetLowestCostOpen() > 0
for XOffset = -1 to 1
X = SEARCH_CurrentPosition.X + XOffset
if X >= 0 and X < SEARCH_MapWidth
for YOffset = -1 to 1
if (XOffset && YOffset) = 0
Y = SEARCH_CurrentPosition.Y + YOffset
if Y >= 0 and Y < SEARCH_MapHeight
if SEARCH_TileInfo[X,Y].Status = 0
SEARCH_TileInfo[X,Y].ParentX = SEARCH_CurrentPosition.X
SEARCH_TileInfo[X,Y].ParentY = SEARCH_CurrentPosition.Y
if X = TX and Y = TY then exitfunction SEARCH_BuildPath(Path,SX,SY,TX,TY)
SEARCH_TileInfo[X,Y].G = SEARCH_TileInfo[SEARCH_CurrentPosition.X,SEARCH_CurrentPosition.Y].G + 10
SEARCH_TileInfo[X,Y].H = SEARCH_EstimateDistance(X,Y,TX,TY)
SEARCH_TileInfo[X,Y].F = SEARCH_TileInfo[X,Y].G + SEARCH_TileInfo[X,Y].H
Cost as integer
if SEARCH_MaximumCost = 0 or Cost < SEARCH_MaximumCost
SEARCH_AddToOpenList(X,Y)
SEARCH_TileInfo[X,Y].Status = 1
endif
else
if SEARCH_TileInfo[X,Y].Status = 1
NewCost = SEARCH_TileInfo[SEARCH_CurrentPosition.X,SEARCH_CurrentPosition.Y].G + 10
if SEARCH_TileInfo[X,Y].G > NewCost
SEARCH_TileInfo[X,Y].ParentX = SEARCH_CurrentPosition.X
SEARCH_TileInfo[X,Y].ParentY = SEARCH_CurrentPosition.Y
SEARCH_TileInfo[X,Y].G = NewCost
SEARCH_TileInfo[X,Y].F = NewCost + SEARCH_TileInfo[X,Y].H
SEARCH_AddToOpenList(X,Y)
endif
endif
endif
endif
endif
next YOffset
endif
next XOffset
endwhile
n as integer
n = SEARCH_ClearPath(Path,SX,SY)
exitfunction n
endfunction 0
// ****************************************************************************
// ****************************************************************************
//
// ****************************************************************************
// ****************************************************************************
function SearchMapFlood8(Path as integer, SX as integer, SY as integer, TX as integer, TY as integer)
XOffset as integer
YOffset as integer
X as integer
Y as integer
Cost as integer
if SEARCH_MapInitialized = 0 then exitfunction -1
if SEARCH_PathsInitialized = 0 then exitfunction -1
if Path < 0 or Path > SEARCH_MaxPaths then exitfunction -1
if SEARCH_ParametersChanged = 1 or SEARCH_LastSearch <> 3
SEARCH_ParametersChanged = 0
SEARCH_PreviousStart.X = -9999
SEARCH_LastSearch = 3
endif
if SX <> SEARCH_PreviousStart.X or SY <> SEARCH_PreviousStart.Y
SEARCH_PreviousStart.X = SX
SEARCH_PreviousStart.Y = SY
SEARCH_PopulateTileInfo()
SEARCH_TileInfo[SX, SY].Status = 1
SEARCH_TileInfo[SX, SY].ParentX = SX
SEARCH_TileInfo[SX, SY].ParentY = SY
SEARCH_TileInfo[SX, SY].F = 0
SEARCH_AddToOpenList(SX,SY)
SEARCH_SearchMode as integer
while SEARCH_GetLowestCostOpen() > 0
for XOffset = -1 to 1
X = SEARCH_CurrentPosition.X + XOffset
if X >= 0 and X < SEARCH_MapWidth
for YOffset = -1 to 1
Y = SEARCH_CurrentPosition.Y + YOffset
` Not the current cell (offsets both zero)
if (XOffset || YOffset) = 0
Y = -1
else
` Restrict diagonals
if SEARCH_RestrictedDiagonals
if XOffset <> 0 and YOffset <> 0
if SEARCH_TileInfo[X, SEARCH_CurrentPosition.Y].Status = 2
` This bit depends on Y *not* being set to -1
if Y<>-1
if SEARCH_TileInfo[SEARCH_CurrentPosition.X, Y].Status = 2
Y = -1
endif
endif
endif
endif
endif
endif
if Y >= 0 and Y < SEARCH_MapHeight
if SEARCH_TileInfo[X,Y].Status = 0
SEARCH_TileInfo[X, Y].Status = 1
SEARCH_TileInfo[X, Y].ParentX = SEARCH_CurrentPosition.X
SEARCH_TileInfo[X, Y].ParentY = SEARCH_CurrentPosition.Y
Cost = SEARCH_TileInfo[SEARCH_CurrentPosition.X, SEARCH_CurrentPosition.Y].F + SEARCH_SingleStepCost(XOffset,YOffset)
SEARCH_TileInfo[X, Y].F = Cost
if SEARCH_MaximumCost = 0 or Cost < SEARCH_MaximumCost
SEARCH_AddToOpenList(X,Y)
endif
endif
endif
next YOffset
endif
next XOffset
endwhile
endif
if SEARCH_TileInfo[TX,TY].Status > 0 then exitfunction SEARCH_BuildPath(Path,SX,SY,TX,TY)
n as integer
n = SEARCH_ClearPath(Path,SX,SY)
exitfunction n
endfunction 0
// ****************************************************************************
// ****************************************************************************
//
// ****************************************************************************
// ****************************************************************************
function SearchMapFlood4(Path as integer, SX as integer, SY as integer, TX as integer, TY as integer)
XOffset as integer
YOffset as integer
X as integer
Y as integer
if SEARCH_MapInitialized = 0 then exitfunction -1
if SEARCH_PathsInitialized = 0 then exitfunction -1
if Path < 0 or Path > SEARCH_MaxPaths then exitfunction -1
if SEARCH_ParametersChanged = 1 or SEARCH_LastSearch <> 2
SEARCH_ParametersChanged = 0
SEARCH_PreviousStart.X = -9999
SEARCH_LastSearch = 2
endif
if SX <> SEARCH_PreviousStart.X or SY <> SEARCH_PreviousStart.Y
SEARCH_PreviousStart.X = SX
SEARCH_PreviousStart.Y = SY
SEARCH_PopulateTileInfo()
SEARCH_OpenListTop=-1
SEARCH_OpenListBottom=-1
SEARCH_TileInfo[SX, SY].Status = 1
SEARCH_TileInfo[SX, SY].ParentX = SX
SEARCH_TileInfo[SX, SY].ParentY = SY
SEARCH_TileInfo[SX, SY].F = 0
SEARCH_QueueOntoOpen(SX, SY)
while SEARCH_UnqueueFromOpen() > 0
for XOffset = -1 to 1
X = SEARCH_CurrentPosition.X + XOffset
if X >= 0 and X < SEARCH_MapWidth
for YOffset = -1 to 1
if (XOffset && YOffset) = 0
Y = SEARCH_CurrentPosition.Y + YOffset
if Y >= 0 and Y < SEARCH_MapHeight
if SEARCH_TileInfo[X, Y].Status = 0
SEARCH_TileInfo[X, Y].Status = 1
SEARCH_TileInfo[X, Y].ParentX = SEARCH_CurrentPosition.X
SEARCH_TileInfo[X, Y].ParentY = SEARCH_CurrentPosition.Y
SEARCH_TileInfo[X, Y].F = SEARCH_TileInfo[SEARCH_CurrentPosition.X, SEARCH_CurrentPosition.Y].F + 10
if SEARCH_MaximumCost = 0 or SEARCH_TileInfo[X, Y].F < SEARCH_MaximumCost
SEARCH_QueueOntoOpen(X, Y)
endif
endif
endif
endif
next YOffset
endif
next XOffset
endwhile
endif
if SEARCH_TileInfo[TX,TY].Status > 0 then exitfunction SEARCH_BuildPath(Path,SX,SY,TX,TY)
n as integer
n = SEARCH_ClearPath(Path,SX,SY)
exitfunction n
endfunction 0
New Example
// Project: AStar
// Created: 2017-07-29
// show all errors
SetErrorMode(2)
// set window properties
SetWindowTitle( "AStar" )
//SetWindowSize( 1024, 768, 0 )
SetWindowAllowResize( 1 ) // allow the user to resize the window
// set display properties
SetVirtualResolution( 1024, 768 ) // doesn't have to match the window
SetOrientationAllowed( 1, 1, 1, 1 ) // allow both portrait and landscape on mobile devices
SetSyncRate( 30, 0 ) // 30fps instead of 60 to save battery
SetScissor( 0,0,0,0 ) // use the maximum available screen space, no black borders
UseNewDefaultFonts( 1 ) // since version 2.0.22 we can use nicer default fonts
#Option_Explicit
// These 1 lines are needed to use the library
#include "AStar.agc"
// Define some variables for this demo
#constant MAP_GRID_WIDTH 40
#constant MAP_GRID_HEIGHT 30
#constant MAP_CELL_WIDTH 15
#constant MAP_CELL_HEIGHT 15
global total_map_width
global total_map_height
total_map_width=1024/MAP_CELL_WIDTH
total_map_height=1024/MAP_CELL_HEIGHT
Global CurrentPath as integer
Global diags as integer
Global grid as integer
Global start as float
Global time as float
Global found as integer
Global c_blue as integer
Global c_green as integer
Global c_red as integer
Global c_grey as integer
Global c_yellow as integer
c_blue=MakeColor(0, 0, 255)
c_green=MakeColor(0, 255, 0)
c_red=MakeColor(255,0,0)
c_grey=MakeColor(154,154,154)
c_yellow=MakeColor(255,255,0)
// Create a map and initialize 4 paths
CreateSearchMap(total_map_width, total_map_height, MAP_CELL_WIDTH, MAP_CELL_HEIGHT)
CreateSearchPathLists(3) // 4 paths
SetPrintSize(30)
SetPrintColor(0,255,0)
CurrentPath=0
do
grid_x as integer
grid_y as integer
grid_x = WorldToGridX(getPointerX())
grid_y = WorldToGridY(getPointerY())
if GetRawMouseLeftState() = 1 then SetSearchMap(grid_x, grid_y, 1)
if GetRawMouseRightState() = 1 then SetSearchMap(grid_x, grid_y, 0)
if getRawKeyPressed(65) = 1
SetPathMarker(CurrentPath, PATH_START, grid_x, grid_y)
endif
if getRawKeyPressed(66) = 1
SetPathMarker(CurrentPath, PATH_TARGET, grid_x, grid_y)
endif
if getRawKeyPressed(68) = 1
diags = 1 - diags
SetSearchRestrictDiagonals(diags)
endif
td as string
// output instructions and junk
if GetSearchRestrictDiagonals() = 0
td = "off"
else
td = "on"
endif
if getRawKeyPressed(112) = 1
CurrentPath=0
endif
if getRawKeyPressed(113) = 1
CurrentPath=1
endif
if getRawKeyPressed(114) = 1
CurrentPath=2
endif
if getRawKeyPressed(115) = 1
CurrentPath=3
endif
print("Current Path ="+str(CurrentPath))
PrintC("F1=Path 0-")
PrintC("F2=Path 1-")
PrintC("F3=Path 2-")
Print("F4=Path 3")
print("(1) A*8 (2) A*4 (3) Flood8 (4) Flood4")
print("(D) Restrict Diagonals is "+td)
print("(A) Place Start")
print("(B) Place Target")
print("(G) Draw Grid")
print("")
print("Moves Taken: "+str(GetSearchPathSize(CurrentPath)))
if getRawKeyPressed(49) = 1 then ProcessAStar8(CurrentPath)
if getRawKeyPressed(50) = 1 then ProcessAStar4(CurrentPath)
if getRawKeyPressed(51) = 1 then ProcessFlood8(CurrentPath)
if getRawKeyPressed(52) = 1 then ProcessFlood4(CurrentPath)
if getRawKeyPressed(71) = 1 then grid=1-grid
if found = 0
print("Search Failed: "+str(time)+" ms")
else
print("Search Successful: "+str(time)+" ms")
endif
print("Mouse X="+Str(WorldToGridX(getPointerX())))
print("Mouse Y="+Str(WorldToGridY(getPointerY())))
// draw map
if grid then DrawSearchGrid(c_grey)
DrawSearchMap(c_red)
DrawSearchPath(CurrentPath, c_yellow)
DrawPathMarker(CurrentPath, PATH_START, c_blue)
DrawPathMarker(CurrentPath, PATH_TARGET, c_green)
Sync()
loop
function ProcessAStar8(path)
startX as integer
startY as integer
targetX as integer
targetY as integer
start = getMilliseconds()
startX=GetPathMarkerX(path, PATH_START)
startY=GetPathMarkerY(path, PATH_START)
targetX=GetPathMarkerX(path, PATH_TARGET)
targetY=GetPathMarkerY(path, PATH_TARGET)
found = searchMapAStar8(path, startX, startY, targetX, targetY)
time = getMilliseconds() - start
endfunction
function ProcessAStar4(path)
startX as integer
startY as integer
targetX as integer
targetY as integer
start = getMilliseconds()
startX=GetPathMarkerX(path, PATH_START)
startY=GetPathMarkerY(path, PATH_START)
targetX=GetPathMarkerX(path, PATH_TARGET)
targetY=GetPathMarkerY(path, PATH_TARGET)
found = SearchMapAStar4(path, startX, startY, targetX, targetY)
time = getMilliseconds() - start
endfunction
function ProcessFlood4(path)
startX as integer
startY as integer
targetX as integer
targetY as integer
start = getMilliseconds()
startX=GetPathMarkerX(path, PATH_START)
startY=GetPathMarkerY(path, PATH_START)
targetX=GetPathMarkerX(path, PATH_TARGET)
targetY=GetPathMarkerY(path, PATH_TARGET)
found = SearchMapFlood4(path, startX, startY, targetX, targetY)
time = getMilliseconds() - start
endfunction
function ProcessFlood8(path)
startX as integer
startY as integer
targetX as integer
targetY as integer
start = getMilliseconds()
startX=GetPathMarkerX(path, PATH_START)
startY=GetPathMarkerY(path, PATH_START)
targetX=GetPathMarkerX(path, PATH_TARGET)
targetY=GetPathMarkerY(path, PATH_TARGET)
found = SearchMapFlood8(path, startX, startY, targetX, targetY)
time = getMilliseconds() - start
endfunction
EDIT:
Calling CreateSearchPathList() will reset markers for all paths so you will want to think ahead when it comes to the amount of paths required, maybe add more than you will need or set it to thwe maximum number of units in your game.
