TheGameCreators - CodeBase - A

Return to the CodeBase listing

Category: Complete Applications

Version: 0.1

Information

Uploaded: 19th Feb 2008 10:13

Modified: 13th Jul 2009 07:36

Author: PALMER

Summary

Raster map Path Finder / AI / NPC Finds a path from Pointa(startx,starty) to Pointb(destx,desty)

Full Description

I use this in my rts and it works. Variable intensity: Setting stack_run to 10 would be very much in background, enableing you game to run through while path is being worked out. setting stack_run to 0 would be constant, slowing system. To make seperate path finders for seperate types of unit eg Workers/Attack we could make a copy of all variables change all there names eg function boss_A_pathfinder_isonopen() function boss_A_pathfinder_work_stack() function dog_A_pathfinder_isonopen() function dog_A_pathfinder_work_stack()

DarkBASIC Professional Source Code

` This code was downloaded from The Game Creators

` It is reproduced here with full permission

` http://www.thegamecreators.com

gosub advanced_pathfinder_setup` Call this at start.

`----------------------------------------------------------

`EXAMPLE unit (type) var

`----------------------------------------------------------

`type u_nit_path_type

`x as integer

`y as integer

`endtype

`max_units = 1000

`max_indexsize = 7000`The tile search limit

`dim unit_path(max_units,max_indexsize) as u_nit_path_type

`---------------------------------------------------------

set display mode 1024,768

`--------------------------------

`More INFO/Example;

`eg: Add Object to the map Array.

`Object..(make sure the vars for thease objects are global so the function has access)

`wall = 1(map_object_data)

`tree = 2(map_object_data)

`Array map(x,y).mtype = wall

`----------------------------

inc stack_turn,1

if stack_turn > stack_run `(stack_run = the amount of tiles to check per game loop cycle)

A_pathfinder_work_stack()`works out paths for units on pathfinder stack.

stack_turn = 0

endif

`Your code

`To add a path, to be searched for a unit >

`Call A_pathfinder_add_to_stack(startx,starty,destinationx,destinationy,Unit_number)

loop

`should never get to here!

end.

advanced_pathfinder_setup:

`Types

type squaretype

fscore as integer

gscore as integer

hscore as integer

mtype as integer

px as integer

py as integer

endtype

type pointtype

x as integer

y as integer

endtype

type stack_info`Stack Store

unit as integer

finished as integer

started as integer

spx as integer

spy as integer

dpx as integer

dpy as integer

index as integer

endtype

`Vars

global A_pathfinder_runtime = 5             `Time in ms.

global A_pathfinder_max_steps = 150*6       `Tiles to check before moving on to next unit in stack.

(N)tiles *(6) a must!

global A_pathfinder_max_stacks = 1000       `Sets the limit for unit paths to work out.

global A_pathfinder_max_index = 50000       `The maximum Size of search.

global A_pathfinder_time_started as integer `timer()

global index_pos as integer

global A_pathfinder_waiting as integer

A_pathfinder_waiting = 1

global false = 0

global true = 1

`Controls the intesity of pathfinding

global stack_run as integer

stack_run = 10`0 is intence and 1000 is never ish.

`Stack intensity counter

global stack_turn as integer

stack_turn = 0

`Constants

`Search logic

global ground_grass = 1`global constants

global hill = 8`global constants

global crops = 2`global constants

global water = 3`global constants

global wall = 4`global constants

global corncost = 2`global constants

global groundcost = 1`global constants

`sizewidth = 1024

`sizeheight = 1024

`Arrays

global dim A_pathfinder_stack() as stack_info`A_pathfinder_max_stacks

global dim map(1024,1024) as squaretype

`Make Walls around map to stop searching out of bounds

for x = 1 to 1024

for y = 1 to 1024

map(x,y).mtype = tilelogicarray(x,y)`need to add walls all around map to stop out of bound searches!

if x = 1 then map(x,y).mtype = 4

if y = 1 then map(x,y).mtype = 4

if x = 1024 then map(x,y).mtype = 4

if y = 1024 then map(x,y).mtype = 4

next y

next x

return

function A_pathfinder_add_to_stack(startx,starty,dpx,dpy,UNIT)

`Check to see if this unit is already in stack, if so then remove that stack then add this new one.

stacks = array count(A_pathfinder_stack(0))

for look_instack = 0 to stacks

stacks_now = array count(A_pathfinder_stack(0))

if stacks_now => look_instack`der!

if A_pathfinder_stack(look_instack).unit = UNIT

`Remove this stack

A_pathfinder_stack(look_instack).started = 0

A_pathfinder_remove_from_stack(look_instack)

`if it was the working path remove arrays

if look_instack = 0

undim A_pathfinder_openlist(0)

undim A_pathfinder_closedlist(0)

undim A_pathfinder_path(0)

endif`look_instack

endif`=unit

else`stacks_now = -1

exit

endif`stacks_now

next look_instack

if array count(A_pathfinder_stack(0)) < A_pathfinder_max_stacks` if a stack is availible

`Add to stack

array insert at bottom A_pathfinder_stack(0)

position = array count(A_pathfinder_stack(0)) `at new blank stack

A_pathfinder_stack(position).unit = UNIT

A_pathfinder_stack(position).spx = startx

A_pathfinder_stack(position).spy = starty

A_pathfinder_stack(position).dpx = dpx

A_pathfinder_stack(position).dpy = dpy

A_pathfinder_stack(position).started = 0

A_pathfinder_stack(position).finished = 0

A_pathfinder_stack(position).index = 0

unit(UNIT).waiting_stack = 0

unit(UNIT).has_path = 0

unit(UNIT).need_a_Waypoint = 0

else

`Flag unit to> waiting to be placed on stack.

unit(UNIT).waiting_stack = 1

unit(UNIT).has_path = 0

unit(UNIT).need_a_Waypoint = 0

endif`space on stack?

endfunction

function A_pathfinder_remove_from_stack(stack_number)

array delete element A_pathfinder_stack(0),stack_number

endfunction

function A_pathfinder_work_stack()

stacks = array count(A_pathfinder_stack(0))

if stacks => 0

A_pathfinder_find_path(0)

endif

endfunction

`Function finds path from spx,spy to dpx,dpy and adds this path to Unit_Path(unit)

`The Path Engine Â¬Mince 08

function A_pathfinder_find_path(stack_num)

`Temp Vars

tempg as integer

x as integer

y as integer

fcx as integer

fcy as integer

path_posible as integer

tile_score as integer

steps as integer

index_pos as integer

`Get Time Stamp

A_pathfinder_time_started = timer()

A_pathfinder_stop_time = A_pathfinder_time_started + A_pathfinder_runtime

`Pull stack info

spx = A_pathfinder_stack(stack_num).spx

spy = A_pathfinder_stack(stack_num).spy

dpx = A_pathfinder_stack(stack_num).dpx

dpy = A_pathfinder_stack(stack_num).dpy

UNIT = A_pathfinder_stack(stack_num).unit`unit data

`Check if this is a new search or if to continue a search.

if A_pathfinder_stack(stack_num).started = 1

`Search through the open list to find lowest f score

tile_score = 90000`reset high

path_posible = 0

for i = 1 to array count(A_pathfinder_openlist(0))

if A_pathfinder_isonclosed((A_pathfinder_openlist(i).x),(A_pathfinder_openlist(i).y)) = 0

if map((A_pathfinder_openlist(i).x),(A_pathfinder_openlist(i).y)).fscore =< tile_score

c.x = A_pathfinder_openlist(i).x

c.y = A_pathfinder_openlist(i).y

tile_score = map((A_pathfinder_openlist(i).x),(A_pathfinder_openlist(i).y)).fscore

path_posible = 1

endif

next i

`--------------------------------------------------------------------------------

else`New search or Continue search.>NEW SEARCH

index_pos = 0

`Set up Arrays each time function is called

global dim A_pathfinder_openlist() as pointtype

global dim A_pathfinder_closedlist() as pointtype

global dim A_pathfinder_path() as pointtype

global  mstart as pointtype`Global?

global  mfinish as pointtype`Global?

`global dim comp() as pointtype`????? fix

global c as pointtype`Global?

global dim  onfinish() as integer`???

A_pathfinder_stack(stack_num).started = 1`Flag Now Started!

endif`End of continue check

steps = 0

mstart.x = spx

mstart.y = spy

mfinish.x = dpx

mfinish.y = dpy

`Search logic

`ground = 1`global constants

`hill = 8`global constants

`crops = 2`global constants

`water= 3`global constants

`wall = 4`global constants

`corncost = 2`global constants

`groundcost = 1`global constants

`sizewidth = 1024

`sizeheight = 1024

`Also

if A_pathfinder_stack(stack_num).started = 1

c.x = mstart.x

c.y = mstart.y

endif

A_pathfinder_addtoopen(c.x,c.y)`Start/Continue Search Location.

onfinish = 0

while onfinish = 0`----------------------------------------------------------------------------Â¬

A_pathfinder_addtoclosed(c.x,c.y)

for y = -1 to 1

for x = -1 to 1

fcx = c.x + x

fcy = c.y + y

if a_pathfinder_inbounds(fcx,fcy) = 1

if map(fcx,fcy).mtype <> 4`not = 4 wall

if map(fcx,fcy).mtype <> water`not water

if A_pathfinder_isonclosed(fcx,fcy) = false`not on closed list

if A_pathfinder_isonopen(fcx,fcy) = false`not on open list

`Caculate tile scores

`G first------------------------------------Â¬

if map(fcx,fcy).mtype = ground_grass

map(fcx,fcy).gscore = map(c.x,c.y).gscore + groundcost`echo

else

map(fcx,fcy).gscore = map(c.x,c.y).gscore + corncost`not water or wall so must be corn!

endif

`-------------------------------------------

`Now H--------------------------------------Â¬

`Using whats known as Manhatten distance sys

`hx = 10 * (abs( fcx - mfinish.x) )

`hy = 10 * (abs( fcy - mfinish.y) )

`Now using whats known as Mince distance

hx = 20 * (abs( fcx - mfinish.x) )

hy = 20 * (abs( fcy - mfinish.y) )

map(fcx,fcy).hscore = (hx + hy)

`Finally the F score = G + H

map(fcx,fcy).fscore = map(fcx,fcy).gscore + map(fcx,fcy).hscore

`Make the current square (c.x,c.y) the parent of this square (c.x+x,c.y+y)

map(fcx,fcy).px = c.x

map(fcx,fcy).py = c.y

`Add this square to the open list

A_pathfinder_addtoopen(fcx,fcy)

`If its the finish square we have completed the search! when added to close!!

if fcx = mfinish.x and fcy = mfinish.y then onfinish = 1

else`on open list

`check g scores

if map(fcx,fcy).mtype = ground_grass

tempg = map(fcx,fcy).gscore + groundcost

else`on closed list

`if water

`if hill

tempg = map(c.x,c.y).gscore + corncost`corn

endif`map = ground

if tempg < map(fcx,fcy).gscore

`make the current square the parent of this square

map(fcx,fcy).px = c.x

map(fcx,fcy).py = c.y

`re calculate scores

map(fcx,fcy).gscore = tempg

map(fcx,fcy).fscore = map(fcx,fcy).gscore + map(fcx,fcy).hscore

endif`tempg<map.gscore switch

endif`open list

endif`closed=false

endif`<>water

endif`<>wall

endif`inbounds() = 1

next x

next y

`Search through the open list to find lowest f score

tile_score = 99999`reset high

path_posible = 0

for i = 1 to array count(A_pathfinder_openlist(0))

if A_pathfinder_isonclosed((A_pathfinder_openlist(i).x),(A_pathfinder_openlist(i).y)) = 0

if map((A_pathfinder_openlist(i).x),(A_pathfinder_openlist(i).y)).fscore =< tile_score

c.x = A_pathfinder_openlist(i).x

c.y = A_pathfinder_openlist(i).y

tile_score = map((A_pathfinder_openlist(i).x),(A_pathfinder_openlist(i).y)).fscore

path_posible = 1

endif

next i

`IF No Path open then quit current search.

if path_posible = 0 then exit

`Check A_pathfinder runnung time.

`if timer() > A_pathfinder_stop_time then exit

inc steps,1

inc index_pos,1

if steps > A_pathfinder_max_steps then exit

if index_pos => A_pathfinder_max_index

path_posible = 0

`OH DEAR!

endif

endwhile

`Exit or endwhileÂ¬

`-Path Found Store Working

PathÂ¬-----------------------------------------------------------------------------------------

if onfinish = 1`Via Endwhile

`Work backwards to get path!

c.x = mfinish.x

c.y = mfinish.y

i = 0

onstart = 0

`Store path either to A_pathfinder_path().x/y or to your array like mine >unit_path(unit).x/y

while onstart = 0

`   unit_path(UNIT,i).x = c.x

`   unit_path(UNIT,i).y = c.y

`OR  A_pathfinder_addtopath(x,y) can store one path at a time.

`Check to see if at start.

if c.x = mstart.x and c.y = mstart.y then exit`onstart = 1

x = c.x

y = c.y

`Make the current square the parent square.

c.x = map(x,y).px

c.y = map(x,y).py

inc i,1

endwhile

`This path is created from parented tiles,working from destination to start.

`Rather than reversing it just set your unit to start at the end. unit(unit).index = i

`Each step taking 1 from unit(unit).index until unit(unit).index = 0.

`Also you know how many steps are left unit(unit).index = steps left.

`Here you would place the search result into a array like below.

`unit_path(UNIT,0).x = mfinish.x

`unit_path(UNIT,0).y = mfinish.y`Update Unit Path.

`you then can flag your unit to has path = true, in your function/sub controlling your

`units only control units with paths.

`unit(UNIT).has_path = 1

A_pathfinder_stack(stack_num).finished = 1

A_pathfinder_stack(stack_num).started = 0

` unit(UNIT).waiting_stack = 0

` waypoint(UNIT).path_step_counter = i`start at end and dec till 0!

`remove from stack

A_pathfinder_remove_from_stack(stack_num)

undim A_pathfinder_openlist(0)

undim A_pathfinder_closedlist(0)

undim A_pathfinder_path(0)

`Happy Dayz!!

else`No Path posible or Ran out of time!Â¬

if path_posible = 0

`No Path posible

A_pathfinder_stack(stack_num).finished = 1

A_pathfinder_stack(stack_num).started = 0

`remove from stack

A_pathfinder_remove_from_stack(stack_num)

undim A_pathfinder_openlist(0)

undim A_pathfinder_closedlist(0)

undim A_pathfinder_path(0)

`set unit to stop

`unit(UNIT).action = stopped

else

`Ran out of time..

endif`path_posible = 1?

endif`onfinish?

endfunction

function a_pathfinder_inbounds(x,y)

ret_bounds = 0

if x > 0 and x <1024

if y > 0 and y <1024

ret_bounds = 1

endif

endfunction ret_bounds

function A_pathfinder_addtoopen(x,y)

array insert at bottom A_pathfinder_openlist(0)

A_pathfinder_openlist(array count(A_pathfinder_openlist(0))).x = x

A_pathfinder_openlist(array count(A_pathfinder_openlist(0))).y = y

endfunction

function A_pathfinder_addtoclosed(x,y)

array insert at bottom A_pathfinder_closedlist(0)

A_pathfinder_closedlist(array count(A_pathfinder_closedlist(0))).x = x

A_pathfinder_closedlist(array count(A_pathfinder_closedlist(0))).y = y

endfunction

function A_pathfinder_addtopath(x,y)

array insert at bottom A_pathfinder_path(0)

A_pathfinder_path(array count(A_pathfinder_path(0))).x = x

A_pathfinder_path(array count(A_pathfinder_path(0))).y = y

endfunction

function A_pathfinder_isonclosed(x,y)

onclosed = 0

for i = 1 to array count(A_pathfinder_closedlist(0))

if A_pathfinder_closedlist(i).x = x and A_pathfinder_closedlist(i).y = y

onclosed = 1

exit

endif

next i

endfunction onclosed

function A_pathfinder_isonopen(x,y)

onopen = 0

for i = 1 to array count(A_pathfinder_openlist(0))

if A_pathfinder_openlist(i).x = x and A_pathfinder_openlist(i).y = y

onopen = 1

exit

endif

next i

endfunction onopen

Download

Please login to download

Comments

No comments yet.

CodeBase - A_Pathfinder By Mince

Information

Summary

Full Description

DarkBASIC Professional Source Code

Download

Screen Shot

Author

Comments

Author Name:	PALMER
CodeBase Entries:	4