Path Finding / Path Finder / AI / NPC. For raster type maps 8 Directional seach type.

This is good to understand the basics of type A* Path finding.
When finished I will post my new Path-Finding project that is timer based can handle lots of searches at once.

I hope this is useful, I found nothing In the way of source on this subject via forums.
(I Hate it when People keep things to them self!!!!!!)

                                    ` This code was downloaded from The Game Creators
                                    ` It is reproduced here with full permission
                                    ` http://www.thegamecreators.com
                                    
                                    `Mince 08                         Path Finder for Raster maps(2d data array)

`This is the first thing I have ever added and I hope its in a way you can run with it:>
`


`DIRECTIONS:
`Add this lot at the bottum of what ever you have made, 
` then call Mince_a_star_setup from start of you program


`What you need to do is read the info from your map , and place relevent info from it say 
` its a wall> in your_map_array(x,y) = (wall_value) then add (wall_value) to map(x,y).mtype
`I use 4 as my wall value.

`Also you must have walls_val all around map to stop the search from going out of bounds,crashing.
`There are other ways like you could make a function inbounds(x,y)
` and then add it into function minces_a_star>  if inbounds(x,y) = true : else dont search 


`Then call function ( function minces_a_star_create_arrays_and_find_path(startx,starty,dpx,dpy,UNIT) )
`startx point,starty point,destinationx,destinationy,unit> untit


global map_size_width = 1024` Path Finders Map Array Size change to match your own map_array(x,y)
global map_size_height = 1024



Mince_a_star_setup:
type squaretype
fscore as integer
gscore as integer
hscore as integer
mtype as integer  `move type
px as integer
py as integer
endtype

type pointtype
x as integer
y as integer
endtype
global false = 0
global true = 1

`Now update Map for path finder
` this is the map used by function >for path search!.
global dim map(map_size_width,map_size_height) as squaretype
return





`Function finds path from spx,spy to dpx,dpy and adds this path to Unit_Path(unit)
function minces_a_star_create_arrays_and_find_path(startx,starty,dpx,dpy,UNIT)`whole map!


ground = 1` Here use values to define what you dont want to check, or what would be a slower path
hill = 8
crops = 2
water= 3
wall = 4
start = 5
finnish = 6
hill = 7

false = 0 
true = 1

groundcost = 10` cost of move info
hillcost = 25
watercost = 100
cliffcost = 100
wallcost = 200




`Set up Arrays


global dim openlist() as pointtype
global dim closedlist() as pointtype
global dim path() as pointtype
global  mstart as pointtype
global  mfinish as pointtype
global dim comp() as pointtype




`get spx,spy and store them
mstart.x = startx
mstart.y = starty

`get dpx,dpy and store them
mfinish.x = dpx
mfinish.y = dpy

global c as pointtype
global dim onfinish() as integer

c.x = mstart.x
c.y = mstart.y
addtoopen(c.x,c.y)

onfinish = 0
`Search through the open list to find lowest f score
global tile_score as integer
tile_score = 99999

while onfinish = 0`----------------------------------------------------------------------------¬
addtoclosed(c.x,c.y)
for y = -1 to 1
 for x = -1 to 1

 `Debug--------------------------------¬ take out (`) to see whats going on!¬ 
`                                         I have my Display res at 1024,768

  `set text size 35
  `ink RGB(0,0,255),0
  `text 100,400,"loc x("+str$(c.x+x)+")Loc y("+str$(c.y+y)+")open = "+str$(array count(openlist(0)))+"/closed = "+str$(array count(closedlist(0)))
  `sync
  `ink rgb(0,0,0),0
  `text 100,400,"loc x("+str$(c.x+x)+")Loc y("+str$(c.y+y)+")open = "+str$(array count(openlist(0)))+"/closed = "+str$(array count(closedlist(0)))
  `wait 1

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

 fcx = c.x + x`fcx is used to Save addind repetativly
 fcy = c.y + y
  if map(fcx,fcy).mtype <> 4`not = 4 wall
   if map(fcx,fcy).mtype <> water`not water
    if isonclosed(fcx,fcy) = false`not on closed list
     if isonopen(fcx,fcy) = false`not on open list
    `Caculate tile scores
    `G first------------------------------------¬
     if map(fcx,fcy).mtype = ground
      map(fcx,fcy).gscore = map(fcx,fcy).gscore + 10`groundcost
      else
      map(fcx,fcy).gscore = map(c.x,c.y).gscore + 30
     endif
    `-------------------------------------------

   `Now H--------------------------------------¬
   `Using whats known as Manhatten distance sys(basicaly this is the distance to go till finish square)
   hx = 10 * (abs( fcx - mfinish.x) )
   hy = 10 * (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
   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
  if map(fcx,fcy).mtype = ground
   tempg = map(fcx,fcy).gscore + 10
  else
   `if water
   `if hill
    tempg = map(c.x,c.y).gscore + 30`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

next x
next y

`Search through the open list to find lowest f score
`global tile_score as integer
tile_score = 99999

for i = 1 to array count(openlist(0))
 if isonclosed((openlist(i).x),(openlist(i).y)) = 0
  if map((openlist(i).x),(openlist(i).y)).fscore =< tile_score
   c.x = openlist(i).x
   c.y = openlist(i).y
   tile_score = map((openlist(i).x),(openlist(i).y)).fscore
  endif
 endif
next i
endwhile
`-------------------------------------------------------------------------------------------------------

`We found the target square
global dim onstart() as integer

c.x = mfinish.x
c.y = mfinish.y

i = 1
onstart = 0
while onstart = 0
addtopath(c.x,c.y)
if c.x = mstart.x and c.y = mstart.y then onstart = 1
x = c.x
y = c.y
`make the currentsquare the parent square
c.x = map(x,y).px
c.y = map(x,y).py
inc i,1
endwhile

`Save Path into your array like I done with my array unit_path(unit_number,Path_step)
size = (array count(path(0)))` = i
for i = 1 to size
 `unit_path(UNIT,i).x = path(i).x  >>>> This is where you add path(i).x to your path array
 `unit_path(UNIT,i).y = path(i).y
next i


`Happy Dayz!!
endfunction







function path_error(x,y)`needs work
 retval = 0
 if mstart.x <0 then retval = 1
 if mstart.y <0 then retval = 1
 if mstart.x > x then retval = 1
 if mstart.y > y then retval = 1
endfunction retval



function addtoopen(x,y)
global dim tempopen(array count(openlist(0))) as pointtype

for i = 1 to array count(openlist(0))
 tempopen(i).x = openlist(i).x
 tempopen(i).y = openlist(i).y
next i

size = array count(openlist(0)) + 1
global dim openlist(size) as pointtype

for i = 1 to array count(tempopen(0))
 openlist(i).x = tempopen(i).x
 openlist(i).y = tempopen(i).y
next i

openlist(array count(openlist(0))).x = x
openlist(array count(openlist(0))).y = y
endfunction






function addtoclosed(x,y)

global dim tempclosed(array count(closedlist(0))) as pointtype

for i = 1 to array count(closedlist(0))
 tempclosed(i).x = closedlist(i).x
 tempclosed(i).y = closedlist(i).y
next i

size = array count(closedlist(0)) + 1
global dim closedlist(size) as pointtype

for i = 1 to array count(tempclosed(0))
 closedlist(i).x = tempclosed(i).x
 closedlist(i).y = tempclosed(i).y
next i

closedlist(array count(closedlist(0))).x = x
closedlist(array count(closedlist(0))).y = y
endfunction







function addtopath(x,y)
global dim temppath(array count(path(0))) as pointtype

for i = 1 to array count(path(0))
 temppath(i).x = path(i).x
 temppath(i).y = path(i).y
next i

size = array count(path(0))
global dim path(size+1) as pointtype
for i = 1 to array count(temppath(0))
 path(i).x = temppath(i).x
 path(i).y = temppath(i).y
next i

path(array count(path(0))).x = x
path(array count(path(0))).y = y
endfunction





function isonclosed(x,y)
onclosed = 0
for i = 1 to array count(closedlist(0))
 if closedlist(i).x = x and closedlist(i).y = y
  onclosed = 1
  exit
 endif
next i
endfunction onclosed




function isonopen(x,y)
 onopen = 0
for i = 1 to array count(openlist(0))
 if openlist(i).x = x and openlist(i).y = y
  onopen = 1
  exit
 endif
next i
endfunction onopen