Wall checking between two points

[coreys]

I was wondering if there was an easy and/or non-lag-intensive way to check if there's a wall in between two points. I'm working on a baddy script, and when in the "searching" or "chasing" mode I want it to check if there's a wall between two points (the baddy's x/y and a players x/y). This would be happening every .1 seconds when in those modes, so yeah not being laggy would be a pretty important thing. Anyone know?

[DustyPorViva]

Well, there's no function for it(see my suggestion thread about onwall3), but the only way to do it is to do something like I did for my lighting script...

PHP Code:

accuracy=.25;
onwall=0;
while (i<dist/accuracy) {
  onwall=onwall(x+dx*i,y+dx*i);
  if (onwall==1) break;
  i+=accuracy;
} 


This isn't going to be too] tax-worthy on CPU, but a lot of baddies doing it might slow it down... but there's no other way.

[Googi]

The best way to do it would probably be to have the baddy already know the x and y of each wall tile in the area, and have precomputed paths to get around them, but that can be a pain for the scripters (though you could have a one-time function to compute and store the information). There's also Kaimetsu's checkpath function (would need to be adapted, it's for determining where a projectile would stop).

PHP Code:

function CheckPath() {
 tx = int(arg[0]); ty = int(arg[1]);

 stepx = 1 / vx; stepy = 1 / vy;

 if (stepx < 0) {dirx = -1; stepx = -stepx; }
 else dirx = 1;
 if (stepy < 0) {diry = -1; stepy = -stepy; }
 else diry = 1;

 tempx = arg[0] - tx; if (dirx == -1) tempx = 1-tempx;
 tempy = arg[1] - ty; if (diry == -1) tempy = 1-tempy;
 bankx = stepx * (1-tempx);
 banky = stepy * (1-tempy);

 dist = 0;

 while(true) {
  if (bankx < banky) {dist += bankx; temp = 0;}
  else {dist += banky; temp = 1;}
  if (dist > mag) break;
  if (temp == 0) {
   banky -= bankx; bankx = stepx;
   tx+=dirx;
  }
  else {
   bankx -= banky; banky = stepy;
   ty+=diry;
  }

  if (tx < 0 || tx > 63 || ty < 0 || ty > 63) break;
  if (onwall(tx, ty)) {
   tx = arg[0] + vx * dist;
   ty = arg[1] + vy * dist;
   if(temp == 0) {tempx = dirx; tempy = 0;}
   else {tempx = 0; tempy = diry;}
   r = {tx, ty, tempx, tempy}; r = 0;
   return;
  }
 }
 r = -1;
} 


[Crow]

Since when do you script Googi?O.o

[xXziroXx]

Since before you were born son.

[Crow]

I guess I missed a pretty large part of Graal's history here. Btw, Graal didnt even exist when I was born ;o

[Kyranki]

Erm,

PHP Code:

....
if (onwall(obj.x + temp.gotox, obj.y + temp.gotoy)) {
.... 


[DustyPorViva]

He wants to check between those two points, the destination.

[Kyranki]

Ahhhh,

[coreys]

Originally Posted by DustyPorViva

Well, there's no function for it(see my suggestion thread about onwall3), but the only way to do it is to do something like I did for my lighting script...

PHP Code:

accuracy=.25;
onwall=0;
while (i<dist/accuracy) {
  onwall=onwall(x+dx*i,y+dx*i);
  if (onwall==1) break;
  i+=accuracy;
} 


This isn't going to be too] tax-worthy on CPU, but a lot of baddies doing it might slow it down... but there's no other way.

Didn't work.

[DustyPorViva]

EDIT: here's a fixed version, my mistake!

PHP Code:

function onTimeout() {
  temp.delta={playerx-x,playery-y,(temp.delta[0]^2+temp.delta[1]^2)^.5}; // get the delta's and distance
  temp.onwall=i=0; // reset i and onwall check
  while (i<temp.delta[0]) { // while i is less than the distance between player and NPC
    temp.onwall=onwall(x+(temp.delta[0]/temp.delta[2])*i,y+(temp.delta[1]/temp.delta[2])*i);
    if (temp.onwall==1) break;
    i++;
  }

  setTimer(0.05);
} 


Key mistakes I fixed were resetting i before the loop, or else it'd grow beyond the actual distance! And also fixed the wall check, I was multiplaying i*dx/dy, and that 'cause it to check way farther than needed. You needed to divide the dx/dy by the distance, then multiply by i. This one however doesn't have a check for accuracy, though that would be easy enough to figure out(i+=accuracy )

[coreys]

I edited to this:

PHP Code:

function checkPath(ox, dx, oy, dy) {
  temp.delta = {dx - ox, dy - oy, (temp.delta[0]^2+temp.delta[1]^2)^.5}; // get the delta's and distance
  i = 0;
  temp.onwall = false;
  while (i < temp.delta[0]) { // while i is less than the distance between player and NPC
    temp.onwall = onwall2(ox+(temp.delta[0]/temp.delta[2])*i,oy+(temp.delta[1]/temp.delta[2])*i, 1, 1);
    if (temp.onwall) break;
    i++;
  }
  return temp.onwall;
} 


And it's still not working. =o

[xXziroXx]

You cant break a 'while' dumbnuts!

PHP Code:

while (this.foo == false) {
  player.chat = "I've failed" SPC temp.bar SPC "times!";
  temp.bar ++;
  if (temp.bar == 10) {
    player.chat = "I didnt fail, yay!";
    temp.foo = true;  // Automaticly breaks the 'while' since the reason its being run is now invalid.
  }
} 


[DustyPorViva]

Err, why can't you? It's a loop, and I just tested it and it works fine...
EDIT: My mistake while converting it to GS2...
change:
while (i < temp.delta[0]) {
to:
while (i < temp.delta[2]) {

[coreys]

Okay, well I have this now:

PHP Code:

function checkPath(ox, dx, oy, dy) {
  temp.delta = {dx - ox, dy - oy, (temp.delta[0]^2+temp.delta[1]^2)^.5};
  i = 0;
  temp.onwall = false;
  while (i < temp.delta[2]) {
    this.chat = onwall2(ox+(temp.delta[0]/temp.delta[2])*i,oy+(temp.delta[1]/temp.delta[2])*i, 1, 1);
    if (onwall2(ox+(temp.delta[0]/temp.delta[2])*i,oy+(temp.delta[1]/temp.delta[2])*i, 1, 1)) {
      temp.onwall = true;
      i = temp.delta[0];
    }
    else i++;
  }
  return temp.onwall;
} 


aaaand, nothin...isn't even setting this.chat o.0

[xXziroXx]

try changing 'i' to something else, another script is most likely interfering.

[DustyPorViva]

It's not that. This is what I get for posting a script I haven't tested... it had to do with the array I was using, apparently you can't grab values from the same array you're setting. Used to be able to.
Here:

PHP Code:

function checkPath(ox, dx, oy, dy) {
  temp.dx=dx - ox;
  temp.dy=dy - oy;
  temp.delta=((temp.dx^2)+(temp.dy^2))^.5;
  i = 0;
  temp.onwall = false;
  while (i < temp.delta) {
    temp.onwall=onwall2(ox+(temp.dx/temp.delta)*i,oy+(temp.dy/temp.delta)*i,1,1);
    if (temp.onwall) break;
    i++;
  }
  return temp.onwall;
} 


[coreys]

Works, but damn it looks like for him to stop suddenly when you're like slightly, slightly behind a wall. xD
I could script it to find ways around walls but it would be super laggy, most likely.

[Googi]

Originally Posted by Crow

Since when do you script Googi?O.o

I used to but I stopped a long time ago.

The method you guys are using can return false negatives in a situation like this:



Even though the line that's being checked crosses over two wall tiles, there's a good chance of both being "missed" because not enough points along the line are checked.

There's also potential problems with gaps in the wall that are too small for the baddy to fit through, but that's more of a problem of the script's scope rather than it not correctly doing what it's suppose to do (check if a line intersects with a wall).

[DustyPorViva]

There's no real way to avoid that other than upping the check. Actually, his script is using onwall2, and checking a whole tile rather than a single pixel, so that's a good step in avoiding that problem. I believe this is the simplest way to do this other than doing a lot of of CPU hogging loops.
As for going around walls, I've done something similar, which I posted in the code gallery if you want to check it out. Instead of doing pathfinding like A*, it simple logged the players movements and 'followed' them. It was kind of cheating, but it worked, if you want to get ideas from it.

[Googi]

Originally Posted by DustyPorViva

There's no real way to avoid that other than upping the check. Actually, his script is using onwall2, and checking a whole tile rather than a single pixel, so that's a good step in avoiding that problem.

Thinking about it further, that problem wouldn't actually happen except under very rare circumstances, and can be eliminated entirely by increasing size of the area checked to 1.1,1.1. A greater problem would be the potential for the script to break down when the player is right up against a wall (shouldn't be a problem with 1,1, but would be with 1.1,1.1) or worse, "half" on a wall, as I'm sure you know is entirely possible (and would cause a breakdown even with 1,1).

[DustyPorViva]

Well that can be fixed by upping the check, for example:

PHP Code:

while (i<dist/.5) {
  onwall2(x+(dx/(dist/.5))*i,x+(dx/(dist/.5))*i),1,1);
  i+=.5;
} 


But that only increases the loop substantially. A simple fix would be to do a seperate check BEFORE doing the check between the two points, that involves checking for a wall in the direction of the player, but only half a tile away. If there is no wall, carry on with checking between them.

[coreys]

Well the way my baddy class works, a player getting up next to a wall, or even half on one, isn't a problem.

But now I'm having trouble with the pathcheck...in some cases it thinks theres a wall in between us, when there isn't...O.o

[Googi]

Originally Posted by coreys

Well the way my baddy class works, a player getting up next to a wall, or even half on one, isn't a problem.

It would cause the script to return what would more or less be false positives.

Originally Posted by coreys

But now I'm having trouble with the pathcheck...in some cases it thinks theres a wall in between us, when there isn't...O.o

Perhaps the line it's checking partially intersects a wall? Try having it put something (putnpc, showimg, even putbomb) at each point it checks along the line.

Regarding pathfinding and CPU usage, I don't know much about the limitations Graal servers have to work under, but Yen has claimed that pathfinding is impossible to do for every baddy without crashing the server.

If I were going to try to make a pathfinding script, I'd have it have two "levels". Macro and micro. First I'd divide each level into sectors (like in the attachment) and have the baddy first determine which sector the player is in. Each baddy would have a preprogrammed path to each sector within its level and it would follow its preprogrammed path (while checking if the player changes sectors and adjusting its path accordingly by determining the best route to get to the preprogrammed path to the new sector). Once it got to the same sector as the player then it would go into "micro" mode and do normal shortest-distance-to-the-player pathfinding. There's minor problems like the player changing sectors while the baddy is in micro mode, but they wouldn't be too hard to solve. The biggest problem would be that it's hard on the scripters as unique preprogrammed paths would have to be created for every single baddy.

[DustyPorViva]

Kaimetsu had a good theory on pathfinding. Instead of actually calculating tiles, he said that it would be easier to predefine nodes in levels, and have the NPC 'pathfind' through the nodes instead of the tiles. This means you'd be able to up the accuracy in tight spots by placing more nodes, and get lax in large spaces by only placing a couple nodes. I'd honestly put aside pathfinding though, it's way too much for something so simple.

I made a baddy, that instead of going in the direction of the player, moved left or right/up or down, depending on the player's position. This meant that instead of running straight into a wall and stopping, he'd run into the wall, but if the player was still lower than him keep running down and around the obstacle. Of course this wouldn't work in messy levels, and not too effective if the player is still right in front of the baddy, but it was better than the average running towards the player script.

[Inverness]

Predefining nodes is how its done in most 3D games. Its certainly a good option.

PHP Code:

//#CLIENTSIDE
function onCreated() {
  this.level.nodes = {
    {5, 13, 0},
    {20, 24, 0},
    {30, 30, 0},
  };
} 


It could be defined in that manner for compatibility with the vector functions.

Or probably a better idea for nodes is to store them all serverside in a database and have them sent to player on login or such. Also you could make some staff tool that highlights nodes in levels with lights and allows you to place new ones and such.

[coreys]

Damn that's a pain in the ass.

And no, it's having problems even when there IS no wall in between the player and the baddy. But only sometimes. o.0

[Twinny]

I set up nodes all over my gmaps while using dynamic a* to navigate between nodes. I figured that using a* for a whole gmap would quickly set fire to the NPC-Server .

[Googi]

Originally Posted by coreys

Damn that's a pain in the ass.

And no, it's having problems even when there IS no wall in between the player and the baddy. But only sometimes. o.0

Does it happen when there isn't a single wall tile in the entire level?

[coreys]

Originally Posted by Googi

Does it happen when there isn't a single wall tile in the entire level?

Well I hadn't tried that. I naturally kinda figured that it was just checking in the wrong places. And I can't do a showimg where it's checking since this is all serverside.

Edit:
Also, if I used putnpc2() I'd most likely crash the server.

Edit:
I made it so it would only use putnpc2() to show where it's checking the path ONCE, so it wouldn't crash the server. It's pretty off. o.o

[PrinceOfKenshin]

Originally Posted by Twinny

I set up nodes all over my gmaps while using dynamic a* to navigate between nodes. I figured that using a* for a whole gmap would quickly set fire to the NPC-Server .

hehe 10 points for Twinny <3

I hate scripting baddys they are a pain. I'm trying to work on some IRC for atrius and boy does my head hurt

[coreys]

This is what I have now.

PHP Code:

function checkPath(ox, dx, oy, dy) {
  temp.dx = (dx + 1.25) - (ox + 1.25);
  temp.dy = (dy + 1.25) - (oy + 1.25);
  temp.delta = getDist((ox + 1.25), (oy + 1.25), (dx + 1.25), (dy + 1.25));
  i = 0;
  temp.onwall = false;
  while (i < temp.delta) {
    this.chat = temp.onwall;
    //putnpc2((ox + 1.25) + ((temp.dx/temp.delta) * i), (oy + 1.25) + ((temp.dy/temp.delta) * i), "join(\"object_chair\");");
    if (onwall2((ox + 1.25) + ((temp.dx/temp.delta) * i), (oy + 1.25) + ((temp.dy/temp.delta) * i),.5,.5)) {
      temp.onwall = true;
      this.chat = temp.onwall;
      break;
    }
    i += .75;
  }
  return temp.onwall;
} 


It's always returning true, and it isn't always working correctly.

All the + 1.25 and all that is so that it's centered from the center of the baddy to the center of the player, so that it's not going from the left corner of the baddy to the left corner of the player.

[DustyPorViva]

You can't have i increasing by .75, it has to be by one unless you go through the trouble of increasing the loop and distance between each check(I described how to do that up there). I don't really see a reason to lower it below 1 though.

I've ran tests on the last script I posted and I'm not having any such problems with it, this is on a gmap as well.

Also, you might want to do the checks for finding the 'center' of the player/npc BEFORE the function, and send them through the parameters, instead of doing all that in the function.

[coreys]

Originally Posted by DustyPorViva

You can't have i increasing by .75, it has to be by one unless you go through the trouble of increasing the loop and distance between each check(I described how to do that up there). I don't really see a reason to lower it below 1 though.

I've ran tests on the last script I posted and I'm not having any such problems with it, this is on a gmap as well.

Also, you might want to do the checks for finding the 'center' of the player/npc BEFORE the function, and send them through the parameters, instead of doing all that in the function.

Well it seems like onwall2() is returning true when it shouldn't, sometimes...

[Googi]

Originally Posted by coreys

Well it seems like onwall2() is returning true when it shouldn't, sometimes...

Have you tried it in a level with no wall tiles yet?

[coreys]

Yes, just did, it's returning true o.0

[DustyPorViva]

No idea... maybe it's your server. The script I posted works fine, and it used onwall2...

[coreys]

I'm getting this sort of thing...(the red square represents where it's checking)
Also, in a completely blank level, sometimes the onwalls returns true sometimes false. It should ALWAYS return false. ._.

EDIT:
Actually it's returning true unless the player is to the npcs left, or below it. o.0
OH I SEE, it's a problem with negatives.

[bscharff]

Fairly Simple - Not Sure If It Would Work In Your Situation...
I've Only Read The First Page - Too Lazy
Of Course Add Timeout Etc Blah Blah:

PHP Code:


this.width = (this.x - player.x);
this.height = 2;

if (onwall2(this.x,this.y,this,width,this.height)){

}else{
this.mode = "idle"; //Whatever Your Go Into Idle Is
} 


[coreys]

Not nearly accurate enough.