new experimental FOV
Mingos
I wrote an experimental FOV algorithm and figured some of you might be
interested in having a look.
Initial tests reveal that it's reasonably fast, but I still lack any
exact details, especially about its symmetry (I reckon it's
acceptable) and possible misbehaviour in specific situations.
It's C++ code (can be changed to C easily - in fact, I already rewrote
it for libtcod and it had to be in pure C to work with the C interface
of the lib) with a simple HTML doc about how to use it and with some
comments to make understanding it a little easier (refer to fov.cpp).
I might write an article about it later on.
In the meanwhile, head to the downloads section of UR's homepage
(http://umbrarumregnum.110mb.com) and check it out. Some feedback
about possible issues and suggestions about how to optimise it would
be appreciated. It's written in a very straightforward manner
(separate code for each octant, which might seem a bit messy), hope
that doesn't bother you too much.
Thanks in advance for your opinions about it.
Mingos
Xecutor
Wow... Very impressive.
Wow again.
I like it a lot.
Can I use it in my rl? :)
Mingos
> Wow... Very impressive.
> Wow again.
> I like it a lot.
Thanks!
> Can I use it in my rl? :)
Don't be silly - of course you can!
Mingos
Matthew Allen
differed from shadow casting. Could you maybe provide some high-level
discussion to explain how this differs from the other techniques?
One piece of feedback I have is this: get rid of the octet code, or at
least express the meat of the code in a function. It looks like, if
you need to make a change to the algo, you have to change it in 8
different places. That's asking for trouble as a maintainer.
Still... good work. FOVs are hard to understand and the code is easy
to read. While I don't like the octet code from the perspective of a
developer/maintainer, it makes it easier for a novice to read and
understand because there is no trickery to generalize the function.
Mingos
Thank you for your feedback :).
I will try to write a detailed article about how this works later
today. If it's short, I'll post it here, if not, I'll post a link.
Right now let me just offer a quick sketch of the underlying
philosophy.
As in your usual shadowcasting, MRPAS scans the map octant by octant,
and each octant is scanned line by line (horizontal or vertical) from
the source outwards. The scan of a single line is made from the
orthogonal edge of the octant towards the diagonal (shadowcasting does
the opposite). For each line, the cells' angles (slopes) are
calculated, although in a different manner than in shadowcasting. The
angles have a value between 0.0f and 1.0f. The max value, 1.0f, is
divided by the number of cells in the currently processed line. That's
the angle range a single cell occupies. Knowing the number of the
currently processed cell, calculating its exact angle range is
trivial. For each cell, 3 angles are used: two for its corners and one
exactly in the middle. The algo checks whether those 3 angles are
blocked or not. A transparent cell requires the centre angle and one
of the corner angles to be unblocked. Opaque cells need any single
angle unblocked. When an opaque cell is found, its angle range (the
two corner angle values) are saved as a blocked angle range in an
array. The cells' visibility is checked by comparing their angles with
this blocked ranges array.
That's the general description. I hope it's not too cryptic (I always
sucked at explanations). Please be patient while I write a more
detailed description.
I am aware that any change in the code requires copying it 8 times,
which leaves plenty of field for bugs. In fact, you're not the first
person to make this remark and I completely agree with you. But this
code is 4 days old, so I haven't got to simplifying it yet (you know
how it is: you get an idea, you implement it in the most
straightforward way possible, then you optimise and finally
generalise... I'm in the middle of step 3 right now, hehe). I was
thinking about creating a quadrant function that would be called 4
times. The problem is that I'm not sure how to efficiently deal with
some conditional statements and for loops, which come in 4 different
versions, depending on the octant... Dunno, maybe I'll think of
something.
Anyways, thanks again for your comment!
Mingos
Jotaf
was generalized for the 4 quadrants, IIRC, it received a pair of
values that were either 1.0 or -1.0, and were multiplied by the
coordinates so that the algorithm "thought" it was working in the
first quadrant, but the coordinates could be reversed so that it was
actually working in another one.
Just my 2 cents :)
Jotaf
Mingos
An interesting possibility, I'll give it a thought.
In the meanwhile, I'm proud to announce that MRPAS has survived Jice's
torture chamber. The results are mind-blowing. Jice seems very
enthusiastic about the libtcod version. I already know the stats, but
I don't like boasting, so wait for the official results announcement.
Stay alert, the news should appear soon on Jice's blog: http://doryen.blogspot.com/
Mingos
Matthew Allen
> As in your usual shadowcasting, MRPAS scans the map octant by octant,
> and each octant is scanned line by line (horizontal or vertical) from
> the source outwards. The scan of a single line is made from the
> orthogonal edge of the octant towards the diagonal (shadowcasting does
> the opposite).
>
> For each line, the cells' angles (slopes) are
> calculated, although in a different manner than in shadowcasting. The
> angles have a value between 0.0f and 1.0f. The max value, 1.0f, is
> divided by the number of cells in the currently processed line. That's
> the angle range a single cell occupies. Knowing the number of the
> currently processed cell, calculating its exact angle range is
> trivial.
>
> For each cell, 3 angles are used: two for its corners and one
> exactly in the middle. The algo checks whether those 3 angles are
> blocked or not. A transparent cell requires the centre angle and one
> of the corner angles to be unblocked. Opaque cells need any single
> angle unblocked.
>
> When an opaque cell is found, its angle range (the
> two corner angle values) are saved as a blocked angle range in an
> array. The cells' visibility is checked by comparing their angles with
> this blocked ranges array.
That was a decent description, IMO. I know it was just a rough first
attempt, and there were some rough patches. I put some paragraph
breaks in it to give my thoughts on how to organize it.
I may be wrong, but I think the term "shadowcasting" really just
refers to a general method and not a specific algorithm. As such, I
think you should avoid statements like "shadowcasting does the
opposite" in your description. Your algorithm really specifies a
method to scan the map, represent shadows, and decide when a square is
visible or not. But you probably already realize that.
Jotaf's suggestion is a good one... I think it should work with
octants too if you tweak it right.
jice
I also suggested to Mingos to put the octant code in a function. This
would reduce the code to 60 or 70 lines (more than 500 currently).
I still didn't dive in the code to see how it works, but what is sure
is that it seem to get the best of all the algorithms I tried.
Its main characteristics is that it's blazing fast, has no gameplay
glitch as most of the others and is as simple as shadowcasting to
understand/implement. It has still to come under close scrutiny, but
early results are more than encouraging.
--
jice
Mingos
> That was a decent description, IMO. I know it was just a rough first
> attempt, and there were some rough patches. I put some paragraph
> breaks in it to give my thoughts on how to organize it.
Yeah, I should have put the paragraph breaks myself :P.
> I may be wrong, but I think the term "shadowcasting" really just
> refers to a general method and not a specific algorithm. As such, I
> think you should avoid statements like "shadowcasting does the
> opposite" in your description. Your algorithm really specifies a
> method to scan the map, represent shadows, and decide when a square is
> visible or not. But you probably already realize that.
Well, by "shadowcasting" I meant the descriptions on roguebasin and
Dirk Kok's blog, which I used to understand how the whole
shadowcasting thing works. But the algorithm's name implies that it's
still a form of shadowcasting, even though modified :).
> Jotaf's suggestion is a good one... I think it should work with
> octants too if you tweak it right.
Yes, it's good, but I'm not sure how to make it work with the for
loops that process entilre lines...
Mingos
Jotaf
> > Jotaf's suggestion is a good one... I think it should work with
> > octants too if you tweak it right.
>
> Yes, it's good, but I'm not sure how to make it work with the for
Ok. It can also work for octants instead of quadrants, which is way
better. Just use a reduced transformation matrix:
T=[Txu, Txv;
Tyu, Tyv]
mapping from the space (u,v), the one that the algorithm works on, to
the space (x,y), the actual tile space. You don't need matrices
though, you can just pass in those 4 parameters.
Accessing one tile:
map[u * Txu + v * Txv][u * Tyu + v * Tyv] = something;
As you can see, you can design a for loop and it doesn't have to be
tied to a particular coordinate (x or y; or as I'm calling them, u or
v). The trivial case, where both spaces are equal, is with an identity
transformation:
T=[1, 0;
0, 1]
To rotate by an angle, which in your case should be a multiple of 90º,
replace "ang" here:
T=[cos(ang), -sin(ang);
sin(ang), cos(ang)]
Yielding the 4 quadrants you need with values like -1, 0 and 1.
To work on octants, you also need to flip the space; you can do that
by reversing the sign in one line, or both (or column; can't be sure
off the top of my head right now). But that would probably be easier
to figure out through some experiments.
Jotaf
Jotaf
extremely wasteful for a roguelike :)
After briefly considering bit masks and abuse of macros, I concluded
that the best compromise between your sanity and speed of execution
would be a little abuse of #includes.
You write the one-octant version in one header file, like this:
void FOV(startx, starty, etc) {
//Here you access tiles like this:
for (x = 0; x < w; x++)
map[MAPX][MAPY] = something;
}
Then you define the 8 variants of the function in succession, in the
main header:
#define FOV fov_octant_0
#define MAPX x
#define MAPY y
#include fov_one_octant
#define FOV fov_octant_1
#define MAPX y
#define MAPY -x
#include fov_one_octant
...
void fov(etc) {
fov_octant_0(etc);
fov_octant_1(etc);
...
}
A bit messy but at least you still get to define a proper function for
one octant; I once saw one implementation that had to turn the whole
function (!) into a macro. The neat thing is that all the "nasties"
are concentrated in one spot and they might make some sense; while the
meat of the algorithm is carefully isolated from this. And no costly
multiplications by 1, 0 or -1.
Jotaf
Mingos
At the moment, the C++ version available for download has two bugs
that kick in when the PC is on the border of the map. After they're
corrected, I'll think about shortening the stuff. Oh, and I'll try to
write a more extensive article about how this works. I wanted to do it
yesterday, but finally didn't manage to.
Mingos
Matthew Allen
> Well, by "shadowcasting" I meant the descriptions on roguebasin and
> Dirk Kok's blog, which I used to understand how the whole
> shadowcasting thing works. But the algorithm's name implies that it's
> still a form of shadowcasting, even though modified :).
This is dullish nit-pickery, but I would say it is an "implementation
of shadowcasting" and not a "modification of shadowcasting". I believe
any algorithm that scans outwards from the player keeping track of
obstacles that create shadow is a "shadowcasting" algorithm.
Also, have you considered a dynamic data structure (linked list, etc)
for storing the shadows? I'm not actually sure if its a good idea...
less space on the heap but more processing time, but these days memory
is so cheap it seems like its worth the tradeoff.
Mingos
Well, I repeat: the word "shadowcasting" in the algo's name implies
that this still is shadowcasting, it matters not whether it's a
"modification" or an "implementation". Plus, I disagree with your
generalised definition of shadowcasting as an algo that scans from the
source outwards, keeping track of obstacles that create a shadow. What
algo doesn't do that? I don't know how permissive FOV works, but
modeling rays ("diamond raycasting" in libtcod) and standard
raycasting do the very same thing. I guess you'd need to add the fact
that shadowcasting scans the map line by line to make it valid. But,
to be honest, I'm not really interested in classifying the algos and
in the nomenclature. As long as they work, they might as well be named
"Bugawuga Ding Dong Splat" and I wouldn't mind that.
Yes, I tried it with linked lists instead of arrays. The speed loss
was nearly 50%. And I used TCODLists, which are faster than STL... I
guess either 2 separate arrays or possibly an array of structs is the
fastest way. The excess memory that is used is tiny. Up to 6kB in case
of UR (1500 indexes, 4 bytes each), so it's not a real concern. The
libtcod version deals with it more gracefully, since it uses 1/7th of
the total number of the map's cells, which means the excess memory is
smaller in case of smaller maps. It's still excessive, of course, but
as you remark, memory is cheap nowadays. Even an extra MB wouldn't be
something outrageous.
Mingos
David Damerell
>I will try to write a detailed article about how this works later
>today. If it's short, I'll post it here, if not, I'll post a link.
This is the meat of the question. I'm interested not so much in
implementation detail as in how visibility is defined. "A square A can see
a square B if ..."
--
David Damerell <dame...@chiark.greenend.org.uk> Kill the tomato!
Today is Second Oneiros, April.
Mingos
wrote:
> Quoting Mingos <dominikmarc...@gmail.com>:
>
> >I will try to write a detailed article about how this works later
> >today. If it's short, I'll post it here, if not, I'll post a link.
>
> This is the meat of the question. I'm interested not so much in
> implementation detail as in how visibility is defined. "A square A can see
> a square B if ..."
> --
> Today is Second Oneiros, April.
OK, I've finished the article. You can find it under either of these
two links:
http://umbrarumregnum.110mb.com/art9_fov.php
http://roguebasin.roguelikedevelopment.org/index.php?title=Restrictive_Precise_Angle_Shadowcasting
Mingos
Matthew Allen
> Plus, I disagree with your
> generalised definition of shadowcasting as an algo that scans from the
> source outwards, keeping track of obstacles that create a shadow. What
> algo doesn't do that?
That wasn't a very good definition... I agree. I'm not enough of an
expert, nor enough of an RL elder statesman, to dictate a definition.
I still stand by my statement that your algorithm is an
"implementation of shadowcasting" and not a "modification of
shadowcasting", but who cares? :)
I would say that raycasting draws a line from the source to either the
edge of the FOV radius or every potentially visible square, and
calculates visibility along that path. Shadowcasting, on the other
hand, scans the map in concentric circles (usually split into
quadrants/octants), making a list of all obstacles encountered and
using that list to determine which later tiles are concealed.
Permissive FOV (based on the roguebasin description) is a raycasting
algorithm. However, it checks visibility between all corners (or
subcells) of the source and destination tile--something that
shadowcasting algorithms often accomplish by allowing a tile to be
visible if only one corner is visible.
> Yes, I tried it with linked lists instead of arrays. The speed loss
> was nearly 50%.
I'm not surprised, and that's good to know. I think for roguelikes
with less resolution than UR the array length doesn't need to be
nearly as big anyways. Besides... memory is cheap, but chasing
pointers is a lot slower than traversing arrays for a few major
reasons.
Mingos
wrote:
> Quoting Mingos <dominikmarc...@gmail.com>:
>
> >today. If it's short, I'll post it here, if not, I'll post a link.
>
> This is the meat of the question. I'm interested not so much in
> implementation detail as in how visibility is defined. "A square A can see
> a square B if ..."
> --
> Today is Second Oneiros, April.
By the way, the article is quick work. Please let me know whether
there's anything that needs to be improved. As I always emphasize: I
suck at explaining...
Mingos
Mingos
> I'm not surprised, and that's good to know. I think for roguelikes
> with less resolution than UR the array length doesn't need to be
> nearly as big anyways. Besides... memory is cheap, but chasing
> pointers is a lot slower than traversing arrays for a few major
> reasons.
In the libtcod version of MRPAS, the array size is determined this
way: map's total cells (width*height) divided by 7. That's more than
there would fit in one octant, and besides, if there were so many
obstacles, the algo would find all cells unlit after the first couple
of lines, so yeah, that's always "wasted" memory. But better to
sacrifice a few additional kB than get a segmentation fault.
Mingos
Matthew Allen
> OK, I've finished the article. You can find it under either of these
> two links:
That's a very clear description, and the illustrations are excellent.
Good job!
Now that I understand it better, I have two observations. First, in
the final illustration, I was expecting tiles along the left-hand side
of the octant to be visible--namely (5,6), but also potentially (6,7).
I was specifically surprised because (2,6) is visible, and it seems to
have an equvalent level of visibility. Does this get addressed when
the octant opposite it (which shares the orange section shown in the
second figure) gets processed?
Also, have you considered using these precise angles?
Mingos
> That's a very clear description, and the illustrations are excellent.
> Good job!
Thank you!
> Now that I understand it better, I have two observations. First, in
> the final illustration, I was expecting tiles along the left-hand side
> of the octant to be visible--namely (5,6), but also potentially (6,7).
> I was specifically surprised because (2,6) is visible, and it seems to
> have an equvalent level of visibility. Does this get addressed when
> the octant opposite it (which shares the orange section shown in the
> second figure) gets processed?
You see, the angles that are taken into account are the ones displayed
on the first image, namely, the centre and both ends of the bottom
edge of the cell. If you have a look at the lines that mark the
obscured areas, you'll notice that the bottom edges of (5,6) and (6,7)
have the left edges and the centres of the bottom edges obscured, thus
are considered unlit. You may change the algo to light cells when
there's just one angle visible, but the excessive permissivity
achieved this way will cause some cells immediately behind a pillar to
become lit as well, which is precisely what I wanted to get rid of due
to gameplay reasons, as well as visual attractiveness.
As for the cells shared by two adjacent octants, they are visible if
any of the two octants marks them as visible. There's a check in the
example code (which, by the way, has just been updated - two bugs have
been removed) which makes the algo refuse to process an already lit
cell.
> Also, have you considered using these precise angles?
>
> http://mayhem.cs.ucsb.edu/~msa/ironage/RPAS.jpg
Hm... Calculating them isn't difficult. In fact, I was thinking about
precalculating all the single cell angle ranges and putting them in an
array (however, this resulted in a speed loss, although I don't quite
understand why). This way, you could calculate the starting angle by
using the next line's cell angle range. Simple.
I might try to implement this later. The cells taken into account
might be the upper right corner you marked on the image, the lower
left one and the centre angle would be right between the two (the
current starting angle might be eliminated). If the speed loss is
acceptable and the visual results are worth it, I'll modify the algo
to use this approach. Thanks for the suggestion!
Mingos
Jotaf
> At the moment, the C++ version available for download has two bugs
> that kick in when the PC is on the border of the map. After they're
> corrected, I'll think about shortening the stuff. Oh, and I'll try to
> write a more extensive article about how this works. I wanted to do it
> yesterday, but finally didn't manage to.
>
> Mingos
Yeah sure. But you can disregard my first post completely
(transformation matrices etc), and look only at the second -- the idea
is that you simply take note of the differences between the code of
different octants/quadrants (which are just copy-paste-edit versions
of the original), and use the definitions to replace them selectively.
Like, if in the original code there's a map[x][y], or a for (x =
0; ...) you use some macros instead of x,y (such as MAPX, MAPY), and
through re-defining them before an #include, you can do funky stuff
like switch x and y around, or reverse their signs, whatever you need
to work on another octant.
Jotaf
Mingos
Jotaf: Great idea, but will it work in other languages? I'm starting a
great action to port it to C#, Java and FreePascal and I'm not sure
such a solution will be valid for the three... Still, I might use it
in the final C/C++ implementations.
Matthew: Your idea turned out fine. Have a look at these images:
http://img246.imageshack.us/img246/9643/bottomonly.png
http://img152.imageshack.us/img152/6870/bottomandtop.png
The first one represents the FOV using my original implementation. The
second one, using your idea. As you can see, the FOV became even more
restrictive (whic I think is good), but also has a slightly more
natural feel to it. I mean, the infamous FOV needles in a forest...
they look more precise! In other situations, the algo differs very
little from the original implementation, which is good (I
intentionally chose an extreme situation, where changes would be most
visible). I think I'll keep this version (expect a credit).
And now, even better news. While in closed spaces, the speed of this
modified version remains the same or suffers a very minor decrease,
but where the algo's speed was the worst, namely in open spaces with
lots of obstacles (forests), it experienced a considerable boost.
That's slightly odd, since I expected the opposite, but hey! A speed
boost is always welcome!
The time has come for the best news: I realised there were two lines
in the algo that resulted in many excessive calculations (instead of
once per cell, they were being made once per cell). After the tweak
and together with the angle modification, the algo's speed increased
between 10% in closed spaces (labyrinths) and up to 50% in forests!
Jesus, this will be unbeatable in terms of speed!
Mingos
Matthew Allen
> Matthew: Your idea turned out fine. Have a look at these images:
Those look really nice. Feel free to credit or not to credit... I
won't take it personally. I'm just happy to discuss it.
One observation, which in hindsight isn't a surprise, is that two
diagonal objects will completely block LOS. Ie. you can't see through
diagonals. Some people apparently don't like this, although I happen
to think its fine. This might be the effect of a tie-breaking routine
if you are using the corners as I suggested, but I'm not sure.
My main concern with the algorithm you originally presented is that
visibility is different depending on which side of the octant you are
on. I believe its still symmetric in that if you can see an tile, an
entity there can also see you. But in that last illustration in your
very good writeup, it looked a little odd to see one tile visible and
another obscured when they both seemed to be in similar levels of
shadow. My mod was only an effort to address this, but I harbor no
illusion that my solution is right ;)
Grats on the performance boost! It might be because my suggestion
makes it more restrictive, so less tiles are considered and less
shadows are calculated.
Kusigrosz
> The time has come for the best news: I realised there were two lines
> in the algo that resulted in many excessive calculations (instead of
> once per cell, they were being made once per cell). After the tweak
> and together with the angle modification, the algo's speed increased
> between 10% in closed spaces (labyrinths) and up to 50% in forests!
> Jesus, this will be unbeatable in terms of speed!
Is it necessary to use floating point arithmetic in the algorithm?
If the angles only need to be compared, you could give integer numbers
to all relevant points (cells' vertices and centres) so that they
increase monotonously with the angle, and look them up when needed.
It might increase or decrease speed - the table lookups may turn out
to be more costly than the floating point operations. I used such an
approach in the bimodal vision algorithm:
http://tinyurl.com/cvrqzz
posted here a few months ago, but I wasn't entirely satisfied with its
speed.
--
Kusi...@AUtorun.itvk.pl To send mail, remove 'AU' from the address
You see here a scroll labeled "BlxelewpCY4"
Mingos
> Those look really nice. Feel free to credit or not to credit... I
> won't take it personally. I'm just happy to discuss it.
Well, giving you a credit costs nothing and I feel it's the right
thing to do.
> One observation, which in hindsight isn't a surprise, is that two
> diagonal objects will completely block LOS. Ie. you can't see through
> diagonals. Some people apparently don't like this, although I happen
> to think its fine. This might be the effect of a tie-breaking routine
> if you are using the corners as I suggested, but I'm not sure.
You are wrong (HA!). I also thought it would block the LOS, but it
turned out to remain unchanged. Well, unchanged is an exageration
because from many angles, the diagonal line of obstacles does
completely clock the LOS. But when you're right in front of the
diagonal line (not necessarily adjacent), you can see through it just
like before.
> My main concern with the algorithm you originally presented is that
> visibility is different depending on which side of the octant you are
> on.
Yeah, I was a little worried about it as well... Well, I guess the
issue is solved now :).
> I believe its still symmetric in that if you can see an tile, an
> entity there can also see you. But in that last illustration in your
> very good writeup, it looked a little odd to see one tile visible and
> another obscured when they both seemed to be in similar levels of
> shadow. My mod was only an effort to address this, but I harbor no
> illusion that my solution is right ;)
The symmetry is acceptable. According to Jice's tests, it's up to
around 5% asymmetry in outdoor areas and in dungeons/caverns it's
below 1%, which is fine.
> Grats on the performance boost! It might be because my suggestion
> makes it more restrictive, so less tiles are considered and less
> shadows are calculated.
My thoughts exactly.
I'll try to update the article tomorrow, but right now I'm too tired
to do it. Good night!
Mingos
Matthew Allen
> You are wrong (HA!). I also thought it would block the LOS, but it
> turned out to remain unchanged. Well, unchanged is an exageration
> because from many angles, the diagonal line of obstacles does
> completely clock the LOS. But when you're right in front of the
> diagonal line (not necessarily adjacent), you can see through it just
> like before.
Oh goodie. I was looking at your image and I thought that the trees
southwest of the @ were demonstrating this problem. It turns out they
are shifted over one square and aren't directly diagonal. Damn you and
your teeny tiny fonts ;) Or my half-blind bug-eyes. Whatever.
Mingos
Kusigrosz:
The first version of my algo used this approach: an array of integers.
The speed wasn't an issue. The accuracy, sadly, was. Unless the
integer array was really big (say, 10000 angles), at some point it
generated big ugly squares instead of nice and clean FOV lines. I know
floating point operations are expensive, but the elimination of soch a
large integer array probably compensates it. Probably.
Matthew:
I am so ashamed. I will try to post screenshots in a higher resolution
next time... ;)
Mingos
jice
I don't think float operations are that slow nowadays. John Carmack
made a massive switch to float in Quake 3 and Lua, one of the fastest
scripting languages, simply has no support for int and uses only
float. Also, tests made with Mingos showed that using double was
faster than using float... With nowadays CPU, optimization is often
counter-intuitive. That's why I always rely on benchmark rather than
common sense when trying to optimize my code.
--
jice
Mingos
> I don't think float operations are that slow nowadays. John Carmack
> made a massive switch to float in Quake 3 and Lua, one of the fastest
> scripting languages, simply has no support for int and uses only
> float. Also, tests made with Mingos showed that using double was
> faster than using float... With nowadays CPU, optimization is often
> counter-intuitive. That's why I always rely on benchmark rather than
> common sense when trying to optimize my code.
I think you've hit the spot. Additionally, the excellent accuracy
offered by doubles makes it worthwhile to use them when accuracy is
crucial.
In my first attempts, I used an array of 100 integers, but it wasn't
accurate at all. 1000 integers were accurate at low ranges, but at ~40
cells from the PC, the FOV lines got more and more blocky. 10000
integers might solve this issue for most conceivable map sizes, but
marking the blocked ranges requires a for loop for each obstacle. In
the first scanned line, the for would have to go through 5000
iterations. That's obviously slower than marking two doubles, and it's
still less accurate.
What still amazes me is the fact that doubles turned out faster than
floats. But then again, I guess you remember what I told you the other
day: "Computers are getting more and more like women; the moment you
think you understand them, they somehow manage to prove you wrong".
The optimisations I tried out yesterday are an example. According to
logic, they should make the algo faster, but, against all intuition,
the result was the opposite to what I expected...
Mingos
Kusigrosz
> On 7 Kwi, 11:26, jice <jice.nos...@gmail.com> wrote:
>> I don't think float operations are that slow nowadays. John Carmack
>> made a massive switch to float in Quake 3 and Lua, one of the fastest
>> scripting languages, simply has no support for int and uses only
>> float. Also, tests made with Mingos showed that using double was
>> faster than using float... With nowadays CPU, optimization is often
>> counter-intuitive. That's why I always rely on benchmark rather than
>> common sense when trying to optimize my code.
>
> I think you've hit the spot. Additionally, the excellent accuracy
> offered by doubles makes it worthwhile to use them when accuracy is
> crucial.
>
> In my first attempts, I used an array of 100 integers, but it wasn't
> accurate at all. 1000 integers were accurate at low ranges, but at ~40
> cells from the PC, the FOV lines got more and more blocky. 10000
> integers might solve this issue for most conceivable map sizes, but
> marking the blocked ranges requires a for loop for each obstacle. In
> the first scanned line, the for would have to go through 5000
> iterations. That's obviously slower than marking two doubles, and it's
> still less accurate.
I'm not sure I understand where these iterations come from.
Suppose the maximum vision radius is 100 cells. An octant contains
some 5050 cells and there are just a few 'important' angles
(or slopes) per cell (to the vertices and centre) so the total
number of different important slopes in the octant is a few times
5050. Lets give each important slope an integer number, increasing
monotonously with the slope. For each cell we remember in some
lookup table (three integers per cell - in C I'd use a struct) the
numbers of its important slopes.
If I read the code right, the only difference in the octant code would
be that startSlope, endSlope and centreSlope would be integers looked
up in the table rather than doubles computed on the fly; the
comparisons and marking would stay the same. And there would be no loss
of accuracy as different 'double' slopes would get different numbers.
Now whether this would bring any speed benefit is another question that
could be answered only by testing (well, some optimization guru could
probably guess, but I'm not one). There may be other reasons for
avoiding floats, for example if a game could be saved on one computer
and restored on another, rounding differences could lead to some cells
changing their visibility status. I don't think it is likely for
sensible vision ranges though.
Mingos
> I'm not sure I understand where these iterations come from.
>
> Suppose the maximum vision radius is 100 cells. An octant contains
> some 5050 cells and there are just a few 'important' angles
> (or slopes) per cell (to the vertices and centre) so the total
> number of different important slopes in the octant is a few times
> 5050. Lets give each important slope an integer number, increasing
> monotonously with the slope. For each cell we remember in some
> lookup table (three integers per cell - in C I'd use a struct) the
> numbers of its important slopes.
>
> If I read the code right, the only difference in the octant code would
> be that startSlope, endSlope and centreSlope would be integers looked
> up in the table rather than doubles computed on the fly; the
> comparisons and marking would stay the same. And there would be no loss
> of accuracy as different 'double' slopes would get different numbers.
>
> Now whether this would bring any speed benefit is another question that
> could be answered only by testing (well, some optimization guru could
> probably guess, but I'm not one). There may be other reasons for
> avoiding floats, for example if a game could be saved on one computer
> and restored on another, rounding differences could lead to some cells
> changing their visibility status. I don't think it is likely for
> sensible vision ranges though.
I'm not 100% sure I understand your approach. How exactly would you
calculate the slopes of a given cell? Either the slopes will be very
large numbers or they will only be approximated (which is what I
wanted to avoid by using doubles). Also, do you suggest precalculating
the important slopes for all cells in an octant? Bear in mind that
only on an empty map this would have sense, since the more obstacles
there are, the smaller the FOV size. For instance, if you are on a
600x600 map, but inside a 5x5 room with all doors closed. If the PC is
right in the middle of the room, what percentage of the octant will
actually be calculated? What part will be wasted?
Of course, I'm open to discussing this subject, so if you could
explain your approach with more detail, I'd be infinitely grateful.
Mingos
Ray Dillinger
> I'm not 100% sure I understand your approach. How exactly would you
> calculate the slopes of a given cell? Either the slopes will be very
> large numbers or they will only be approximated (which is what I
> wanted to avoid by using doubles).
Let's say you have a sight radius of 32 squares. Make 'slopes' a
64x64 array of doubles and initialize it by iterating over the whole
thing letting slopes[x][y] = ((x+1)*1.0)/((y+1)*1.0). That will
calculate the 'double' value of all important slopes in a quadrant.
(you need twice the sight distance because you'll want to calculate
angles to/from both square centers and square corners).
Now dump all the numbers from slopes[][] into a list, sort the list
into ascending order, and eliminate duplicates. Then convert that
sorted list into an array named 'slopeindex'.
Now let 'intangles' be a 64x64 array of integers and initialize each
intangles[x][y] with the number z, where slopeindex[z] == slopes[x][y].
Dump intangles to a text file, munge it into a static array
initializer, and include the static table intangles in your source
code. Keep the code that generates the intangles initialization
(and creates slopes[][], and slopindex[]) somewhere in your project
so you can repeat this later as you experiment with different sight
radii or FOV algorithms, but it doesn't need to be linked into the
build because it's not part of the game. In principle you might
never run it again.
Now whenever you want the integer angle-number of a particular
angle with slope x/y, you look in the table intangles[x][y] and
there it is.
The angle number doesn't bear any particular mathematical relation
to the actual angle; all I guarantee, and all you need for FOV
calculations, is that for any two angles A and B, if the angle number
of A is greater than the angle number of B, then the angle (or slope)
of A is also greater than the angle (or slope) of B.
> Also, do you suggest precalculating
> the important slopes for all cells in an octant? Bear in mind that
> only on an empty map this would have sense, since the more obstacles
> there are, the smaller the FOV size. For instance, if you are on a
> 600x600 map, but inside a 5x5 room with all doors closed. If the PC is
> right in the middle of the room, what percentage of the octant will
> actually be calculated? What part will be wasted?
The static array intangles[] is a resource for your program to use
while calculating FOV every time th player moves. It is never written
to during play, and is precalculated once while writing the code, not
at each turn. You will never waste CPU cycles calculating it in game
time because you will never calculate it at all in game time.
Bear
Mingos
An interesting approach, although I'd rather calculate everything,
depending on the map size, the first time the FOV is used and store it
in a static array. The first frame would be slow, but that's only one
frame in the entire game...
> The static array intangles[] is a resource for your program to use
> while calculating FOV every time th player moves. It is never written
> to during play, and is precalculated once while writing the code, not
> at each turn. You will never waste CPU cycles calculating it in game
> time because you will never calculate it at all in game time.
Contrary to all intuition, tabular lookup instead of calculating all
angles on the fly turned out slower in my tests a few days ago.
Still, I might use your suggestion to develop something slightly
different... Let the idea mature in my head for a few days. If I come
up with something good, I'll let you know :P.
Mingos
Kusigrosz
> calculate the slopes of a given cell? > Either the slopes will be very
> large numbers or they will only be approximated (which is what I wanted
> to avoid by using doubles).
only their ordering. Different slopes have to get different numbers,
and the numbers have to be monotonously increasing with the slope,
but apart from that their exact values are not important.
> Also, do you suggest precalculating the important slopes for all
> cells in an octant?
Yes. This precalculation needs to be done _once per game session_,
when you start. In principle one could even load it from a file
distributed as part of the game package.
> Bear in mind that
> only on an empty map this would have sense, since the more obstacles
> there are, the smaller the FOV size. For instance, if you are on a
> 600x600 map, but inside a 5x5 room with all doors closed. If the PC is
> right in the middle of the room, what percentage of the octant will
> actually be calculated? What part will be wasted?
It would just sit in memory, to be used when PC goes out for a walk in
the forest - after all, the slope of the line from (0, 0) to (274, 211)
doesn't change with time, so why should its number change?
Now, if you need vision ranges of 600 or so, the size of the look-up
table might get into many magabytes - I don't know if that would be
a problem.
> Of course, I'm open to discussing this subject, so if you could
> explain your approach with more detail, I'd be infinitely grateful.
Well, 1 kilobyte of code is worth 1000 characters, so maybe the
bimodalvision.c can help a bit in explaining. I posted a link in
this thread a few posts before. The precomputation is done (for
a quadrant) in vis_vtinit().
Mingos
> On 2009-04-07, Mingos <dominikmarc...@gmail.com> wrote:> I'm not 100% sure I understand your approach. How exactly would you
> You see here a scroll labeled "BlxelewpCY4"
OK, thanks for explaining it, now I see your point. Indeed, this
*might* do the trick. Or might not, depends on how I resolve the slope
numbering and a few other issues... I'll have to think about that a
little bit.
In the meanwhile, I managed to optimise the actual code even more. I
also made the quadrant methods, so the amount of code was
automatically reduced by 75%. The speed gain, together with the
previous optimisation, is impressive. Might be hard to beat :P.
Now, let me get a ballpen and a sheet of paper. I have to think
seriously about that slope numbering thing...
Mingos
Mingos
moment it's available in C and C++, although I'm planning some ports
to other languages.
I finally reverted to the initial angle calculation. I spent quite
some time trying to solve the problem of impenetrable diagonal lines
of obstacles and found no acceptable solution. Those of you who have
downloaded the initial version will notice that the code has been
cleaned up and optimised, apart from being generalised using a
quadrant calculation function.
Those of you who use libtcod may also download the latest 1.4 branch
from its SVN repository to try MRPAS out and possibly bench it against
other libtcod FOV algorithms.
Mingos
russell...@gmail.com
It really only took moving the methods into the Fov class, and
changing array declarations to C# style ones.
It's working very well.
@Mattew Allen:
It is definitely not symmetrical like that.
In a situation like this:
#
#
#
#
@
#
#
#
#M
The M can see you, but you can't see the M.
russell...@gmail.com
Anyways,
Instead of storing it as a float, what about a struct with some shorts
for the x and y.
You could compare them by doing fraction algebra:
y1 y2
___ > ___
x2 x2
Is equivalent to a*d > b*c, so you only have whole numbers.
Mingos
Hey.
I'm glad it works. I've done a few improvements since I last uploaded
it to the server so you'll be able to squeeze a bit more from the
algo. I'll upload the optimised version later.
As for storing "it" as a struct with shorts and comparing "them" -
I've no idea what you are referring to :/. Anyways, the formula you
wrote is equivalent to y1 > y2...
Editing posts, AFAIK, isn't possible, but you can delete your own post
and then post a new one.
Mingos
Paul Donnelly
> Is it possible to edit posts?
No, that wouldn't make any sense. I see you're posting through Google,
so this may look like a forum to you, but it isn't. Usenet is more like
email.
> Anyways,
> Instead of storing it as a float, what about a struct with some shorts
> for the x and y.
> You could compare them by doing fraction algebra:
> y1 y2
> ___ > ___
> x2 x2
> Is equivalent to a*d > b*c, so you only have whole numbers.
What would the benefit be? Not that I've really been following this
discussion closely, but I figured I should say something on topic
too. Seems like floats are plenty precise for this purpose. Not that
exact rationals aren't cool.
Martin Read
>russell...@gmail.com writes:
>> Is it possible to edit posts?
>
>No, that wouldn't make any sense. I see you're posting through Google,
>so this may look like a forum to you, but it isn't. Usenet is more like
>email.
It is technically possible to supersede a post with a revised version,
but many news servers no longer honour such requests due to abuse.
--
\_\/_/ turbulence is certainty turbulence is friction between you and me
\ / every time we try to impose order we create chaos
\/ -- Killing Joke, "Mathematics of Chaos"
Matthew Allen
> @Mattew Allen:
> It is definitely not symmetrical like that.
> In a situation like this:
> #
> #
> #
> #
> @
> #
> #
> #
> #M
>
> The M can see you, but you can't see the M.
Ah well...
Mingos
No, neither M can see you no can you see M. The algo isn't 100%
symmetrical, but the corner peeking/T-junction is flawless.
Mingos
russell...@gmail.com
If you have a room, someone inside it can see all of the walls all the
way around, so the @ coming in can't see the corner, but the M in the
corner can see. Maybe in my example it was too long for any of them to
see it.
############
#__________#
@_________#
#__________#
#__________#
#__________#
#__________#
#M________#
############
Either way, I don't symmetricallity is that big of a deal. I might add
something that makes them automatically visible, or at least some
marker that shows where they are if the monsters shoot at you.
Presumably you can guess where a monster that's shooting at you is, at
least after several shots, even if you can't see them.
My game is coming along... but there's still quite a ways to go. It is
traditional ASCII (well, extended ASCII actually), programmed in C#.
It uses Windows API commands, but with WINE it should work under Mono
on Linux. It will be a futuristic, space-trader type theme. Some
features that I have so far are separate threads for reading key
presses and displaying the screen. This allows for effects like the
ASCII snow on another discussion. I could also implement randomly
morphing creatures like Nethack has when your hallucinating, but ones
that change in real-time. I also added smart box drawing characters
that only show up when it's explored. So, in a room complex like this,
someone teleported to (1) would see a single room, with the corner
characters on the right, not the T connectors that are there. Someone
at 2 would see something similar. Someone at (3) would see a wall with
no bends until they saw around the corner.
#########################
#_____1_____#___________#
#___________#___________# 3
#___________#_____2_____#
#########################
Simple animations would be possible, though I don't have much to work
with. Maybe like stars streaking by when you're flying.
I also plan to add some Lua support.
If I ever finish, I'll put it up here.
Mingos
Could send me your C# version of the algo via email? If it does
something like this, something's not working fine there. It is
possible that the version that's currently on the site is a little
buggy as well since I made some improvements since it was uploaded. I
just didn't find the will to update all 3 versions I'm with (C++, C
and C for libtcod - only the last one, available via libtcod's SVN, is
fully up to date, and perhaps the C++ version on my hard disc, but
I'll have to double check that since I think I only updated the test
version... :/
Mingos
Mingos
One more thing. Do you mark, by any chance, the cell where the @ is as
opaque? This would explain the misbehaviour, although I see no reason
why you would mark this cell as opaque...
Mingos
russell...@gmail.com
That must be it. I only have the beginnings so far, so the character
was walking through walls, and the wall is opaque.
I didn't expect that that would make a difference.
Anyway, I tested it with a clear door, and you're right.
Mingos
It makes a difference.
When processing transparent tiles, the algorithm checks whether their
central angle is unobstructed, nothing else. If you cannot see the
centre of the angle range, you cannot see the tile. In a corridor, a T-
junction can only be seen when you're at most 2 tiles away from it.
After that, it's not visible. However, walls have a different
behaviour. The algo checks all three angles: centre and both sides of
the cell. If you can see any of them, you can see the whole tile. This
assures that when in a corridor, you'll see the walls and not only the
ground right in front of you.
Anyway, glad that's sorted out :D.
Mingos
pende...@gmail.com
> In a corridor, a T-
> junction can only be seen when you're at most 2 tiles away from it.
> After that, it's not visible. However, walls have a different
> behaviour. The algo checks all three angles: centre and both sides of
> the cell. If you can see any of them, you can see the whole tile. This
> assures that when in a corridor, you'll see the walls and not only the
> ground right in front of you.
So if I understand you, in such a corridor with a distant T-
intersection going off at a right angle, you'd see a series of visible
walls, then a black "undiscovered / unseen" tile, then a series of
visible walls after it. When you get within two tiles, the black
square would turn into a floor tile (or a monster if one is standing
there, etc.).
Is that right? As an approach, I think it makes a lot of sense toward
reconciling some of our contradictory intuitions about line-of-sight,
even if I'd personally find it a little strange visually.
Also, kudos on breaking the performance record if I'm reading this
thread correctly.
Mingos
> So if I understand you, in such a corridor with a distant T-
> intersection going off at a right angle, you'd see a series of visible
> walls, then a black "undiscovered / unseen" tile, then a series of
> visible walls after it. When you get within two tiles, the black
> square would turn into a floor tile (or a monster if one is standing
> there, etc.).
>
> Is that right? As an approach, I think it makes a lot of sense toward
> reconciling some of our contradictory intuitions about line-of-sight,
> even if I'd personally find it a little strange visually.
Yes, this is exactly how it behaves. I find it the most natural and
intuitive. In the corridor you mentioned (I assume it's going straight
north from the PC), you see the right and left sides of the wall
cells, thus they should be in FOV. However, the empty cell at the
corridor intersection cannot be identified. The only thing the PC
knows about it is that there's no wall, but since it's an open space,
there might be an item lying there, or perhaps a creature hiding. To
see the cell's contents, the PC needs to draw nearer.
Visually, it might not be as pleasing as, say, permissive FOV, because
by seeing a wall's edge, the entire cell is lit, resulting in a lit
square area instead of just a surface. But the gameplay implications
are very positive because both the PC and the NPC's can use stealth
effectively. Such behaviour, paired with the algo's restrictivity and
the fact it always projects a shadow behind an obstacle, makes it a
possibility worth of considering if you want stealth play. Not that
I'm advertising, but this was the purpose I wrote the algo for. Note
that the only algorithm that always projects a shadow behind an
obstacle used to be modeling LOS rays ("diamond raycasting" in
libtcod), which is, unfortunately, rather slow and the shadow, even
though quite elegant, is still just a one cell wide line.
> Also, kudos on breaking the performance record if I'm reading this
> thread correctly.
It seems so. The performance tests haven't been performed for the
final version yet, but it is expected to mash the other algos to a
pulp since quite a few optimisations have been introduced since the
last speed test. Large outdoor areas still seem to be the algo's weak
point, but apart from that the speed is quite good.
Although your kudos tickles my overdeveloped sense of vanity in a very
pleasant way, I prefer to wait for the "official" benchmarks in Jice's
paper (he promised to update it) :D. Thanks for the acknowledgement
nonetheless :).
Mingos
Matthew Allen
> > Also, kudos on breaking the performance record if I'm reading this
> > thread correctly.
>
> It seems so. The performance tests haven't been performed for the
> final version yet, but it is expected to mash the other algos to a
> pulp since quite a few optimisations have been introduced since the
> last speed test. Large outdoor areas still seem to be the algo's weak
> point, but apart from that the speed is quite good.
Do you have a sense of how switching from octants to quadrants changed
the performance? I would expect it to be faster with octants on large
maps, for sure, although I'm not sure what would happen in more
confined situations.
Mingos
10% performance loss. This was measured in a large open space (112x90
forest), which is the "worst case" for the algo. In tight spaces,
speed loss wasn't visible at all.
Mingos