2009
01.27

In search of the fov graal

I’ve been working for a few weeks on various field of view algorithms. The conclusion is near and I should post results on r.g.r.d and roguebasin soon. Nothing revolutionary, but some data and facts that will probably be of some help.

Sadly I haven’t found the perfect algorithm yet (if it exists…).

Also, you can check two new songs on the rogue bard, both being covers of titles submitted for the 2008 roguelike soundtrack contest. Enjoy 🙂

7 comments so far

Add Your Comment
  1. I don’t know if you are using this technique, something like it was posted once.

    Pre-Compute tile visibility for an octant:
    – Use standard line algo to trace rays from origin to each tile.
    – Use as many rays as desired for accuracy. For instance trace to center of all sides of tile, tile center, and corners.
    – For each ray store ordered set of tiles it passes through.
    – For all rays find common sequences of tile from origin outward and move into a new ray which lists the original rays as children. Remove the shared sequence from the original rays. Repeat until no new rays are created.
    – For tile in the sequence of each ray add the index of the ray into a list in a tile array to store the octant.
    – The pre-computed info is then the tile array which ray indexes and the ray array with tile sequences and child ray indexs.

    Now to compute FOV:
    – Create boolean (or bit) array (blocked array) equal to size of ray array.
    – For each tile in map in visible order (spiral, bsp, or some other heuristic):
    – Check all rays in the blocked array. If any are false (not blocked) mark the tile as visible, otherwise mark as hidden.
    – If the tile is opaque, set all rays in the blocked array that are false to true (blocked) and recursively all child rays.

    That’s the gist. Very flexible and accurate. Can be modified to support various accuracy and corner case requirements with selection of initial pre-computed rays. Can support fog or progressive opacity by using a scaler instead of bit for the blocked array etc. Visits each tile once and does retrace near tiles. Can skip empty space.

  2. Sorry for the typos and nonsense, I wrote that on the bus real quick. To clarify…

    Precompute Process:
    1 Precompute all rays which will be traced and give each an index.
    2 If any rays move through the same sequence of tiles, split that portion out into a new ray, and reference the originals as children.
    3 Create a two dimensional array of tiles which represent locations relative to the viewer, and store in each a list of indices for the rays that pass through that tile.

    FOV process:
    1 Create a boolean array (the blocked array) sized to the number of precomputed rays all initialized to false. This stores whether the corresponding ray has been obstructed yet.
    2 Visit each tile in visiblity order, such as spiral, diamond, quad-tree nearest first, etc.
    3 For each tile:
    3.1 Find the corresponding tile in precomputed tile array. This has a list of (the idicies of) all the rays which pass through that tile.
    3.2 For each ray listed in the tile array:
    3.2.1 If the ray hasn’t already hit something (the blocked array is set to false for the ray index), then mark the tile as visible.
    3.2.2 If the tile obstructs vision then set the ray to true in the blocked array and, if the ray has children, recursivly set them to true as well. (Child rays split off to fill in the gaps between adjacent rays as you get further away from the viewer.)
    3.3 If all of the candidate rows were already blocked and set to true, then mark the tile as hidden.

    Of course this can be optimized in a number of ways.

  3. Sounds interesting. Do you have a working implementation ?
    The pre-compute step is probably slow. That means you cannot use this algorithm for real-time games if you have moving fov-blocking creatures or moving walls.

    Yet, something might come out of the idea of using various subcell coordinates for the rays starting and ending points.

    The main issue with current algorithms is not the speed, but gameplay issue due to either too much permissivity or inconsistency (flickering pillar shadows, stuff like that)…

  4. I can’t wait until you post your analysis with the full comparison screens. It is really interesting to see cases where one algorithm can sees but another does not.

    FYI, permissivity is a tweakable property for FoV. All you need to do is to restrict viewing within the cell. For instance, instead of defining FoV as “if a line exists from any point in the source to any point in the destination”, you could define it as “if a line exists from any point in the central 0.5 by 0.5 source square to any point in the destination 0.5 by 0.5 center square”, you will have a less permissive algorithm. As long as the criteria for source and destination squares is identical, it will be symmetric.

  5. I don’t as of yet unfortunately because I’m still coding the tile engine. I’m working on a roguelike in a 3d voxel grid rather than 2D, and this is one of the few algorithms that will scale reasonably into 3d.

    I’m afraid I must not have explained the algorithm adequately. You precompute the tables (relative cell and traced ray arrays) once at start-up and they work for any scene from there on out for the rest of the program (assuming you generate at the maximum radius you will need). It doesn’t matter what cells are transparent or opaque each frame. That makes it ideal for real-time games, because all the math and tracing is already done. It does help to try and arrange the arrays for good cache coherency though.

    Speed is an issue for me (because of a 3d grid), but flexibility/permissibility also aren’t a problem because you pre-compute however many rays, in whatever configuration you need at start-up. You can cast one ray per cell, or multiple for more accuracy. They don’t have to just cast to cell centers, but can cast through corners (for the visible corner fix), to mulitple points on each side etc.

    The idea is, assuming the observer always moves by whole cells each time step, you are casting the same exact rays each frame relative to the observer. So instead of doing the math to trace them over again each frame, just have each relative cell track witch rays will go through it (the same each frame). If you visit your cells in visibile order, like diamond, then you can just mark which rays get obstructed as you go along.

    Then make it more efficient by joining portions of rays that go through the same tiles (like all the rays that go through the same tiles right next to the observer in the beggining) so you aren’t tracing the same path over and over.

    I’ve left some detail out, but hopefully i’ve explained it well enough?

  6. ok, I see now. Indeed that sound very efficient but the pre-computed data must take a huge amount of memory. You have to calculate every ray from every cell of the map… Definitely deserves a closer look though…

  7. It’s not that bad.

    You can do the trick of only storing the table for one octanct and then read into it by reflecting the coordinates for the other seven octants.

    Also running time and space are optimised by merging portions of rays that travel through the same series of cells. In the end each cell only need 3-5 ints or so for ray indicies, and each ray only needs 2-3 ints for child indices on average.

    I’m working on a prototype, so maybe I’ll send some demo code your way sometime.