I am currently trying to devise a good algorithm to test if point A is in line of sight of point B. It is for use in a 2D Tank game I am developing in C++ using SFML. Here is a video showing how my algorithm is currently functioning:

[media][/media]

The problem I am trying to solve is that I want many (30+) enemies to track the player's location and react accordingly when the player is in line of sight (for example, fire at the player). Therefore the alorithm needs to be quite efficent. Currently what I am doing is making a sprite at the enemy's location, then fire it towards the player's location. As the sprite moves, it samples it's current location to check if it has either collided with an obsticle (where the method returns false) or it's target (returning true). In the video, the points at which the sprite is sampling is represented by yellow dots.

I am wanting to then ask two questions: is there a more efficient way of working out line of sight? Also, if someone could check my maths that would be extreemly helpful. The tracers dont seem to hit the player's center always so I know Im calculating something wrong.

Thanks for any help you can give, Im probably getting into stuff way too complex for me. This is in fact my first game and first C++ program. Yet I still need to go on to figure out how to do A* Jump point search! Argh!

The code for working out LOS is below:

#include "stdafx.h"
#include "Pathfinder.h"
#include "Game.h"

#define PI 3.14159265

//Returns true if target is in line of sight
bool Pathfinder::LineOfSight(float startx, float starty, float endx, float endy)
{
//Load tracer image
if(!_isLoaded)
Load("images/tracer.png");
_tracer.SetPosition(startx, starty);

//Get the angle between the start and end point
float angle = GetAngle(startx, starty, endx, endy);

//Calculate movement in x y coords depending on rotation
float xvel = 1;
float yvel = 1;
if(angle >= 0 && angle < 90) //q1
{
xvel = (angle/90);
yvel = 1 - (angle/90);
}
if(angle >= 90 && angle < 180) //q2
{
xvel = 1 - ((angle - 90)/90);
yvel = 0 - ((angle - 90)/90);
}
else if(angle >= 180 && angle < 270) //q3
{
xvel = 0 - ((angle - 180)/90);
yvel = ((angle - 180)/90) - 1;
}
else if (angle >= 270 && angle < 360) //q4
{
xvel = ((angle - 270)/90) - 1;
yvel = ((angle - 270)/90);
}

float increment = 15; //Distance traveled before sampling
float error = 10; //Max error when targeting end point

//While tracer is not at goal
while(((_tracer.GetPosition().x < endx - error) ||
(_tracer.GetPosition().x > endx + error)) &&
((_tracer.GetPosition().y < endy - error) ||
(_tracer.GetPosition().y > endy + error)))
{

//Move the tracer to next sampling point
_tracer.Move(xvel*(increment), yvel*(increment));
if(_isLoaded) //Draw tracer at this location
Game::GetWindow().Draw(_tracer);

//Check if the tracer collides with a impassable
//object on the tilemap
if(Game::GetGOM().GetTileMap()->Collision(_tracer.GetPosition()))
{
return false;
}
}

return true;

}

//Get angle between two points
float Pathfinder::GetAngle(float startx, float starty, float endx, float endy)
{
float mX = endx;
float mY = endy;

mX = mX - startx;
mY = mY - starty;

return atan2(-mY,mX) * (180 / PI) + 90;
}

void Pathfinder::Load(std::string filename)
{
if(_image.LoadFromFile(filename) == false)
{
_filename = "";
_isLoaded = false;
}
else
{
_filename = filename;
_tracer.SetImage(_image);
_isLoaded = true;
}
}

sf::Sprite Pathfinder::_tracer;
sf::Image Pathfinder::_image;
std::string Pathfinder::_filename;
bool Pathfinder::_isLoaded = false;

since you are only doing a single ray testing, it's extremely easy to test line of sight.

psedo-code:

void LineOfSight(PlayerPosition, EnemyPosition){
pointA = EnemyPosition;
pointB = PlayerPosition;
for(i=0;i<NbrObstacles;i++){
//Check linexObstacle(if your using rectangle's look up linexRectangle, for all simple shapes, their's simple formula, for complex shapes, you simple loop though all the edges, and check linexPlane(in 2D, it's basically linexline collision).)
if(IntersectionWithObstacleI) PointB = Intesect location; //(if we just care if the other tank can't see the player, you could return false for a line of sight function here.
}
return PointB==PlayerPosition?1:0;
}


that's the jist of it, for line of sight with cones/complex vision's, then it gets quite a bit more complicated.

Yep, ray casting is definitely the way to go. Since you're just doing ray/bounding-box checks it should be easy to implement and very fast.

Thanks for the help guys, I had a feeling I was overcomplicating the problem! I wasnt sure how ray casting was implemented so that pseudo-code is very useful. Ill give it a shot in the near future, using this answer for the line rectangle intersection logic: http://stackoverflow.com/questions/99353/how-to-test-if-a-line-segment-intersects-an-axis-aligned-rectange-in-2d

On another note, can any of you point me to a easy to understand guide on A* Jump point search? Seems the most efficient method for working out the enemy's path to the player. But I could be wrong, how else would you work that out in this scenario? (bearing in mind the path should be constantly recalculated as the player moves).

Thanks for the help guys, I had a feeling I was overcomplicating the problem! I wasnt sure how ray casting was implemented so that pseudo-code is very useful. Ill give it a shot in the near future, using this answer for the line rectangle intersection logic: http://stackoverflow...-rectange-in-2d

On another note, can any of you point me to a easy to understand guide on A* Jump point search? Seems the most efficient method for working out the enemy's path to the player. But I could be wrong, how else would you work that out in this scenario? (bearing in mind the path should be constantly recalculated as the player moves).

Jump point search?

i'm not certain if your asking for a specefic A* algorithm, or asking for a tutorial on A* in general. if it's the latter, http://www.policyalmanac.org/games/aStarTutorial.htm <-- a great starting place for A* imo, and taught me pretty much what i needed to know when i started learning A*.

Ive read that and its simple to understand, but for what Im trying to do pure A* is simply too costly. For a rundown on jump point search read http://harablog.wordpress.com/2011/09/07/jump-point-search/ which gives a quick overview on it. It seems to be a lot faster version of A*.

i'll take a look at your link, seems very interesting. on a side note, i'd also suggest looking at binary heaps if A* is proving to be slow. I've found that this is an excellent method for speeding up A* 10 fold without having to do much other work. Their's a handy link to the implementation in the tutorial i posted earlier.

anywho, i'll chime back in once i've read and understand the article you've linked to.

A* is not too slow.

A particular implementation may make some trivial ease-of-programming tradeoffs that sacrifice huge amounts of speed, but fundamentally, the algorithm is not the problem. I've written A* implementations that can search hundreds of thousands of nodes in a handful of milliseconds; if that's not fast enough, you probably have some major opportunities for optimizing your design.

Personally, I've found that the fastest line of sight algorithm is Bresenham's line plotting algorithm since it's completely based on integers.

That's... somewhat akin to saying that wine is the most flavorful beverage because it's completely based on grapes.

It's also patently false.



A 2D ray/box intersection is a trivial algorithm, even for non-axis-aligned boxes:

- For each edge
- Check if the ray is parallel to the edge; if so, skip to the next edge
- Compute the intersection point of the ray and the infinite line along which the edge lies
- If the intersection lies outside the endpoints of the edge, skip to the next edge
- Otherwise, return a positive collision
- If you get this far, return negative

This is, in the worst case:

- Four conditionals for parallel checks
- A handful of additions and divisions

This can even be unrolled so it doesn't even include a loop, making it ideal for CPUs that don't do good branch prediction or have generally superscalar behavior and can compute faster in unrolled circumstances - i.e. most CPUs these days.


By contrast, consider Bresenham:

- At minimum a loop
- Two additions and four conditionals (eight if you want to be pedantic) per iteration of the loop
- If you do this in entirely integer math, it's even harder, so you're kind of screwed; good line marching algorithms at least are fixed-point
- Non-deterministic running time depending on the distance between the ray origin and the object
- Additional overhead for bounds/sanity checks
- Additional overhead for directional checks so you don't march away from the target infinitely before giving up


By the time you optimize a line marching algorithm - Bresenham or otherwise - to not do really silly things, you're basically duplicating a ray/box check anyways, and might as well just write the simpler code.


If that was overly technical, consider this case:

- A ray originating 5 million units from the bounding box you wish to test

A ray/box test can solve this in basically constant time. Naive Bresenham needs at least 5 million iterations. Now, point the ray the opposite direction (i.e. so it never hits the box at all) and you have an even more pathological scenario.