3-dimensional Z-level support, Core Part 3: FOV calculation. [$250]

[GlyphGryph]

Master Ticket #6822

This will be a "bounty issue" for the development of z-line track development.

This has following requirements:
Expand fov calculations to use the new map system.
Insure there are no significant drops in performance.
(Benchmarks will be added)

There is a $250 open bounty on this issue. Add to the bounty at Bountysource.

[KyleSiefring]

I tried to do pure 3d shadow casting but it's really hard. Is this a good enough solution? https://github.com/KyleSiefring/Cataclysm-DDA/tree/3d_zlevel_fov_bresenham_exp

The meat of it is that it draws bresenham lines to the perimeter of the region we are testing. A modified version of 2d shadowcasting is then done on each of those lines.

[Coolthulhu]

The meat of it is that it draws bresenham lines to the perimeter of the region we are testing.

That sounds very prone to edge cases, of which there will be tons.

[KyleSiefring]

Any examples?

[kevingranade]

I tried this approach before I originally switched the game to shadowcasting, it has two fatal flaws. First it simply does not visit certain squares, you can see this for yourself by having the algorithm increment the value of each square it touches in the grid, then print out the grid when it is done (you should be able to modify the shadowcasting unit test under tests/ to do this). Even in 2D there were IIRC 8 points that were visited 0 times. This is a deal-breaker by itself, but the same test case highlights another issue, which is that any bresenham-based solution is going to repeatedly visit nearby squares a huge number of times, causing unacceptable slowdown (it was unacceptably slow in 2D, in 3D it would be strictly worse). I don't know of a solution other than shadowcasting that will work for this problem.

[KyleSiefring]

It only seems to miss spots if you mess with t. I am doing that in my code but it should be possible to fix that. Even though it visits nearby squares multiple times, it should be visiting squares an average of 2 times. It's not that bad.

This is the code I used to test the bresenham thing.

    bool test[1000][1000] = {{0}};
    auto lambda = [&](const point &p){
        test[p.x][p.y] = true;
        return true;};
    for ( int x = 0; x < 1000; x++ ) {
        bresenham(0, 0, x, 999, 0, lambda);
    }
    for ( int y = 0; y < 1000; y++ ) {
        bresenham(0, 0, 999, y, 0, lambda);
    }
    for ( int x = 0; x < 1000; x++ ) {
        for ( int y = 0; y < 1000; y++ ) {
            if (!test[x][y])
                printf("%d %d\n", x, y);
        }
    }

I'm also unsure that 3d shadowcasting is as fast as you think it is. One of my concerns is that I'll end up writing code to check if a polygon is within a polygon or some weirdness.

[KyleSiefring]

After a deleting a derpy comment where I was always passing 0 to bresenham, I now have actually tested that my code does everything I want it to. I'm pretty sure this code works now.

    bool test[1000][1000] = {{0}};
    auto lambda = [&](const point &p){
        test[p.x][p.y] = true;
        return true;};
    for ( int x = 0; x < 1000; x++ ) {
        int a = std::min(x, 999);
        int b = std::max(x, 999);
        bresenham(0, 0, x, 999, a-b, lambda);
    }
    for ( int y = 0; y < 1000; y++ ) {
        int a = std::min(y, 999);
        int b = std::max(y, 999);
        bresenham(0, 0, 999, y, a-b, lambda);
    }
    for ( int x = 0; x < 1000; x++ ) {
        for ( int y = 0; y < 1000; y++ ) {
            if (!test[x][y])
                printf("%d %d\n", x, y);
        }
    }

[kevingranade]

Even though it visits nearby squares multiple times, it should be visiting squares an average of 2 times. It's not that bad.

You didn't check did you? Odd since all you need to do is change that bool array to an int and increment instead of setting true. Here's my code and results: https://gist.github.com/kevingranade/5147616 The values are in hex, so those "2D" values near the middle are 46 visitations per cell. The access patterns of bresenham also make memory prefetchers cry. If you think otherwise you need to provide some profiling data to back up "it's not that bad". Patching your solution into the shadowcasting unit test should be a pretty straightforward way to do that.

In addition to that there is the correctness issue, if you draw a bresenham line to the edge of the map, what you're doing is raycasting, but unfortunately "a line passed through this square" isn't quite the same as "a line was able to be drawn to this square" unless your sample rate is fairly high. I never looked into how high because as soon as I started checking alternatives I found shadowcasting.

One of my concerns is that I'll end up writing code to check if a polygon is within a polygon or some weirdness.

I think you're getting the algorithm we're using confused with something from traditional 3D rendering, the algorithm we're using is a grid (or voxel, now that it's 3D) based algorithm that

[KyleSiefring]

What I mean by an average of 2 times is that if the sum of all the frequencies divided by the total number of squares will be 2.

Here are some benchmark numbers that I got after

castLight() executed 1000 times in 161738 microseconds.
cast_zlight() executed 1000 times in 13174736 microseconds.
new/old execution time ratio: 81.46.

x80 overall and x4 for each block (since there are 20 times as many from adding a new dimension). Originally it was x40 but after making it so that each zlevel gets it's own data it hammered the cache more.

One of my concerns is that I'll end up writing code to check if a polygon is within a polygon or some weirdness.

I think you're getting the algorithm we're using confused with something from traditional 3D rendering, the algorithm we're using is a grid (or voxel, now that it's 3D) based algorithm that

The polygon thing was kinda an exaggeration. Here are some 3d grids. http://stackoverflow.com/questions/7309188/how-to-plot-3d-grid-cube-in-matlab

If you look at the lines from z to z+1 you can see that there is a steeper slope. That means that when you hit a block the region that goes to the next layer isn't exactly square.

I came across this when I tried to do 3d shadowcasting here. https://github.com/KyleSiefring/Cataclysm-DDA/tree/3d_zlevel_exp

Here is an example. In this attempt, when the shadowcasting hits A one of the slopes is going at the same rate as B and the other is much shallower. The slope should be z/sqrt(x^2+y^2) or something. I really don't know anymore.

[KyleSiefring]

Upon further examination I think my shadowcasting is right (for the most part). I seem to have misled myself.

[KyleSiefring]

I finally got around to making this. This should hopefully help anybody else trying to work this out.

ShadowcastingSlide.pdf

[Coolthulhu]

The theory isn't really that tough, the problem is devising an algorithm that handles it well AND in reasonable time.
Benchmark and unit test would be very useful here.

[KyleSiefring]

The problem is that the current code doesn't make a real attempt to deal with the geometrical realities in that pdf. This tripped me up and I expect that it will trip up anybody else trying to work with the code.

[Epictyphlosion]

I hate to mention another game, but Dwarf Fortress uses a system which gives each creature a field of view, and a field of hearing. If someone can reverse-engineer the FOV code in DF, then we might get somewhere. Plus, I'd really love to see something like this, it would allow me to perform sneak attacks on zombies and NPCs. And come on, who wouldn't love getting $250?