Evolution of Visibility Determination - I

I recently started working on a 2D game engine with an aim to provide a game programmer with tools that may be of interest. And even more recently I chose to build the visibility determination tools that can be used in several environments.

Not to skip any steps, I began with the most basic visibility idea: The width of visibility increases with the distance from the eye. That reminds me of a triangle if we consider one point to be the eye. I will call this "the visibility triangle"

Remember, right now, the only intention is two create the most basic form of VD.
So hmm.. let's begin with putting a box over here, a box over there, maybe a player... and an object to be seen:


Let's go for blue to be the player and pink to be the... the enemy! Well, why do we need a check to see if we can see the enemy? We don't. I am only thinking that, to be honest, moving the enemy in a certain pattern would require far more work than to move it ourselves.

Oh the visibility triangle! I probably need to see that instead of guessing where it is but more importantly, if it works or not. Visualization is the most important debugging tool in my opinion.

So now, to begin easy, I'm going to say that I am facing North-East and I can see about...hmm...60 degrees wide. Probably enough for now. I should ask my friend to measure my angle of visibility sometime though. But right now, a triangle, means three vertices, one for my eye and two for the far ends. I probably need the distance I can see clearly too. Combine them all and one can create a structure like this:

VisibilityTriangle:
3DFloat center;
3DFloat vertex1;
3DFloat vertex2;
float distance;
float angle;

And...can use that to draw me a nice little triangle:


That looks neat. A probably good idea is to take care of the movement. My new little system of VD should probably have functions that update the triangle vertices with the appropriate functions as I move.

So now it moves accordingly. It didn't by any means starting working on its own right? Double check...Nope, it neither recognizes "The Pink" nor it turns green or flashes. Not like we are going for some cool effects anyway.

So the second aim is to teach the triangle appropriate test to understand that, if the object is within all three of the edges, FLASH! Turning green works too. But how... Hmmm..

Well we want it to be inside the edges. So there 'should' be a test that gives one result if it is inside the edge and one if it is outside the edge. How about + and -? We will say, if the result is positive, than it means it is inside. Oh well, said the vertices are 3 dimensional vectors so why not use some of the cool vector functions?

Quoting Vorpy from GameDev.net forums:

"You can calculate the dot product of the plane normal and a point on the plane to get the distance from the origin to the plane. A point x is on the plane if Nx = d, where N is the normal, x is the point, and d is the distance of the plane from the origin. For any other point x', the sign of Nx'-d tells you if the point is on one side of the plane or the other, or on the plane itself."

Let's work on the left edge. If I can get that one to work, rest should be quite simple.
I have one center vector, which points the beginning and another vector that points the end of the left side. To get the side vector,




Now, normal vector of a vector is ( -y , x , 0 ). I put the 0 simply because we are actually in 3D though don't really worry about the Z-dimension.






And I need the distance from the origin which is the dot product of normal vector and a point that lies on the side. For the point I have two options: center and the other vertex. I will use the center for this one.




And finally a check, that is, if the dot product of the normal vector and the center of the "pinkie" minus the distance from the origin is positive, it should lay on the inside of the side. If it is not, than we know that it is on the outside.





Add some function that changes the color of the polygon and voila!