Efficient Line of Sight Algorithm

This topic is 2430 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

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;

Share on other sites
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.

Share on other sites
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.

Share on other sites
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).

Share on other sites

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*.

Share on other sites
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*.

Share on other sites
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.

Share on other sites
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.

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

Share on other sites
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 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.

1. 1
2. 2
Rutin
21
3. 3
4. 4
5. 5
A4L
14

• 13
• 26
• 10
• 11
• 9
• Forum Statistics

• Total Topics
633736
• Total Posts
3013602
×