TheGameCreators - CodeBase - A* Path Finder Algorythm

Return to the CodeBase listing

Category: Math / Physics

Version: 1.0

Information

Uploaded: 2nd Jun 2004 12:52

Modified: 1st Jan 1970 01:00

Author: PantheR RIP

Summary

This one will find optimal path on a tiled matrix

Full Description

Project created by Alexander aka Panther Email: panthernet@mail.ru ICQ: 7657870 Some basic info about A* algorythm: It is designed to work on a coordinate grid (tiled matrix in our case). So we start search from some Start tile abd store next tile in the array. Also we store 'Cost' of the tile (each tile can be set to have different pass priority during path search process) and finally 'Weight Function' of the tile (wich uses 'Cost' value and used to determine final tile passage priority). And so on till bound tiles array is empty

DarkBASIC Professional Source Code

` This code was downloaded from The Game Creators

` It is reproduced here with full permission

` http://www.thegamecreators.com

` Ð* algorythm itself

function FindPath(x1,z1,x2,z2)

A as TPoint

i as integer

j as integer

k as integer

dx as float

dz as float

RESULT as integer

dim kk(1) as float

` Get start and end tiles numbers

Src.x=x1:Src.z=z1

Dst.x=x2:Dst.z=z2

i=0;j=0;

` This one used to determine odd numbers

kk(0)=1.42;kk(1)=1

dx=Src.X-Dst.X;dz=Src.z-Dst.z;

` Set initial values for start and end points

Map(Src.X,Src.z).Status=tsBound;

Map(Dst.X,Dst.z).Status=tsFinish;

BSize=1; Map(Src.x,Src.z).gval=0;

HEst(Src.X,Src.z,Dst.X,Dst.z,dx,dz);

Map(Src.x,Src.z).hval=floatval

Map(Src.x,Src.z).fval=Map(Src.x,Src.z).gval+Map(Src.x,Src.z).hval;

` First element of Bound array is - Start

Bound(1).x=Src.X;Bound(1).z=Src.z;

RESULT=0;

k=1

` While Bound array isn't empty

while BSize>0

` Find tile with lesser Weight Func

k=FindMin(k)

i=Bound(k).x;

j=Bound(k).z;

` Set tile status to Passed

Map(bound(k).X,bound(k).z).Status=tsPassed;

bound(k)=bound(BSize);

dec BSize;

k=1;

` Check all 8 movement directions from current tile

for k=1 to 8

A.X=i+Courses(k).X;

A.Z=j+Courses(k).z;

` If current tile isn't wall

if Map(A.x,A.z).TerrType<>ttWall

` If current tile wasn't checked

if Map(A.x,A.z).Status=tsUnvisited

` Get Weight Func

Map(A.X,A.z).gval=Map(i,j).gval+Map(A.X,A.z).value*kk(k mod 2);

HEst(A.X,A.z,Dst.X,Dst.z,dx,dz);

Map(A.X,A.z).fval=Map(A.X,A.z).gval+floatval

` Store prevoius tile

Map(A.X,A.z).Prev.x=i;Map(A.X,A.z).Prev.z=j;

` Set tile status to Bound and store it in Bound array

Map(A.X,A.z).Status=tsBound;

gosub AddToBound;

endif

` If current tile is End tile

if Map(A.x,A.z).Status=tsFinish

` Store prevoius tile

Map(A.X,A.z).Prev.x=i;Map(A.X,A.z).Prev.z=j;

` Set start tile status to Start

Map(Src.X,Src.z).Status=tsStart;

` Exit cycle

RESULT=1;

goto ENDS

endif

next k

ENDWHILE

` There is the path analyzer goes

`*******************************

ENDS:

`  Map(Src.X,Src.z).Status=tSStart;

` If search succefull

if RESULT=1

wp_player_leng=0

leng=1;

` Get previous tile from End tile and set it to Passed status

c=Map(Dst.X,Dst.z).Prev;

Map(c.x,c.z).Status=tsPassed;

` WP array generations

` First element - End tile

wp_player(leng).x=Dst.x

wp_player(leng).z=Dst.z

` Increase passes count

inc leng

` Place WP indication object

position object 2000,player.dx,get ground height(1,player.dx,player.dz),player.dz

show object 2000

` While current tile isn't Start tile

While not EqualPoints(c.x,c.z,Src.x,Src.z)

` If current tile isn't bound tile

if Map(c.X,c.z).Status<>tsBound

` Set current tile status to Path

Map(c.X,c.z).Status=tsPath;

` Store tile nums in WP array

wp_player(leng).x=c.x

wp_player(leng).z=c.z

` increase WP count

inc wp_player_leng

` Position WP indication object

position object 2000+wp_player_leng,GetTileCoordX(c.x),get ground height(1,GetTileCoordX(c.x),GetTileCoordZ(c.z)),GetTileCoordZ(c.z)

show object 2000+wp_player_leng

endif

` Increase passes count

inc leng

` Get next (prevoius realy) tile

c=Map(c.x,c.z).Prev;

endwhile

` Store tile next from Start tile

wp_player(leng).x=c.x

wp_player(leng).z=c.z

inc wp_player_leng

position object 2000+wp_player_leng,GetTileCoordX(c.x),get ground height(1,GetTileCoordX(c.x),GetTileCoordZ(c.z)),GetTileCoordZ(c.z)

show object 2000+wp_player_leng

` Store Start tile

wp_player(leng+1).x=src.x

wp_player(leng+1).z=src.z

inc wp_player_leng

` Go to WP movement preparations

PreMove(player.obj)

endif

undim kk(0)

exitfunction RESULT

` Adds tile to Bound array

AddToBound:

if BSize>=MaxBoundSize

else

inc BSize

Bound(BSize).x=A.x

Bound(BSize).z=A.z

endif

RETURN

endfunction RESULT

` Searches for the tile within Bound array with lesser Weight Func

function FindMin(xx as integer)

var as integer:i as integer

n=xx;

for u=1 to BSize

if Map(bound(n).X,bound(n).z).fval>Map(bound(u).X,bound(u).z).fval then minaret=u:n=u

CodeBase - A* Path Finder Algorythm

Information

Summary

Full Description

DarkBASIC Professional Source Code

Download

Screen Shot

Author

Comments

Author Name:	PantheR RIP
CodeBase Entries:	1