Introduction

An important part of most AIís is line of sight. This article describes an original technique, which uses no detectors at all, is fast and the vision angle can be easily adjusted. This article is quite long, if you prefer to read it, split up in pages, goto http://www.crobasoft.com/tools/article/line-of-sight/1

Note: This article is not intended for any specific multimedia tool or language, this is a general article, and the techniques I explain here, can be implemented in most multimedia tools and languages.

The usual approach to line of sight is simply shooting out a detector in the direction of the enemy, and if it hits the player, the enemy can see him. There quite a few problems with approach:

ē The enemy can only see whatís immediately in front of him, if the player is slightly to the right, or the left, the enemy wont be able to see him

ē This method usually slow. Say you the enemy shoots out a detector every second, and it was looking straight at you, it might take a second for the detector to be shot, and even more time before it hits you, and the enemy becomes aware of you.

ē And then thereís the obvious problem with too many objects. If you had 10 enemies each shooting out a detector every second, you could end up with a lot of objects, which might slow the game down considerably.

But of course, this method might work for some simple games, however, in most situations, you will need your enemy to have a broad line of sight, and you want it to see the player instantly. Therefore I have developed a method, which works by comparing the angle and distance between the player and enemy. In this article, I will walk you through the steps of creating an enemy that has a sight similar to this:

Image

This is how our ideal enemy will see. The red ellipse is the enemy, and the area shown pink is the part of the map it scans. Scanning such a large area seems slow, however, we will not scan that entire area at once, only the parts thatís needed, which makes it relatively fast. Looking at this diagram for a while, you will notice that there are 3 things that limit the line of sight: Distance, Angle and obstacles. The latter isnít made clear here, but I will go in to more detail further down. These 3 limitations will be our conditions. All 3 of these conditions must be true before the enemy see the player. Iíll refer to these conditions as flags that can either be turned on or off; this is the same as a Boolean value that can either be TRUE or FALSE, but I will stick to flags as itís easier.

Image

In this image, our red ellipse is the enemy, and the blue is the player. In this example, an obstacle have been added, that the enemy cannot see through. Thus, in this case, the enemy cannot see the player, as he is hiding behind a wall. So, before the enemy can see the player, the path between them, must be obstacle-free. When the path is obstacle free, we turn ON the obstacle flag, and when it is not obstacle free, we turn it OFF. I will explain one way to check for obstacles later in the article.

Image

In this diagram, the enemy does not see the player either, because the enemy cannot see that much to the right. So, before the enemy can see the player, it must be within a certain angle from the enemy. We call this flag within_angle; it must be turned ON when the player is within the angle, and off when heís not. Iíll explain how to get the angle between them, later in this article.

Image

And last, the enemy cannot see for miles, so we must have a limit, as to how long it can see. In this case, it can see 200 pixels straight ahead. So, when the player is within 200 pixels, the distance flag is turned ON, and when heís not, itís turned OFF. Iíll explain how to get the distance later in this article.

Obstacle recognition

The first step in the line of sight algorithm is to recognize obstacles, which might be between the player and enemy. This step can either be very hard, or very easy, depending on what tool you use. What we will want to do is shoot a detector from the enemy, towards the player. (Note: A detector doesnít have to be another object; it could just be an X and a Y value) When this detector moves from the enemy towards the player, you check if it hit any obstacle on its path. If it hits anything on the way, you know thereís an obstacle in the way, and you turn the obstacle flag OFF, but if it reaches the player without hitting an obstacle on the way, it means there are no obstacles in the way, and you turn the obstacle flag ON.

The hard part here (In some languages/multimedia tools) is moving the detector. Iíll assume there are no built-in features in the tool you use to help you with this. We first need to figure out the angle between the player and enemy, so we know which direction to move the detector in. This can (in most languages) be done by:

Atan2( (Player.Y Ė Enemy.Y ) , (Player.X Ė Enemy.X) )

If you donít have the Atan2 function available, youíll have to find another way to get the angle between the points.

After that, you have to move the detector in a loop, one pixel at a time.

X = Enemy.X + Cos(angle) * Loop step/index
Y = Enemy.Y + Sin(angle) * Loop step/index

You run this loop until you hit an obstacle, or reach the player.

Distance comparison

As explained in the introduction, our enemyís line of sight must have 3 restrictions: Distance, obstacles, and angles. In this section, I will be focusing on distance.
In real life, a person would have a limited viewing distance. For example, must people wouldnít be able to see another person a mile away, even if thereís no obstacles in between, so we need to add a similar system to our line of sight algorithm. First, we need to figure out the distance between our enemy and player.

Finding out the distance is relatively easy, Iíll explain how to do it using Pythagoras, which is the standard way of getting the exact distance between two points.

a^2+b^2=c^2

Pythagoras works on the principle, that in any right triangle, the length of the longest side, or the side that is opposite to the right angle (The Hypotenuse) increased by a power of 2, is equal to the length of the 2 shortest sides or the sides that is not opposite to the right angle, increased by power of 2.

In the above equation, the Hypotenuse is expressed a c, and the other two sides are expressed as a and b. From these facts, we can conclude that to get the distance between two positions (in this case the Player and enemy), we must use the following equation:

Squareroot((X1-X2)^2+(Y1-Y2)^2)

After you have figured out the distance, you simply need to compare it to the enemyís maximum viewing distance. In this case, its 200, so simply check if the distance is lower than 200; if it is, turn the distance flag ON, if itís not, turn it OFF.

Angle Comparison

The last step is to make sure the player doesnít stand out of the enemyís viewing angle. For example, if you were looking forward, and someone was standing to the immediate right or left of you, you wouldnít be able to see him, as illustrated in diagram 2.B

First thing first, we need to figure out the angle between our enemy and player. This was covered in the distance comparison section.

When you have figured out the angle between the player and enemy, you compare it to the angle the enemy is facing. In diagram 2.B, the enemy can see 45 degrees to the left, and the same to the right. So, we need to figure out if the player is within this area.

Abs(Angle-Enemy_viewing_angle)

Now you simply compare if the value is lower than the maximum angle, in this case; 45. If it is, turn the angle flag ON, if itís greater than 45, turn it OFF.

Thatís pretty much it; we now have 3 flags, all you have to do is check whether all 3 of these are turned on, If they are, you know the player is within the enemyís sight.

That pretty much conclude this article. If you want an example, you can download it here:
http://www.crobasoft.com/products/tutorials/Advanced_line_of_sight.zip