Pathfinding Script

[ShadowMancer]

here is a script that uses basic concepst from A* pathfinding.
it is not TRUE A* but it works.
there is a random factor to it so it will not always find the target right away
(you can tweak the random for your own uses)
I created a demo with a damage combo that looks like a trap
the trap follows link through a maze
i am not sure how to upload a demo but here is the script


//Script to have a FFC find Link and follow him

ffc script pathfinding{




void run(int this_ffc_num)
{
//declare vars
int clo1X = 0;
int clo1Y = 0;
int clo2X = 0;
int clo2Y = 0;
int clo3X = 0;
int clo3Y = 0;
int clo4X = 0;
int clo4Y = 0;
int cls_ptr = 1;

while (true){
int Gtop = 0;
int Gbot = 0;
int Glft = 0;
int Grht = 0;
int Htop = 0;
int Hbot = 0;
int Hlft = 0;
int Hrht = 0;
int Ftop = 500;
int Fbot = 500;
int Flft = 500;
int Frht = 500;
int best_dir = 0;



// "this_ffc->" bug workaround
ffc this_ffc = Screen->LoadFFC(this_ffc_num);

//set close list X and Y to current pos
if (cls_ptr == 1) {
clo1X = this_ffc->X;
clo1Y = this_ffc->Y;
}
if (cls_ptr == 2) {
clo2X = this_ffc->X;
clo2Y = this_ffc->Y;
}
if (cls_ptr == 3) {
clo3X = this_ffc->X;
clo3Y = this_ffc->Y;
}
if (cls_ptr == 4) {
clo4X = this_ffc->X;
clo4Y = this_ffc->Y;
}
//check walkabilty on 4 sides
if (is_walkable(this_ffc->X, this_ffc->Y-16, clo1X, clo1Y, clo2X, clo2Y, clo3X, clo3Y, clo4X, clo4Y) )
{
Gtop = 10;
Htop = Abs((Link->X - this_ffc->X) + (Link->Y - (this_ffc->Y-16)));
}

if (is_walkable(this_ffc->X, this_ffc->Y+16, clo1X, clo1Y, clo2X, clo2Y, clo3X, clo3Y, clo4X, clo4Y))
{
Gbot = 10;
Hbot = Abs((Link->X - this_ffc->X) + (Link->Y - (this_ffc->Y+16)));
}

if (is_walkable(this_ffc->X-16, this_ffc->Y, clo1X, clo1Y, clo2X, clo2Y, clo3X, clo3Y, clo4X, clo4Y))
{
Glft = 10;
Hlft = Abs((Link->X - (this_ffc->X-16)) + (Link->Y - this_ffc->Y));
}

if (is_walkable(this_ffc->X+16, this_ffc->Y, clo1X, clo1Y, clo2X, clo2Y, clo3X, clo3Y, clo4X, clo4Y))
{
Grht = 10;
Hrht = Abs((Link->X - (this_ffc->X+16)) + (Link->Y - this_ffc->Y));
}
//increment close list pointer
if (cls_ptr == 4) { cls_ptr = 1; } else { cls_ptr += 1; }


//test for any EQUAL H scores
if (Gtop > 0 && Htop == Hbot || Gtop > 0 && Htop == Hlft || Gtop > 0 && Htop == Hrht) { Gtop += Rand(10); }
if (Glft > 0 && Hlft == Hbot || Glft > 0 && Hlft == Htop || Glft > 0 && Hlft == Hrht) { Glft += Rand(10); }
if (Gbot > 0 && Hbot == Htop || Gbot > 0 && Hbot == Hlft || Gbot > 0 && Hbot == Hrht) { Gbot += Rand(10); }
if (Grht > 0 && Hrht == Hbot || Grht > 0 && Hrht == Hlft || Grht > 0 && Hrht == Htop) { Grht += Rand(10); }
//Calculate F scores for each direction
if (Gtop > 0) { Ftop = Gtop + Htop; }
if (Gbot > 0) { Fbot = Gbot + Hbot; }
if (Glft > 0) { Flft = Glft + Hlft; }
if (Grht > 0) { Frht = Grht + Hrht; }

//test for LOWEST F score
if (Ftop <= Fbot && Ftop <= Flft && Ftop <= Frht) { best_dir = 1; }
if (Flft <= Ftop && Flft <= Fbot && Flft <= Frht) { best_dir = 2; }
if (Fbot <= Ftop && Fbot <= Flft && Fbot <= Frht) { best_dir = 3; }
if (Frht <= Fbot && Frht <= Flft && Frht <= Ftop) { best_dir = 4; }


//routine to move FFC in chosen direction

if (best_dir==1)
{
for (int n=0 ; n<16 ; n+=2)
{
this_ffc->Y-=2;
Waitframe();
}
}
if (best_dir==2)
{
for (int n=0 ; n<16 ; n+=2)
{
this_ffc->X-=2;
Waitframe();
}
}
if (best_dir==3)
{
for (int n=0 ; n<16 ; n+=2)
{
this_ffc->Y+=2;
Waitframe();
}
}
if (best_dir==4)
{
for (int n=0 ; n<16 ; n+=2)
{
this_ffc->X+=2;
Waitframe();
}
}


Waitframe();
}//ends while true


}//ends void run
bool is_walkable(int x, int y , int cls1X, int cls1Y, int cls2X, int cls2Y, int cls3X, int cls3Y, int cls4X, int cls4Y)
{
if(x<0 || x>240 || y<0 || y>160)
{
return false;
}
if (x == cls1X && y == cls1Y || x == cls2X && y == cls2Y || x == cls3X && y == cls3Y || x == cls4X && y == cls4Y)
{
return false;
}
return Screen->ComboS[y+(x>>4)]==0;
}


}//ends pathfinding

EDIT: updated the script, works a bit better less random
once we can use arrays it will be able to be much better


UPDATE: I droped the A* elements (not really needed on such a small screen)
Simpler algorithem, as far as my testing goes it works flawless.
Although you may not want to use this update for damage combos that follow link (you will never escape!)



//Script to have a FFC find Link and follow him
ffc script pathfinding{
void run()
{


while (true){
//declare vars which will be reset every loop
bool Wup = false;
bool Wdn = false;
bool Wlt = false;
bool Wrt = false;
int best_dir = 0;
int target_at = 0;
int horz = 0;
int vert = 0;
int hdist = 0;
int vdist = 0;

//check walkabilty on 4 sides

//up
if (is_walkable(this->X, this->Y-16)) { Wup = true; }
//down
if (is_walkable(this->X, this->Y+16)) { Wdn = true; }
//right
if (is_walkable(this->X-16, this->Y)) { Wrt = true; }
//left
if (is_walkable(this->X+16, this->Y)) { Wlt = true; }

//check hor and ver best direction
//vert 1=up ; 2=down
//horz 1=right ; 2=left

if (this->Y == Link->Y)
{ vert = 0; }
else
{
vdist = Abs(this->Y - Link->Y);
if (this->Y > Link->Y && Wup==true) { vert = 1; }
if (this->Y < Link->Y && Wdn==true) { vert = 2; }
}
if (this->X == Link->X)
{ horz = 0; }
else
{
hdist = Abs(this->X - Link->X);
if (this->X > Link->X && Wlt==true) { horz = 1; }
if (this->X < Link->X && Wrt==true) { horz = 2; }
}
if (hdist < vdist)
{
if (vert == 1) { best_dir = 1; } else { best_dir = 3; }
}
else
{
if (horz == 1) { best_dir = 2; } else { best_dir = 4; }
}

//test to see if target is found
//!!!!!NOT FULLY FUNCTIONING YET!!!!!
//int distance_to = Abs(((Link->X - this_ffc->X)+(Link->Y - this_ffc->Y))/2);
//if (distance_to <= 16) { target_at = 1; }

//routine to move FFC in chosen direction

if (best_dir==1) //up
{
for (int n=0 ; n<16 ; n+=2)
{
this->Y-=2;
//ani_update(1);
Waitframe();
}
}
if (best_dir==2) //left
{
for (int n=0 ; n<16 ; n+=2)
{
this->X-=2;
//ani_update(2);
Waitframe();
}
}
if (best_dir==3) //down
{
for (int n=0 ; n<16 ; n+=2)
{
this->Y+=2;
//ani_update(3);
Waitframe();
}
}
if (best_dir==4) //right
{
for (int n=0 ; n<16 ; n+=2)
{
this->X+=2;
//ani_update(4);
Waitframe();
}
}


Waitframe();
}//ends while true
}//ends void run
bool is_walkable(int x, int y)
{
if(x<0 || x>240 || y<0 || y>160)
{
return false;
}
return Screen->ComboS[y+(x>>4)]==0;
}
}//ends pathfinding



EDIT: well it seems now my walkable check is not working right.. :(
hopefully i'll fix it soon


Next step, a full Ally script... :)

[DarkDragon]

Cool.

Yeah, arrays will come eventually. I just need to fix enough bugs to release b18 first.

What is the "this_ffc->" bug? Those gymnastics shouldn't be necessary.

[Dan Furst]

Cool.

Yeah, arrays will come eventually. I just need to fix enough bugs to release b18 first.

What is the "this_ffc->" bug? Those gymnastics shouldn't be necessary.

http://www.armageddongames.net/forums/showthread.php?t=95526

[C-Dawg]

Bravo on a very cool script, by the way. I'll check it out. I'm very happy with all of the cool new scripters coming out of the woodwork!

[ShadowMancer]

Yes that post is exactly where i got the workaround, is it still needed?

Thankyou to DarkDragon, Dan Furst and C-Dawg you all helped write this script ethier by answering my questions or writeing great scripts yourself which i used code from. I've got more ideas in the works, i've been waiting for Zscript for a long time (since 1.83 i think :) )