ID:2130277
 
I'm currently working on a ray casting algorithm in java and I'm having certain issues with artefacts. When near/adjacent to a line of walls ,say a strip of 1 * 8 opaque objects , the immediate walls render however further down the wall they don't render (ie they have a black overlay). I am using a raycast algorithm that runs on the bres algorithm.

The reason I am posting this here is because the view() proc does almost exactly what I would like my raycast to do hence it would be great to know how it works.

Here is an example of the artefacting (ignore the horrible art) https://i.gyazo.com/85d799fc0aac798d85e420d8952c4062.png

View() proc works like so

view(Distance from center,Center)

The Distance is how far out you would like to see, and center is basically the middle
EX:
view(5,src)//5 is the area outwards of my body since im source.

Usually to determine the distance there is a default world.view var that should be set before hand.

You can find more about view and other queries if you go here
Under the hood, view() is very idiosyncratic and not at all pretty. Some time ago, it even used to be O(N^3), which is dreadful. It is not, strictly speaking, a proper raycasting algorithm, and won't shed any light on why your own algorithm isn't working as expected--but yours won't look the same as BYOND's for sure. However for illumination's sake, I'll go over what it does in detail here.

The basic algorithm is as follows:

1) Get the view parameters for each tile in range: whether it's clear (not opaque), what its lamp value (luminosity) is, its infra_light value (infra_luminosity), and whether it's lit regardless. Store these parameters in a 2D array.

2) In the same array, mark down the value of max(dx,dy) and dx+dy as max_xy and sum_xy, respectively, and also determine the highest possible max and sum as max_depth_max and sum_depth_max. The values of dx and dy are distance, in tiles, from the eye position. Each tile also has vis and vis2 set to 0. (Note: For efficiency, the max_xy and sum_xy calculations can be done only on eye position changes. But each time the view is checked, vis and vis2 need to be reset.)

2b) If everything is visible, just set vis=1 for all tiles. Otherwise if the viewer is blind, set vis=vis2=infra_light=0 for all tiles. Because these are both simple cases, you can skip ahead to step 10.

3) Diagonal shadow loop: For each value of d from 0 up to (but not including) max_depth_max, loop over each tile. If the tile's max_xy==d+1, check to see if any of its 8 neighbors have vis2==d. If so, then set this tile's vis2=d+1 if it's clear, or vis2=-1 if it's opaque. (I cleaned up this loop by skipping over large swaths of tiles if max_xy!=d1, jumping to the next appropriate tile, since max_xy follows a predictable pattern. Now it's effectively O(N^2) instead of O(N^3).) The vis2 value is a placeholder that will be used in the next step, and we'll reuse it for another purpose later.

4) Straight shadow loop: For each value of d from 0 up to (but not including) sum_depth_max, loop over each tile. If the tile's sum_xy==d+1, check to see if any of its 8 neighbors have vis==d. If so: If this tile is not clear, set vis=-1; otherwise set vis=d but only if vis2 is not 0. (This also got a cleanup to skip tiles.)

5) Set the eye position's vis=1.

6) Light loop: This is still relatively ugly, but the gist of it is that you look for any tiles with lamp > 0. For each of its neighbors, if the neighbor is opaque you set the neighbor's lamp to 1; if it's clear, you set it to the current tile's lamp minus 1. This continues until the lights have spread out.

7) If infrared sight is enabled, loop through all tiles. If a tile's infra_light value (set in step 1) is not 0, make sure its vis!=0 and max_xy<=infra_light. If that's not the case, set its infra_light to 0.

8) For each tile, copy vis to vis2, so that vis2 now holds the LOS calculation. If the tile's lamp is 0 and so is its light (light is either 0 or 1, indicating a lit area), then set its vis=0. Now vis holds LOS+lighting.

9) Boundary calculation. Loop through each opaque tile where vis==0. Walls: If it has both east or west neighbors with vis!=0, or both north and south neighbors with vis!=0, make a note of this tile. Corners: If it has a diagonal neighbor with vis!=0 and the same cardinal neighbors do too, AND if the cardinal neighbors are opaque but the diagonal is not, then make a note of this tile. Once the loop is finished, all tiles so marked will be given vis=-1.

10) Wrapup: Each tile is given some bitflags to say what its visibility is. If vis!=0, then it has NORMAL_VIS; this means either it's in line of sight, or it's been lit by a lamp, or it's been made visible by the corner/wall boundary checking that pretties everything up. If vis2!=0, it has LOS_VIS, which means it's in line of sight but not necessarily anything else. And if infra_light!=0, it has INFRA_VIS.
In response to Lummox JR
Says basic algorithm<
Gives a 1504 page report<
Step 9 is really what I needed , thank you so much for such a detailed explanation.

I can add in a calculation to check if the adjacent non opaque tiles are shadowed and if they are then remove the shadow on the current tile. I'll let you know how it pans out.
In response to Lcass123
Lcass123 wrote:
Step 9 is really what I needed , thank you so much for such a detailed explanation.

No problem.

Corners are special cases for most raycasting algorithms. You'll find some good info here:

http://www.roguebasin.com/ index.php?title=Articles#Line_of_sight.2C_field_of_vision
well i've got close enough with what I have written to what I want , https://i.gyazo.com/d36d5d60da469a73434ba99f3c6d72c7.png
my god that is a goldmine of guides, thanks for the link.