A more difficult algorithm: Line of sight and ballistic range.

[Calin Leafshade]

I have another, more difficult algorithm to implement and I dont quite understand it.

Ok so imagine this fellow here:



He is an archer stood high up. So he should be able to fire his arrows further than someone at ground level.

now look at this fellow:



He has a big block of terrain in front of him which should block his line of sight.

Now how do i calculate where this guy can aim and also *how far* his shot will go in any particular direction.

I found this article on LOS but i dont really understand it much:

http://www-cs-students.stanford.edu/~amitp/Articles/LineOfSight.html

Help would be appreciated. I'll give you credit on ma gamez! (but only if SquareEnix dont want to work with me)

[abstauber]

First of all: wow!  :o

I'm sorry that I can't offer much help, as this is way out of my league. But I can offer some more stuff to read:
http://roguebasin.roguelikedevelopment.org/index.php?title=Articles#AI

At least those guys made me understand A* and they have a few article about LOS and FOV.

*pressing thumbs that those screenies make it to a final game*

[Calin Leafshade]

Thanks for the link.

If i use this (http://roguebasin.roguelikedevelopment.org/index.php?title=Eligloscode) algorithm and just ignore the higher = more distance thing then It should be fairly easy.

EDIT: Ok here's what i have:



if the circled guy is shooting then the crossed tiles should not be visible to him if a straight line is used. Heres my algorithm:

Code: ags

void DoFov(Point2D *pos, float x,float y,  int radius)
{
  int i;
  float ox,oy;
  ox = IntToFloat(pos.X)+0.5;
  oy = IntToFloat(pos.Y)+0.5;
  while (i < radius){
    int index = tileIndex(FloatToInt(ox, eRoundNearest), FloatToInt(oy, eRoundNearest));
    if (!SaneIndex(index)) return;
    if(tiles[index].Height - tiles[tileIndex(pos.X, pos.Y)].Height > 1)return;
    tileMask[tileIndex(FloatToInt(ox, eRoundNearest), FloatToInt(oy, eRoundNearest))] = 1;//Set the tile to visible.
    ox+=x;
    oy+=y;
    i++;
  }
}

void SetFOV(Point2D *pos, int radius)
{
  float x,y;
  int i;
  ClearTileMask();
  while (i < 360){
    x = Maths.Cos(IntToFloat(i) * 0.01745);
    y = Maths.Sin(IntToFloat(i) * 0.01745);
    DoFov(pos, x, y, radius);
    i+=1;
  }
}

[Kweepa]

If you're going to fire the arrow at the same angle every time then you can (pre?)compute the path that the arrow will take and then check it against the map heights for the squares it goes through.

Is the idea to decide whether an arrow can reach a particular target?
Or a particular square?
Or to draw the range of the arrow in all directions?
Can you fire anywhere?

There are lots of different problems...

[EDIT] This http://www.youtube.com/watch?v=mpkTHyfr0pM is a fascinating series of videos about mechanical ballistics computers.

[Calin Leafshade]

The purpose of the function is to determine which squares an archer at position P with a shooting radius R can shoot at taking into account the heights of the various tiles which may get in the way.

Each tile on the map has a height value where 0 is ground level, 1 is 1 step up and 2 is 2 steps up. Any tile which cannot be shot through from any height (the pillars for instance) has a height value of 100.

I assumed a perfect linear trajectory to make things simpler.

In the diagram given the red tiles show the algorithms current output, i.e. which tiles can be reached with an arrow shot by the circled character.

[Kweepa]

Oh, I see.
I presume the arrow goes from the center of your square to the center of the target square
You should
- run over the potentially hittable squares (loop over x and y, and check if the target is within radius)
- using a Ray Cast algorithm, check each square that is touched by the line between the centers - this is a little different to a Bresenham routine since you want to visit every touched square
- as you change square, determine the height of the arrow at that point using  h0 + (d/D)*(h1-h0) and make sure it's higher than the new square
- if you reach the target square, mark it as visible

[Khris]

A few thoughts:

I checked Final Fantasy Tactics on the GameboyAdvance too see how they handled bows and it seems that shooting from somewhere higher didn't affect the range but the accuracy and thus hit percentage.

To calculate whether a tile blocks the arrow's path you can neglect the top; only the walls are important.
(A path that would hit the top of the tile but no wall is much too steep to occur.)
To calculate whether a wall blocks the arrow's path you can use a simple line vs. line intersection (actually two).

The easiest way to go about this is to express both lines in the form: s + k*d where s is the starting point and d the directional vector.
If the player is standing on tile 2;3, shooting at tile 5;4, the arrow's line is (1.5;2.5) + k*(3;1).
The first potential blocking wall is the left wall of tile 3;3: (2;2) + l*(0;1)

Here's line vs. line:

Code: ags

void LineIntersectsLine(float x1, float y1, float xs1, float ys1, float x2, float y2, float xs2, float ys2) {
  
  float denom = ys1*xs2 - xs1*ys2;

  if (denom == 0.0) {
    results = 0;
    return;
  }
  
  results = 1;
  resultf[0] = (ys2*(x1-x2) - xs2*(y1-y2))/denom; // factor for movement
  resultf[1] = (ys1*(x2-x1) - xs1*(y2-y1))/(-denom); // line factor
}

If the resulting k and l are both inside [0;1] then the lines intersect.
If the calculation does reveal a collision, check the wall height. Since we know the fraction of arrow path to the wall (k), we can simply insert this into a sideview equasion. The wall is vertical (in terms of x and y of the top view), so now it's (1.5;h) + k*(3;dh). k is known so collison_h = h + k*dh (Kweepa's equasion). All that's left to do is check collision_h against tile_height.

[Kweepa]

Here's an explanation of Ray Casting:
http://www.permadi.com/tutorial/raycast/rayc7.html

[EDIT] And here's an implementation (now tested and fixed!)

// new module script

struct Tile
{
  int Height;
  int Visible;
};

Tile tiles[1024];

function raycast(int sx, int sy, int sh, int tx, int ty, int th)
{
  int x = sx;
  int y = sy;

  int dx = tx - sx;
  int dy = ty - sy;

  float cdx = 10000.0;
  float cdy = 10000.0;
  if (dy != 0)
  {
    // change in x for a y step of 1
    cdx = IntToFloat(dx)/IntToFloat(dy);
    if (cdx < 0.0) cdx = -cdx;
  }
  if (dx != 0)
  {
    // change in y for an x step of 1
    cdy = IntToFloat(dy)/IntToFloat(dx);
    if (cdy < 0.0) cdy = -cdy;
  }
  
  float D = Maths.Sqrt(IntToFloat(dx*dx + dy*dy));
 
  // distance travelled
  float fx = 0.0;
  float fy = 0.0;

  // initial steps to get from the center of the tile to lines
  float hdx = 0.5*cdx;
  float hdy = 0.5;
  float vdx = 0.5;
  float vdy = 0.5*cdy;
  
  int xstep = 1, ystep = 1;
  if (dx < 0) xstep = -1;
  if (dy < 0) ystep = -1;

  bool done = false;
  while (!done)
  {
    // decide whether to use the h(orizontal) or v(ertical) step
    if (hdx < vdx)
    {
      // hit a horizontal line
      fx += hdx;
      fy += hdy;
      
      vdx -= hdx;
      vdy -= hdy;
      
      hdx = cdx;
      hdy = 1.0;
      
      y += ystep;
    }
    else
    {
      // hit a vertical line
      fx += vdx;
      fy += vdy;
      
      hdx -= vdx;
      hdy -= vdy;
      
      vdx = 1.0;
      vdy = cdy;
      
      x += xstep;
    }
    // calculate the distance
    float d = Maths.Sqrt(fx*fx + fy*fy);
    float h = IntToFloat(sh) + (d/D)*IntToFloat(th - sh);
    if (FloatToInt(h) < tiles[32*y + x].Height)
    {
      done = true;
    }
    else if (x == tx && y == ty)
    {
      // we're done
      // mark the target square as visible
      tiles[32*y + x].Visible = true;
      done = true;
    }
  }
}

[Calin Leafshade]

Ok so the raycast function works on a single tile (t) and determines if its visible from the source tile (s)?

so

Code: ags

    if (FloatToInt(h) < tiles[32*y + x].Height)
    {
      done = true; // This branch is if tile t is *NOT* visible?
    }
    else if (x == tx && y == ty)
    {
      // we're done
      // mark the target square as visible
      tiles[32*y + x].Visible = true; // and this is if tile t *IS* visible?
      done = true;
    }

correct?

And i can just replace those branches with return true or return false?

[Kweepa]

That's right.

[Calin Leafshade]

Divide By Zero at:

Code: ags

float h = IntToFloat(sh) + (d/D)*IntToFloat(th - sh);

Edit: Nevermind, Tried to calc the value for the shooters tile thus dy && dx = 0

Edit Again:

Ok well that seems to work but I think I might have to add some kind of fudge factor since It calcs the LOS essentially from the shooters feet I think. So for instance:



The circled shooter should really be able to hit the crossed square.

[Kweepa]

That's why I have you pass in sh and th.

[Calin Leafshade]

Yus, I just added 1 to the source height to simulate arm height.. Works nicely now. Thanks kweeeps