Most efficient method for concealment objects?

Hey all.

I’m thinking of implementing concealment as part of a tactical AI package. Concealment is basically stuff like bushes that affect the perception of the AI, so basically you can sneak up on them if you are concealed. Now right now I’ve been considering using a raycast based method, using LineTraceMultiByObjectType to line trace to the player/ai, so basically the raycast does a line trace THROUGH a concealment object on the way to the character to test for visibility, if the concealment object is hit, then the character is concealed.

But we all know line traces are pricy in terms of performance and to do it justice I’d need multiple tests per character.

So, anyone got any other ideas how this might work?

I would go for a method that uses line tracing as a final test, but a simpler method that cuts down the number of traces that you need to do. They call that a broad phase method sometimes.

One idea that comes to mind is by doing a range check before doing the line of sight check, if your AI has a limited vision range. Instead of checking Pythagoras between each AI and each player manually though, you can let the object overlap system optimize on this: Give players and AI a sphere collision shape. The AI’s sphere radius is set to his vision radius. Whenever a player enters the AI’s vision sphere, you ‘somehow’ store that the player is within the AI’s set of potentially visible players. When the player leaves the vision sphere, remove it from the set. Then when its time to do a query for players in vision, you know exactly the set of players that is in range reducing the number of raycasts you need to do. Edit: The assumption here is that because all the spheres are known to UE4’s collision detection system, it can optimize collision detection and does not check each sphere against each other sphere. I’m pretty sure UE4 does this.

So this idea is something that I tested in a multiplayer team vs team game project with vision mechanics like in Dota or League of Legends. In my experience it works quite well and significantly reduces the number of raycasts. The use of this broad phase depends on your context though, if actors are going to be close to each other a lot then less vision checks will be excluded and you will gain less performance.

I think raycasts or something like sphere traces will be necessary for your vision testing purposes and it boils down to finding a suitable broad phase method depending on your game. I would love to hear if someone has an idea that does not require raycasting.

As NisshokuZK says, it’s not really something you’ll be able to avoid, more something you can just try to minimize as much as possible. One possibility would be to move as much calculation as possible into a precomputation stage. I think it’s a fair assumption that the majority of concealment objects will be static. You could generate a spatial subdivision and calculate conservative concealment values between pairs of cells based only on static concealers. So then you know for example that every point in cell X is concealed from every point in cell Y. At runtime you then do a quick lookup based on the current cells of your source and target to determine concealment by static objects, and if necessary combine this with results of ray traces for dynamic concealers.

If you want different concealment objects to have varying degrees of concealment (eg. wall is stronger than bush) then it becomes a little more difficult. You could still do it, you’d just have to trade off some precision for speed gains.

I’d probably just go ahead and implement it using dynamic raytracing first though. You may find that by making the system sufficiently asynchronous (which I think you’re going for anyway) that you don’t end up needing a prohibitive number of traces per frame in order to get good results.

I’m using the AI Perception system for the broad phase. What I’m doing is modifying the senses for a “Tactical Sense” and implementing a raycasts method in there. I can’t really think of any smart way of making that better though, because it requires you raycast to be able to test if cover is between the two characters. The problem is that most of the bushes and stuff in the game are instanced static meshes, so there’s an issue there too. I guess I could cheap out and simply have a “is there a bush near me” kind of thing on the character being detected. Actually, that might work better, instead of raycasting, have each player update a “concealment” value that is derived from the number of bushes within a particular radius of them (small) in the direction of the threat. I guess that would negate things like dense cover mid-way to the target though.