Fast fog of war/exploring in RTS
October 04, 2009 11:04 AM
Im planning a 2d rts in the clasic style of total annihilation or dune 2. Im thinking of a simple tile-based world like dune 2 or warcraft 2.
So i have a map like:
--char groundtype[max][max];
--char visible[max][max];
--char explored[max][max];
Every time a unit change tile, it explores (set explored[x][y] to 1) around it according to its sightRadius and removes its old visible "stamp" and creates a new visible-stamp at the new location.
If a tile is explored==1 i can see it
if a tile is visible>0 it is lit and enemy-units there can be seen.
I can optimize this by only effecting the "outer ring" of concerned tiles when i unit moves/updates according to its sightRadius. I will then precalculate these patterns at startup.
Is this a smart way of doing it? Coulnt this be pretty heavy for the cpu if i got a lot of units moving around at the same time? I had it in a turn-based game but there obviously updating this is not a problem
Thanks for your input
Erik
224
October 04, 2009 11:24 AM
Quote: Coulnt this be pretty heavy for the cpu if i got a lot of units moving around at the same time?
Doubtful, unless you're well into the thousands of units. If it becomes an issue, you can scale up the tile size (which doesn't have to be tied to the size of your graphics assets, for example).
By the way...
struct MapTile { short groundtype; bool visible; bool explored;};MapTile map[sizex][sizey];Much nicer.
2,410
October 04, 2009 12:14 PM
One way to speed up the tests is to avoid recomputing the visibility if the area around it has been explored. Have a boolean flag in each tile. When you enter a tile without this flag set, you explore around it, and set the flag to true.
This avoids recomputation of visibility on already visited tiles. That is, assuming visibility ranges do not change.
The above accomplishes the following: You can only explore the area around the tile once. After that, area around it is explored, never to need to be checked again. Since there is finite area available (4096 for Dune2), at some point, no visibility checks will be performed anymore.
If units have different ranges, instead of boolean flag, have an integer. Set it to zero initially. Each time a unit explores, set the flag to that units range. If new unit comes to this tile, check if explored area around it is bigger than previous, and only explore in that case.
Other hacks shouldn't be necessary.
Pseudo code:
Always arrange maps as rows. So map[sizey][sizex]. Since all sequential processing will be done via rows (rendering at least), it plays better with cache.
This avoids recomputation of visibility on already visited tiles. That is, assuming visibility ranges do not change.
The above accomplishes the following: You can only explore the area around the tile once. After that, area around it is explored, never to need to be checked again. Since there is finite area available (4096 for Dune2), at some point, no visibility checks will be performed anymore.
If units have different ranges, instead of boolean flag, have an integer. Set it to zero initially. Each time a unit explores, set the flag to that units range. If new unit comes to this tile, check if explored area around it is bigger than previous, and only explore in that case.
Other hacks shouldn't be necessary.
Pseudo code:
// init all map[][].range to 0...void exploreTile(int x, int y, int range) { if (map[y][x].range < range) { exploreAround(x, y, range); map[y][x].range = range; }};Quote:MapTile map[sizex][sizey];
Always arrange maps as rows. So map[sizey][sizex]. Since all sequential processing will be done via rows (rendering at least), it plays better with cache.
October 04, 2009 12:31 PM
but the problem is mainly visibility (fog of war) not exploration. In this case i need to recheck all the time as units leave the area the fog comes back and must be relifted when units come back. Thus i cannot flag it as "done" and ignore checks furthermore.
I didnt get your last point.
i normally do (in c++)
Is there any problem with this code? Is the two different?
I didnt get your last point.
i normally do (in c++)
for(y=0;y>1000;y++)for(x=0;x>1000;x++) myArray[x][y]=1;for(x=0;x>1000;x++)for(y=0;y>1000;y++) myArray[x][y]=1;Is there any problem with this code? Is the two different?
291
October 04, 2009 01:56 PM
>>Is the two different?
yes its faster
think of a 2 dimensional array as a single dimensional one
eg A[4][4]
depending on what method u use, u will loop over the elements as
A/ 0,1,2,3,4,5,6 .... // what u want
B/ 0,4,8,12,1,5,.... // what u dont want
its the same result but #A is quicker
yes its faster
think of a 2 dimensional array as a single dimensional one
eg A[4][4]
depending on what method u use, u will loop over the elements as
A/ 0,1,2,3,4,5,6 .... // what u want
B/ 0,4,8,12,1,5,.... // what u dont want
its the same result but #A is quicker
2,410
October 04, 2009 03:21 PM
Wondering and discussing performance before having anything to test is somewhat pointless. Just time it:
The above gives me following results:
Or, to move 500 units, it takes around 4-7ms. That is without optimization or anything else, each unit has visibility radius of 8 (or 15 tiles across).
Map tiles with visibility larger than 0 are visible. When a unit is moved, everything in visibility range is first decreased by 1, then the unit is moved, then everything it sees is increased by one.
Obviously, a lot could be made to improve this, such as using masks instead of range test, and pre-computing delta instead of decrement/increment routine. But at least it's a baseline.
But the most important factor here is - what does "move 500 units" mean. This could be a lot, or it could be nothing. For example, Dune2 uses radius of 2 or 3, and each unit can effectively move to another tile only once a second.
#include <boost/multi_array.hpp>#include <boost/timer.hpp>#include <iostream>struct Tile { int visible;};struct Unit { int x; int y; int range;};typedef std::vector<Unit> Units;struct Map { Map(int w, int h, int n) : tiles(boost::extents[h][w]), units(n) { for (int y = 0; y < height(); y++) for (int x = 0; x < width(); x++) tiles[y][x].visible = 0; for (size_t i = 0; i < units.size(); i++) { Unit & u = units; u.x = rand() % width(); u.y = rand() % height(); u.range = 8; } for (size_t i = 0; i < units.size(); i++) exploreTile(units, 1); } int width() const { return tiles.shape()[1]; } int height() const { return tiles.shape()[0]; } int unitCount() const { return units.size(); } void moveUnit(int i, int x, int y) { Unit & u = units; exploreTile(u, -1); u.x = x; u.y = y; exploreTile(u, 1); }private: void exploreTile(const Unit & u, int delta) { int left = u.x - u.range < 0 ? -u.x : -u.range; int right = u.x + u.range >= width() ? width() - u.x : u.range+1; int top = u.y - u.range < 0 ? -u.y : -u.range; int bottom = u.y + u.range >= height()? height() - u.y : u.range+1; int range2 = u.range * u.range; for (int y = top; y < bottom; y++) { for (int x = left; x < right; x++) { if (x*x + y*y <= range2) tiles[u.y+y][u.x+x].visible += delta; } } } typedef boost::multi_array<Tile, 2> Tiles; Tiles tiles; Units units;};void test(int w, int h, int n, int m) { Map map(w, h, n); const int N = 100; boost::timer timer; for (int i = 0; i < N; i++) { for (int j = 0; j < m; j++) { map.moveUnit(rand() % map.unitCount(), rand() % map.width(), rand() % map.height()); } } double t = 1000.0 * timer.elapsed() / N; std::cout << "(" << w << "," << h << "," << n << "," << m << "): = " << t << " ms\n";}int main(){ test(64, 64, 10, 500); test(64, 64, 10, 2000); test(64, 64, 2000, 500); test(64, 64, 2000, 2000); test(1000, 1000, 10, 500); test(1000, 1000, 10, 2000); test(1000, 1000, 1000, 500); test(1000, 1000, 1000, 2000); test(5000, 5000, 100000, 500); test(5000, 5000, 100000, 2000);}The above gives me following results:
Quote: (width, height, n_units, n_moves)
(64,64,10,500): = 3.86 ms
(64,64,10,2000): = 15.25 ms
(64,64,2000,500): = 3.89 ms
(64,64,2000,2000): = 15.31 ms
(1000,1000,10,500): = 5.3 ms
(1000,1000,10,2000): = 21.17 ms
(1000,1000,1000,500): = 6.02 ms
(1000,1000,1000,2000): = 24.05 ms
(5000,5000,100000,500): = 6.89 ms
(5000,5000,100000,2000): = 27.4 ms
Or, to move 500 units, it takes around 4-7ms. That is without optimization or anything else, each unit has visibility radius of 8 (or 15 tiles across).
Map tiles with visibility larger than 0 are visible. When a unit is moved, everything in visibility range is first decreased by 1, then the unit is moved, then everything it sees is increased by one.
Obviously, a lot could be made to improve this, such as using masks instead of range test, and pre-computing delta instead of decrement/increment routine. But at least it's a baseline.
But the most important factor here is - what does "move 500 units" mean. This could be a lot, or it could be nothing. For example, Dune2 uses radius of 2 or 3, and each unit can effectively move to another tile only once a second.
2,420
October 04, 2009 06:11 PM
Think in terms of visibility "primitives". Every time you update the FOW system, each unit/structure emits a circle at its location, with a radius equal to the visibility range. The circles can be stored in a std::map/stdext::hash_map, and keyed via (position,radius). The value you store in the map is remaining lifetime. If you try to add a circle that already exists in the map, then just reset its lifetime back to maximum. Otherwise, if a new circle is added, you then iterate over all the tiles within its radius and increase each of their FOW refcounts by 1, and the tile is considered visible if it wasn't already. Every update, you decrease each circle's lifetime by the amount of time since the last update. If a circle's remaining lifetime is equal or less than 0 after the update, then you iterate all its tiles again and decrease their refcount by 1 before removing the circle from the map. If a tile's refcount drops to 0, it becomes hidden. Note that the only time you ever need to iterate over tiles is when you're reasonably sure their FOW state is going to change, subject to the amount of overlap from other circles. Moving units will create quite a bit of circles for sure, but this gives you the desired behavior once you consider timing and overlap.
If you let the initial refcount of a tile be -1 (and check for that special case during increment so that it goes from -1 to 1), you get the unexplored state. Otherwise, for just visible and not visible, you start at 0 and don't worry about special cases. Also note that I originally mentioned "primitives", and this is because such a system can easily support more than circles. In that case the map key becomes (shape,position,params), but everything else is relatively unchanged. Thus you can have special units which can only see in a certain direction with a 45° spread let's say, but see a lot farther than regular units. If you rotate this cone around the unit, then you get an interesting lighthouse effect.
If you let the initial refcount of a tile be -1 (and check for that special case during increment so that it goes from -1 to 1), you get the unexplored state. Otherwise, for just visible and not visible, you start at 0 and don't worry about special cases. Also note that I originally mentioned "primitives", and this is because such a system can easily support more than circles. In that case the map key becomes (shape,position,params), but everything else is relatively unchanged. Thus you can have special units which can only see in a certain direction with a 45° spread let's say, but see a lot farther than regular units. If you rotate this cone around the unit, then you get an interesting lighthouse effect.
October 05, 2009 09:19 AM
I think ill be ok if i precalc a mask and just uses this when units move to update view. For explore i can use an intiger as each tiles "max explored from this tile" to skip a lot of exploring when having loads of units move around the same area.
[Edited by - suliman on October 5, 2009 10:19:27 AM]
[Edited by - suliman on October 5, 2009 10:19:27 AM]
2,410
October 05, 2009 11:56 AM
Quote: Original post by suliman
I think ill be ok if i precalc a mask and just uses this when units move to update view. For explore i can use an intiger as each tiles "max explored from this tile" to skip a lot of exploring when having loads of units move around the same area.
My benchmark is above. Algorithm is completely memory limited. If I change the range test to use a mask, algorithm slows down by a factor of 2-4.
In other words, lookup tables are often bad idea on modern systems.
And again, profile, profile, profile. Don't guess, it won't gain anything.
100
October 06, 2009 07:30 AM
I'm confused about this array row order thing now.. should I worry about it or not? I thought that, it takes the exact same time to access any element of an array regardless of its position in the array, as it's a pointer with an offset added to it. So what difference does the order in which you do this matter??
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
