Tile based visibility is not a new problem, however it's one I needed to solve for my pet project.
I'm working on a roguelike game to run on my mobile phone in Java.
So I have a couple of requirements to keep in mind.
- Fast
- Small
- Integer only maths
Firstly I went off searching for a solution but sadly didn't find anything I liked although there are some solutions
on RogueBasin and a discussion of different
algorithms. None of them directly fitted my need though as usual I find myself re-inventing the wheel, but that's OK as
this is just for fun and education after all.
The first problem I need to solve is I want to have a fog of war (so only regions of the map you've seen are visible). This
needs to be updated everytime you move to reveal the world as you trapse about it. My solution works as follows:
- Split the problem into four quadrants and process each one individually
- Walk every tile in the quadrant getting progressively further away from the player
- As I go keep a record of which angles are visible and which are obscured from the viewpoint
- When I enter a tile, if any of the angles it subtends are visible then the tile is visible
The first problem with this is of course the angles - I want everything to fit as integer maths because of the target platform.
I also want to arrive at a single integer value for each angle that can be compared less than or greater than to other
angles. This isn't so difficult a problem as I first thought. Having already split my problem up into quadrants I need only to
consider the part of the graph between the positive X and X axis. I then imagined a square with the bottom and left sides on the
X and Y axis and the right and top at some large distance away (D). If I project any point in the quadrant onto this square from the
origin it will end on one of the far sides. If it's on the top side I can use the x value of the projection as my angle, if
it's on the right side I can use the y value of the projection as my angle. Then if I invert one of the numbers either for the x
or y projection (so D-number) then add D onto it (or in total 2D-number) then I have my solution for the angle representation.
My example Java source code is available if you want
to take a look.
I'm sure this problem has been solved countless different ways by many programmers that have come before me and probably faster and
better too however I'm pleased with this solution and it's accurate enough for my needs and appears to be quick enough too. If
anyone reading this knows of some alternative ways to solve the problem please do drop me a note as I'd like to see them.
Now that I've solved this problem I need to figure out how I'm going to store the information about which angles are occluded.
Initially I thought a list would be a good idea but I didn't much fancy the idea of working with lists as it means I can be allocating
and managing the nodes. I didn't want to build a heap of nodes and I don't like not having a fixed memory usage for an algorithm.
So I settled on simply storing and updating a boolean array with the angles that are visible and those that are obscured. Then for
each tile I just need to check those slots it overlaps. This doesn't guarantee accuracy but it works nicely in practise. I've
not yet tried to figure out an optimal array size for a given radius though I just plugged in a 'guesstimate' number and it seems
to work! There will be plenty of time for tuning later.
After getting all of this working I ran into one final problem. Corner cases. Imagine the case where our player (represented by an
'@' symbol can see into the corner of some walls (represented by '#' symbols. My algorithm gave me problems
because the tile in the corner was obscured - but I want it to be visible (represented by '?'). Further I'm going to allow
my player to move through diagonal gaps like that - so I want them too see through them too.
This seems difficult however I modified my solution to handle the situation. Firstly I need to make sure I iterate the tiles along
diagonals which is pretty easy. Then I can accumulate a boolean to tell me if the previous tile on this diagonal was also an occluder.
If this is the case we can check the tile in front of the corner (represented by 'I') and the tile inside the corner ('?')
and decide what to do as appropriate. If it's decided that the player can see through the corner then it's easy to then mark that
section as non-obscuring and continue.
| Corner case | Order to visit tiles | Tiles to consider |
|
###?
#
#
@ #
|
6...
37..
148.
@259
|
###?
I#
#
@ #
|
Finally using almost exactly the same logic I was able to implement a simple algorithm to decide if any tile is visible from any other.
You can browse the source code
of my implementation. Again please do send me any comments you may have.