Fast LOS algorithm
cmiller
fast solution for raycasting LOS. In fact, I can't think of anything
that would be more efficient for a tile-based game.
The full description (including animations) is here:
http://www.geocities.com/temerra/los_rays.html
It's hosted on a Geocities site at the moment, but it would be great
if people could host it if it seems useful (full page and attribution
please.)
cheers
C Miller
The Wicked Flea
> Not sure if this algorithm is well-known or not, but I have a very
> fast solution for raycasting LOS. In fact, I can't think of anything
> that would be more efficient for a tile-based game.
> cheers
> C Miller
That is very interesting. I am planning to write a roguelike, I can't
not do it now I guess, and it will implement basic geometry with some
height to it. For instance a "layer" system that lets a person design
a level like a castle with ramparts above it; when inside you could
see it, but not before. And thus you couldn't see out either.
However I have one little dilemma... how would I extend this algorithm
into a limited height playing field? For an example I'm _planning_ on
no more than three levels at the moment. Think of it like a blueprint
where you only know what the floor and walls for a given level/floor
is like and there are an unknown number up and down.
Any suggestions or demonstrations on how to extend the algorithm that
way?
cmiller
> where you only know what the floor and walls for a given level/floor
> is like and there are an unknown number up and down.
>
> Any suggestions or demonstrations on how to extend the algorithm that
> way?
Hmm, not too sure I understand what you mean. If you're on a
particular level/floor then you can do everything in 2D as explained
in the article i.e. you only search the X and Y axes. If the agent
also needs to look up and down (e.g. X-Com/UFO world) then you also
search the Z axis - there's a quick explanation near the end of the
article.
You can model floors by either ignoring the Z-axis when indoors or
simply ensuring there is a layer of obscure nodes between floors.
MrBudgens
This seems a very efficient way of calculating LOS, but I am having trouble understanding the algorithm.
Firstly:
"Because we stepped in the X direction, we adjust the data to suit: the X value drops by the vector Y, and the Y value increases by the vector Y. Or rather, since we moved in the X direction, our propensity to move further in the X direction is reduced, and our propensity to move in the Y direction is increased (by the amounts needed to follow the ray)."
I don't follow the logic of this - why is the vector's Y-value used to modify BOTH of the values? Just what do the numbers represent? The description says "The numbers on the right represent the offset from the obstruction vector" but it is hard to see exactly what that means. In the example shown, position (4,1) is given an obstructionn vector of (3,1) and an error value of (2,2). What do these numbers represent? The error value is especially confusing as it is not (0,0) on the exact location of an obstruction - so what is the error here?
Secondly, I'm not sure how one calculates whether a particular square is visible or not. How are the numbers used to determine this? Also, in the animations shown what do the pink colours represent? Are these squares completely invisible? What about the lighter pink colours?
As a final point related specifically to roguelikes, this method would not necessarily be suitable for games where diagonal movement is allowed between squares as shown in the example. In nethack, if the player stood in square (2,1) he would be able to see through to (3,2) and beyond. Obviously this is not a flaw in the algorithm, but something to be borne in mind if using this in a roguelike.
Many thanks,
MrBudgens
cmiller
> I don't follow the logic of this - why is the vector's Y-value used to modify BOTH of the values? Just what do the numbers represent? The description says "The numbers on the right represent the offset from the obstruction vector" but it is hard to see exactly what that means. In the example shown, position (4,1) is given an obstructionn vector of (3,1) and an error value of (2,2). What do these numbers represent? The error value is especially confusing as it is not (0,0) on the exact location of an obstruction - so what is the error here?
I was actually going to call the error/offset data "proximity" data
instead - this is something I still haven't made up my mind about.
It's perhaps better named "proximity", but on the other hand it *is*
error data, and people understand what error data is.
When we expand, we need to remember the obstruction vector data (which
is why 4,1 gets the obstruction vector 3,1 -> it is expanded from
3,1), and we adjust the error data. If the error is too great, we
don't copy anything (too far away from the shadow).
How you represent the error is entirely up to you - and yes my method
is weird, you could start yours from 0,0 if you wanted. In 2D you can
even represent it as one int, positive for X movement, negative for Y
movement, but I have two numbers because I want the sample code to be
in roughly canonical form for extending to 3D.
I'll work on clarifying this stuff soon.
> Secondly, I'm not sure how one calculates whether a particular square is visible or not. How are the numbers used to determine this? Also, in the animations shown what do the pink colours represent? Are these squares completely invisible? What about the lighter pink colours?
I have a function in the code which you can download (it's very
simple, clean code) which is part of the node (RayData) class. Of
course, it relates directly to my error values so it may make equal
sense to you. It currently classes a node as obscure if it has either
X or Y "error" greater than zero and less than max. I think I might be
doing a bit much work here, since previous implementations of mine
didn't require the less-than part.
Pink colours are obscure nodes that were checked. These may include
the nodes that aren't expanded (ignored nodes), which is why the pink
shadows are extra thick around arcs. Lighter pink colours are not
obscure, but they are carrying some obscurity information.
> As a final point related specifically to roguelikes, this method would not necessarily be suitable for games where diagonal movement is allowed between squares as shown in the example. In nethack, if the player stood in square (2,1) he would be able to see through to (3,2) and beyond. Obviously this is not a flaw in the algorithm, but something to be borne in mind if using this in a roguelike.
I think it can be adapted to allow for diagonal vision, though it
requires technically saying that an obscure node is not completely
obscure. Off the top of my head, we would allow for this by changing
our conditions for cutting nodes to check whether the node itself is
directly obscured.
Kenneth 'Bessarion' Boyd
> cmiller wrote:
> > Not sure if this algorithm is well-known or not, but I have a very
> > fast solution for raycasting LOS. In fact, I can't think of anything
> > that would be more efficient for a tile-based game.
> >
> > The full description (including animations) is here:
> >
> > http://www.geocities.com/temerra/los_rays.html
> >
> > It's hosted on a Geocities site at the moment, but it would be great
> > if people could host it if it seems useful (full page and attribution
> > please.)
> >
> > cheers
> > C Miller
> >
>
>
> This seems a very efficient way of calculating LOS, but I am having trouble understanding the algorithm.
Actually, this is the second algorithm based on updating blocked lines of sight
in realtime posted here. The first one has been refined a bit; the current
summary is at
http://roguebasin.roguelikedevelopment.org/index.php?title=Permissive_Field_of_View
cmiller
> in realtime posted here. The first one has been refined a bit; the current
Yes, this algorithm would be in that class of algorithms (Permissive
Field of View). Hard to say whether this one offers many advantages
over the others. It's probably most similar to the shadowcasting
Spiral Path FOV, except permissive.
Kenneth 'Bessarion' Boyd
> > Actually, this is the second algorithm based on updating blocked lines of sight
> > in realtime posted here. The first one has been refined a bit; the current
> > summary is athttp://roguebasin.roguelikedevelopment.org/index.php?title=Permissive...
>
> Yes, this algorithm would be in that class of algorithms (Permissive
> Field of View). Hard to say whether this one offers many advantages
> over the others.
Yours actually looks generalizable to a three-dimensional grid. I wasn't able
to quickly do this for the first implementation, as it was too tightly
integrated with angle measure (and as such actually could be adapted to 2D
continuum space).
> It's probably most similar to the shadowcasting Spiral Path FOV, except permissive.
Yes, that was my impression as well. (Spiral-path has a tedious but routine
generalization to n-dimensional spaces.)
Björn Ritzl
It would be great if you could post it to roguebasin
(roguebasin.roguelikedevelopment.org)
>
> cheers
> C Miller
BR,
Björn
Ray Dillinger
> Yes, that was my impression as well. (Spiral-path has a tedious but routine
> generalization to n-dimensional spaces.)
Really? I invented spiral-path fov, and I didn't know that.
How does it work??
Bear
The Wicked Flea
Mmmm... close but not exactly what I meant. I want to know, from a
certain location where I can see through those vertical levels. For
instance in a modern FPS game a sniper takes the high ground so he/she
has a good view of the battlefield. Now, if that high ground happens
to be the top of a partially constructed building he has to look down
through, around, and over then how would that affect his FOV
*downwards*? Likewise, someone hunting said sniper would have their
FOV obscured *upwards* because of the terrain ... but the sniper would
still be visible unless they were hiding. I am guessing I'd have to
create a "partial visibility" flag for things between Z layers so that
you could still see and counterattack a sniper on a building because
it wouldn't be an X-COM style "swtich" between layers of a level.
Because this FOV method is a little advanced for me, someone who
hasn't played with LOS/FOV before, what you've put at the end of the
article is more a teaser than a help. I could probably fake what I
want by using a limited ray-casting system for parts, and using the
NULL tiles of the layer above or below plus a little "fuzzy" range
from it to control what would be visible.
-- Flea
Kenneth 'Bessarion' Boyd
In two dimensions, I find spiral-path traversal is a mnemonic for the
following:
* Start: put the 4 squares corresponding to their basis directions and their
inverses on the queue. [Generalization to n-d: 2n basis vectors]. Manhattan
distance i.e. Lesbegue-1 i.e. L1 distance from center: 1. (In any case, the sum
of absolute values of coordinates, taking the source as origin with all
coordinates 0.)
* When dequeuing a square with L1 distance n from the origin, mark it as lit;
then, if not opaque, pass light to squares with L1 n+1 that are adjacent to it
and enque new squares getting light. Squares need to be enqueued if and only if
they started with no light.
Since no square with L1 distance n+1 will be dequeued until all squares with L1
distance n have been dequeued, all light that will reach the square will be
accounted for. Tracking the polygons of illumination (whose corners are morally
n-1 dimensional points whose elements are angles) is somewhat intricate,
although there are ways to avoid taking inverse trig functions.
Kenneth 'Bessarion' Boyd
Spiral-path fov is a specific way of guaranteeing that squares with Manhattan
distance i.e. Lesbesgue-1 distance i.e. L1 distance n [sum of absolute value of
coordinates] are all dequed (with light passed through to squares at L1 distance
n+1, squares with no prior light enqued, etc.) before any squares with L1
distance n+1 are dequed.
For the N-d case:
* There are 2n squares with L1 distance 1, indexed by the basis vectors and
their additive inverses.
* Light bounds are represented by n-1 dimensional polygons (projections of the
square faces) whose points have angle coordinates.
Macoln
wrote:
I'd really like to see a more detailed description of spiral path for
the truly geometry/trigonometry-dumb, i.e. what kind of things need to
be calculated as you go around queuing and de-queuing cells. Oh, and
not in C or pseudocode either, but English!
Kenneth 'Bessarion' Boyd
> I'd really like to see a more detailed description of spiral path for
> the truly geometry/trigonometry-dumb, i.e. what kind of things need to
> be calculated as you go around queuing and de-queuing cells. Oh, and
> not in C or pseudocode either, but English!
May I assume you have already read the authoritative description at
http://www.roguelikedevelopment.org/php/article/showArticle.php?path=development/LOS/articles/&article=Spiral%20Path%20FOV%20-%20Ray%20Dillinger.txt
?
Ray Dillinger
> Spiral-path fov is a specific way of guaranteeing that squares with Manhattan
> distance i.e. Lesbesgue-1 distance i.e. L1 distance n [sum of absolute value of
> coordinates] are all dequed (with light passed through to squares at L1 distance
> n+1, squares with no prior light enqued, etc.) before any squares with L1
> distance n+1 are dequed.
It actually gets a lot less finicky to code in 2-d (eg, not caring
if the order is actually a spiral) if you use two queues (one for
each "active" manhattan distance), and just don't go to the next
until all the ones at the current distance are done, doesn't it?
I mean, it "wastes" space, but it's easier to get correct.
I kept getting tangled when I wanted to move it to 3-d because I
couldn't visualize a traversal order that would satisfy the invariant
the way a spiral does for 2-d. But you're right, here: you actually
don't need to do that. Just maintain separate queues for the "current"
and "next" manhattan distance, and that constraint goes away.
>
> For the N-d case:
> * There are 2n squares with L1 distance 1, indexed by the basis vectors and
> their additive inverses.
> * Light bounds are represented by n-1 dimensional polygons (projections of the
> square faces) whose points have angle coordinates.
Okay, I can see that, sort of.... light passes into a cube above and
northeast of the origin, through its bottom, south, and west faces,
so you get a sort of squashed hexagon as your unimpeded light passage,
degenerating to squares if the cubes are along an axis.
But your impeded light passage (ie, where the cube didn't get all the
light it could have gotten) has a more complex shape because it can be
cut by the shadow of another cube. You have to do some more complex
geometry than just keeping track of minimum and maximum lit angles to
find the shape that's the union of the light that got passed in,
before you can pass it out. Not "hard" geometry; just more complex.
Bear
Kenneth 'Bessarion' Boyd
> Kenneth 'Bessarion' Boyd wrote:
>
> > Spiral-path fov is a specific way of guaranteeing that squares with Manhattan
> > distance i.e. Lesbesgue-1 distance i.e. L1 distance n [sum of absolute value of
> > coordinates] are all dequed (with light passed through to squares at L1 distance
> > n+1, squares with no prior light enqued, etc.) before any squares with L1
> > distance n+1 are dequed.
>
> It actually gets a lot less finicky to code in 2-d (eg, not caring
> if the order is actually a spiral) if you use two queues (one for
> each "active" manhattan distance), and just don't go to the next
> until all the ones at the current distance are done, doesn't it?
> I mean, it "wastes" space, but it's easier to get correct.
Yes.
I don't see a material space wastage from two queues instead of one, at least on
relatively modern hardware. Any reasonable queue implementation should have
o(1) swap time. You might even get some space savings as there's one less
excuse to store the manhattan distance with the square. Even if the time cost
of recomputation was unacceptable, it could be managed as a global attribute of
the current queue.
> I kept getting tangled when I wanted to move it to 3-d because I
> couldn't visualize a traversal order that would satisfy the invariant
> the way a spiral does for 2-d. But you're right, here: you actually
> don't need to do that. Just maintain separate queues for the "current"
> and "next" manhattan distance, and that constraint goes away.
>
> >
> > For the N-d case:
> > * There are 2n squares with L1 distance 1, indexed by the basis vectors and
> > their additive inverses.
> > * Light bounds are represented by n-1 dimensional polygons (projections of the
> > square faces) whose points have angle coordinates.
>
> Okay, I can see that, sort of.... light passes into a cube above and
> northeast of the origin, through its bottom, south, and west faces,
> so you get a sort of squashed hexagon as your unimpeded light passage,
> degenerating to squares if the cubes are along an axis.
Yes, in the 3-d case. Your comments about the complexity of the light geometry
are also true in general.
Macoln
wrote:
> On 2007-11-05 07:29:50, Macoln <mr.gao...@gmail.com> wrote:
>
> > I'd really like to see a more detailed description of spiral path for
> > the truly geometry/trigonometry-dumb, i.e. what kind of things need to
> > be calculated as you go around queuing and de-queuing cells. Oh, and
> > not in C or pseudocode either, but English!
>
> ?
Yep, but I'm not sure how to calculate the angles, or what angles to
calculate and all that. Also, I'm not clear what it means by opaque...
Kenneth 'Bessarion' Boyd
> On 11 5 , 10 51 , Kenneth 'Bessarion' Boyd
> wrote:
> > On 2007-11-05 07:29:50, Macoln wrote:
> >
> > > I'd really like to see a more detailed description of spiral path for
> > > the truly geometry/trigonometry-dumb, i.e. what kind of things need to
> > > be calculated as you go around queuing and de-queuing cells. Oh, and
> > > not in C or pseudocode either, but English!
> >
> > May I assume you have already read the authoritative description athttp://www.roguelikedevelopment.org/php/article/showArticle.php?path=...
> > ?
>
> Yep, but I'm not sure how to calculate the angles, or what angles to
> calculate and all that. Also, I'm not clear what it means by opaque...
Or whether to calculate the angles at all :)
Opaque squares do not pass light, thus do not cause processing (enqueuing,
etc.); they are simply visible when illuminated.
As for the angles: English is the hardest way to explain it. I'll just
illustrate some key cases. All of this follows from the authoritative
description, other than the choice of how to represent angles.
We want the angles corresponding to the arctangent of the corners of the square,
relative to the origin/viewpoint. However, we don't actually need to calculate
the arctangent. For a pure integer representation, note that the corners of the
squares are all odd multiples of 1/2. So, if we multiply everything by two, the
corners are all pairs of odd integers.
Let's take the origin square as an example. It has four corners:
* ( 0.5, 0.5) [represent as ( 1, 1)]
* ( 0.5, -0.5) [represent as ( 1,-1)]
* (-0.5, 0.5) [represent as (-1, 1)]
* (-0.5, -0.5) [represent as (-1,-1)]
While actually using the arctangent function (e.g., C library arctan2(x,y)) is
asking for roundoff error, we aren't actually reusing the values...it merely is
bloat to call it. In this case, arctan2 should return, within machine rounding
error:
* ( 0.5, 0.5) [represent as ( 1, 1)]: pi/4
* ( 0.5, -0.5) [represent as ( 1,-1)]: 3pi/4
* (-0.5, 0.5) [represent as (-1, 1)]: -3pi/4
* (-0.5, -0.5) [represent as (-1,-1)]: -pi/4
Then, we check whether the following squares pass light, or do not pass light
(opaque):
* ( 1, 0): try to pass light through [arctan2( 1,-1), arctan2( 1, 1)]
* ( 0, 1): try to pass light through [arctan2( 1, 1), arctan2(-1, 1)]
* (-1, 0): try to pass light through [arctan2(-1, 1), arctan2(-1,-1)]
* ( 0,-1): try to pass light through [arctan2(-1,-1), arctan2( 1,-1)]
I'm thinking of these intervals as going counterclockwise. Order *does* matter
here.
In all cases, the square is visible. If the target square is opaque, that's it.
Otherwise, enqueue it (none of these squares already have light), and record
the interval passing light into it.
Let's suppose (1,0) and (0,1) pass light, but (-1,0) and (0,-1) are opaque. Let
us also suppose that (1,1) and (-1,1) both pass light. Considering the
processing of (1,0), the corners are:
* (1.5, 0.5) [represent as (3, 1)]
* (1.5, -0.5) [represent as (3,-1)]
* (0.5, 0.5) [represent as (1, 1)]
* (0.5, -0.5) [represent as (1,-1)]
Spiral-path says that (1,0) passes light to the following squares in this
order:
* (1,-1): try to pass light through [arctan2(1,-1),arctan2(3,-1)]
* (2, 0): try to pass light through [arctan2(3,-1),arctan2(3, 1)]
* (1, 1): try to pass light through [arctan2(3, 1),arctan2(1, 1)]
So they're all visible. No light yet, so enqueue and record intervals being
illuminated by.
Note: the ordered union of the three angle-intervals we are trying to pass light
from, is simply the angle-interval we passed light into (1,0) from.
Considering the processing of (0,1), the corners are:
* ( 0.5, 1.5) [represent as ( 1,3)]
* ( 0.5, 0.5) [represent as ( 1,1)]
* (-0.5, 1.5) [represent as (-1,3)]
* (-0.5, 0.5) [represent as (-1,1)]
Spiral-path says that (0,1) passes light to the following squares in this
order:
* ( 1,1): try to pass light through [arctan2( 1,1), arctan2( 1,3)]
* ( 0,2): try to pass light through [arctan2( 1,3), arctan2(-1,3)]
* (-1,1): try to pass light through [arctan2(-1,3), arctan2(-1,1)]
But...(1,1) already *has* light, it does not need enqueueing. We update the
interval of illumination. It now is getting light from both [arctan2(3,
1),arctan2(1, 1)] and [arctan2( 1,1), arctan2( 1,3)]. The union of these
angle-intervals is [arctan2(3, 1), arctan2( 1,3)] (just glue the right-hand
endpoint to the left-hand endpoint).
(-1,1) gets light and is enqueued, but since (-1,0) is opaque it gets
illumination only from [arctan2(-1,3), arctan2(-1,1)].
At some point, (-1,1) will be dequeued and processed. The corners are:
* (-0.5, 1.5) [represent as (-1,3)]
* (-0.5, 0.5) [represent as (-1,1)]
* (-1.5, 1.5) [represent as (-3,3)]
* (-1.5, 0.5) [represent as (-3,1)]
Spiral-path says (-1,1) passes light to the following squares in this order:
* (-1,2): try to pass light through [arctan2(-1,3),arctan2(-3,-3)]
* (-2,1): try to pass light through [arctan2(-3,-3),arctan2(-3,-1)]
[Observe that a working arctan2 has arctan2(-1,-1)=arctan(-3,-3); it is
permissible to divide out the least common multiple before calculating.]
But...(-1,1) only got light from [arctan2(-1,3), arctan2(-1,1)] A singleton
interval is not enough to pass light in spiral-path, so (-2,1) gets no light
from (-1,1). (-1,2) does get light, and is processed with the interval of
illumination [arctan2(-1,3),arctan2(-3,-3)]. (If it was already illuminated, the
interval of illumination is updated as usual.)
Ray Dillinger
> Yep, but I'm not sure how to calculate the angles, or what angles to
> calculate and all that. Also, I'm not clear what it means by opaque...
Okay ... the point of origin is the center of the square the
character is standing on.
The angle "zero" is the line that goes straight along the
X axis.
The angles you want to calculate for all squares are the
angles between "zero" and the line from the origin to each
corner of that square.
Calculating angles is basic trigonometry - and looking it up
in a reference in your own language is likely to do more good
than me trying to explain it in English.
"Opaque" is a word that means light can't pass through it.
If a square is opaque, that means that if light is passed to
it, it is visible - but it doesn't pass light to the squares
beyond.
Bear