• Advertisement
Sign in to follow this  

Sight checking for many units

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
Does this sort of thing help...
http://www.heavymetalpro.com/los.htm

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Just a wacky thought.....but I think you can break down the problem by simply implementing a scene graph or using a scene graph. I know Scene graphs are usually used for rendering purposes to to object culling etc, but won't object culling help in visibility as well?

I haven't looked into the stuff on scene graphs closely, but then from a rendering pipeline point of view, doing object culling from the purspective of each usit will simply resolve most visibility issues. Its just a thought off the top of my head, not tested yet.

Also, if your units travel in close groups, then you can test just one person in the group's visibility of enemies. If one person in the group can see it, especially someone standing near the center, then you know most of your group should be able to see it. This of course is assuming that visibility is judged only by distance. So, you do 1 distance check from the center of the group to all enemies, then do view angle checks only for each individual unit. So, basically, only test visibility with units within range of the group's average visibility range. Something of the sort.

Most of these are just thoughts off the top of my head. But I feel using information from the scene graph, if any, and the rendering pipeline , may be an interesting approach.

Share this post


Link to post
Share on other sites
First of all, everybody thanks for the tips!

@WeirdoFu
Sharing info like distance could help. Units are moving indeed in groups (5 or 6 men). So in common, they will be close. However, the AI and game allows a squad to split up (flanking or sending some scouts forward). In that case sharing the information wouldn't be accurate enough. I could make a flag to share or not but that might bring some overhead because I need to check if all squad members are close enough to each other then.

I never heard of these Scene graphs so I should take a look at that. I already thought about stuff like Octree or BSP but there's a slight problem though, the terrain objects are dynamic. Trees can be removed, moving vehicles should block the sight as well and buildings can be placed or destroyed any time. So pre-computing the visibility isn't really possible, except for the (static) terrain itself. But the terrain collision check itself is really fast and simple. Howeverm if these 'Scene Graphs' can be updated fast (remove a tree something) and don't eat too much memory, it could work.

[EDIT]
I saw something about those graphs (on gamedev.net of course). I guess I'm already using something like that with the usage of cells. Each cell contains a bunch of objects that can be checked by stuff like raytracing or bullets. Packs of objects like a vehicle ( chassis, wheels, turret etcetera) are handled as 1 group as well.

Share this post


Link to post
Share on other sites
I plan to have a blackboard approach. Basically, anytime someone does a LOS check, he stores from what area to what area the check was in, ( I already have rectangles for the navigation map ), and what time the check was made, and the success of the check.

So, if you are looking for a good shot at the enemy, you may choose to move to the same square as your friend who did a successful LOS at him recently. Or, you may use that info to move elsewhere, in order to surrround him.

I want enemies to waste some shots, and hit near the character, so having a sloppy LOS can be good, too. Like treat the player has having a bounding box 50% bigger than normal for the sake of the LOS check. That way it can be sloppy. Another way to slop it up is to not shoot the LOS from exactly the enemy's head or gun, but rather a nearby random location.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement