Jump to content

  • Log In with Google      Sign In   
  • Create Account


Efficient Line of Sight Algorithm


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
16 replies to this topic

#1 longshorts   Members   -  Reputation: 106

Like
0Likes
Like

Posted 12 April 2012 - 02:02 PM

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:

http://www.youtube.com/watch?v=Qwv_c1Oc78w

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;


Sponsor:

#2 slicer4ever   Crossbones+   -  Reputation: 2607

Like
1Likes
Like

Posted 12 April 2012 - 02:22 PM

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.
Check out https://www.facebook.com/LiquidGames for some great games made by me on the Playstation Mobile market.

#3 ApochPiQ   Moderators   -  Reputation: 12431

Like
1Likes
Like

Posted 12 April 2012 - 02:25 PM

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.

#4 longshorts   Members   -  Reputation: 106

Like
0Likes
Like

Posted 12 April 2012 - 03:33 PM

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

#5 slicer4ever   Crossbones+   -  Reputation: 2607

Like
0Likes
Like

Posted 12 April 2012 - 07:14 PM

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*.
Check out https://www.facebook.com/LiquidGames for some great games made by me on the Playstation Mobile market.

#6 longshorts   Members   -  Reputation: 106

Like
0Likes
Like

Posted 12 April 2012 - 07:48 PM

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

#7 slicer4ever   Crossbones+   -  Reputation: 2607

Like
0Likes
Like

Posted 12 April 2012 - 08:03 PM

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.
Check out https://www.facebook.com/LiquidGames for some great games made by me on the Playstation Mobile market.

#8 ApochPiQ   Moderators   -  Reputation: 12431

Like
2Likes
Like

Posted 12 April 2012 - 08:05 PM

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.

#9 ssrun   Members   -  Reputation: 152

Like
-2Likes
Like

Posted 12 April 2012 - 09:23 PM

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

#10 ApochPiQ   Moderators   -  Reputation: 12431

Like
1Likes
Like

Posted 12 April 2012 - 10:26 PM

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.

#11 ApochPiQ   Moderators   -  Reputation: 12431

Like
0Likes
Like

Posted 12 April 2012 - 10:57 PM

I will concede, though, that if you are:

- In a regular 2D grid (op: check)
- Using only perfectly grid-aligned obstacles (op: bzzzt, nope, tanks are not grid-aligned)
- Populating a majority of the grid cells with obstacles (op: bzzzt, nope)
- Casting fewer LOS checks than obstacles by an order of magnitude (op: bzzzt, nope)

You might be able to win out with a line marching algorithm. But outside of that contrived scenario, spatial partitioning and ray casting will almost certainly be faster, and will most certainly be more robust and flexible. If you do geometry coalescing so that a single long rectangular wall is one rect instead of an obstacle in each grid cell, you get even better gains using ray casting, and as soon as you no longer have perfectly-grid aligned obstacles you can forget getting 100% accurate results from a line march algorithm.

#12 lawnjelly   Members   -  Reputation: 429

Like
0Likes
Like

Posted 14 April 2012 - 03:31 PM

Don't know if anyone has mentioned it yet .. the fastest way to determine line of sight is to precalculate it.

Three most important rules in game programming - precalculate, precalculate and precalculate. Posted Image

If you are using a smallish grid like that you can easily generate a PVS (potentially visible set) of what other cells are potentially visible from each cell. This greatly cuts down on the checks you need to do.

e.g. if enemy 1 is in cell 20, 24 and your pvs tells you that the cell your player is in 90.34 is not visible from there due to a wall in the way, that's it, you know it's not in sight. You only end up needing to do realtime checks for dynamic objects that might get in the way.

#13 slicer4ever   Crossbones+   -  Reputation: 2607

Like
0Likes
Like

Posted 14 April 2012 - 06:11 PM

Don't know if anyone has mentioned it yet .. the fastest way to determine line of sight is to precalculate it.

Three most important rules in game programming - precalculate, precalculate and precalculate. Posted Image

If you are using a smallish grid like that you can easily generate a PVS (potentially visible set) of what other cells are potentially visible from each cell. This greatly cuts down on the checks you need to do.

e.g. if enemy 1 is in cell 20, 24 and your pvs tells you that the cell your player is in 90.34 is not visible from there due to a wall in the way, that's it, you know it's not in sight. You only end up needing to do realtime checks for dynamic objects that might get in the way.


while i agree for more complex scenarios, pre-calculating line of sight would be beneficial. In the scenario the OP has described, i find it doubtful he'll need to pre-calculate the line of sight for any serious performance gains. as well, creating a grid based PVS with objects that arn't locked to the grid, their's the small possibility that valid line of sight's could be missed with this method.
Check out https://www.facebook.com/LiquidGames for some great games made by me on the Playstation Mobile market.

#14 leopardpm   Members   -  Reputation: 148

Like
0Likes
Like

Posted 14 April 2012 - 11:10 PM

Don't know if anyone has mentioned it yet .. the fastest way to determine line of sight is to precalculate it.

Three most important rules in game programming - precalculate, precalculate and precalculate. Posted Image

If you are using a smallish grid like that you can easily generate a PVS (potentially visible set) of what other cells are potentially visible from each cell. This greatly cuts down on the checks you need to do.

e.g. if enemy 1 is in cell 20, 24 and your pvs tells you that the cell your player is in 90.34 is not visible from there due to a wall in the way, that's it, you know it's not in sight. You only end up needing to do realtime checks for dynamic objects that might get in the way.

sorry, but my simplistic mind is a bit confused here... to 'pre-calc' LOS for a 10 x 10 grid would necessitate storing a 10x10 table for EACH location (100 locations)... or am I missing something here? Perhaps I am overly paranoid about memory usage. Of course, there are a variety of ways to start pruning this memory usage down, for instance eliminating redundant pairs: if loc (1,1) can see loc (5,3) then no need to also store the fact that (5,3) can also see loc (1,1) - that alone will reduce memory usage by half.

Did I misunderstand the whole pre-calc thing or what?

#15 lawnjelly   Members   -  Reputation: 429

Like
0Likes
Like

Posted 15 April 2012 - 04:19 AM

Yeah, sorry that's posting when tired lol.

Sure to do it you have to partition space into something reasonable memory wise. Whether you can use your grid directly depends how big your maps are. Your screen there looks to be about 20x20 so let's use that for an example:

20x20 = 400 bits per grid square for a naive PVS = 50 bytes

then 50 bytes x 400 grid squares = 20000 bytes, so under 20K, so not that memory hungry.

That's very naive though .. you can also cut this by half if your PVS is reciprocal (i.e. if you can't see 40,40 from 20, 20, then you also know that you can't see 20, 20 from 40,40)

You could also use RLE if memory really was a problem (although the cost of decompressing this probably wouldn't be worth it unless you have a complex environment lol).

Then other ways is to use different partitioning for your space. If for example you used a 10x10 grid for the PVS instead of 20x20, that quarters the memory size. Or use a 2d BSP tree maybe, not sure. Grid sounds more tempting, if you keep it small.

As to how to handle the case of tanks being in different 'parts' of the gridsquare, and the visibility being 1 in some parts and 0 in others, just mark it as invisible ONLY when there are no parts of the grid squares that are visible to each other.

Then if it is marked as potentially visible, do a runtime check. For enemy AI often you can afford to be lazy about this, and there's no reason you need to do vis checks every frame. You could also store 3 (or 4) states in the PVS, instead of just 2 - i.e. definitely not visible, maybe visible, definitely visible, that way you only have to do runtime checks in say 2% of the grid squares.

Given that your current grid is only using 20K, I'd be tempted to just increase the resolution of the PVS grid by about 5x and then just go with the definitely visible / definitely invisible approach, and forego the accuracy.

For a BSP tree you may be able to be more exact than this.

You don't even need to use a BSP tree .. you could use something as simple as AA bounding boxes and probably still get a decent result, the only limit is your imagination! Posted Image

And this is pretty much one of the simplest situations for using a PVS. There are some really good solutions in 3d for far more complex environments (see quake stuff using BSP and PVS, or portal engines, etc etc). If you do some googling you should get some good ideas.

#16 lawnjelly   Members   -  Reputation: 429

Like
0Likes
Like

Posted 15 April 2012 - 04:45 AM

Forgot to mention, you can also precalculate your A* pathfinding too. Posted Image But it won't take account of dynamic obstacles, you'd need to cope with that separately.

This is in fact my first game and first C++ program.


Sorry, just read this .. in this case I'd stick to the simple stuff as dealing with the special cases in visibility determination can be quite tricky. But feel free to have a google as it's really interesting stuff and the kind of thing that most professional games use, as they have to determine visibility (mainly for deciding what to draw) really quickly, on really complex environments.

Awesome effort for your first go! :D

#17 Steadtler   Members   -  Reputation: 220

Like
0Likes
Like

Posted 20 April 2012 - 06:40 PM

You seem to be in 2d. If you just build a simplified representation of your space (navmesh, or since you seem to be grid-based a quadtree) should make your line of sight checks negligible. There is no reason you shouldnt be able to do hundreds of those every frame.

Also, looking at your original code up there, it seems you're working in polar coordinates (angle/distance). Believe my experience when I say its evil. Work with vector algrebra.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS