Possibly a new field of view algorithm
Joni Toivanen
The recent LOS [1] thread started by Mario Donick reminded me of the
field of view algorithm I developed some time ago, and I was wondering
if it was something really new, or if I just haven't seen it used before
(I had a quick look at the different FOV algorithms at roguebasin and,
at least to my understanding, none of them was similar to the one I
currently use).
I refer to the algorithm as Recursive Raycasting, as it is similar to
the usual raycasting algorithms and because my original implementation
made heavy use of recursion -- although Incremental Raycasting might be
a more accurate name. The pros of the algorithm are its simplicity and
intuitivity (I guess those are relative), quite nice field of view even
at longer radii, and an acceptable performance. Regarding simplicity: my
current C implementation is only about 100 lines of code.
The idea of the algorithm is to start from the center of the field of
view and shoot a limited number of rays away from the center, increasing
the number at each step as you get further away. The initial rays will
be shot along the diagonals/orthogonals and the new rays that are
spawned from these will have a slightly different direction. The rays
will end their journey when they are blocked by an object or when they
reach the desired radius.
For example, let's look at a ray going north from the starting point:
(use a fixed width font to view these)
ooo
x
@
('@' is the starting position, 'x' is where the ray has travelled, and
the 'o's are the directions where the ray can split on next iteration)
At this point the ray will be split in three separate rays:
o ooo o
x x x
x x x
@ @ @
Notice that the left and right rays can only continue to one direction;
I call this "locking" the rays, and it will be done to all the rays that
are split from the initial rays to restrict the paths a bit. Otherwise
you could get something like this (which isn't usually a desirable result):
x
x
x
x
x
@
This isn't all that's required for the algorithm, yet, and there are a
couple more issues to deal with, but before writing a longer description
of the algorithm (with possible pseudocode) I'd like to know if this
really is something new. I actually doubt that, because this is such a
simple variation of raycasting and rather intuitive to come up with
(I've had the idea in my head for a long time, but only recently I
bothered to actually implement it because I felt like it would be too
complex).
Finally, to give some kind of an idea of what it actually looks like,
here are two screenshots with slightly different variations of the code:
http://www.hytti.uku.fi/~jmtoivan/fov.png
http://www.hytti.uku.fi/~jmtoivan/fov2.png
(Yeah, I know they're quite awful, but I couldn't find a font with equal
height and width, so I used a space between the characters to make it
look like an actual circle... :)
The shadows aren't continuous and look somewhat ugly, but otherwise I
think it looks quite nice and I don't think many roguelikes use this
long radii in practise anyway.
Thanks for reading, and looking forward to your feedback,
Joni.
[1] A lot of people seem to use the term "line of sight", but for some
reason I prefer "field of view" instead.
zai...@zaimoni.com
> Hello, everyone!
>
> The recent LOS [1] thread started by Mario Donick reminded me of the
> field of view algorithm I developed some time ago, and I was wondering
> if it was something really new, or if I just haven't seen it used before
> (I had a quick look at the different FOV algorithms at roguebasin and,
> at least to my understanding, none of them was similar to the one I
> currently use).
>
> I refer to the algorithm as Recursive Raycasting, as it is similar to
> the usual raycasting algorithms and because my original implementation
> made heavy use of recursion -- although Incremental Raycasting might be
> a more accurate name. The pros of the algorithm are its simplicity and
> intuitivity (I guess those are relative), quite nice field of view even
> at longer radii, and an acceptable performance. Regarding simplicity: my
> current C implementation is only about 100 lines of code.
>
> The idea of the algorithm is to start from the center of the field of
> view and shoot a limited number of rays away from the center, increasing
> the number at each step as you get further away. The initial rays will
> be shot along the diagonals/orthogonals and the new rays that are
> spawned from these will have a slightly different direction. The rays
> will end their journey when they are blocked by an object or when they
> reach the desired radius.
>
This is most similar in concept to Tyrecius' Permissive Field of View
(judging from the fact that both naturally lend themselves to a
"floodfill outwards" checking of global visibility). The selection of
the new rays for Permissive Field of View does require some implicit
understanding of trigonometry at each step; I have a feeling that your
algorithm doesn't actually need that.
Also, your algorithm looks like it would exactly replicate Zaiband's
current visibility/line of fire weirdnesses (at least up close):
xxxx#
.xxx#
###@#
###x#