The obvious way I was thinking is this: have a set of integer pairs that hold the X and Y coordinates. In the begining the set is empty. Then I add all the fields controlled by me. Then I call for each unit a recursive function which marks fields, reduces the depth and then moves to the neighboring field, until depth == 0. I can add the fields all the time because this is a set and there won't be duplicates. I can also check if the field is already in the set, and if it is then don't do anything.
Finally, I paint all the fields not in the set as black, while the rest get drawn.
But I would be calling this procedure whenever I'm drawing out the map. Allocating a set, iterating through a potentially large map, then through all of the player's units could take a long time. So I was wondering if there's a more efficient way to do this?
Range of sight - the most optimal way to implement it
Author
I ama bout to write a procedure which will detect which fields are visible to the player, and then have the rest of the fields get covered with the fog of war. The player sees the fields controlled by him, plus those that are seen by his units.
So if I have a unit that has a range of sight 1 it is easy cause I only need to mark the neighboring fields. But what if I have a range of sight 2 like on this picture:
The obvious way I was thinking is this: have a set of integer pairs that hold the X and Y coordinates. In the begining the set is empty. Then I add all the fields controlled by me. Then I call for each unit a recursive function which marks fields, reduces the depth and then moves to the neighboring field, until depth == 0. I can add the fields all the time because this is a set and there won't be duplicates. I can also check if the field is already in the set, and if it is then don't do anything.
Finally, I paint all the fields not in the set as black, while the rest get drawn.
But I would be calling this procedure whenever I'm drawing out the map. Allocating a set, iterating through a potentially large map, then through all of the player's units could take a long time. So I was wondering if there's a more efficient way to do this?
The obvious way I was thinking is this: have a set of integer pairs that hold the X and Y coordinates. In the begining the set is empty. Then I add all the fields controlled by me. Then I call for each unit a recursive function which marks fields, reduces the depth and then moves to the neighboring field, until depth == 0. I can add the fields all the time because this is a set and there won't be duplicates. I can also check if the field is already in the set, and if it is then don't do anything.
Finally, I paint all the fields not in the set as black, while the rest get drawn.
But I would be calling this procedure whenever I'm drawing out the map. Allocating a set, iterating through a potentially large map, then through all of the player's units could take a long time. So I was wondering if there's a more efficient way to do this?
How are you storing your map coordinates? Most sane ordered paired system should allow you to easily figure out the coordinates of the tiles surrounding a given tile.
Author
Well I'm using a matrix so I can of course detect the fields like (x-1,y), (x-2,y) etc. but I want the range of sight to be flexible, so if I set it to 5 then it has to recursively light up every field inside the distance of 5. I can have each field to have a bool and then I don't need to use a set.
Still, I would be calling this for every unit. There can be more than one units on a field. So if there are 10 units on the same field I would be calculating the same thing over and over.
OK, I guess I could add a new field to every unit called LOSCalculated, and then I iterate through all the units, and check if there already is a unit on the same field which has LOSCalculated == true, and if it does then don't do anything. But is there a better way to do this?
Still, I would be calling this for every unit. There can be more than one units on a field. So if there are 10 units on the same field I would be calculating the same thing over and over.
OK, I guess I could add a new field to every unit called LOSCalculated, and then I iterate through all the units, and check if there already is a unit on the same field which has LOSCalculated == true, and if it does then don't do anything. But is there a better way to do this?
If you can afford to put an extra field in each tile, put an unsigned integer in. Increment it whenever a unit moves or appears in sight range of it, and decrement it whenever it moves out of a unit's sight range. It therefore describes how many units can see it at that moment.
And don't use a recursive algorithm to paint sight range. I can think of two ways (one generative and one validative) to find the visible field of radius R around a hex.
Generative:
For X = 1 to R, Do: Start at unit. Move X tiles north (do not mark any as 'visible' yet). Move X tiles southeast, marking each one as 'visible' as you leave it. Move X tiles south, marking as you go. Move X tiles southwest, marking. Move X northwest, X north, and X northeast.
Validative: testing (tX,tY) for being within R tiles of (uX,uY). Odd columns are assumed to be 1/2 unit offset in the Y direction, ie (0,0) is adjacent to (-1,-0.5),(-1,+0.5),(0,-1),(0,+1),(+1,-0.5),(+1,+0.5).
Determine oX = absolute value of uX - tX, and oY = absolute value of uY - tY.
If R+0.5 <= oY - oX, then (tX,tY) is within R of (uX,uY).
And don't use a recursive algorithm to paint sight range. I can think of two ways (one generative and one validative) to find the visible field of radius R around a hex.
Generative:
For X = 1 to R, Do: Start at unit. Move X tiles north (do not mark any as 'visible' yet). Move X tiles southeast, marking each one as 'visible' as you leave it. Move X tiles south, marking as you go. Move X tiles southwest, marking. Move X northwest, X north, and X northeast.
Validative: testing (tX,tY) for being within R tiles of (uX,uY). Odd columns are assumed to be 1/2 unit offset in the Y direction, ie (0,0) is adjacent to (-1,-0.5),(-1,+0.5),(0,-1),(0,+1),(+1,-0.5),(+1,+0.5).
Determine oX = absolute value of uX - tX, and oY = absolute value of uY - tY.
If R+0.5 <= oY - oX, then (tX,tY) is within R of (uX,uY).
Author
OK I wrote a procedure using something similar to your validative solution. What you wrote would make a huge X across the map, so I had to change a few things. Here's the complete procedure:
Thanks for your help [wink] This probably works in O(width*height) right?
public void drawLOS(int x, int y, int range) { // x,y - position of the unit // range - how far he sees // lx,ly - iterating through the matrix // ox,oy - absolute distance from (x,y) for (int ly=0; ly<w; ly++) { for (int lx=0; lx<h; lx++) { int ox = Math.abs(x - lx); int oy = Math.abs(y - ly); if ( (ox <= range) && (oy <= range - (ox + (ly>=y?1:0))/2) ) { matrix[ly*w+lx] = DESERT; // gets lit up } else { matrix[ly*w+lx] = FOG_OF_WAR; // fog of war } } } }Thanks for your help [wink] This probably works in O(width*height) right?
Umm...
1) Your code as it is will black out everything that cannot be seen by one, and exactly one, unit. You're gonna have to rethink that.
2) Your terrain as it is will be obliterated by it moving out of view. Store a separate field, just a boolean or char, for visibility, independant of what the terrain underneath the fog actually is.
3) You only really need to go from X-range to X+range, and from Y-range-1 to Y+range+1, to cover all cases, and then it's O(range), instead of O(mapwidth*mapheight).
1) Your code as it is will black out everything that cannot be seen by one, and exactly one, unit. You're gonna have to rethink that.
2) Your terrain as it is will be obliterated by it moving out of view. Store a separate field, just a boolean or char, for visibility, independant of what the terrain underneath the fog actually is.
3) You only really need to go from X-range to X+range, and from Y-range-1 to Y+range+1, to cover all cases, and then it's O(range), instead of O(mapwidth*mapheight).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
