Sounds like you need to use visibility polygons, like for example

http://www.visilibity.org/

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

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.

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...