Advertisement

Hidding Tiles Behind Other Tiles Efficiently

Started by March 28, 2018 09:19 AM
2 comments, last by frob 6 years, 5 months ago

So I am trying to figure out an efficient way to block the rendering of tiles that are not in "line of sight" (behind other certain tiles), something like in CDDA:

autumn.png

Now I know I could do something like this by raycasts (as I currently do that that enemies to determine if they are line of sight of the player) however I am going to want to display probably somewhere between 7000 - 9000 tiles at the max zoom level and the only way I would know how to use raycast for this would be raycasting each tile which I imagine at that scale would not be usable (though I have not tried).

What would be an efficient way to try to accomplished what I am looking to do (also if it matters, this game in turn based)?

I would do two things to reduce the need of evaluating every tile in the game to a minimum:

  1. Put your game into a quad tree structure so that lookups at certain position wont be that costly as well
  2. Every dynamic tile (I would declare tiles you are able to change during runtime as dynamic to eliminate the need to double check anything) marks its quad cell as dynamic so you can go down the tree and filter each cells that have dynamic tiles in the game. This way you now what tiles are effectively hit by a propable test

Then you have a heavily reduced data basis you could do any test on. To the test, doing raycasts is something I wouldnt do at all; my first solution that comes into mind is to use the quad tree as a stack so every tile is a stack of 1 - N tiles while only the top tile gets rendered, it could be dynamically popped from the stack to ge the underlaying tiles back

Advertisement

There are a few good algorithms for it. Here is a list of several over on the RogueLikeDevelopment wiki.

Exactly what is best depends on your game.  For a non-symmetric version (where it only affects the player) shadow casting is generally one of the best techniques.  For a symmetric view (where you want both the player the monsters to know) then permissive field of view is probably best.  They aren't always best if they don't look quite like the effect you are going for, so you may need something different and the list gives more choices.

They've also got a visual comparison of a few algorithms. 

This topic is closed to new replies.

Advertisement