Good ways to do LoS

[Vanguard]

What's your favorite way to do line of sight?

What do you think is the easiest way to do line of sight?

[PaulBlay]

What's your favorite way to do line of sight?

What do you think is the easiest way to do line of sight?

There's currently massive amounts of line of sight discussion going on in Angband.oook.cz and RogueBasin.

Or did you come from there?

[Vanguard]

No, I didn't, I'm just at the point where I need to implement that, but I have no idea how to actually go about doing it.  I'll take a look at those links though, thanks!

[rdc]

I personally just use a simple ray caster with a post processing step. Here is an example of the results. In the pic the zombies block line of sight (the gray areas are seen tiles) which make corridor fighting a bit more interesting imo. The advantage is that is is quite fast and I don't really see the need to use the more esoteric models.

[Ex]

Raycasting, while not the best option, is quick and easy to implement and it works. I either raycast in a 360 degree circle around the player, or I send a ray to every square within a certain radius. Not perfect or even very good, but it gets the job done and it's very simple to implement.

[Vanguard]

I was thinking that shadow casting looks like the most attractive option to me, from reading through Paul's links.  I'll let you guys know how it goes, but I'm still open to suggestions if I hear a good idea.

Edit:  This is harder than I thought it'd be.  I think I've got raycasting figured out though, so maybe I'll just do one of those for now, and if I want to change it later I can come back to it.

[ido]

I agree with the others, just do a naive raycasting and see if it's good enough.

You can implement one very easily, for example (from one of my older games, Y_ and X_ represent the size of the map):

Code: [Select]

//radial field of view
void fov(int y, int x, int radius) {
for (int yy=max(y-radius,0); yy<=min(y+radius,Y_-1); yy++)
for (int xx=max(x-radius,0); xx<=min(x+radius,X_-1); xx++)
if (in_range(y,x,yy,xx,radius) && los(y,x,yy,xx,WALL))
view[yy][xx]=IN_SIGHT;
}

Where los is a simple line-of-sight algorithm (mostly ripped straight off of wikipedia) that plots a line to that point and return true if it reached it without bumping into a wall (or another opaque tile):

Code: [Select]

//line of sight
bool los(int y0,int x0,int y1,int x1,chtype opaque) {
//Bresenham's line algorithm
//taken from: http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
bool steep=fabs(y1-y0)>fabs(x1-x0);
if (steep) {
swap(&x0,&y0);
swap(&x1,&y1);
}
if (x0>x1) {
swap(&x0,&x1);
swap(&y0,&y1);
}
float err_num=0.0;
int y=y0;
for (int x=x0; x<=x1; x++) {
if (x>x0 && x<x1) {
if (steep) {
if (opaque==map[x][y].type)
return false;
} else {
if (opaque==map[y][x].type)
return false;
}
}

err_num+=(float)(fabs(y1-y0))/(float)(x1-x0);
if (0.5<fabs(err_num)) {
y+=y1>y0?1:-1;
err_num--;
}
}
return true;
}

and in_range is the euclidean distance, used to create a nice circular shape:

Code: [Select]

bool in_range(int y0,int x0,int y1,int x1,int r) {
return dist(y0,x0,y1,x1)<=pow(r,2);
}


I used this basic code or variation-thereof in a couple of games, the first and easiest to understand is in the 7drl version of CryptRover from the 2008 7drl challange.

[Vanguard]

Alright, well thanks for your help guys!  I've got a raycaster up and running now.

Have some screens:

http://img38.imageshack.us/img38/7599/screen1hfu.png

http://img38.imageshack.us/img38/6303/screen2sts.png

http://img33.imageshack.us/img33/6909/screen3kgt.png

It's not perfect yet.  As you can see it's not being as generous as it should be with showing wall tiles, but I should be able to work that out.  Thanks again for your advice!

[ido]

Looks like you are stopping 1 step too early or beginning 1 step too late.

Maybe when checking if there is a obstacle in the line of sight omit checking the origin and destination tiles, and only check for the tiles in-between.

Also, that's a nice character - did you draw it yourself? If you invest the same amount of effort in all tiles/sprites I think you could have a very good looking game.

[Anvilfolk]

I'm guessing you could have a flag/option on each tile which defined whether the object occupies the whole square. If that was the case, you'd be able to see the wall if the ray hit one of the corners or sides. It could be set for big monsters, walls and the like.

[Vanguard]

Looks like you are stopping 1 step too early or beginning 1 step too late.

Maybe when checking if there is a obstacle in the line of sight omit checking the origin and destination tiles, and only check for the tiles in-between.

I think the reason is because right now the code that determines which direction the ray moves in to reach its target is too absolute.

It works by getting the slope of a line from the character in question to the tile being checked, and then as the ray moves towards the tile, it checks that against the current slope of a line from where it is to the destination tile.

If the it gets above the original line, it goes down, and if it's gotten to the left of it, it goes right until it reaches the end.  It's just not very flexible or forgiving with angles right now - it will only move diagonally if the destination tile is exactly diagonal from its current location, and with a nearly, but not quite horizontal line, it'll move horizontally at first, and then it'll be above/below the original slope, even if only by a tiny bit, and for that reason it will move vertically, and in tight corridors, this means it'll prematurely hit a wall.

I'll add a little bit of "breathing room" for the slope checks, so it doesn't do such dramatic movements for such negligible differences, and it should be okay after that.

Does that explanation make sense?

Also, that's a nice character - did you draw it yourself? If you invest the same amount of effort in all tiles/sprites I think you could have a very good looking game..

Hey, thanks!  I really appreciate you saying that!

I think having a unique tileset will help my game stand out in the crowd a little more.  Ascii will still be supported for those who prefer it.

I'm guessing you could have a flag/option on each tile which defined whether the object occupies the whole square. If that was the case, you'd be able to see the wall if the ray hit one of the corners or sides. It could be set for big monsters, walls and the like.

I'm not sure how I'd be able to do that for walls and other "inanimate visual obstructions, for the way I have everything set up, but it'd be really easy to do it for monsters.  I don't know if I actually want to do that or not, but I'm keeping the option open.

[Vanguard]

Hey, I'm back for some more advice.

I replaced my old method of comparing the current slope with the end slope to one that only uses the current slope of where the "scanner" is to where the destination tile is.  It's much simpler, and is working mostly better, but with one problem - it's being too permissive with what it shows, but only to targets that are mostly horizontal.  I'll add some screens to show what I mean:

http://img6.imageshack.us/img6/8611/badscreen.png

See, in this one it's expanding at a 45 degree angle at the end of the hallway.  That's just too much.

http://img6.imageshack.us/img6/1197/goodscreen.png

Here is how I want it.  It expands, but much more conservatively.


Here's the code I'm using for this, anyone who wants to use or modify this is free to do so.

    public void calculateFieldOfView() {
        initializeTileVisibility();
        for (int tileCounterY = 0; tileCounterY < Map.getStageSizeY(); tileCounterY++) {
            for (int tileCounterX = 0; tileCounterX < Map.getStageSizeX(); tileCounterX++) {
                // This will cut out unnecessary tiles to save processing time.
                if (tileCounterX < xLocation - lineOfSightRange) {
                    tileCounterX = xLocation - lineOfSightRange;
                }
                if (tileCounterY < yLocation - lineOfSightRange) {
                    tileCounterY = yLocation - lineOfSightRange;
                }
                if (tileCounterX > xLocation + lineOfSightRange) {
                    tileCounterX = Map.getStageSizeX();
                }
                if (tileCounterY > yLocation + lineOfSightRange) {
                    tileCounterY = Map.getStageSizeY();
                }
                if (Calculate.calculateLineOfSightDistance(xLocation, yLocation, tileCounterX, tileCounterY) <= lineOfSightRange) {
                    if (tileVisibility[tileCounterX][tileCounterY] == false) {
                        checkLineOfSightConnection(tileCounterX, tileCounterY);
                    }
                }
            }
        }
    }


    // This will check whether the character in question can see the location in question
    private void checkLineOfSightConnection(int xCoordinate, int yCoordinate) {
        Map currentLevel = Main.getCurrentLevel();
        int scanX = xLocation;
        int scanY = yLocation;
        boolean blocked = false;
        double currentSlope;

        tileVisibility[scanX][scanY] = true;
        if (this == Main.getPlayer()) {
            int tileType = currentLevel.getMapData(scanX, scanY);
            currentLevel.setMapMemoryData(scanX, scanY, tileType);
            tileLighting[scanX][scanY] = true;
        }

        // This will loop until the ray has reached its target, or is blocked by something;
        while (scanX != xCoordinate || scanY != yCoordinate) {
            // This is to ensure we don't get any divide by zero errors.  The slope is high enough that it'll work no matter what.
            if (scanX == xCoordinate) {
                currentSlope = 10000;
            } else {
                // We figure out what our current slope is, so we know how to reach our target.
                currentSlope = Math.abs(Calculate.getSlope(scanX, scanY, xCoordinate, yCoordinate));
            }
            // Now we use the slope to figure out how the scan coordinates should move.
            if (currentSlope <= 0.50) {
                if (scanX < xCoordinate) {
                    scanX += 1;
                }
                if (scanX > xCoordinate) {
                    scanX -= 1;
                }
            } else if (currentSlope >= 2.00) {
                if (scanY < yCoordinate) {
                    scanY += 1;
                }
                if (scanY > yCoordinate) {
                    scanY -= 1;
                }
            } else {
                if (scanX < xCoordinate) {
                    scanX += 1;
                }
                if (scanX > xCoordinate) {
                    scanX -= 1;
                }
                if (scanY < yCoordinate) {
                    scanY += 1;
                }
                if (scanY > yCoordinate) {
                    scanY -= 1;
                }
            }
            // If the ray hits something opaque, we set blocked to true so the ray stops.
            if (blocked == false) {
                tileVisibility[scanX][scanY] = true;
                if (this == Main.getPlayer()) {
                    int tileType = currentLevel.getMapData(scanX, scanY);
                    currentLevel.setMapMemoryData(scanX, scanY, tileType);
                    tileLighting[scanX][scanY] = true;
                }
            }
            if (currentLevel.checkOpacity(scanX, scanY) == true) {
                blocked = true;
            }
        }
    }


// This sets every tile to unseen to start the turn out.
    private void initializeTileVisibility() {
        for (int yCounter = 0; yCounter <
                Map.getStageSizeY(); yCounter++) {
            for (int xCounter = 0; xCounter <
                    Map.getStageSizeX(); xCounter++) {
                tileVisibility[xCounter][yCounter] = false;
            }
        }
    }


Can any of you spot what the cause of the problem I'm having is?  I can't figure it out.


Edit:  And a few explanations to help make this more clear maybe:

Calculate.getSlope returns the slope of the two coordinate pairs it's given.

Calculate.calculateLineOfSightDistance returns the distance between the two tiles.

xLocation and yLocation are the current character's coordinates.

tileLighting is a boolean array for whether the player character can currently see the tile's location.  It currently does nothing, but that'll change in the near future when I make it so tiles that are remembered but not seen are darkened/don't have characters drawn on them.

currentLevel.setMapMemoryData sets what the current tile on the current level is remembered as.  This is exclusively what is currently used for determining what to draw.

tileVisibility is whether the current character can see the current tile, regardless of whether they're a player character or not.  This is what will be used for ai characters' sight.

scanX and scanY are the locations of the scanner that moves from the character's location to the destination tile.

Does that explain everything well enough?

[Ex]

When doing a raycaster in a tiled enviornment, remember to always add 0.5 onto your coordinates so that you check LOS from the center of one tile to another, rather than from the upper left corner of one to the upper left corner of the other. Assuming you're using actual rays, instead of just a line algorithm like Bresenham.

[Vanguard]

When doing a raycaster in a tiled enviornment, remember to always add 0.5 onto your coordinates so that you check LOS from the center of one tile to another, rather than from the upper left corner of one to the upper left corner of the other. Assuming you're using actual rays, instead of just a line algorithm like Bresenham.

I'm not really familiar with this stuff, since this is the first time I've ever done anything with LOS, but I'm assuming that what I'm doing is the second one.  Adding 0.5 to my coordinates wouldn't do anything other than confuse and break the game.

Anyway, if my code I copy pasted above is readable (I hope it is, I tried my best to make it readable) then you can see what I did for yourself.

[Ex]

Note: I haven't checked the code below, this is just an example. It's roughly designed in the same way as the above code by Curseman.

Code: [Select]

void FOV()
{
  int i,j;
  float x,y,l;
  for(i=0;i<80;i++)for(j=0;j<25;j++)
  {
    MAP[i][j]= NOT_VISIBLE;//Pseudo code
    x=i-PLAYERX;
    y=j-PLAYERY;
    l=sqrt((x*x)+(y*y));
    if(l<VIEW_RADIUS)
      if(DoFov(i,j)==true)
        MAP[i][j] = VISIBLE;//Pseudo code, you understand.
  };
};

bool DoFov(int x,int y)
{
  float vx,vy,ox,oy,l;
  int i;
  vx = x-PLAYERX;
  vy = y-PLAYERY;
  ox = (float)x+0.5f;
  oy= (float)y+0.5f;
  l=sqrt((vx*vx)+(vy*vy));
  vx/=l;
  vy/=l;
  for(i=0;i<(int)l;i++)
    {
    if(MAP[(int)ox][(int)oy]==BLOCK)
      return false;
    ox+=vx;
    oy+=vy;
    };
  return true;
};

Edit; If this is a bit slow, try only casting rays in a 360 degree or less circle around the player. You can convert degrees to radians and then use sin and cos to figure out the unit vector to use, which can be precomputed. Then you can cast rays along each of the degrees marking squares as visible until you hit a block at which point the ray terminates. That is technically much closer to raycasting than the above example.

Raycasting:

Code: [Select]

void FOV()
{
  float x,y;
  int i;
  CLEAR_MAP_TO_NOT_VISIBLE();//Initially set all tiles to not visible.
  for(i=0;i<360;i++)
  {
    x=cos((float)i*0.01745f);
    y=sin((float)i*0.01745f);
    DoFov(x,y);
  };
};

void DoFov(float x,float y)
{
  int i;
  float ox,oy;
  ox = (float)PLAYERX+0.5f;
  oy = (float)PLAYERY+0.5f;
  for(i=0;i<VIEW_RADIUS;i++)
  {
    MAP[(int)ox][(int)oy]=VISIBLE;//Set the tile to visible.
    if(MAP[(int)ox][(int)oy]==BLOCK)
      return;
    ox+=x;
    oy+=y;
  };
};