Sight checking for many units
Hi,
Does someone know a fast way to check if somebody is insight? In my case I have 2 (or more) large armies that need to check each other. Each unit has a list of enemies which are in his sight that needs to be updated a few times per second. The terrain is pretty complex as it contains hills and all kinds of objects that can be used for cover. I had the following thing in mind:
The terrain is divided in cells, each cell has a list of units in that area
per Unit:
1- Check for all enemy units in that area(and the surrounding area's) if the 2Dimensional distance < max_view
2- Ifso, check if the enemy unit is in the viewing angle
3- Ifso, send a 'dummy bullet' towards that unit. Just like any other bullet, this bullet checks if it hits the terrain or objects.
4- If the dummy bullet hits the enemy unit, that means he is in sight. That info can be shared with the enemy unit as well.
But what if there are 20 units of each side in one area for example? It would require 20x20 + 20x20 = 800 calculations. Maybe I can reduce it by sharing info but then there would still be 400 calculations. Does somebody knows some tips or tricks?
Greetings
Well, one thing you could do is that once a unit is in sight by one unit, you do not check for any others...
Therefore at optimum you'd only have to do 1x20 + 1x20 = 40 instead of 800...
And the benefit would be noticible I believe even in much-less-than-optimum scenarios.
PS: Plus if you go by the 'ol rule of "If I can see you then you can see me," then you really only have to do it for one side of your forces, which would be a substantial speedup.
Further, if the resolution of your cells was right, you could just test for cell-visibility. Any unit inside of a cell would then be visible, no independent checks.
PLUS if you wanted to get fancy-pants on the map-preload, you could just CHECK which cells within a certain neighborhood are visible from each cell.. May take up memory though.
Therefore at optimum you'd only have to do 1x20 + 1x20 = 40 instead of 800...
And the benefit would be noticible I believe even in much-less-than-optimum scenarios.
PS: Plus if you go by the 'ol rule of "If I can see you then you can see me," then you really only have to do it for one side of your forces, which would be a substantial speedup.
Further, if the resolution of your cells was right, you could just test for cell-visibility. Any unit inside of a cell would then be visible, no independent checks.
PLUS if you wanted to get fancy-pants on the map-preload, you could just CHECK which cells within a certain neighborhood are visible from each cell.. May take up memory though.
Thanks for the tips! But there's still a slight problem
"Well, one thing you could do is that once a unit is in sight by one unit, you do not check for any others"
This could save many checks and maybe its unnescesary to check all enemies as you can't attack them all at once anyway. But, as I want my units to be pretty smart, it would be nice if they could memorize multiple units. Here are a few scenarios which would require the checking of all units (I think):
- Which unit to attack first? The closest, the most dangerous, the weakest...
If they would stop checking units once they see one they might attack a criple guy 50 metres away while there's a more dangerous enemy right next to them.
- Attack or not? If you see only one guy, its not a problem, but if you see a complete army in front of your nose, I wouldn't attack.
- Memorize other units. If you see a few enemies sneaking behind a tree while
youre fighting with another, it would handy if the unit is aware of that after he finished the fight.
I would say each unit needs to check all enemies (in that area) but maybe there are smarter solutions for the things I discribed? A 486 could also calculate Command & Conquor with many units. Of course, those units and visibility checks were much simpler but then again, it was a slow pc.
Greetings and thanks for helping!
"Well, one thing you could do is that once a unit is in sight by one unit, you do not check for any others"
This could save many checks and maybe its unnescesary to check all enemies as you can't attack them all at once anyway. But, as I want my units to be pretty smart, it would be nice if they could memorize multiple units. Here are a few scenarios which would require the checking of all units (I think):
- Which unit to attack first? The closest, the most dangerous, the weakest...
If they would stop checking units once they see one they might attack a criple guy 50 metres away while there's a more dangerous enemy right next to them.
- Attack or not? If you see only one guy, its not a problem, but if you see a complete army in front of your nose, I wouldn't attack.
- Memorize other units. If you see a few enemies sneaking behind a tree while
youre fighting with another, it would handy if the unit is aware of that after he finished the fight.
I would say each unit needs to check all enemies (in that area) but maybe there are smarter solutions for the things I discribed? A 486 could also calculate Command & Conquor with many units. Of course, those units and visibility checks were much simpler but then again, it was a slow pc.
Greetings and thanks for helping!
Ray sphere intersection is what the 'dummy bullet' does. It travels very fast toward a target and checks collisions with the terrain and sphere collision checks with objects like trees. If it collided before it struck the enemy, the enemy is behind something and thus not visible. Sphere collisions should be pretty fast, but would it still be fast if there are hundreds of these rays flying over the field?
It probably depends on the collision detection quality. The terrain check is very simple, checking objects (cylinder or sphere) would be pretty simple as well, but there are can be pretty much objects. A ray only checks the contents of its current cell. I don't have the exact size yet but it could be 6x6 metres. A crowded cell of that size could have 10 objects so that means 10 sphere collision checks for 1 ray at 1 moment. If there are 400 rays active, that would mean 4000 checks in a worst case scenario. I wonder if that doesn't hit the framerate badly.
Maybe I underestimate the capabilities of a modern computer. Or maybe its just too much. Shooters mainly have all their CPU units focussed on 1 of 2 players. But games like Battlefield can have pretty much bots though...
It probably depends on the collision detection quality. The terrain check is very simple, checking objects (cylinder or sphere) would be pretty simple as well, but there are can be pretty much objects. A ray only checks the contents of its current cell. I don't have the exact size yet but it could be 6x6 metres. A crowded cell of that size could have 10 objects so that means 10 sphere collision checks for 1 ray at 1 moment. If there are 400 rays active, that would mean 4000 checks in a worst case scenario. I wonder if that doesn't hit the framerate badly.
Maybe I underestimate the capabilities of a modern computer. Or maybe its just too much. Shooters mainly have all their CPU units focussed on 1 of 2 players. But games like Battlefield can have pretty much bots though...
If you can preprocess your terrain, you can divide it in regions and precompute what regions are at least partially visible from each region. Then in the loop, for each unit on one side of the army you only have to check enemy units located in the regions that might be visible. This is similar to the precomputed occlusion that games like Quake II use for rendering. If your level can be divided in "rooms", this can save you a lot of time.
You already point at this in your first post, but let me make it more explicit: if A has a line of sight to B, then B has a line of sight to A. Well, that's not exactly true in real life, but probably good enough for your type of game. You can cache the dummy bullet tests that you have performed from army X to army Y; this can save you a bunch of tests from army Y to army X (so in your example with 20 units in each side, you only have to perform 400 tests, not 800).
You already point at this in your first post, but let me make it more explicit: if A has a line of sight to B, then B has a line of sight to A. Well, that's not exactly true in real life, but probably good enough for your type of game. You can cache the dummy bullet tests that you have performed from army X to army Y; this can save you a bunch of tests from army Y to army X (so in your example with 20 units in each side, you only have to perform 400 tests, not 800).
Thanks again for all the help! That region visibility stuff is interresting, but probably hard to implement. Its a RTS game with large open areas. Trees, buildings, rocks, walls and hills can block the sight. With buildings it can be easy to check if the neighbour cells are visible from that cell, unless you can look over the building like this
A
\
1 \___2____[3 ]___4_B
A tries to see B:
From cell 2, cell 4 wouldn't be visible because of the building in 3, but as cell1 is on a hill you can look over it. I'm trying to create a jungle so most of the sight blocking will be by trees. But as you can look through the trees from certain angles, its almost impossible to define another cell as completely invisible or not, unless I use small cells. But as the terrain is really large, I'm afraid that would eat too much memory and when using many cells, it wouldn't be really effective anymore. Well, maybe that's why most RTS games don't have jungles or just a simple visibility check... Come to think of it, are there any RTS games with many units where trees are blocking bullets and sight?
A
\
1 \___2____[3 ]___4_B
A tries to see B:
From cell 2, cell 4 wouldn't be visible because of the building in 3, but as cell1 is on a hill you can look over it. I'm trying to create a jungle so most of the sight blocking will be by trees. But as you can look through the trees from certain angles, its almost impossible to define another cell as completely invisible or not, unless I use small cells. But as the terrain is really large, I'm afraid that would eat too much memory and when using many cells, it wouldn't be really effective anymore. Well, maybe that's why most RTS games don't have jungles or just a simple visibility check... Come to think of it, are there any RTS games with many units where trees are blocking bullets and sight?
One of my fellow programmers had a simialar problem implementing a clone of Advance Wars. They were doing it in Java and the line of sight took 30 seconds to complete. They used a really poor algorithm. There terrain was nothing more than a 2d array, which in turn is a form of a graph. The answer for them was to do a breadth-first search. They got the algorithm down to 3 seconds, but that also included all of Java's paint calls, so the algorithm really ran faster.
Well usually there are many ways to cover up the expensiveness of the sight check. For instance, if a unit is facing a particular direction, you can break up his field of view into a dozen or so chunks, and only test within each chunk each frame, advancing from one to the other - as if the unit is scanning the horizon. Also you should limit the objects which can be blockers.
Then you can proceed to hierarchical methods, where you group soldiers into platoons based on their location, and decide which of the enemies' platoons are visible on a per-group basis.
Tom
Then you can proceed to hierarchical methods, where you group soldiers into platoons based on their location, and decide which of the enemies' platoons are visible on a per-group basis.
Tom
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement