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

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()

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

do
 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
    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
 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
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