Sign in to follow this  
suliman

vision in tiledbased world?

Recommended Posts

hi Im doing a topdown-2d shooter. The map consists of tiles. Im asking for a fast and simple way to check if a unit can see another unit. Do i calculate the angle between looker and possible target and then check along this line every 1/2 lenght of a tile to see if there is an blocking tile (like a wall) that will hinder vision? Is there a smarter way? Thanks is advance Erik

Share this post


Link to post
Share on other sites
Short answer: Build a line segment with the first unit's position as one endpoint and the other unit's position as the other endpoint, and then check to see if it intersects any non-empty tiles. (Note that no angles are required - it can all be done using vector math.)

Also, are your tiles either entirely solid or entirely empty? Or can tiles be partially blocked and/or contain irregularly shaped obstacles?

Share this post


Link to post
Share on other sites
When I used to read about developing roguelike games the subject of line of sight algorithms would be discussed often.

Here is an example of a place that discusses this subject.

The grid ASCII world of the roguelike can definitely be extended to the 2D tile world in yr top-down shooter. The link I provided shows some example code and discussion.

Share this post


Link to post
Share on other sites
yeah i think those examples are exactely what i meant.

With angle a actually meant the "moving-speed" for checking along the line. But this is a vector i realize now:)

Tiles are either fully blocked or fully visible for now.

How long should each step be to not miss courners of tiles etc? I mean if i step too much between each check, it will not be very exact right? If i step to short there will be many checks, and with lots of units checking all the time, it might get slow.

Thanks
E

Share this post


Link to post
Share on other sites
Quote:
How long should each step be to not miss courners of tiles etc? I mean if i step too much between each check, it will not be very exact right? If i step to short there will be many checks, and with lots of units checking all the time, it might get slow.
There are no steps; you just perform single intersection tests using the line segment described previously.

Setting aside the issue of broad-phase culling for the moment, what you'll need is a ray vs. axis-aligned box intersection test. A Google search for 'ray AABB intersection' should lead you to some good references (note that the 2-d and 3-d versions of the test are basically the same, so if you happen to find example code for the 3-d test, you can easily adapt it to 2-d).

Share this post


Link to post
Share on other sites
yeah i know basically what that is and has a function for it, but there will be LOADS of boxes to test against (as the world is composed entierly of tiles). And each test does take some time.

My idea is to instead use the vector that describes the line between the two units and step through it, testing each position and simply checking if there is a blocking tile at each location. This test is superfast.

Ill try something, if it doesnt work ill get back to you guys:)

Thanks for the input
E

Share this post


Link to post
Share on other sites
Quote:
yeah i know basically what that is and has a function for it, but there will be LOADS of boxes to test against (as the world is composed entierly of tiles). And each test does take some time.

My idea is to instead use the vector that describes the line between the two units and step through it, testing each position and simply checking if there is a blocking tile at each location. This test is superfast.
What you're talking about is 'broad-phase culling', which I mentioned previously.

For this particular problem, 2D-DDA would probably be a good choice. It basically reduces to what you describe - stepping along the line and checking for intersections as you go - but it does so in a deterministic way that doesn't require any guesswork regarding the step size, and won't miss any intersections accidentally (in principle at least - there's always floating-point error to take into consideration).

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