TheGameCreators - CodeBase - Path Finder By Mince

Return to the CodeBase listing

Category: Complete Applications

Version: 1.0

Information

Uploaded: 6th Feb 2008 14:24

Modified: 6th Feb 2008 15:27

Author: PALMER

Summary

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

Full Description

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

DarkBASIC Professional Source Code

` 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

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

Download

Please login to download

Comments

No comments yet.

Author Name:	PALMER
CodeBase Entries:	4

CodeBase - Path Finder By Mince

Information

Summary

Full Description

DarkBASIC Professional Source Code

Download

Screen Shot

Author

Comments