Picture two characters, in a game, passing each other. The plane can be either two- or three-dimension, and their phenotypes do not matter (space ship? ninja? barrel-throwing ape?). The only things that matter is the distance between them and the direction they are facing.
Can they see each other?
This is the problem of visibility, and it can be hard to do. In this article, we will implement it together.
The Math Part
We get into a little trigonometry, particularly vectors. It won't be incredibly technical but if you learn just a little bit about them, it will make retrofitting that much easier.
Most games operate on a two-dimensional plane, even if they simulate three dimensions. What we are usually working with is x and y, and we could think of those like this:
class Position
{
public $x = 0;
public $y = 0;
}
In this case, the x,y coordinate pair can be positive, negative, and even have decimal places. It doesn't really matter as long as you agree that 0,0 is dead center. This method of representing position is very common in the gaming world.
However, when dealing with two characters seeing each other we have to consider the direction they are facing (or angle) and the distance they are from each other. For this we use vectors.
Theorem: A vector is nothing more than an array of two variables, one is an angle and the other is a distance.
Math guys try to make it so fucking difficult sometimes. If you are a programmer, there is little chance you can screw up that definition. Whenever I say "vector", in your mind I want you to think the following:
class Vector
{
public $angle = 0;
public $distance = 0;
}
A math person will give you a much more formal definition, but trust me, they are compatible. The next concept is how the angle is represented...
For our purpose we will be using angle measurements from 0 to 360 degrees, because even though I like radians, it's easier for me to visualize degrees.
The only real thing left is to figure out a decent way of converting between the two. We sometimes have to do that.
Theorem: There exists three functions, called sin(), cos(), and tan(), that allow you to convert between x,y coordinates and angle,distance coordinates.
So we know we can convert between the two systems easily. This completes the math part of the article, but look forward to the examples in the code part below.
The Code Part
Recall that we have two characters on an x,y positioning system. In order to fully express whether or not they can see each other, we need a third class to describe the complete capability of the characters.
class Character
{
/// How wide is the viewing angle
public $field_of_view = 160;
/// Vector class
public $visibility;
/// Position Class
public $position;
}
We are going to make some assumptions. First: two characters cannot be at the same place at the same time. Second: the characters are deaf. Third: the unit of distance is arbitrary. For the heck of it, call it yards or meters.
Now, let's define our characters:
$char1 = new Character; $char1->visibility = new Vector; $char1->position = new Position; $char2 = new Character; $char2->visibility = new Vector; $char2->position = new Position; $char1->field_of_view = 90; // tunnel vision? $char1->visibility->angle = 45; // northeast $char1->visibility->distance = 3; $char1->position->x = 1; $char1->position->y = 1; $char2->field_of_view = 180; // feline-sighted? $char2->visibility->angle = 0; // due east $char2->visibility->distance = 4; $char2->position->x = -1; $char2->position->y = 5;
The question is, can char1 see char2? Similarly, can char2 see char1? Who can see who? If you stare at the property values for long enough you can figure it out. Human brains are good at that sort of thing. But how can you do this in code?
To start, lets determine the vector between two characters using their position. Some trigonometry will teach you that it is not very hard to convert between a 360-degree system and an x/y system.
function get_vector(Position $from_pos, Position $to_pos)
{
$vector = new Vector; // Output a vector
// Think Pythagorean Theorem for distance
$vector->distance =
sqrt(pow($to_pos->x - $from_pos->x,2) +
pow($to_pos->y - $from_pos->y,2));
// Difference between from_pos and to_pos
$fixed_pos = new Position;
// Essentially we are zeroing the from_pos and
// relatively positioning the to_pos.
$fixed_pos->x = $to_pos->x - $from_pos->x;
$fixed_pos->y = $to_pos->y - $from_pos->y;
// Determine the quadrant
$fixed_pos->quadrant = ($fixed_pos->x >= 0) ?
($fixed_pos->y >= 0 ? 1 : 4) :
($fixed_pos->y >= 0 ? 2 : 3);
// Found out the angle we are dealing with
if ($fixed_pos->x == 0)
{
// We are right on the vertical asymptote
$vector->angle = ($fixed_pos->y >= 0) ?
M_PI_2 :
M_PI + M_PI_2;
}
elseif ($fixed_pos->y == 0)
{
// We are right on the horizontal asymptote
$vector->angle = ($fixed_pos->x >= 0) ?
0 :
M_PI;
}
else
{
// We are not on an asymptote, so we have
// to do some funky math to find our angle.
switch ($fixed_pos->quadrant)
{
case 1:
$vector->angle =
atan($fixed_pos->y / $fixed_pos->x);
break;
case 2:
case 3:
$vector->angle =
M_PI +
atan($fixed_pos->y / $fixed_pos->x);
break;
case 4:
$vector->angle =
(2 * M_PI) +
atan($fixed_pos->y / $fixed_pos->x);
break;
}
}
// Convert from radians to degrees
$vector->angle = ($vector->angle * 180) / M_PI;
return $vector;
}
I recommend that you carefully review the last code example. A lot is happening here. First, realize that the vector between two characters is based off of their position. In fact, for the get_vector() function we are only concerned with position, not direction or viewing angle. An equivalent problem would be "to which degree is Seattle northwest of Denver?" It doesn't matter which direction the first city is facing, just whether it's NW, NNW, NWW, or otherwise from second one.
The get_vector() function will return a vector class containing an angle between 0 and 360 degrees and a distance greater than or equal to 0. It will not return a negative angle, so you will have to deduce that it's faster to turn -40 than it is +320, because +320 is what you'd get from get_vector().
Note also that you can't pass Characters to get_vector() because get_vector() wants Positions. Keep this in mind!
Back to the Math
If you have been following, there are three vectors so far. V1 describes the "blue" character, V2 describes the "Yellow" character, and V3 describes the difference between the two.
All three of the above-mentioned vectors are position vectors, meaning the angle and distance refer to the position from the origin (at 0,0). Once we have the positions in vector form, we can "convert" them to visibility vectors. In a visibility vector, the angle and distance refer to facing direction and how far the character can see.
Fortunately it is actually easier than you think. You see, once we have the angle between the two characters (courtesy of the get_vector() function) we can see if it is within a certain area using simple tests. In this case, the area we are looking for is the "viewing area" of one of the characters.
Consider the can_see() function, which returns true or false whether or not the first character can see the second character:
function can_see(Character $from_char, Character $to_char)
{
// Grab a vector to work with
$vector = get_vector(
$from_char->position,
$to_char->position);
// Find out the smallest angle to check for
$minimum_angle = $from_char->visibility->angle -
($from_char->field_of_view / 2);
$minimum_angle = ($minimum_angle < 0) ?
$minimum_angle + 360:
$minimum_angle;
// Find out the largest angle to check for
$maximum_angle = $from_char->visibility->angle +
($from_char->field_of_view / 2);
$maximum_angle = ($maximum_angle > 359) ?
$maximum_angle - 360 :
$maximum_angle;
if ($minimum_angle < $maximum_angle)
{
$is_within_angle =
(($minimum_angle <= $vector->angle) &&
($vector->angle <= $maximum_angle));
}
else
{
$is_within_angle =
(($minimum_angle <= $vector->angle) ||
($vector->angle <= $maximum_angle));
}
$is_within_distance =
($vector->distance <=
$from_char->visibility->distance);
return $is_within_distance && $is_within_angle;
}
To be honest there is not much math to the code above, unless you count some calculus. All we are really doing is butchering the vector between the two characters in order to find out whether they can see each other.
A Real Summary
Use the form on the top left to try out the visibility classes yourself. You can set the viewing distance (D), the field of view angle (vθ), the direction they are facing (dθ), and the x/y coordinate pair for both of the characters. The image will tell you if they can "see" each other based on the inputs you have provided.
You are encouraged to carefully test all angles and positions that would be valid for your game arena (on your own server. The above tester is limited for a very good reason.) For example, if your arena is 200x200, run a loop on x and y that feeds positions in relative to 0. Look for any inconsistencies. I ask that you do this because it is a good habit for coders to be in.
The code above is licensed under Creative Commons v3.0 with Attribution. We ask that you put a link to http://zablocky.org/visibility.php in your source code in a comment somewhere. If you compile your code for commercial use, mention the link somewhere in a credits or readme file. That's all I ask. For that much, I may even support this a bit.
Good luck, and happy coding!