TheGameCreators - CodeBase - Tile based pathfinding for rts,rpg and strategy games.(2d/3d)

Category: 2D

Version: 1.1

Information

Uploaded: 3rd Jan 2010 15:03

Modified: 5th Jan 2010 19:34

Author: Cliff Mellangard 3DEGS

Summary

NEW IMPROVED VERSION! 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. Screen shot is the neaded media. And this code! works really well :)

Full Description

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.

DarkBASIC Professional Source Code

` This code was downloaded from The Game Creators

` It is reproduced here with full permission

` http://www.thegamecreators.com

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. ////

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

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

`//// 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

`//// 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

`//// 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

`//// 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

`//// 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

`//// 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

`//// 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

`//// 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

Download

Please login to download

Comments

No comments yet.

Author Name:	Cliff Mellangard 3DEGS
CodeBase Entries:	15

CodeBase - Tile based pathfinding for rts,rpg and strategy games.(2d/3d)

Information

Summary

Full Description

DarkBASIC Professional Source Code

Download

Screen Shot

Author

Comments