Jump to content

  • Log In with Google      Sign In   
  • Create Account


#Actualnonoptimalrobot

Posted 21 August 2013 - 11:31 PM

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
	{
		switch(a_nIndex)
		{
		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);
			break;
		}

		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);
	assert(a_kPlatform.ContainsPoint(a_vViewPoint));

	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.


#2nonoptimalrobot

Posted 21 August 2013 - 11:20 PM

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 shadow volume but you get to make a bunch of convenient assumptions.  The crux of the algorithm is to construct a 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
	{
		switch(a_nIndex)
		{
		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);
			break;
		}

		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
                        AABB&           a_kOcclusion)       // Resulting bounds of visibility occlusion.
{
	assert(a_fViewHeight > 0);
	assert(a_fPlayerHeight < a_fPlatformHeight);
	assert(a_kPlatform.ContainsPoint(a_vViewPoint));

	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.


#1nonoptimalrobot

Posted 21 August 2013 - 11:19 PM

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 shadow volume but you get to make a bunch of convenient assumptions.  The crux of the algorithm is to construct a 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
	{
		switch(a_nIndex)
		{
		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);
			break;
		}

		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.x) return false;
		if(p.y > vMax.x) 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
                        AABB&           a_kOcclusion)       // Resulting bounds of visibility occlusion.
{
	assert(a_fViewHeight > 0);
	assert(a_fPlayerHeight < a_fPlatformHeight);
	assert(a_kPlatform.ContainsPoint(a_vViewPoint));

	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.


PARTNERS