FOV algorithm demonstration

[sokol815]

I was not satisfied with the naive FOV algorithm I was using for my current RL development in javascript, so I rummaged around the roguebasin wiki and found an article titled Pre-Computed Visibility Tries. This is very similar to something I had done a little work on about 5 years ago, but hadn't gotten results I liked... so I thought I would attempt again. My last attempt involved casting rays to the perimeter of the circle instead of to the edges of a box containing the circle. This is a very subtle, but important difference. (The article explains the difference in full, so I will leave that as an exercise to the reader)

The naive algorithm, which this is replacing, involved dividing a circle into arcs of a small size. (I think I was using about 1 degree arcs), then using the obtained deltaX/deltaY from cos/sin to simulate a light beam until it reached the length of the sight radius, or hit something and died. This method was extremely expensive, requiring about 18ms to complete even when in relatively enclosed spaces. Only because it was a turn-based roguelike was it usable.

I have finished implementation of the new algorithm and found it runs at < 1ms rates for a completely open sight radius of 15(approximate area of 700 tiles) vs the old method running on a sight radius of 8(approximately 200 tiles). Most of the speed here is a massive reduction in redundant tile checking, and using a cache to store each individual ray along with distances for each tile in each ray.

I created an account on the roguebasin wiki so I could update the article with an implementation section. I further intend to write a few articles for the roguebasin wiki, as I have had quite a lot of great ideas out of reading the articles stored there.

I have a test up on my website if anyone would like to "see it in action". The code is also plainly visible to anyone who inspects the source.

javascript LOS test

[Tilded]

I got some errors.

Code: [Select]

ReferenceError: init2dArray is not defined
<anonymous>
 los.js:27
 los.js:27:5
The character encoding of the HTML document was not declared. The document will render with garbled text in some browser configurations if the document contains characters from outside the US-ASCII range. The character encoding of the page must be declared in the document or in the transfer protocol. los
TypeError: jsRL.sighting is not a constructor
<anonymous>
 los:50
n.Callbacks/j()
 jquery.min.js:2
n.Callbacks/k.fireWith()
 jquery.min.js:2
.ready()
 jquery.min.js:2
K()
 jquery.min.js:2
 losCool idea. You may want to check out recursive shadowcasting, which is a similar idea, but instead of caching children you calculate them. Here's my implementation in js.

[Quendus]

I used a similar kind of system in KleinRL. It's very well suited to maps with portals, glued boundaries, and other kinds of non-euclidean geometry.
Often games need to calculate point-to-point line of sight between non-player objects (for which the full field of vision isn't known or required). Is it possible to use this data structure to make that kind of calculation efficiently? I presume the result would differ from a check using a simple bresenham line from A to B.

[sokol815]

I got some errors.

Code: [Select]

ReferenceError: init2dArray is not defined
<anonymous>
 los.js:27
 los.js:27:5
The character encoding of the HTML document was not declared. The document will render with garbled text in some browser configurations if the document contains characters from outside the US-ASCII range. The character encoding of the page must be declared in the document or in the transfer protocol. los
TypeError: jsRL.sighting is not a constructor
<anonymous>
 los:50
n.Callbacks/j()
 jquery.min.js:2
n.Callbacks/k.fireWith()
 jquery.min.js:2
.ready()
 jquery.min.js:2
K()
 jquery.min.js:2
 losCool idea. You may want to check out recursive shadowcasting, which is a similar idea, but instead of caching children you calculate them. Here's my implementation in js.

Hmm... looks like your browser didn't like the way I was checking if a variable was initialized... what browser are you using? I fixed the source to not worry about checking any of those things (as it is not needed...)

also, said code looks very nice and concise, I especially like the inclusion of custom callbacks for reveal and transparent. Definitely some good usage of javascript's... peculiarities. If ever I am not satisfied with my sight algorithm, this is totally where I will go.

Also, congrats on starting the journey to make a javascript roguelike. There are lots of interesting problems to work out for that. Here is the repository for my javascript roguelike... feel free to look around if you want. (github)strife repository

I used a similar kind of system in KleinRL. It's very well suited to maps with portals, glued boundaries, and other kinds of non-euclidean geometry.
Often games need to calculate point-to-point line of sight between non-player objects (for which the full field of vision isn't known or required). Is it possible to use this data structure to make that kind of calculation efficiently? I presume the result would differ from a check using a simple bresenham line from A to B.

I don't think you will be able to find a better solution than the Bresenham line algorithm, which it sounds like you are using already. That is guaranteed to give you the same line from pointA to pointB and pointB to pointA.

[Tilded]

Thanks! I tried again and had no problems - Firefox 45.

[Quendus]

I used a similar kind of system in KleinRL. It's very well suited to maps with portals, glued boundaries, and other kinds of non-euclidean geometry.
Often games need to calculate point-to-point line of sight between non-player objects (for which the full field of vision isn't known or required). Is it possible to use this data structure to make that kind of calculation efficiently? I presume the result would differ from a check using a simple bresenham line from A to B.

I don't think you will be able to find a better solution than the Bresenham line algorithm, which it sounds like you are using already. That is guaranteed to give you the same line from pointA to pointB and pointB to pointA.

Sorry, I wasn't clear. I know that Bresenham (when implemented correctly) has D4 symmetry, and draws the same line A->B as B->A (at least when max(dx,dy) is odd or min(dx,dy) is even - then one of those symmetries must be lost).
My concern is that checking the Bresenham line A->B will yield a different result to calculating FOV from A and checking the value at B. Ideally, different situations shouldn't use different line of sight rules - that leads to things like corner shooting in DoomRL.