Thursday, December 13, 2007

Evolution of Visibility Determination - II

I have a a fortunate side (can also be unfortunate at times) with me. Whenever I start working with a 100% focus on a project, I never tend to loosen that focus outside the work area. For instance way back in the day, when I started playing around with one of the greatest 3D modelling-rendering tools, 3D Studio Max there were times where I visualized pretty much everything in wireframe. Those who had a touch on 3D graphics probably know what I'm talking about. Well a similar case happened today. Here is the story:

I'm walking to one of my classes, trying 'not' to think about the current 2D Polygon Engine I'm working on, 20% because my brain needs to relax but 80% because I am actually walking to the class to take a Discrete Mathematics final. So I hear a sound far away, calling my name, and I look up to see some green shape, coming towards me.

- Hey Dogan, what's up?

Oh, nothin' much, only if I knew who you are not that I have a short term memory but mainly because I can't pick your figure from the distance. Here is what went through my brain from that moment through I actually found out what that green thing was:

~0-3 seconds: I saw: 'A SHAPE coming towards me, yelling my name'
~3-5 seconds: I saw: 'SOME GUY, walking towards me, calling my name, asking me what's up'
~5-5.5 seconds: I think: 'That it is THE GUY that sits by me in my class, could be, I'm not sure, better wait...'
~5.5-6 seconds: I'm sure that: 'It is HIM. I better call his name if I want to avoid this weird situation. Standing in the middle of the street trying to think about what's going on in the brain might not be what a person should be doing when someone asks what's up.'

And I said nothin' much. Ready for the final?
So from the moment I saw him, it took me about 8 seconds to actually realize what the shape was, who it was and so on...So kept that thought process aside, took my final and now I am here, with the same thoughts again, this time sitting beside my 'thought transformation tool', or some say 'the computer'. I am actually writing this right now, instead of studying for my Film Musics elective final tomorrow partially because I think I can wing some essay on 'The development of Electronic Music in Film' and partially because I can't keep these thoughts on my brain too much.
Going back to the problem... Currently the visibility determination tool I am programming is on a state where if you attach it to an object, that object can see another figure that is inside the object's triangle of visibility. With my experience today, I right now want to improve this and add an illusion of the process I went through today.
Opening up the development tool...
So, right now, since I want to create the illusion of the gradual improvement of vision with distance, I know that I need to call the eye let's say 100% vision and the furthest point I can see 0% vision. This means that the vision quality will increase with an inverse proportion to the distance.

Adding the vision variable...

Onto the function. So what I'm thinking is that, If I start the vision from zero always, I can create a function that gradually increases the vision percentage up to one hundred percent. But, imagine the real life situation as I gave in seconds above, our vision gradually increases but as it gets closer, the speed that it increases gets faster which not very surprisingly looks like a quadratic function.

So I want to implement that probably on my 'update-the-whole-thing' function.

And voila!

Unfortunately, the current status of the engine does not allow minimizes and resizes so I can't really use text-wise debugging tools to see if the function outcome is right. So what I did was, I wrote a getter function that gave me the vision_percentage. In the client, I used it to change the color of the polygon from 0% green to 100% green and used it for debugging. If the color changed too slow, I increased the 'fairly large constant' and added a couple more housekeeping tools.
Remember, visualization is the most important debugging tool.

Monday, December 10, 2007

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 d
istance 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 b
ox 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:

3DFloat center;

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