Jump to content
  • Advertisement
Sign in to follow this  
milan_b

Line of Sight Problem

This topic is 3003 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm making a graphical roguelike game in Python and I have a problem trying to get the player to not be able to see past obstructions.

Here is the section of code that I'm trying to do it with:


removeList = []
# Find the tiles that shouldn't be in view and add to remList
for t in blocktiles:
for tile in self.view:
# 90 Degree angle
if t.rect.x == self.rect.x:
if tile.rect.y < t.rect.y:
if not tile in removeList:
removeList.append(tile)
continue
# 0 < angle < 90 degrees
if tile.rect.y < t.rect.y and ((t.rect.y - self.rect.y)/(t.rect.x - self.rect.x))*
(tile.rect.x - self.rect.x)-(((t.rect.y - self.rect.y)/(t.rect.x - self.rect.x))*(tile.rect.x - self.rect.x)) % 32 == tile.rect.y - self.rect.y:
if not tile in removeList:
removeList.append(tile)
# Does the actual removing
for tile in removeList:
self.view.remove(tile)







blockTiles is a subset of view btw.

The logic behind it was that the player and the obstruction create a line joining them and the line that is behind the block goes out of view.

So I figure when the player is facing UP:
for all y(tiles) > yb(blocktile):
(blocktile.y - player.y)/(blocktile.x - player.x) * (anytiles.x - player.x) == anytiles.y - player.y

[Edited by - milan_b on July 1, 2010 5:15:50 PM]

Share this post


Link to post
Share on other sites
Advertisement
Firstly, the problem you are describing is called 'Field of View' (FOV) or 'Line of Sight' (LoS). You should change the name of your post title so that you can increase the likelihood of you receiving helpful responses.

FOV and LoS algorithms are widely used. There are many open source implementations in a variety of languages. Of course, they are quite popular in roguelike games.

Secondly, you should describe the method/algorithm that you are using now. Is it something that you came up with, or is it your implementation of a preexisting algorithm?

Thirdly, my monitor is 1920x1080 and I cannot fit your post on the screen; perhaps you could break it up so as to not distort the viewing screen. This will also encourage more helpful responses.

And lastly, have you checked out Rogue Basin, specifically their Development Articles?

They have a Field of Vision Article that is quite helpful.

I have implemented this algorithm in C++ and C#. It was easy to implement and reasonably fast. It may not be as flashy as some of the others, but it is simple and looks decent. Perhaps you can give this a spin. I think it is decent.

So I'd recommend trying a preexisting algorithm. Why reinvent the wheel?

Share this post


Link to post
Share on other sites
Alright, I can't seem to understand how this works to implement it correctly.

I added comments to show where/how I can't follow it.


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;
// distance between player and position being tested
l=sqrt((vx*vx)+(vy*vy));
// cos and sin of angle made by horizontal line and line from player to position?
vx/=l;
vy/=l;
for(i=0;i<(int)l;i++)
{
// not sure why these were added .5 to in the first place
if(MAP[(int)ox][(int)oy]==BLOCK)
return false;
// not really getting what ox and oy do, they seem to go past the testing position
ox+=vx;
oy+=vy;
};
return true;
};



Share this post


Link to post
Share on other sites
Quote:
Original post by milan_b
Alright, I'm going to try to understand your algorithm and implement it, thanks very much

To clarify, I am not the author of this algorithm I just used it before in some of my own projects. Also, I'd recommend implementing the simplest algorithm first (I think it works decently) which is the second on the page I linked.

So here's the explanation: See the code comments for explanation. For simplicity assume you have a level described by Map[xCo][yCo]. Let's say it is a 10x10 grid. Your game loop would look something like:

while( running )
{
player.update()
gameLogic.update()
game.draw()
}



So you want to implement FOV/LoS. You then modify the game loop to

while( running )
{
player.update()
gameLogic.update()
FOV() // calculate visible Map[][] tiles
game.draw() // the draw function will only draw
// visible tiles.
}



Where FOV() is:

void FOV()
{
float x,y;
int i;

// Write not visible values to Map[][] Array.
CLEAR_MAP_TO_NOT_VISIBLE();//Initially set all tiles to not visible.
for(i=0;i<360;i++) // check 0 to 360 degrees around player.
{
x=cos((float)i*0.01745f); // x-vector projection for ith degree
y=sin((float)i*0.01745f); // y-vector projection for ith degree
// The 0.01745f converts from degrees to radians.
DoFov(x,y); // now calculated FOV for ith degree.
}
}


And DoFov(float x,float y) calculates the tiles that are visible for the ith angle, with x and y being the x/y - projections given by the ith angle.

void DoFov(float x,float y)
{
int i; // this is now variable for keeping track of distance from
// from origin (player's position).

float ox,oy; // seems like offsetX and offsetY would be
// better variable names here.
// they are the offset from the player's position.
// for the current angle under scrutiny.

// Init ox and oy values to center on the player's current tile.
ox = (float)PLAYERX+0.5f;
oy = (float)PLAYERY+0.5f;

// now using the current angle under scrutiny,
// traverse outward toward the extent of the player's
// maximum FOV radius.
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; // increment by the ith angle's projection on x-axis.
oy+=y; // increment by the ith angle's projection on y-axis.
// this will look to the next tiles traversing the ray that
// travels the ith angle from player's position to FOV radius.

// this loop continues until you hit a BLOCK
// the loop ends on a BLOCK since the player cannot
// see past the BLOCK.
}
}

Share this post


Link to post
Share on other sites
No problem.

I forgot to say that the lines:


ox = (float)PLAYERX+0.5f;
oy = (float)PLAYERY+0.5f;


Are the offset from the player's tile tracing the ray given by the i'th angle. This would be in map space. If your graphical tiles are say 32x32 pixels, let's say, then you'd still use 0.5f to center on the current Map[][] tile. You may be tempted to center by 16.0f (32pixels/2), but that is in graphical space, not map space.

You prolly knew that, but I just wanted to make it clear since I do not know how exactly your system is set up.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!