This tiled based pathfinding have 3 levels of terrain to either walk on or avoid.(normal,rough and even rougher)
It also tryes to get as close as possible to target if it cant find an path to the original target.
If it takes to long to search path or it cant find an path so does it simply exit the loop and waits for a new target.
I created this while i whas trying to learn ai coding for path finding.
And its easially done for 3d games with some small changes.
I used the book Ai game engine programming by Brian Schwab when i wrote this.
The neaded media is in the attachement.
NEW HIGHLY IMPROVED VERSION!
left mb to target an tile.
set max tiles and type of pathfinding easy and quickly in code and realtime.
Rem Project: Simple pathfinding
Rem Created: 2009-12-27 21:52:56
Rem ***** Main Source File *****
set display mode 800,600,32
sync on : sync rate 0
set text font "tahoma"
set text size 14
`//// Prepare our images for the map. ////
load image "images.bmp",100,1
for t=1 to 8
paste image 100,0,0
get image t,0+t2,0,50+t2,50,1
inc t2,50
next t
delete image 100
`//// AI pathfinding code initiating. ////
`//// Create some data types to make it easier to implement AI code in to game code. ////
type AI_DATA SEARCH as integer X_ORIGIN as integer Y_ORIGIN as integer endtype
type AI_DATA2 START_X as integer START_Y as integer END_X as integer END_Y as integer EXIST as integer endtype
type AI_DATA3 SIZE_X as integer SIZE_Y as integer endtype
type AI_DATA4 X as integer Y as integer Xstart as integer Ystart as integer endtype
AI_PATH as AI_DATA2
AI_GRID as AI_DATA3
global AI_PATH_TYPE = 8 `ingame can you change this to either 4 = 4 directions or 8 = 8 directions pathfinding
global AI_START_ID = 4 `number used to assign a start tile in pathfinding
global AI_END_ID = 5 `number used to assign a end tile in pathfinding
global AI_SOLID_ID = 3 `number for none passable tiles
global MAX_TILES = 20 `max tiles being drawn of path(simply to show how to limit etc units walkable tile amount)
global MAX_ERROR_TILES = 16 `max tiles in 8 directions that the ai will search! to get closest to target if path error(high nr is slow)
`//// Map size. ////
AI_GRID.SIZE_X = 16
AI_GRID.SIZE_Y = 10
dim AI_GRID(AI_GRID.SIZE_X,AI_GRID.SIZE_Y) as AI_DATA
dim AI_PATH_count() as AI_DATA4
`//// New! instead of the tile id section of ai grid array. ////
`//// As this is constant and the ai grid array constantly changes. ////
`//// Now can you easy and fast empty that array when neaded. ////
`//// Is used to tell the ai wath on the map is solid and not. ////
dim AI_MAP(AI_GRID.SIZE_X,AI_GRID.SIZE_Y)
gosub refresh
Ti=Timer()
`//// Main Loop. ////
do
cls
gosub texts
gosub draw_2d
if keystate(2)=1 then gosub refresh:delete image 1000:steve=0
if keystate(3)=1 then AI_PATH_TYPE=4
if keystate(4)=1 then AI_PATH_TYPE=8
`//// Let the user set the max amount of walkable tiles. ////
if keystate(5)=1 then dec MAX_TILES
while keystate(5)=1
endwhile
if keystate(6)=1 then inc MAX_TILES
while keystate(6)=1
endwhile
if MAX_TILES<1 then MAX_TILES=1
`//// Make steve follow the path if it exist :) ////
Elapsed=(Timer()-Ti)/200
if Elapsed>1
Ti=Timer()
if ARRAY COUNT(AI_PATH_count())>0
inc steve
if steve>ARRAY COUNT(AI_PATH_count()) then steve=0
endif
endif
if steve=0 then paste image 8,(AI_PATH.START_X*50)-50,(AI_PATH.START_Y*50)-50,1
if steve>0 then paste image 8,(AI_PATH_count(steve).Xstart*50)-50,(AI_PATH_count(steve).Ystart*50)-50,1
`//// If an path exist draw an nice path with boxes. ////
if ARRAY COUNT(AI_PATH_count())>0
paste image 7,(AI_PATH.START_X*50)-50,(AI_PATH.START_Y*50)-50,1
for t=1 to ARRAY COUNT(AI_PATH_count())
``if t =< MAX_TILES
paste image 7,(AI_PATH_count(t).Xstart*50)-50,(AI_PATH_count(t).Ystart*50)-50,1
``endif
next t
endif
`//// Here do we convert screen cordinates to array cordinates. ////
msxtrg=(mousex()/50)+1
msytrg=(mousey()/50)+1
`///////////////////////////////////////////////////////////////////////////
`//// If user clicks left mb so will we start the path finding process. ////
`///////////////////////////////////////////////////////////////////////////
if mouseclick()=1
steve=0
`//// Empty the path array from old data. ////
undim AI_GRID(0,0)
undim AI_PATH_count()
`//// And set it up again. ////
dim AI_GRID(AI_GRID.SIZE_X,AI_GRID.SIZE_Y)
`//// This is the stuff that makes the magic happen :) ////
AI_PATH.END_X = msxtrg
AI_PATH.END_Y = msytrg
PASSED = 1
AI_GRID(AI_PATH.START_X,AI_PATH.START_Y).SEARCH = 1
AI_PATH.EXIST=0
gosub AI_MAIN_PATHFINDING
while mouseclick()=1
endwhile
endif
sync
loop
`//// Used to empty the map and grid data and create an brand new one. ////
refresh:
while keystate(2)=1
endwhile
temp=0
undim AI_GRID(0,0)
undim AI_PATH_count()
undim AI_MAP(AI_GRID.SIZE_X,AI_GRID.SIZE_Y)
dim AI_GRID(AI_GRID.SIZE_X,AI_GRID.SIZE_Y)
`//// Generate the random map. ////
`//// 0 = walkable 1 = rough terrain 2 = rougher terrain 3 = obstacle ////
dim AI_MAP(AI_GRID.SIZE_X,AI_GRID.SIZE_Y)
for t=1 to 90
AI_MAP(1+rnd(AI_GRID.SIZE_X-1),1+rnd(AI_GRID.SIZE_Y-1))=AI_SOLID_ID
next t
for t=1 to 10
AI_MAP(1+rnd(AI_GRID.SIZE_X-1),1+rnd(AI_GRID.SIZE_Y-1))=1
next t
for t=1 to 15
AI_MAP(1+rnd(AI_GRID.SIZE_X-1),1+rnd(AI_GRID.SIZE_Y-1))=2
next t
`//// setup a random start tile. ////
empty_tile = 0
while empty_tile = 0
x = 1+rnd(AI_GRID.SIZE_X-1)
y = 1+rnd(AI_GRID.SIZE_Y-1)
if AI_MAP(x,y)<AI_SOLID_ID then empty_tile = 1
endwhile
AI_GRID(x,y).SEARCH = 1
AI_PATH.START_X = x
AI_PATH.START_Y = y
return
`//// Draw map image on screen. ////
draw_2d:
oldx=0:oldy=0
if image exist (1000)=1 then paste image 1000,0,0,0
for x=1 to AI_GRID.SIZE_X
if x=1 then xs=0
for y=1 to AI_GRID.SIZE_Y
if y=1 then ys=0
if image exist (1000)=0 then paste image AI_MAP(x,y)+1,xs,ys,0
if AI_MAP(x,y)>AI_END_ID and AI_MAP(x,y)<7 then paste image AI_MAP(x,y)+1,xs,ys,1
`//// Some text data i used while i whas writing the code. ////
``if image exist (1000)=1 then center text (xs)+25,(ys+32),"("+str$(AI_GRID(x,y).SEARCH)+")"
``if image exist (1000)=1 then center text (xs)+25,(ys),str$(AI_GRID(x,y).X_ORIGIN)+":"+str$(AI_GRID(x,y).Y_ORIGIN)
inc ys,50
next y
inc xs,50
next x
`//// If user refreshed the map? so do we nead an image of the new one and grabbes it. ////
if image exist (1000)=0 then get image 1000,0,0,AI_GRID.SIZE_X*50,AI_GRID.SIZE_Y*50,1
return
`//// Show text. ////
texts:
set cursor 0,500
print "TILE BASED PATHFINDING. Left mb = Target and search / 1 = refresh map / Max tiles ( key 4-5)=";MAX_TILES
print "FPS = ";screen fps();" Tiles = ";AI_TILE_COUNT;" Pathfinding directions ( KEY 2-3 )= ";AI_PATH_TYPE
print "It will try to avoid the chairs and bottles as much as possible. "
return
`///////////////////////////////////
`//// Main AI pathfinding code. ////
`///////////////////////////////////
AI_MAIN_PATHFINDING:
AI_SEARCH_X_CYCLES = 0
AI_SEARCH_Y_CYCLES = 0
AI_ERROR = 0
global X_AI
global Y_AI
while AI_PATH.EXIST=0
`/// Here do we fix an error that makes the search path continous cyckle without an end. ////
if AI_PATH_TYPE = 4 and AI_SEARCH_X_CYCLES => AI_GRID.SIZE_X*2 then AI_PATH.EXIST = 1 : AI_ERROR=1
if AI_PATH_TYPE = 8 and AI_SEARCH_X_CYCLES => AI_GRID.SIZE_X then AI_PATH.EXIST = 1 : AI_ERROR=1
`//// Search in AI array. ////
for x = 1 to AI_GRID.SIZE_X
if x = AI_GRID.SIZE_X then inc AI_SEARCH_X_CYCLES
for y = 1 to AI_GRID.SIZE_Y
if y = AI_GRID.SIZE_Y then inc AI_SEARCH_Y_CYCLES
if AI_GRID(x,y).SEARCH = PASSED
X_AI = x : Y_AI = y
`//// The order of the ai search cycle. ////
`//// 6 2 5 ////
`//// 3 * 1 ////
`//// 7 4 8 ////
tx = X_AI+1
ty = Y_AI
for t = 1 to 4
if t = 2 then dec tx : dec ty
if t = 3 then dec tx : inc ty
if t = 4 then inc tx : inc ty
if tx > 0 and tx =< AI_GRID.SIZE_X and ty > 0 and ty =< AI_GRID.SIZE_Y
AI_SEARCH_TILE(tx,ty,X_AI,Y_AI,PASSED)
endif
next t
if AI_PATH_TYPE = 8 then gosub AI_CORNER_TILES
endif
next y
next x
inc PASSED
endwhile
`//// If ai cant get to target so will this find a new target. ////
AI_TILE_COUNT = 0
if AI_ERROR = 1 and AI_NEW_TARGET = 0 then gosub AI_NEW_END_TILE
if AI_TILE_COUNT = MAX_ERROR_TILES then goto AI_MAIN_PATHFINDING
gosub AI_DRAW_PATH
AI_NEW_TARGET=0
return
`//// Main ai search function. ////
function AI_SEARCH_TILE(x,y,org_x,org_y,tile)
`//// Check if first square is a wall and not processed. ////
if AI_MAP(x,y) <> AI_SOLID_ID and AI_GRID(x,y).SEARCH = 0
`//// Helps the ai to take the shortest and not so tough route. ////
if AI_MAP(x,y) = 0 then AI_GRID(x,y).SEARCH = tile + 1
if AI_MAP(x,y) = 1 then AI_GRID(x,y).SEARCH = tile + 2
if AI_MAP(x,y) = 2 then AI_GRID(x,y).SEARCH = tile + 3
`//// Assign the origin to this square. ////
AI_GRID(x,y).X_ORIGIN=org_x : AI_GRID(x,y).Y_ORIGIN=org_y
`//// Check if we arrive at the end? If so exit the search. ////
if x=AI_PATH.END_X and y=AI_PATH.END_Y then AI_PATH.EXIST=1:X_AI=x:Y_AI=y
endif
endfunction
`//// The corner tile search is placed in an gosub. ////
`//// to shorten the main pathfinding gosub for speed. ////
`//// This code aint always used. ////
AI_CORNER_TILES:
tx = X_AI + 1
ty = Y_AI - 1
for t = 5 to 8
if t = 6 then dec tx,2
if t = 7 then inc ty,2
if t = 8 then inc tx,2
if tx > 0 and tx =< AI_GRID.SIZE_X and ty > 0 and ty =< AI_GRID.SIZE_Y
AI_SEARCH_TILE(tx,ty,X_AI,Y_AI,PASSED)
endif
next t
return
`//// Here do we search for the closest new target tile. ////
`//// Only used if the main pathfinding failed. ////
AI_NEW_END_TILE:
AI_NEW_X = 0:AI_NEW_Y = 0 : SEARCH_COUNT = 100
repeat
inc AI_TILE_COUNT
`//// 4 3 2 ////
`//// 5 * 1 ////
`//// 6 7 8 ////
`//// 1 ////
if AI_PATH.END_X + AI_TILE_COUNT =< AI_GRID.SIZE_X
if AI_GRID(AI_PATH.END_X + AI_TILE_COUNT,AI_PATH.END_Y).SEARCH > 0 and AI_GRID(AI_PATH.END_X + AI_TILE_COUNT,AI_PATH.END_Y).SEARCH < SEARCH_COUNT
AI_NEW_X = AI_PATH.END_X + AI_TILE_COUNT : AI_NEW_Y = AI_PATH.END_Y
SEARCH_COUNT = AI_GRID(AI_PATH.END_X + AI_TILE_COUNT,AI_PATH.END_Y).SEARCH
endif
endif
`//// 2 ////
if AI_PATH.END_X + AI_TILE_COUNT =< AI_GRID.SIZE_X and AI_PATH.END_Y - AI_TILE_COUNT > 0
if AI_GRID(AI_PATH.END_X + AI_TILE_COUNT,AI_PATH.END_Y - AI_TILE_COUNT).SEARCH > 0 and AI_GRID(AI_PATH.END_X + AI_TILE_COUNT,AI_PATH.END_Y - AI_TILE_COUNT).SEARCH < SEARCH_COUNT
AI_NEW_X = AI_PATH.END_X + AI_TILE_COUNT : AI_NEW_Y = AI_PATH.END_Y - AI_TILE_COUNT
SEARCH_COUNT = AI_GRID(AI_PATH.END_X + AI_TILE_COUNT,AI_PATH.END_Y - AI_TILE_COUNT).SEARCH
endif
endif
`//// 3 ////
if AI_PATH.END_Y - AI_TILE_COUNT > 0
if AI_GRID(AI_PATH.END_X,AI_PATH.END_Y - AI_TILE_COUNT).SEARCH >0 and AI_GRID(AI_PATH.END_X,AI_PATH.END_Y - AI_TILE_COUNT).SEARCH < SEARCH_COUNT
AI_NEW_X = AI_PATH.END_X : AI_NEW_Y = AI_PATH.END_Y - AI_TILE_COUNT
SEARCH_COUNT = AI_GRID(AI_PATH.END_X,AI_PATH.END_Y - AI_TILE_COUNT).SEARCH
endif
endif
`//// 4 ////
if AI_PATH.END_X - AI_TILE_COUNT > 0 and AI_PATH.END_Y - AI_TILE_COUNT > 0
if AI_GRID(AI_PATH.END_X - AI_TILE_COUNT,AI_PATH.END_Y - AI_TILE_COUNT).SEARCH > 0 and AI_GRID(AI_PATH.END_X - AI_TILE_COUNT,AI_PATH.END_Y - AI_TILE_COUNT).SEARCH < SEARCH_COUNT
AI_NEW_X = AI_PATH.END_X - AI_TILE_COUNT : AI_NEW_Y = AI_PATH.END_Y - AI_TILE_COUNT
SEARCH_COUNT = AI_GRID(AI_PATH.END_X - AI_TILE_COUNT,AI_PATH.END_Y - AI_TILE_COUNT).SEARCH
endif
endif
`//// 5 ////
if AI_PATH.END_X - AI_TILE_COUNT > 0
if AI_GRID(AI_PATH.END_X - AI_TILE_COUNT,AI_PATH.END_Y).SEARCH > 0 and AI_GRID(AI_PATH.END_X - AI_TILE_COUNT,AI_PATH.END_Y).SEARCH < SEARCH_COUNT
AI_NEW_X = AI_PATH.END_X - AI_TILE_COUNT : AI_NEW_Y = AI_PATH.END_Y
SEARCH_COUNT = AI_GRID(AI_PATH.END_X - AI_TILE_COUNT,AI_PATH.END_Y).SEARCH
endif
endif
`//// 6 ////
if AI_PATH.END_X - AI_TILE_COUNT > 0 and AI_PATH.END_Y + AI_TILE_COUNT =< AI_GRID.SIZE_Y
if AI_GRID(AI_PATH.END_X - AI_TILE_COUNT,AI_PATH.END_Y + AI_TILE_COUNT).SEARCH > 0 and AI_GRID(AI_PATH.END_X - AI_TILE_COUNT,AI_PATH.END_Y + AI_TILE_COUNT).SEARCH < SEARCH_COUNT
AI_NEW_X = AI_PATH.END_X - AI_TILE_COUNT : AI_NEW_Y = AI_PATH.END_Y + AI_TILE_COUNT
SEARCH_COUNT = AI_GRID(AI_PATH.END_X - AI_TILE_COUNT,AI_PATH.END_Y + AI_TILE_COUNT).SEARCH
endif
endif
`//// 7 ////
if AI_PATH.END_Y + AI_TILE_COUNT =< AI_GRID.SIZE_Y
if AI_GRID(AI_PATH.END_X,AI_PATH.END_Y + AI_TILE_COUNT).SEARCH > 0 and AI_GRID(AI_PATH.END_X,AI_PATH.END_Y + AI_TILE_COUNT).SEARCH < SEARCH_COUNT
AI_NEW_X = AI_PATH.END_X : AI_NEW_Y = AI_PATH.END_Y + AI_TILE_COUNT
SEARCH_COUNT = AI_GRID(AI_PATH.END_X,AI_PATH.END_Y + AI_TILE_COUNT).SEARCH
endif
endif
`//// 8 ////
if AI_PATH.END_X + AI_TILE_COUNT =< AI_GRID.SIZE_X and AI_PATH.END_Y + AI_TILE_COUNT =< AI_GRID.SIZE_Y
if AI_GRID(AI_PATH.END_X + AI_TILE_COUNT,AI_PATH.END_Y + AI_TILE_COUNT).SEARCH > 0 and AI_GRID(AI_PATH.END_X + AI_TILE_COUNT,AI_PATH.END_Y + AI_TILE_COUNT).SEARCH < SEARCH_COUNT
AI_NEW_X = AI_PATH.END_X + AI_TILE_COUNT : AI_NEW_Y = AI_PATH.END_Y + AI_TILE_COUNT
SEARCH_COUNT = AI_GRID(AI_PATH.END_X + AI_TILE_COUNT,AI_PATH.END_Y + AI_TILE_COUNT).SEARCH
endif
endif
`//// If we found an new target tile? Assign neaded data in to array. ////
if AI_NEW_X > 0 or AI_NEW_Y > 0
AI_NEW_TARGET = 1 : AI_TILE_COUNT = MAX_ERROR_TILES : PASSED = 1 : AI_PATH.EXIST = 0 : AI_ERROR = 0
for x = 1 to AI_GRID.SIZE_X
for y = 1 to AI_GRID.SIZE_Y
AI_GRID(x,y).SEARCH = 0 : AI_GRID(x,y).X_ORIGIN = 0 : AI_GRID(x,y).Y_ORIGIN = 0
next y
next x
AI_GRID(AI_PATH.START_X,AI_PATH.START_Y).SEARCH = 1
AI_PATH.END_X = AI_NEW_X : AI_PATH.END_Y = AI_NEW_Y
endif
until AI_TILE_COUNT = MAX_ERROR_TILES
return
`//// If path found? Follow it back to the start tile in inverse order. ////
`//// If path not found skip it (error) ////
AI_DRAW_PATH:
undim AI_PATH_count(0)
X_AI = AI_PATH.END_X : Y_AI = AI_PATH.END_Y
if AI_ERROR = 0
AI_TILE_COUNT = 0
while X_AI <> AI_PATH.START_X or Y_AI <> AI_PATH.START_Y
inc AI_TILE_COUNT
dim AI_PATH_count(AI_TILE_COUNT)
x1 = X_AI : y1 = Y_AI
X_AI = AI_GRID(x1,y1).X_ORIGIN
Y_AI = AI_GRID(x1,y1).Y_ORIGIN
`//// Setup array that we use to get taget tiles and draw the path on screen with. ////
AI_PATH_count(AI_TILE_COUNT).X = x1
AI_PATH_count(AI_TILE_COUNT).y = y1
`//// Bugg fix! If an path dosent exist. ////
If x1 = X_AI and y1 = Y_AI
X_AI = AI_PATH.START_X : Y_AI = AI_PATH.START_Y
AI_PATH_count(AI_TILE_COUNT).X = AI_PATH.START_X
AI_PATH_count(AI_TILE_COUNT).y = AI_PATH.START_Y
undim AI_PATH_count(0)
endif
endwhile
`//// Here do we turn the path array around! ////
`//// so that 1 in array is tile one and not the last one in the array. ////
`//// Is really not neaded! But i wanted it this way for simplicity. ////
if ARRAY COUNT(AI_PATH_count()) > 0
t2 = ARRAY COUNT(AI_PATH_count()) + 1
for t = 1 to ARRAY COUNT(AI_PATH_count())
AI_PATH_count(t2 - t).Xstart = AI_PATH_count(t).X
AI_PATH_count(t2 - t).Ystart = AI_PATH_count(t).Y
next t
endif
if ARRAY COUNT(AI_PATH_count()) > MAX_TILES then dim AI_PATH_count(MAX_TILES)
endif
return
Rem Project: Simple pathfinding
Rem Created: 2009-12-27 21:52:56
Rem ***** Main Source File *****
set display mode 800,600,32
sync on : sync rate 0
set text font "tahoma"
set text size 14
load image "images.bmp",100,1
for t=1 to 8
paste image 100,0,0
get image t,0+t2,0,50+t2,50,1
inc t2,50
next t
delete image 100
`AI------------------------------------------AI pathfinding code initiating start----------------------------------------------------------
`----------------Create some data types to make it easier to implement AI code in to game code.------------------------------------------
type AI_DATA TILE_ID as integer SEARCH as integer X_ORIGIN as integer Y_ORIGIN as integer endtype
type AI_DATA2 START_X as integer START_Y as integer END_X as integer END_Y as integer EXIST as integer endtype
type AI_DATA3 SIZE_X as integer SIZE_Y as integer endtype
type AI_DATA4 X as integer Y as integer Xstart as integer Ystart as integer endtype
AI_PATH as AI_DATA2
AI_GRID as AI_DATA3
global AI_PATH_TYPE = 8 `ingame can you change this to either 4 = 4 directions or 8 = 8 directions pathfinding
global AI_START_ID = 4 `number used to assign a start tile in pathfinding
global AI_END_ID = 5 `number used to assign a end tile in pathfinding
global AI_SOLID_ID = 3 `number for none passable tiles
global MAX_TILES = 70 `max tiles being drawn of path(simply to show how to limit etc units walkable tile amount)
global MAX_ERROR_TILES = 16 `max tiles in 8 directions that the ai will search! to get closest to target if path error(high nr is slow)
`-------------------------Map size------------------------------
AI_GRID.SIZE_X = 16
AI_GRID.SIZE_Y = 10
dim AI_GRID(AI_GRID.SIZE_X,AI_GRID.SIZE_Y) as AI_DATA
dim AI_PATH_count() as AI_DATA4
`AI-------------------------------------------AI pathfinding code initiating end-----------------------------------------------------------
gosub refresh
`------------------------------------------------Main Loop-------------------------------------------------------------------------------
do
cls
gosub texts
gosub draw_2d
if AI_PATH.EXIST=0 and spacekey()=1 then gosub AI_MAIN_PATHFINDING
if keystate(2)=1 then gosub refresh:AI_PATH.EXIST=0:delete image 1000
if keystate(3)=1 then AI_PATH_TYPE=4
if keystate(4)=1 then AI_PATH_TYPE=8
`--------------only used to show that the array that stores the path works-------------------------------
if controlkey()=1 then inc te:if te>ARRAY COUNT(AI_PATH_count()) then te=1
if ARRAY COUNT(AI_PATH_count())>0 then paste image 8,(AI_PATH_count(te).Xstart*50)-50,(AI_PATH_count(te).Ystart*50)-50,1
if ARRAY COUNT(AI_PATH_count())<0 then paste image 8,(AI_PATH.START_X*50)-50,(AI_PATH.START_Y*50)-50,1
if ARRAY COUNT(AI_PATH_count())>0
for t=1 to ARRAY COUNT(AI_PATH_count())
if t =< MAX_TILES
paste image 7,(AI_PATH_count(t).Xstart*50)-50,(AI_PATH_count(t).Ystart*50)-50,1
endif
next t
endif
while controlkey()=1
endwhile
sync
loop
`------------------------------------------------Main Loop---------------------------------------------------------------------------------
refresh:
while keystate(2)=1
endwhile
te=1
empty array AI_GRID(0,0)
empty array AI_PATH_count()
dim AI_GRID(AI_GRID.SIZE_X,AI_GRID.SIZE_Y)
`--------------------------------generate the random map------------------------
for t=1 to 90
AI_GRID(1+rnd(AI_GRID.SIZE_X-1),1+rnd(AI_GRID.SIZE_Y-1)).TILE_ID=AI_SOLID_ID
next t
for t=1 to 10
AI_GRID(1+rnd(AI_GRID.SIZE_X-1),1+rnd(AI_GRID.SIZE_Y-1)).TILE_ID=1
next t
for t=1 to 15
AI_GRID(1+rnd(AI_GRID.SIZE_X-1),1+rnd(AI_GRID.SIZE_Y-1)).TILE_ID=2
next t
`--------------------------------generate the random map------------------------
remstart
0=walkable
1=rough terrain
2=rougher terrain
3=obstacle
4=start
5=end
6=walked
remend
rem Start and End squares.
rem Change to make test.
AI_GRID(1+rnd(AI_GRID.SIZE_X-1),1+rnd(AI_GRID.SIZE_Y-1)).TILE_ID=AI_START_ID
AI_GRID(1+rnd(AI_GRID.SIZE_X-1),1+rnd(AI_GRID.SIZE_Y-1)).TILE_ID=AI_END_ID
for x=1 to AI_GRID.SIZE_X
for y=1 to AI_GRID.SIZE_Y
if AI_GRID(x,y).TILE_ID=AI_START_ID
AI_GRID(x,y).SEARCH=1 : PASSED=1
AI_PATH.START_X=x : AI_PATH.START_Y=y
endif
if AI_GRID(x,y).TILE_ID=AI_END_ID then AI_PATH.END_X=x : AI_PATH.END_Y=y
next y
next x
return
`----------------Draw map-----------------------
draw_2d:
oldx=0:oldy=0
if image exist (1000)=1 then paste image 1000,0,0,0
for x=1 to AI_GRID.SIZE_X
if x=1 then xs=0
for y=1 to AI_GRID.SIZE_Y
if y=1 then ys=0
``if image exist (1000)=1 then center text (xs)+25,(ys+32),"("+str$(AI_GRID(x,y).SEARCH)+")"
if image exist (1000)=0 then paste image AI_GRID(x,y).TILE_ID+1,xs,ys,0
if AI_GRID(x,y).TILE_ID>AI_END_ID and AI_GRID(x,y).TILE_ID<7 then paste image AI_GRID(x,y).TILE_ID+1,xs,ys,1
``if AI_GRID(x,y).TILE_ID>AI_END_ID then center text (xs)+25,(ys),str$(AI_GRID(x,y).X_ORIGIN)+":"+str$(AI_GRID(x,y).Y_ORIGIN)
``if image exist (1000)=1 then center text (xs)+25,(ys),str$(AI_GRID(x,y).X_ORIGIN)+":"+str$(AI_GRID(x,y).Y_ORIGIN)
``if image exist (1000)=1 and AI_GRID(x,y).TILE_ID=5 then paste image AI_GRID(x,y).TILE_ID+1,xs,ys,0
inc ys,50
next y
inc xs,50
next x
if image exist (1000)=0 then get image 1000,0,0,AI_GRID.SIZE_X*50,AI_GRID.SIZE_Y*50,1
return
`----------------Show text---------------------
texts:
set cursor 0,500
print "TILE BASED PATHFINDING. space = search / 1 = refresh / X:Y = origin tile / CTRL = follow path"
print "FPS = ";screen fps();" Tiles = ";AI_TILE_COUNT;" Pathfinding directions ( KEY 2-3 )= ";AI_PATH_TYPE
print "It will try to avoid the chairs and bottles as much as possible. "
return
`AI---------------------------------------------------main AI code-------------------------------------------------------
AI_MAIN_PATHFINDING:
AI_SEARCH_X_CYCLES = 0
AI_SEARCH_Y_CYCLES = 0
AI_ERROR = 0
global X_AI
global Y_AI
while AI_PATH.EXIST=0
` Search in AI array
` here do we fix an error that makes the search path continous cyckle without end
if AI_PATH_TYPE = 4 and AI_SEARCH_X_CYCLES => AI_GRID.SIZE_X*2 then AI_PATH.EXIST = 1 : AI_ERROR=1
if AI_PATH_TYPE = 8 and AI_SEARCH_X_CYCLES => AI_GRID.SIZE_X then AI_PATH.EXIST = 1 : AI_ERROR=1
for x = 1 to AI_GRID.SIZE_X
if x = AI_GRID.SIZE_X then inc AI_SEARCH_X_CYCLES
for y = 1 to AI_GRID.SIZE_Y
if y = AI_GRID.SIZE_Y then inc AI_SEARCH_Y_CYCLES
if AI_GRID(x,y).SEARCH = PASSED
X_AI = x : Y_AI = y
` Check if fisrt square is into the array
` First Square (like degrees)
` 6 2 5
` 3 * 1
` 7 4 8
tx = X_AI+1
ty = Y_AI
for t = 1 to 4
if t = 2 then dec tx : dec ty
if t = 3 then dec tx : inc ty
if t = 4 then inc tx : inc ty
if tx > 0 and tx =< AI_GRID.SIZE_X and ty > 0 and ty =< AI_GRID.SIZE_Y
AI_SEARCH_TILE(tx,ty,X_AI,Y_AI,PASSED)
endif
next t
if AI_PATH_TYPE = 8 then gosub AI_CORNER_TILES
endif
next y
next x
inc PASSED
endwhile
``------if ai cant get to target find a new target-------------------
AI_TILE_COUNT = 0
if AI_ERROR = 1 and AI_NEW_TARGET = 0 then gosub AI_NEW_END_TILE
if AI_TILE_COUNT = MAX_ERROR_TILES then goto AI_MAIN_PATHFINDING
gosub AI_DRAW_PATH
while spacekey()=1 `remove this if used in other code(lazy mans wait key)
endwhile `remove this if used in other code(lazy mans wait key)
AI_NEW_TARGET=0
return
function AI_SEARCH_TILE(x,y,org_x,org_y,tile)
`Check if first square is a wall and not processed
if AI_GRID(x,y).TILE_ID <> AI_SOLID_ID and AI_GRID(x,y).SEARCH = 0
`Assign next generation
`helps the pathfinding to take the shortest and not so tough route for the ai
if AI_GRID(x,y).TILE_ID = 0 then AI_GRID(x,y).SEARCH = tile + 1
if AI_GRID(x,y).TILE_ID = 1 then AI_GRID(x,y).SEARCH = tile + 2
if AI_GRID(x,y).TILE_ID = 2 then AI_GRID(x,y).SEARCH = tile + 3
`Assign the origin to this square
AI_GRID(x,y).X_ORIGIN=org_x : AI_GRID(x,y).Y_ORIGIN=org_y
`Check if we arrive to the end
if x=AI_PATH.END_X and y=AI_PATH.END_Y then AI_PATH.EXIST=1:X_AI=x:Y_AI=y
endif
endfunction
AI_CORNER_TILES:
tx = X_AI + 1
ty = Y_AI - 1
for t = 5 to 8
if t = 6 then dec tx,2
if t = 7 then inc ty,2
if t = 8 then inc tx,2
if tx > 0 and tx =< AI_GRID.SIZE_X and ty > 0 and ty =< AI_GRID.SIZE_Y
AI_SEARCH_TILE(tx,ty,X_AI,Y_AI,PASSED)
endif
next t
return
AI_NEW_END_TILE:
``------if ai cant get to target find a new target-------------------
AI_NEW_X = 0:AI_NEW_Y = 0 : SEARCH_COUNT = 100
repeat
inc AI_TILE_COUNT
`---------------right---------
if AI_PATH.END_X + AI_TILE_COUNT =< AI_GRID.SIZE_X
if AI_GRID(AI_PATH.END_X + AI_TILE_COUNT,AI_PATH.END_Y).SEARCH > 0 and AI_GRID(AI_PATH.END_X + AI_TILE_COUNT,AI_PATH.END_Y).SEARCH < SEARCH_COUNT
AI_NEW_X = AI_PATH.END_X + AI_TILE_COUNT : AI_NEW_Y = AI_PATH.END_Y
SEARCH_COUNT = AI_GRID(AI_PATH.END_X + AI_TILE_COUNT,AI_PATH.END_Y).SEARCH
endif
endif
`------------right + up-------
if AI_PATH.END_X + AI_TILE_COUNT =< AI_GRID.SIZE_X and AI_PATH.END_Y - AI_TILE_COUNT > 0
if AI_GRID(AI_PATH.END_X + AI_TILE_COUNT,AI_PATH.END_Y - AI_TILE_COUNT).SEARCH > 0 and AI_GRID(AI_PATH.END_X + AI_TILE_COUNT,AI_PATH.END_Y - AI_TILE_COUNT).SEARCH < SEARCH_COUNT
AI_NEW_X = AI_PATH.END_X + AI_TILE_COUNT : AI_NEW_Y = AI_PATH.END_Y - AI_TILE_COUNT
SEARCH_COUNT = AI_GRID(AI_PATH.END_X + AI_TILE_COUNT,AI_PATH.END_Y - AI_TILE_COUNT).SEARCH
endif
endif
`-------------up-------------
if AI_PATH.END_Y - AI_TILE_COUNT > 0
if AI_GRID(AI_PATH.END_X,AI_PATH.END_Y - AI_TILE_COUNT).SEARCH >0 and AI_GRID(AI_PATH.END_X,AI_PATH.END_Y - AI_TILE_COUNT).SEARCH < SEARCH_COUNT
AI_NEW_X = AI_PATH.END_X : AI_NEW_Y = AI_PATH.END_Y - AI_TILE_COUNT
SEARCH_COUNT = AI_GRID(AI_PATH.END_X,AI_PATH.END_Y - AI_TILE_COUNT).SEARCH
endif
endif
`-----------left + up---------
if AI_PATH.END_X - AI_TILE_COUNT > 0 and AI_PATH.END_Y - AI_TILE_COUNT > 0
if AI_GRID(AI_PATH.END_X - AI_TILE_COUNT,AI_PATH.END_Y - AI_TILE_COUNT).SEARCH > 0 and AI_GRID(AI_PATH.END_X - AI_TILE_COUNT,AI_PATH.END_Y - AI_TILE_COUNT).SEARCH < SEARCH_COUNT
AI_NEW_X = AI_PATH.END_X - AI_TILE_COUNT : AI_NEW_Y = AI_PATH.END_Y - AI_TILE_COUNT
SEARCH_COUNT = AI_GRID(AI_PATH.END_X - AI_TILE_COUNT,AI_PATH.END_Y - AI_TILE_COUNT).SEARCH
endif
endif
`--------------left-----------
if AI_PATH.END_X - AI_TILE_COUNT > 0
if AI_GRID(AI_PATH.END_X - AI_TILE_COUNT,AI_PATH.END_Y).SEARCH > 0 and AI_GRID(AI_PATH.END_X - AI_TILE_COUNT,AI_PATH.END_Y).SEARCH < SEARCH_COUNT
AI_NEW_X = AI_PATH.END_X - AI_TILE_COUNT : AI_NEW_Y = AI_PATH.END_Y
SEARCH_COUNT = AI_GRID(AI_PATH.END_X - AI_TILE_COUNT,AI_PATH.END_Y).SEARCH
endif
endif
`--------left + down---------
if AI_PATH.END_X - AI_TILE_COUNT > 0 and AI_PATH.END_Y + AI_TILE_COUNT =< AI_GRID.SIZE_Y
if AI_GRID(AI_PATH.END_X - AI_TILE_COUNT,AI_PATH.END_Y + AI_TILE_COUNT).SEARCH > 0 and AI_GRID(AI_PATH.END_X - AI_TILE_COUNT,AI_PATH.END_Y + AI_TILE_COUNT).SEARCH < SEARCH_COUNT
AI_NEW_X = AI_PATH.END_X - AI_TILE_COUNT : AI_NEW_Y = AI_PATH.END_Y + AI_TILE_COUNT
SEARCH_COUNT = AI_GRID(AI_PATH.END_X - AI_TILE_COUNT,AI_PATH.END_Y + AI_TILE_COUNT).SEARCH
endif
endif
`----------------down---------
if AI_PATH.END_Y + AI_TILE_COUNT =< AI_GRID.SIZE_Y
if AI_GRID(AI_PATH.END_X,AI_PATH.END_Y + AI_TILE_COUNT).SEARCH > 0 and AI_GRID(AI_PATH.END_X,AI_PATH.END_Y + AI_TILE_COUNT).SEARCH < SEARCH_COUNT
AI_NEW_X = AI_PATH.END_X : AI_NEW_Y = AI_PATH.END_Y + AI_TILE_COUNT
SEARCH_COUNT = AI_GRID(AI_PATH.END_X,AI_PATH.END_Y + AI_TILE_COUNT).SEARCH
endif
endif
`----------right + down-------
if AI_PATH.END_X + AI_TILE_COUNT =< AI_GRID.SIZE_X and AI_PATH.END_Y + AI_TILE_COUNT =< AI_GRID.SIZE_Y
if AI_GRID(AI_PATH.END_X + AI_TILE_COUNT,AI_PATH.END_Y + AI_TILE_COUNT).SEARCH > 0 and AI_GRID(AI_PATH.END_X + AI_TILE_COUNT,AI_PATH.END_Y + AI_TILE_COUNT).SEARCH < SEARCH_COUNT
AI_NEW_X = AI_PATH.END_X + AI_TILE_COUNT : AI_NEW_Y = AI_PATH.END_Y + AI_TILE_COUNT
SEARCH_COUNT = AI_GRID(AI_PATH.END_X + AI_TILE_COUNT,AI_PATH.END_Y + AI_TILE_COUNT).SEARCH
endif
endif
if AI_NEW_X > 0 or AI_NEW_Y > 0
AI_NEW_TARGET = 1 : AI_TILE_COUNT = MAX_ERROR_TILES : PASSED = 1 : AI_PATH.EXIST = 0 : AI_ERROR = 0
for x = 1 to AI_GRID.SIZE_X
for y = 1 to AI_GRID.SIZE_Y
AI_GRID(x,y).SEARCH = 0 : AI_GRID(x,y).X_ORIGIN = 0 : AI_GRID(x,y).Y_ORIGIN = 0
next y
next x
AI_GRID(AI_PATH.START_X,AI_PATH.START_Y).SEARCH = 1
AI_GRID(AI_NEW_X,AI_NEW_Y).TILE_ID = AI_END_ID
AI_PATH.END_X = AI_NEW_X : AI_PATH.END_Y = AI_NEW_Y
endif
until AI_TILE_COUNT = MAX_ERROR_TILES
return
AI_DRAW_PATH:
empty array AI_PATH_count(0)
X_AI = AI_PATH.END_X : Y_AI = AI_PATH.END_Y
`Follow the path in inverse order and if path not found skip it (error)
if AI_ERROR = 0
AI_TILE_COUNT = 0
while X_AI <> AI_PATH.START_X or Y_AI <> AI_PATH.START_Y
inc AI_TILE_COUNT
dim AI_PATH_count(AI_TILE_COUNT)
x1 = X_AI : y1 = Y_AI
X_AI = AI_GRID(x1,y1).X_ORIGIN
Y_AI = AI_GRID(x1,y1).Y_ORIGIN
` To draw a marker on this square
`AI_GRID(x1,y1).TILE_ID=6
AI_PATH_count(AI_TILE_COUNT).X = x1
AI_PATH_count(AI_TILE_COUNT).y = y1
`----------fixes an bugg created if the ai cant find an path
If x1 = X_AI and y1 = Y_AI
X_AI = AI_PATH.START_X : Y_AI = AI_PATH.START_Y
AI_PATH_count(AI_TILE_COUNT).X = AI_PATH.START_X
AI_PATH_count(AI_TILE_COUNT).y = AI_PATH.START_Y
empty array AI_PATH_count(0)
endif
endwhile
`here do we turn the path array around so that 1 in array is tile one and not the last one in the array
if ARRAY COUNT(AI_PATH_count()) > 0
t2 = ARRAY COUNT(AI_PATH_count()) + 1
for t = 1 to ARRAY COUNT(AI_PATH_count())
AI_PATH_count(t2 - t).Xstart = AI_PATH_count(t).X
AI_PATH_count(t2 - t).Ystart = AI_PATH_count(t).Y
next t
endif
endif
return
`AI---------------------------------------------------main AI code-------------------------------------------------------
