Sign in to follow this  

Help with visibility test for AI in 2D

Recommended Posts

lukabratzi    198

Hey everyone,


I'm working with some friends on a top down, stealth based, 2D tiled game.  One of the issues we're facing is how to have the AI detect that they can see the player.  


The reason this is difficult is because our levels have the concept of layers (ie: climb a ladder in the scene to get from the lower layer (1) to the upper layer of the scene (2).  This factors into gameplay because we want the AI to be able to see players that are beneath them, unless the players are against the wall or close enough to the wall that the AI shouldn't be able to see them.  See the attached image for an example, red is the AI, green is the player, and yellow is the detectable range that the AI can see.  Note how the ground cuts off the AI's frustum.


The issue is that half the team wants to push for using a 3D collision system in our 2D game.  Meaning everything in the game will have a 3D collision shape in this 2D game where the height is nonvariable except for when you're on different layers.


This seems wasteful to me and I'm trying to think of a way that this system can be implemented simply using 2D AABB's and basic trigonometry.  I'm trying to come up with a solution for this in 2D and wanted to see if anyone else had some thoughts.  Its safe to assume  that we know the height difference between the ai and the player, the distance of the AI from the edge, and the distance of the player from the bottom of the cliff.  The map is tiled and it would be fairly trivial to map the player/ai to the nearest tile (the sacrifice of accuracy isn't an issue) so its possible that there's some use in mapping the ai and player to a tile and figuring out visible tiles from that info.


This may be the one problem that we can't solve in 2D and that requires us to go with a 3D system for checking, but I'd really like to avoid that if at all possible.  


If I can clear anything up or give more detail please feel free to let me know.



Share this post

Link to post
Share on other sites
Zipster    2359

If you're willing to accept tile granularity for your vision detection (which it seems you are), then you can solve this problem using a series of ray traces. For each tile occupied by the player, trace a ray through the world from the enemy's eye to the player's tile (center point). If the ray passes through any tile occupied by an occluder (solid wall, floor, etc.), early-out and move on to the next ray. If none of the rays reach any of the player's tiles, the player is considered hidden. There are various tricks and adjuments you can make to increase accuracy, but this should provide a good rough start :)

Share this post

Link to post
Share on other sites

Even if you didn't have layers (height) and the game took place in a single plane you would still have this problem.  It is essentially one of occlusion.  The player can be obscured from an AI's view by geometry in the horizontal plane.  To see what I mean just look at your diagram as if it was a top down representation and the different levels were walls.  I know, it's a drag.


The "easy" way to do this is as Zipster suggested but you'll have to cast rays in 3 dimensions and impart your tiles with height information.  Fortunately tracing rays though a regular grid can be done efficiently.  You can mitigate the cost by not casting all your rays each frame; human AIs modeling vision rarely need to be updated every frame.


A hacky way to do the same would be to buffer a no-visibility zone around the border of elevated levels and scale the extent of the zone based on the distance an AI is to the edge.  Each AI would need to track it's own scaling factor.  You can work out the amount of scale with some simple trig.  Even if you do this it's a limited solution that doesn't solve any of your other visibility problems.


[edit]  Here's some brief math to help you out with that...


HeightOfAI / DistanceToEdge = HeightOfLayer / OcclusionDistance


OcclusionDistance = HeightOfLayer * DistanceToEdge / HeightOfAI

Edited by nonoptimalrobot

Share this post

Link to post
Share on other sites

Can't sleep and kept coming back to this.  Here's some code to get the "hacky" version that I described working.  This is something of a neat problem, it's very similar to extruding a shadow volume but you get to make a bunch of convenient assumptions.  The crux of the algorithm is to construct 4 rays each starting at the location of your AI and traveling to one of the 4 corners of the platform that the AI is standing on.  Each ray is then intersected with the plane that the player is standing on, these four intersection points will form an AABB which describe the region of space that is occluded by the platform from the AI's point of view.  If the player is inside this AABB they are not visible, if they are outside of it then they are potentially visible if the AI is looking in that direction.

struct AABB
	Vector2 vMin;
	Vector2 vMax;

	void IncludePoint(const Vector2& p)
		vMin.x = min(vMax.x, p.x);
		vMin.y = min(vMax.y, p.y);
		vMax.x = max(vMax.x, p.x);
		vMax.y = max(vMax.y, p.y);

	Vector2 GetCorner(int32 a_nIndex) const
		case 0: return Vector2(vMin.x, vMin.y);
		case 1: return Vector2(vMax.x, vMin.y);
		case 2: return Vector2(vMin.x, vMax.y);
		case 3: return Vector2(vMax.x, vMax.y);

		default: assert(false);

		return Vector2(0, 0);

	bool ContainsPoint(const Vector2& p) const
		if(p.x < vMin.x) return false;
		if(p.x > vMax.x) return false;
		if(p.y < vMin.y) return false;
		if(p.y > vMax.y) return false;
		return true;

void GetOcclusionBounds(const AABB&     a_kPlatform,        // Rectangular bounds of elevated platform
                        float           a_fPlatformHeight,  // Vertical position of the elevated platform
                        const Vector2&  a_vViewPoint,       // Horizontal position of the AI, must be on the platform!
                        float32         a_fViewHeight,      // Height of the AI (tall AIs can see more, short ones can see less
                        float32         a_fPlayerHeight,    // Vertical position of the player's feet + their height
                        AABB&           a_kOcclusion)       // Resulting bounds of visibility occlusion.
	assert(a_fViewHeight > 0);
	assert(a_fPlayerHeight < a_fPlatformHeight);

	a_kOcclusion = a_kPlatform;

	Vector3 vView = Vector3(a_vViewPoint, a_fPlatformHeight + a_fViewHeight);

	for(int32 i = 0; i < 4; i++)
		Vector3 vDelta  = vView - Vector3(a_kPlatform.GetCorner(i), a_fPlatformHeight);
		float32 fDist   = (a_fPlayerHeight-vView.z) / vDelta.z;
		Vector3 vCorner = vView + vDelta * fDist;

		a_kOcclusion.IncludePoint(Vector2(vCorner.x, vCorner.y));

The math can be made leaner but I didn't want to obscure the geometric intuitiveness.  Add a field-of-view check and you are good to go.

Edited by nonoptimalrobot

Share this post

Link to post
Share on other sites
Hiwas    5807
It is a neat problem but pretty easily solved. I'm trying to remember the equation which made this very quick to compute, so forgive me if I get this a bit wrong. The simple solution is to have your tiles represent heights of course and then run a bresenham's from target to source returning false at any point where the "top" of the target hits the content of an intervening tile. As I remember it though, you needed to use the anti-aliased version of bresenham's such that you count edge cases as blockers also. Anyway, computing the 3D line through tiles from target to source solved the problem accurately and quickly.

Additionally I used a "mask" on the surroundings to reduce the ray checks. Basically, I made a mask from source to max view which had a maximal intervening height. So, a single line would be the following:

tile heights:

1 3 2 7 5 2 4=source

Filters to:

7 7 7 7 5 2 4

The reasoning, anything higher than 4 will block anything lower than 4. Using lookup tables this was quick to compute for a circular area around the source. You can avoid the iterative bres algo via this mask check.

Sorry if this is not making a heck of a lot of sense, been a while and want to point it out even though I don't remember the exact details. smile.png

Share this post

Link to post
Share on other sites
serumas    796

Zipsters and AllEightUp ideas nice, but has gaps and lacks of accuracy.

Author first must decide about preciseness he wants, becouse any tile visibility algorithm will have sometimes issues, becouse of player and enemy are not tiles. They can ocupy several tiles at a time. Than tiles goes smaller than accuracy goes more precise.So this method could be good (not perfect) than you granulare your objects not to tile size but even smaller squares. Algorithm speed depends on distance,view width,player size, count of objects and how simple math...


Perfect results will be with geometric math algorithms, like DrEvil suggested, but that costs more time to calculate. Ofcouse it can be greatly optimized becouse you want find visibility not of any shape polygon but aabb.Algorithm speed depends on count of objects and math optimization...

Edited by serumas

Share this post

Link to post
Share on other sites
peibol    354

I have no experience with 3D collision but I think you don't need it for this simple scheme. I liked the overall concept very much.

Let's assume AI height h1, height of layer h, player height h2 and distance from AI to border d1, then the player will be visible when its distance from border is d2 or greater, with:

d2 = d1*(h-h2)/h1

This is basic trigonometry from the following diagram:


You can use any units with this formula, tiles, for example:

h1 = 1

h2 = 1 (player is as tall as the AI)

h = 3 (layer height is 3 times AI and player height)

d1 = 2 (AI 2 tiles away from border)

Player is visible if his distance from border equals or is greater than: 2*(3-1)/1 = 4. So player visible if it is 4 or more tiles away from border.

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this