Raycasts on a 2d map for determining vision.

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

Recommended Posts

So I'm making an RTS on a 2d isometric map. There is a 'fog of war' where units have line of sight and can reveal tiles around them. Making them simply reveal tiles in a box around their location is pretty easy, but I wanted a more realistic circular vision that can be obstructed by objects in the way.

I've already coded this, and the basic code is here:

    resetFog();

for(unsigned int i = 0; i<calcUnits->size(); i++)
{
unsigned int tx = calcUnits->at(i).tileX;
unsigned int ty = calcUnits->at(i).tileY;

tmpExplored[tx+(ty*size)] = true;
for(double vi = 0; vi<360; vi++)
{
double xDir = sin(vi);
double yDir = cos(vi);
for(unsigned int m = 0; m<calcUnits->at(i).type->sightDistance; m++)
{
double xPos = (xDir*m*15)+calcUnits->at(i).x;
double yPos = (yDir*m*15)+calcUnits->at(i).y;
point in(xPos,yPos);
point aq(calcMap->getTileFromPos(in).toArray());
if(aq.x > 0 && aq.x < size && aq.y > 0 && aq.y < size)
{
tmpExplored[(int)aq.x+(size*(int)aq.y)] = true;
if(calcMap->treeGrid[(int)aq.x+((int)aq.y*size)])
break;
}
else
break;
}
}
}

updateHalfExplored();



resetFog() resets the buffer and updateHalfExplored() basically flips the buffer to the main array. As you can see for each unit 360 raycasts are made and each one is checked up to 100 times along the way stopping if an obstacle is found. This means there's up to 36,000 checks per unit which is a ton of processing, and is also far more checks than there are tiles in any units line of sight.

Is there anyway I can do this more efficiently?

The end result can be seen here:

Edited by Syerjchep

Share on other sites
Loop over each fog of war tile in the unit's range and only perform the raycast for each tile. You can skip the raycast if the tile is already visible based in a previous unit's calculation significantly speeding up checking for large groups of units. You could then also decrease the fog of war resolution to improve performance.

Share on other sites

i woud recoommend to use fragment shader for that

Share on other sites

Loop over each fog of war tile in the unit's range and only perform the raycast for each tile. You can skip the raycast if the tile is already visible based in a previous unit's calculation significantly speeding up checking for large groups of units. You could then also decrease the fog of war resolution to improve performance.

This is pretty much what I ended up going with. I took the outer perimeter of the units view point and for each tile (80 tiles if the radius is 10 tiles) did a raycast with 15 iterations each from the unit to that tile. That's only 1,200 calculations where I had needed 36,000. This is good enough to have it run in the main thread without killing FPS.

If anyone's still reading this I got a second question. So I have this code here that determines which tile a specific coordinate is located in:


bool pointInTriangle(point s, point a, point b, point c)
{
//Find out if a point is in a particular triangle
//The first point is the point to check
//The other three are the three vertices of the triangle
int as_x = s.x-a.x;
int as_y = s.y-a.y;

bool s_ab = (b.x-a.x)*as_y-(b.y-a.y)*as_x > 0;

if(((c.x-a.x)*as_y-(c.y-a.y)*as_x > 0) == s_ab) return false;

if(((c.x-b.x)*(s.y-b.y)-(c.y-b.y)*(s.x-b.x) > 0) != s_ab) return false;

return true;
}

point terrainMap::getTileFromPos(point &miso)
{
point ret(-1,-1); //blank coordinate, to be returned -1,-1 if out of bounds

int tmpx = miso.x / 200; //From a non-isometric perspective the tiles are 200 wide and 100 long
int tmpy = miso.y / 100; //Though in an isometric perspective they're actually squares

if(miso.y < 0)
return ret;
if(miso.x < -2*miso.y) //Is it out of bounds?
return ret;
if(miso.x > 2*miso.y)  //Keep in mind the map itself is a diamond as well, in addition to the individual tiles
return ret;
if(miso.y > (signed)(50*gridsize))
{
if((signed)(miso.y-(50*gridsize)) > (miso.x+(100*(signed)gridsize))/2)
return point(-2,-2);
if((signed)(miso.y-(50*gridsize)) > (miso.x-(100*(signed)gridsize))/-2)
return point(-3,-3);
}

if(miso.x < 0) //A diagonal line cuts the map in two, on one side the X coordinates are negative on the other they're positive
{              //We have to calculate differently depending on which side we're on
point center(       (tmpx*200)-100   ,(tmpy*100)+50);
point topRight(     (tmpx*200)       ,(tmpy*100));
point topLeft(      (tmpx*200)-200   ,(tmpy*100));
point bottomRight(  (tmpx*200)       ,(tmpy*100)+100);
point bottomLeft(   (tmpx*200)-200   ,(tmpy*100)+100);

ret.x = tmpx+tmpy;
ret.y = tmpy*2;

if(pointInTriangle(miso,center,topRight,topLeft))
{
ret.y--;
ret.x--;
}
if(pointInTriangle(miso,center,bottomRight,bottomLeft))
ret.y++;
if(pointInTriangle(miso,center,topLeft,bottomLeft))
ret.x--;
}
else
{
point center((tmpx*200)+100,(tmpy*100)+50);
point topRight((tmpx*200)+200,(tmpy*100));
point topLeft((tmpx*200),(tmpy*100));
point bottomRight((tmpx*200)+200,(tmpy*100)+100);
point bottomLeft((tmpx*200),(tmpy*100)+100);

ret.x = tmpx+tmpy;
ret.y = tmpy*2;

if(pointInTriangle(miso,center,topRight,topLeft))
ret.y--;
if(pointInTriangle(miso,center,bottomRight,bottomLeft))
{
ret.y++;
ret.x++;
}
if(pointInTriangle(miso,center,topRight,bottomRight))
ret.x++;
}

return ret;
}

Basically it uses division to determine roughly where the coordinate is to a square, then divides that square into a center tile and four triangles around it containing adjacent tiles. It then uses pointInTriangle to determine which of these triangles it is in, or if it's in the center tile by process of elimination. The problem is this takes quite a lot of calculations for something I feel should be a lot simpler. Is there an easier way to convert coordinates to tile coordinates for diamond shaped tiles? Edited by Syerjchep

Share on other sites
You just need a change of basis. Find the two vectors that define adjacent sides of a diamond, then project your point onto each to find how far your point is in each of the tile space directions. This is functionally equivalent to taking the two diamond side vectors, plugging them as rows into a 2x2 matrix, taking the inverse of that matrix, and then multiplying your vector on the left by that matrix on the right.

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 10
• 9
• 9
• 11
• 11
• Forum Statistics

• Total Topics
633686
• Total Posts
3013324
×