Hello there.
When I was playtesting Tetrogue I found one strange bug in a fov.
I'm using non-recursive shadowcasting implementation.
I tried to fix the bug, but I understood that I have no idea how this algo actually works, despite the fact that I wrote it several years ago. Well, I understand how it is supposed to work, but actual implementation has a lot cryptic flags and variables.
I looked at mrpas. The idea is pretty simple. But actual implementation is not really easy to understand.
While I was thinking about mrpas, I've got an idea.
And this idea is so straightforward, that I don't really understand why I haven't heard about algo like this.
So, here is idea:
The algo requires precomputation. Data for rings up to max sight range radius must be precomputed.
Ring of radius r is set points x,y such that:
floor(sqrt(x*x+y*y))<=r and that point doesn't belong to any ring with radius less than r.
Note, that x*x+y*y<=r*r is NOT equivalent to what I wrote above.
In addition to x,y following info is stored:
indexes of corners that create shadow
octant index of the tile (and second index if tile belongs to two octants).
Actually precomputing this is not strictly necessary, but making these calculation in runtime is not very efficient.
On this image:
indexes of corners that create shadow are 1 and 3.
i.e. lower left corner is 0, lower right 1, upper right 2, upper left 3.
The actual fov calculation works like this:
For each octant there is a list of tiles that block vision.
For each blocking tile starting and ending angles are stored.
Rings from 1 to max sight range are enumerated.
For each ring tiles in this ring are enumerated.
Each tile is checked if it is shadowed by one of blocking tiles in an octant.
If tile is completely shadowed, it is skipped and next is checked.
If current tile is blocking vision and partially shadowed, it is considered visible, and is added to the list of blocking tiles.
If current tile is transparent then it is considered visible if:
at least 50% of it's angle range is visible or at least 20% of it's angle range is visible and median angle is in visible range.
That's all.
Well. Almost. We haven't used corners indexes yet.
Indexes of corners are required to properly implement vision thru diagonal tiles.
Blocking angles of tiles corners that are dungeon corners can be reduced.
Like here:
Here only 60% of possible blocking angle range of corner is used.
This creates diagonal view like here:
So, what are benefits of this algo?
It is reasonably fast. On my PC 1000 fov calculations of range 15 takes around 100ms.
It looks more or less ok.
Using this algo it is possible to implement following features almost for free:
- temporal blockers, to simulate something like bushes, where you can't see several tiles behind the bush, but can see further.
- delayed blockers, to simulate something like cloudy glass in a window, or low located window.
- directional fov of arbitrary direction and angle range.
Here are samples and C++ implementation:
cfov.
sampleDbg.exe is a little older implementation that shows some debugging information when clicking on tiles.
sample.exe have realtime directional fov mode. In samples green tiles are bushes, grey are windows.
Ah! Almost forgot. cfov stands for Circular Field of View
testmap.txt is editable, but the code that reads it is not really foolproof, so be careful.
Method generateFov is template and it's argument MapAdapter must implement following methods:
TileInfo getTile(int x,int y); - returns info about tile
void setVisible(int x,int y); - this one is called to report visible tiles.
int getWidth();
int getHeight();
Hm. Probably instead of getWidth() and getHeight() it is better to make method like:
bool isInside(int x,int y);
Whole CircularFov class is also template and it's parameter is some kind of Point class, that must have
at least members x and y and operator< (to be stored in the std::set).
This is first experimental implementation, so I guess it can be improved in many ways.
Suggestions are welcome.
Thank you for your attention.
