I am fairly proficient in c++ and I am working on a project in college. I am creating a roguelike from scratch without using external libraries other than SDL. I am working on implementing field of view for the player. I have looked a several different kinds of algorithms to use but they are either in a different language or I am unable to follow what is going on. Could someone please explain how any kind of FOV algorithm works. It just needs to be simple. Ive tried using Bresenham's line algorithm but i couldnt get it to detect when something was blocking the line.


void cMap::calculateLOSBresenham(int x0, int y0, int x1, int y1)
{
int x = 0, y = 0;

int delta_x = x1 - x0;
int delta_y = y1 - y0; // slope defined

int steps = max( abs(delta_x), abs(delta_y));
double c = 1.0 / max(1, steps);

for(int i = 0; i <= steps; i++) {
x = int(x0 + (i * delta_x * c) + 0.5);
y = int(y0 + (i * delta_y * c) + 0.5);
// should detect it in here but i couldnt get it to work.
}
}


If anyone could please help me, I would appreciate it.

thanks,
Manderin87

Hmm..it looks like that algorithm will only do lines that descend to the right. here is the wiki for that. It has examples for different situations. http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

Hmm..it looks like that algorithm will only do lines that descend to the right. here is the wiki for that. It has examples for different situations. http://en.wikipedia...._line_algorithm

I managed to get an algorithm to work, however it makes all walls visible within the radius, I just want it to make the first wall visible and hide the ones after. Anyone can help me fix it?


void cMap::los(int x0, int y0, int radius)
{ //Does line of sight from any particular tile

for(int x = 0; x < m_Height; x++) {
for(int y = 0; y < m_Width; y++) {
getTile(x,y)->setVisible(false);
}
}



double xdif = 0;
double ydif = 0;
int check = 1;
float dist = 0;

for (int x = MAX(x0-radius,0); x < x0+radius; x++) { //Loops through x values within view radius
for (int y = MAX(y0-radius,0); y < y0+radius; y++) { //Loops through y values within view radius

xdif = pow( (double) x-x0,2);
ydif = pow( (double) y-y0,2);

dist = (float) sqrt(xdif+ydif); //Gets the distance between the two points

if (dist <= radius) { //If the tile is within view distance,
check = line(x0,y0,x,y); //check if it can be seen.

if (check == 1) { //If it can be seen,
getTile(x,y)->setVisible(true); //Mark that tile as viewable
}
}
}
}
}



int cMap::line(int x0,int y0,int x1,int y1)
{

bool steep = abs(y1-y0) > abs(x1-x0);

if ( steep ){
std::swap(x0, y0);
std::swap(x1, y1);
}
if (x0 > x1){
std::swap(x0,x1);
std::swap(y0,y1);
}

int deltax = x1-x0;
int deltay = abs(y1-y0);
int error = deltax/2;
int ystep;
int y = y0;

if (y0 < y1)
ystep=1;
else
ystep=-1;

for (int x = x0; x < x1; x++) {

if ( steep && getTile(y,x)->getType() == TILE_DUNGEON_WALL) {
getTile(y,x)->setVisible(true);
return 0;
} else if (!steep && getTile(x,y)->getType() == TILE_DUNGEON_WALL) {
getTile(x,y)->setVisible(true);
return 0;
}

error -= deltay;

if (error < 0){
y = y+ystep;
error = error+deltax;
}

}
return 1;


}