   AI Visibility / Sight
  I guess this has been asked a thousand times, but I don't know the game-term for this technique, so it's difficult searching. AI is relative new to me, having spend (too) much time on the graphics first :)How do modern RTS games determine sight? For example, how does an enemy know if the player (or something else interesting) can be seen?Now I just fire a ray with the physics engine to see if there's nothing in between the player/bot (including dynamic objects such as a barrel). But I wondered if games actually use this. Older games such as Quake1 or Halflife1 didn't had the luxery of fast computers those days. And there's another problem with raycasting: 1 ray is not enough. Enemy X fires a ray from his eyes towards the player. But maybe only the lower body, left shoulder or head is visible. I could fix this by shooting multiple rays towards several points on the target body. But yet again, is that really how games work?I was reading about the Node Graph used in Halflife2. Maybe it can be used somehow as well, as they said bots used the graph to get cover for example. But what exactly is a safe spot? It totally depends on where the enemy(s) are. I could make a 'visibility factor' for each possible node combination, but that would give me hundred thousands of links... And pre-calculated info cannot include dynamic objects either (take cover behind a crate, etc.).Greetings,Rick   
  I'm currently battling with a similar problem at the moment.The way I'm doing it and have seen it done before is pretty simple but not something your mind would automatically jump to.What you need to do it calculate the direction vector of one of the player (i.e. the direction its facing in) and normalise it. Then you need to calculate the direction vector between the player and the unit in question and normalise this too. Then you need to determine if the second vector is within a certain threshold from the first vector, by that i mean is the second vector less than a certain angle from the frist vector. The angle you choose is effectivly its field of vision.This should determine whether or not the unit is in the players line of sight although you'll still need to cast your ray to see if there is anything in between the unit and the player. Hope this helps, but like i say, I'm currently bug fixing this method at the moment, to not much success so far, although I'm 99% sure the theory is sound.   ;  Thanks for the reply!Determining if a raycast is going to work at all with a relative simple check is a good start, thanks for that! But in the end it's still raycasting in this case... Not that I have problems with that, but I just wondered if that's the ussual way to do it. How do you deal with the rays? A ray between eye and eye is a good check, but not complete. Sometimes the target is partially covered, but can still be seen.Rick   ;  My guess would be that most games -- especially RTS games -- do not achieve the kind of accuracy in visibility calculations that you seem to be aiming for.If you want this anyway, here are my thoughts...Since this is an RTS game, I assume that your terrain is a heightmap.  In that case, visibility determination can be done with a preprocessing algorithm known variously as the "occlusion horizon" algorithm or "horizon culling."  Try these as Google terms.The visibility estimates that you get from your precomputed occlusion horizons will be pretty accurate, but for additional accuracy you'll need to do some other more accurate kind of test.  Hardware occlusion queries spring to mind.   ;  I wrote RTS... That should have been FPS, my fault!But you mentioned pre-calculated visibility. I was thinking about that as well when looking at the Node Graph stuff, but I don't know how. Well, I could create a relation list for each and every node, but that would take loads of memory I guess. And it doesn't deal with dynamic objects either... RTS games ussually don't require very precise checks indeed, but in the FPS games I know the enemy starts shooting as soon as they see the slightest part of your body.Greetings   ;  Ah, that's a huge topic then.  There are lots of approaches.  Basically any visibility determination algorithm -- image-space or world-space -- is fair game.You might want to wait to hear back from people who actually develop games on modern hardware; I haven't done much of that sort of thing recently (nowadays I spend my time doing math in another field).  However, here's how I'd probably go about it:A classic approach (used by Quake 1-3, among others) is the PVS, or potential visible set.  It might sound like a ton of data to store but it's not unreasonable.  It has fallen out of fashion a little nowadays, but so long as you chunk your level geometry into big enough pieces I think it still has an important place -- because, face it; level geometry is mostly static (unless you're doing something pretty unusual!).So, I'd compute the PVS offline.  Then, at runtime, I'd, for each AI agent,1 - Check the player's visibility against the PVS.  This would rule out most agents.2 - Do a view frustum test.  This would rule out more.3 - Perform a reasonably-accurate image-space occlusion test, e.g with a hardware occlusion query.  This comes with some latency so you might issue the query on one frame and get the answer on the next frame; that's fast enough for AI.As an alternative to #3 you could also do beam-casting; it's essentially the same as shadow-casing a la Doom 3.  My gut tells me that the hardware-accelerated image-space methods are probably faster though if you don't mind the latency and do other stuff while you're waiting.  The image-space stuff is certainly easier.However, you might want to see what other people have to say; there might be more modern approaches to consider.---Finally, let me offer a completely different (and creative?) suggestion: What if each frame you simply cast a different ray from the eye point of the AI agent to a different randomly-chosen point on the agent?  Then, the time it takes for the agent to "notice" the player will be inversely proportional to the area of the player that's visible.  This both gives you a way to amortize the computation over several frames and might give desirably-realistic behavior.   ;  I got a list of visible sectors made with portal culling. But what the player sees is not the same as another character could see. The sector behind me is not in the 'visible' listing, but its agents still might see me. Or do I confuse things and is a PVS different? I could build a list of visible sectors for each character as well though, and then simply look if there is at least one target there.The view frustum test like ScottH87 told is certainly something I should add.Then the image-space occlusion test... I'm not familiar with all these kind of techniques, but does it mean that I render from an agent point of view andthen check for "enemy/target" pixels in a (small) image? It is something I had in mind, but I thought it would be too slow (extra render pass, get theimage data from GPU to CPU, loop through image and check). But come to think of it, I don't have to update the view each and every cycle. For example, I could spread out 30 checks over 1 second. Most probably there will never be that much characters nearby at the same time. Although it would be nice to support larger groups of chararacters. I could also tell AI how many times to check. Someone that sprints in a hurry won't be able to observe the area. Someone that sits in a chair with binoculars on the other hand...Anyhow, the image directly tells me where to target, and can give multiple targets as well. From the amount of visible pixels (distant/coverage), the enemy could choose the primary target. Or spot stuff to pick-up. Beside targets, AI could also use the player image to find cover. Sounds that image data can give quite interesting options, but I'm still a little bit afraid of the cost... I should try it I guess.Your random ray sounds nice as well. I could divide agents into head/body/arms/legs. It won't hurt if it takes more cycles for detection. In fact, I dislike games where the enemy starts firing at you as soon as they spot a single nosehair.Seems I'll have to choose between the two. If they are 'equal' in performance, I'll go for image data as it also introduces other handy info.Thanks for the info!Rick;Quote:Original post by spekI got a list of visible sectors made with portal culling. But what the player sees is not the same as another character could see. The sector behind me is not in the 'visible' listing, but its agents still might see me. Or do I confuse things and is a PVS different?For the PVS approach, you subdivide your world into sectors and then, offline, figure out which sectors could possibly see other sectors.  Essentially, for each pair of sectors you end up with a bit telling you whether there is any point in either sector that can see any point in the other; you store this in your map file and load it when you load the map.The PVS is typically computed using something a lot like the portal culling that you are already using.  See the Wikipedia article for a start; then google if you're interested in this approach.;  You could use a custom view frustum.Not the camera view, but the agent view.Look at this page:http://www.ogre3d.org/wiki/index.php/Frustum_Culling_In_Object_SpaceYou'd be able to implement some wicked vision. :)   ;  So we have 2 systems: Awareness & Visibility.Awareness is no raycasting and asymmetric (that is A can be aware of B and B may not be aware of A)  It checks the enemy against a view cone & a inner radius of "visible awareness".  Also there are event driven audio awareness events.  Only when an entity is aware of an enemy will raycasting happen.  Awareness checks are cheap; raycasting ridiculously expensive.When you're aware of someone you send a message to the Visibility manager to let it know.Raycasting then happens in a visibility manager and is symmetric (only 1 raycast per pair).  We use a half-matrix (team A on top, team B on the left).  Pair up all the entities n*m style.  The visibility manager does X raycasts per frame between pairs in which at least one party is aware of the other. X is a tunable number (balance of fidelity and performance).  When the AI wants to know if it sees an enemy that it is aware of it checks the visibility manager cached value for that entity pairingeasy-peasy & pretty darn performant.That's FPS.I can't remember, for the life of me, how we did visibility in the RTS I worked on.  I think it was just periodic raycasting to enemies inside a certain radius.-me   