• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
longshorts

Efficient Line of Sight Algorithm

16 posts in this topic

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]http://www.youtube.com/watch?v=Qwv_c1Oc78w[/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:

[code]#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;[/code]
0

Share this post


Link to post
Share on other sites
since you are only doing a single ray testing, it's extremely easy to test line of sight.

psedo-code:
[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;
}
[/code]

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

Share this post


Link to post
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).
0

Share this post


Link to post
Share on other sites
[quote name='longshorts' timestamp='1334266402' post='4930710']
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: [url="http://stackoverflow.com/questions/99353/how-to-test-if-a-line-segment-intersects-an-axis-aligned-rectange-in-2d"]http://stackoverflow...-rectange-in-2d[/url]

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).
[/quote]

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, [URL]http://www.policyalmanac.org/games/aStarTutorial.htm[/URL] <-- a great starting place for A* imo, and taught me pretty much what i needed to know when i started learning A*.
0

Share this post


Link to post
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*.
0

Share this post


Link to post
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.
0

Share this post


Link to post
Share on other sites
A* is not too slow.

A particular [i]implementation[/i] 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.
2

Share this post


Link to post
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.
-2

Share this post


Link to post
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 [b]minimum[/b] 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.
1

Share this post


Link to post
Share on other sites
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 [b]most[/b] 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.
0

Share this post


Link to post
Share on other sites
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. [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]

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

Share this post


Link to post
Share on other sites
[quote name='lawnjelly' timestamp='1334439060' post='4931269']
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. [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]

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.
[/quote]

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

Share this post


Link to post
Share on other sites
[quote name='lawnjelly' timestamp='1334439060' post='4931269']
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. [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]

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.
[/quote]
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?
0

Share this post


Link to post
Share on other sites
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! [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]

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

Share this post


Link to post
Share on other sites
Forgot to mention, you can also precalculate your A* pathfinding too. [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] But it won't take account of dynamic obstacles, you'd need to cope with that separately.

[quote]This is in fact my first game and first C++ program.[/quote]

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
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0