fov study
jice
apparent limitation on the number of pictures per article, but you can
get it in pdf format here :
http://roguecentral.free.fr/libtcod/downloads/fov.pdf
Note that contrary to what is said in the intro, digital fov is no
more in libtcod because precise permissive seems to be a better
alternative.
Feel free to bash me on any mistake I may have done, or any divergent
opinion you may have on the conclusions.
--
jice
tyre...@gmail.com
A few minor nits. Permissive speed breakdown should be 9/3/0 red/
yellow/green based on the coloring. s/it consists in/it consists of/ s/
console/text console/ s/there is few/not much has been written/.
Looking at the map comparisons is fascinating. I only wish there were
more. For instance, it would be really interesting to look at all of
the map situations you found which caused asymmetry in shadowcasting/
raycasting and see if they really seem to matter. It would also be
interesting to see a few specific situations which might be common to
a game, for instance the five steps leading to the entrance to a room,
and see how each algorithm handles them. Illustrations of 'flicker'
problems. That sort of thing.
It would also be nifty to compare more algorithms. One question I was
left with was what sorts of changes the artifact-cleanup algorithm had
on raycasting especially in 'outdoor' maps. Another question is how
much does the number of rays affect raycasting accuracy. It would be
really interesting to compare raycasting with 100 rays vs. raycasting
with 10 rays vs. raycasting with 1000 rays. It was also surprising
that raycasting 'visible squares' were not a subset of shadowcasting
'visible squares' which is what I expect from my understanding of the
algorithms.
Even weirder algorithms suggest themselves for comparison like
'reverse shadowcasting' where you can see a square only if that square
has normal shadowcasting fov to you. Or permissive type algorithms
where only a subset of the square is used to determine FoV rather than
the whole thing. Can you publish the source you used to run these
tests and generate those comparisons? That way we could try all kinds
of crazy algorithms and get a good sense of how they stack up.
Regarding digital FoV, I think that you should leave it in the
library. Although your experiments didn't really accentuate the
differences, it actually provides a distinct FoV from permissive and
that difference may be what some people want from a gameplay
perspective.
Thanks for running these tests. It has been illuminating!
-D
b0rsuk
> On Jan 30, 5:59 pm, jice <jice.nos...@gmail.com> wrote:
> Looking at the map comparisons is fascinating. I only wish there were
> more. For instance, it would be really interesting to look at all of
> the map situations you found which caused asymmetry in shadowcasting/
> raycasting and see if they really seem to matter. It would also be
> interesting to see a few specific situations which might be common to
> a game, for instance the five steps leading to the entrance to a room,
> and see how each algorithm handles them. Illustrations of 'flicker'
> problems. That sort of thing.
Yes, yes, yes !
Especially that in some cases assymetry may be ok, for example in
'reverse corner peeking' with 'diamond' algorithm you said it looks
somewhat realistic..
Overall, I was really disappointed that diamond turned out to be so
assymetric. For player/monster FOV precise permissive is probably
still the only choice if you want it to be fair. Please expand the
part on assymetry. You marked visible squares which can't see the
player, could you mark the opposite as well ? Not visible squares
from which player can be seen. They should be marked with another
color, how about light blue ? If we have more insight into assymetry,
perhaps it will be enough to use some post-processing. I'd rather
avoid that, but some algorithms are really interesting. Basic and
shadow are nicer in some ways - they produce triangular shadows.
But in cases where symmetry doesn't matter so much, all of them are
potentially interesting. They could be used for explosions, spells
etc. I think digital lines is overall the ugliest. Meanwhile,
'diamond' has few sharp edges and could even be used for dungeon
generation. If you place the obstacles right, the lit area looks
vaguely like a cave.
b0rsuk
Altefcat
One question, why is symmetry so important? Once you've computed the
player FOV, if the player sees a monster, then the monster sees the
player too, as simple as that. And if you need to know if the monster
sees something else (other monster, door, trap, ...), just run FOV
from the monster pos.
As a sidenote, the diamond FOV seems the closer to reality to me, the
more natural. I don't like the way the other algos let the player see
squares just behind a pillar, that doesn't seem right to me.
b0rsuk
> One question, why is symmetry so important?
It makes things easier - or rather, there are no further complications
and little to worry about.
> Once you've computed the
> player FOV, if the player sees a monster, then the monster sees the
> player too, as simple as that. And if you need to know if the monster
> sees something else (other monster, door, trap, ...), just run FOV
> from the monster pos.
It is a solution, but not a perfect one. Let's assume player sees
monster, but not vice versa. You fix it in the way described above.
Then you try to use FOV to check if monster sees something on player's
square. It doesn't ! Of course, you can fix the fix by making it so if
player sees monster, then monster sees everything on player's square,
including player. But this has another ugly effect - monster's FOV
depends on what player can see.
b0rsuk
> As a sidenote, the diamond FOV seems the closer to reality to me, the
> more natural. I don't like the way the other algos let the player see
> squares just behind a pillar, that doesn't seem right to me.
I'm wondering what would be better - fix diamond fov with some
postprocessing, or apply postprocessing to precise permissive, while
still making sure it remains symmetric ? Either way, it's pretty clear
that 'diamond fov' is has very interesting behaviour.
b0rsuk
Altefcat
> On Jan 31, 9:39 am, Altefcat <edemp...@gmail.com> wrote:
>
> > One question, why is symmetry so important?
>
> It makes things easier - or rather, there are no further complications
> and little to worry about.
>
> > Once you've computed the
> > player FOV, if the player sees a monster, then the monster sees the
> > player too, as simple as that. And if you need to know if the monster
> > sees something else (other monster, door, trap, ...), just run FOV
> > from the monster pos.
>
> It is a solution, but not a perfect one. Let's assume player sees
> monster, but not vice versa. You fix it in the way described above.
> Then you try to use FOV to check if monster sees something on player's
> square. It doesn't ! Of course, you can fix the fix by making it so if
> player sees monster, then monster sees everything on player's square,
> including player. But this has another ugly effect - monster's FOV
> depends on what player can see.
>
> b0rsuk
That's not ugly if the player does not realize it. I think that you
can not deal 'honestly' with everything happening in the game; you
need to 'cheat' at some time by dealing with events directly connected
to the player (micro events), and only simulating at a large scale the
flow of life elsewhere (macro events), so that the game does not
appear centered on the player actions.
Well, after thinking about what I wrote, what I said is mostly true
with persistent dungeons and landscape, which may not be every
roguelike feature.
Jakub Debski
> One question, why is symmetry so important? Once you've computed the
> player FOV, if the player sees a monster, then the monster sees the
> player too, as simple as that. And if you need to know if the monster
> sees something else (other monster, door, trap, ...), just run FOV
> from the monster pos.
It is important for ranged attacks.
You can be attacked by monster that is not seen by you and you can
attack monster that won't be able to notice you.
It's very important gameplay issue for games that use mostly ranged
attacks (f.e. futuristic).
regards,
Jakub
gribbly...@hotmail.com
developers make the right choices. I did however wonder how close to
canonical do you think your implementations are? Behaviour and speed
will probably vary significantly through different implementations, so
I'm interested to know whether (for instance) your shadowcasting
algorithm is fairly standard or heavily modified.
Work is progressing on the new version of 'Diamond' raycasting, which
I hope will perform a bit better. I may work on symmetry as well, as
you've noted gameplay considerations - Diamond is probably not
symmetric due to the starting conditions of obstructions which should
be easily rectified. Basically, obstruction data gets initialised at
one extreme, rather than a midpoint. I believe that if the walls are
initialised with obstruction data at their midpoints, the algorithm
will have a much more symmetric result.
Gerry Quinn
Just to be clear, though, you are saying here (correctly, I think) that
symmetry is bad in games with ranged attacks?
I'm not sure symmetry is either essential or all that bad. One could
argue that some degree of symmetry is necessary insofar as if weapon
damage travels along the path of a light beam, some portion of each
protagonist mist be in FOV of the other, at least some of the time.
Cover could be accounted for separately. Symmetry tends to have
gameplay benefits for roguelikes too - at least there is *something*
direct you can do to challenge the enemy that is shooting you.
On the other hand, realism might dictate that the ranged attacker who
has placed you in a nice killing zone cannot be directly attacked
without a small army that will in the process become still smaller.
Then FOV is irrelevant because you have to find another way round to get
to him.
- Gerry Quinn
--
Lair of the Demon Ape (a coffee-break roguelike)
<http://indigo.ie/~gerryq/lair/lair.htm>
Jakub Debski
> Just to be clear, though, you are saying here (correctly, I think) that
> symmetry is bad in games with ranged attacks?
Symmetry is good for games with ranged attacks.
Read my Introduction to
http://roguebasin.roguelikedevelopment.org/index.php?title=Mutual_Visibility_Field_Of_View
regards,
Jakub
msa...@gmail.com
Jice, a very nicely done report. I can see that it is already
encouraging the people on this forum to develop or optimize these
algorithms based on your findings. Thank you for your hard work.
jice
> On Jan 30, 5:59 pm, jice <jice.nos...@gmail.com> wrote:
>
> > I didn't manage to wikify the document on roguebasin due to an
> > apparent limitation on the number of pictures per article, but you can
> > get it in pdf format here :http://roguecentral.free.fr/libtcod/downloads/fov.pdf
>
>
> yellow/green based on the coloring. s/it consists in/it consists of/ s/
> console/text console/ s/there is few/not much has been written/.
"it consists of the determination of which part blablabla" ?
"it consist in the determination" is not right ? damn, my english
sucks... ;)
>
> Looking at the map comparisons is fascinating. I only wish there were
> more. For instance, it would be really interesting to look at all of
> the map situations you found which caused asymmetry in shadowcasting/
> raycasting and see if they really seem to matter. It would also be
> interesting to see a few specific situations which might be common to
> a game, for instance the five steps leading to the entrance to a room,
> and see how each algorithm handles them. Illustrations of 'flicker'
> problems. That sort of thing.
If you're refering to the flickering bug in diamond raycasting when
facing a wall with two holes, I don't reproduce it with my
implementation. Might be luck because I didn't do anything to fix it,
but yes I think some more specific situations may worth being
analysed.
>
> It would also be nifty to compare more algorithms. One question I was
> left with was what sorts of changes the artifact-cleanup algorithm had
> on raycasting especially in 'outdoor' maps. Another question is how
> much does the number of rays affect raycasting accuracy. It would be
> really interesting to compare raycasting with 100 rays vs. raycasting
> with 10 rays vs. raycasting with 1000 rays. It was also surprising
> that raycasting 'visible squares' were not a subset of shadowcasting
> 'visible squares' which is what I expect from my understanding of the
> algorithms.
In fact I'm only using "perimeter raycasting" (casting a ray to each
cell on the fov perimeter) because there is no interest in lowering
resolution (it becomes only faster and uglier, but we don't really
need it to be faster), nor increasing it (slower but no real visual
improvement). The post-processing step makes it much more permissive,
which explains why it's no more a subset of shadowcasting.
>
> Even weirder algorithms suggest themselves for comparison like
> 'reverse shadowcasting' where you can see a square only if that square
> has normal shadowcasting fov to you. Or permissive type algorithms
> where only a subset of the square is used to determine FoV rather than
> the whole thing. Can you publish the source you used to run these
> tests and generate those comparisons? That way we could try all kinds
> of crazy algorithms and get a good sense of how they stack up.
Yeah i'm interested in any other algorithm that may be competitive
both speed and gameplay wise.
>
> Regarding digital FoV, I think that you should leave it in the
> library. Although your experiments didn't really accentuate the
> differences, it actually provides a distinct FoV from permissive and
> that difference may be what some people want from a gameplay
> perspective.
Indeed it's slightly more permissive than precise permissive, but I
removed it because I think permissivity is bad for fov (because the
main goal of fov is to hide things that are out of fov. The more
shadows you have, the more shadow-based gameplay you can have). The
slight visual difference does not worth the huge speed lost.
>
> Thanks for running these tests. It has been illuminating!
>
Thanks :) I hope it will trigger some new interest in fov algorithms
and who knows, maybe someone will invent a killer algorithm ? Someone
suggested a pretty revolutionary one on doryen's blog (http://
doryen.blogspot.com) that seems to have lots of interesting features.
--
jice
jice
> On Jan 31, 4:12 am, tyrec...@gmail.com wrote:
>
> Overall, I was really disappointed that diamond turned out to be so
> assymetric. For player/monster FOV precise permissive is probably
> still the only choice if you want it to be fair.
In fact I don't think symmetry really matters. In real life, it's
perfectly possible to see someone and being able to shoot at him
without being seen. The real issue is when the creature doesn't react
when you shoot it. It's more an AI issue than a fov issue.
Also note that any asymmetric fov can be converted to symmetric fov
provided your calculate it for every creature (which is perfectly
possible according to the algorithms speed) and replace the "creature
in my fov" test by "creature in my fov or myself in the creature fov"
--
jice
jice
I agree, but on another hand, I don't really like having a shadow
limited to a line where you're next to the pillar.
--
jice
Simon Richard Clarkstone
"We call pillar a wall cell surrounded with empty cells."
should be
"We call a wall cell surrounded by empty cells a pillar."
Your implementation of shadow-casting seems very permissive; it allows
visibility with any non-empty zero-area (zero-angle) intersection.
You could add a second shadow-casting algorithm that requires the start
and end angles of visibility to be different for a cell to be visible
i.e. disallows zero-angle visibility. The difference will be quite
noticeable in your examples.
A more-restrictive variant of shadow-casting would only make cells
visible if their centre was visible (equivalent to having a clear
centre-to-centre straight line). This is symmetric.
An even-more-restrictive variant has both of the above restrictions on
visibility.
Did you use floats, rationals, or scaled arithmetic for the shadow
angles? Floating-point errors will make a difference.
Since your paper is in English, it would probably be best to use the
English and American system of the fraction separator being a dot not a
comma. Also, percent is more widely recognised than permille for ratios.
Mixing ms and µs for units is somewhat confusing and makes comparisons
slightly more difficult, and I don't think it is worth the saving in
digits, so just use µs.
A graph of % visibility (x) against speed (y) could be informative (with
both scales logarithmic).
--
Simon Richard Clarkstone:
s.r.cl?rkst?n?@dunelm.org.uk / s?m?n_cl?rkst?n?@yahoo.co.uk
| My half-daughter went to the GMH riots |
| But all I got was this stupid ¥-shirt. |
jice
> Nice document, and your hard work I'm sure will help roguelike
> developers make the right choices. I did however wonder how close to
> canonical do you think your implementations are? Behaviour and speed
> will probably vary significantly through different implementations, so
> I'm interested to know whether (for instance) your shadowcasting
> algorithm is fairly standard or heavily modified.
I didn't modify the algorithms themselves. Most implementations are
copy & pasted from roguebasin (and converted to C when needed). The
only optimization is on the C implementation (avoid memory allocation
and inept container operations).
All implementations can be reviewed on libtcod svn repository :
http://code.google.com/p/libtcod/source/browse/trunk/src
There's one file per algorithm.
>
> Work is progressing on the new version of 'Diamond' raycasting, which
> I hope will perform a bit better. I may work on symmetry as well, as
> you've noted gameplay considerations - Diamond is probably not
> symmetric due to the starting conditions of obstructions which should
> be easily rectified. Basically, obstruction data gets initialised at
> one extreme, rather than a midpoint. I believe that if the walls are
> initialised with obstruction data at their midpoints, the algorithm
> will have a much more symmetric result.
My main reproach (but it's a personal opinion) is that it's too
permissive in pillar/corner peeking cases.
--
jice
stu
> Feel free to bash me on any mistake I may have done, or any divergent
> opinion you may have on the conclusions.
Nice work, some good illustration there.
I think its pretty amazing that plain old blasting lines out
works better than some of the more advanced stuff.. (imo)..
interesting to note ultima 4 used a permissive fov
but ultima iii used a plain line blasting method.
-stu
jice
Floats. I'm using a C conversion of this algorithm :
http://roguebasin.roguelikedevelopment.org/index.php?title=PythonShadowcastingImplementation
>
> Since your paper is in English, it would probably be best to use the
> English and American system of the fraction separator being a dot not a
> comma. Also, percent is more widely recognised than permille for ratios.
>
> Mixing ms and µs for units is somewhat confusing and makes comparisons
> slightly more difficult, and I don't think it is worth the saving in
> digits, so just use µs.
Thanks. I posted a new version with those fixes.
>
> A graph of % visibility (x) against speed (y) could be informative (with
> both scales logarithmic).
>
What do you call visibility(x) ? The size of the fov ?
--
jice
b0rsuk
> If you're refering to the flickering bug in diamond raycasting when
> facing a wall with two holes, I don't reproduce it with my
> implementation. Might be luck because I didn't do anything to fix it,
> but yes I think some more specific situations may worth being
> analysed.
Perhaps you don't know what to look for ? Try this input data:
Walls: (a horizontal line x 10-12, y = 11; a vertical line x=14, y
5-11)
wall (10, 11)
wall.(11, 11)
wall (12, 11)
wall (14, 11)
wall (14, 10)
wall (14, 9)
wall (14, 8)
wall (14, 7)
wall (14, 6)
wall (14, 5)
Now try FOV from these positions: (walking down 16, 14 to 16, 17)
Origin: (16, 14)
Origin: (16, 15)
Origin: (16, 16)
Origin: (16, 17)
b0rsuk
Kusigrosz
> On Jan 31, 9:39 am, Altefcat <edemp...@gmail.com> wrote:
>> One question, why is symmetry so important?
>
> It makes things easier - or rather, there are no further complications
> and little to worry about.
>
>> Once you've computed the
>> player FOV, if the player sees a monster, then the monster sees the
>> player too, as simple as that. And if you need to know if the monster
>> sees something else (other monster, door, trap, ...), just run FOV
>> from the monster pos.
>
> It is a solution, but not a perfect one. Let's assume player sees
> monster, but not vice versa. You fix it in the way described above.
> Then you try to use FOV to check if monster sees something on player's
> square. It doesn't ! Of course, you can fix the fix by making it so if
> player sees monster, then monster sees everything on player's square,
> including player. But this has another ugly effect - monster's FOV
> depends on what player can see.
Does it make sense to use a different condition to determine
monsters/objects visibility and terrain visibility?
I've been using for some time an algorithm - I think it's a version of
shadowcasting - which computes two kinds of vision: central, if there
is an unblocked line from the centre of the viewer's cell to the centre
of the given cell; and other, when there is an unblocked line from
the centre of the viewer's cell to any point in the given cell.
The central vision is thus symmetric, the other is not. Vision-blocking
terrain is regarded visible in other vision, anything else requires
central vision - this includes ranged attacks. The vision-blocking area
of the cell is a diamond ;-) obtained by connecting the midpoints of
the sides; the lines passing exactly through these midpoints are
considered blocked. The result looks like this:
http://tinyurl.com/av7l6p
The T's are trees - vision blocking terrain. The tree two cells above
and one to the left of the player is visible in other vision,
but the corresponding place two cells above to the right is grey - it
is also visible in other vision, but the terrain there is not vision
blocking (it is remembered to be grass). A monster or object in this
place would not be visible.
The fact that the vision-blocking terrain is blocking only with a
fragment of the cell but is visible whenever a line of sight passes
through any point of the cell is somewhat inconsistent, but I haven't
noticed any practical problems yet. Also, currently I don't have any
passable vision-blocking terrain - in such a case a monster might
pass through a cell that is displayed to the player as terrain. Could
be a feature, but needs testing.
--
Kusi...@AUtorun.itvk.pl To send mail, remove 'AU' from the address
You see here a scroll labeled "cV2NpPqIHnw"
Simon Richard Clarkstone
That seems slightly familiar. I think I saw that done somewhere in a
way that was compiled into a state machine, but I can't find it now.
The result inspected the minimal amount of the map and contained huge
numbers of gotos.
jice
ok I reproduce this one. The one I didn't reproduce is a vertical wall
with two holes in it. Ok, then there are consistency issues with
current diamond implementation.
--
jice
Darren Grey
A brilliant analysis. Especially love the pics :) Remarkable how
well the basic raycasting holds up, and even seems downright
preferable in cavern or outdoor style cases with lots of pillars. For
this reason I think I'll now avoid converting to shadowcasting for
Gruesome - linecasting is perhaps preferable for my needs.
You said elsewhere that increasing resolution of linecasting wasn't
important - well, in some cases I think it is. When first
implementing it I found that increasing the sight radius of the
character would make some areas obscured for higher sight values,
because the lay of the line happened to get blocked, whilst at lower
sight radii it fit perfectly. It seemed illogical to me that
increasing your sight radius would make certain areas no longer
visible. More importantly was the affect this would have on gameplay,
since enemy light was calculated by FOV - it would be unfair for the
player to get killed by enemy light that reached him when he couldn't
see the source because his sight range was too long!
For this reason I do linecasting out to a cirlce of radius 40 (320
lines), and this ensures the player will always be able to see the
same things when his sight radius is increased, and will always be
able to see any light source that can hit him. Probably reduces some
symmetry problems too. I could likely have the same effective
resolution at radius 20 or 15 in fact (used to use 80), but 40 is
handy for when I want to stretch out visual range in bug-testing.
Enemy FOV is cast to radius 10 (their maximum sight is 7) and I have
no FOV speed issues with 15 enemies and the player recalculating every
round.
I have a couple of ideas for other FOV systems that I might try some
time, just for fun really. Will let you know if I get anywhere with
them :)
--
Darren Grey - http://gruesomegames.com
"It is pitch black. You are likely to eat someone..."
Altefcat
> Gerry Quinn brought next idea :
>
> > Just to be clear, though, you are saying here (correctly, I think) that
> > symmetry is bad in games with ranged attacks?
>
> Symmetry is good for games with ranged attacks.
>
> regards,
> Jakub
So symmetry is good for ranged attacks between monsters; that's quite
a rare case. And even in that case, when you browse every monster in
your game loop, whenever a monster A can see another monster B, but B
cannot see A, why not let B know the line of sight from A to B?
tyre...@gmail.com
> So symmetry is good for ranged attacks between monsters; that's quite
> a rare case. And even in that case, when you browse every monster in
> your game loop, whenever a monster A can see another monster B, but B
> cannot see A, why not let B know the line of sight from A to B?
There are three main advantages to symmetric line of sight. And, btw,
adding a post-processing step that says "If you can see me, I can see
you too." is a one way to create a symmetric algorithm.
First, many asymmetries a lot of algorithms have tend to act counter-
intuitively with respect to cover. If somebody is in the doorway of
the room, the expectation is that they will be able to see most of the
room pretty clearly but they will be a bit concealed from a large part
of the room. Raycasting/Shadowcasting tend to result in the reverse.
Nearly every spot in the room will be able to see the entrance, but
the entrance will be limited to a fairly restricted subset. There are
many cases like this including the infamous knight's move around walls
in Angband where if you are on the long end you can see the enemy but
they can't see you.
Second, games (and roguelikes in particular) should strive to treat
the player and monsters equally except where play balance dictates
otherwise. If you don't do this, you risk the player calling foul play
and giving up (I got killed by an archer I couldn't even see), or the
player developing an exploit (I get two extra blows on this enemy
because of the turn in the corridor). Doing a simple "If I can see
them, they can see me." algorithm where only the player's otherwise
asymmetric FoV is used creates the former problem.
Suppose the player is at the entrance to a room like I discussed
earlier, and a monster is inside at the edge of the player's viewing
angle. The monster's AI decides to flee to gain some time to heal. So,
being a clever AI, it moves outside of the player's viewing angle and
gains a turn of respite as the player has to move into the room. This
is especially advantageous if there is something (other monsters)
preventing it from entering the room. Lets see how the reverse
situation plays out. The player is almost dead and moves in the exact
same way. But now, because the enemy is still in the player's FoV, it
can still see the player! Which means that the player cannot take
advantage of a potentially life-saving maneuver that the monster can.
If a player experiences both of these situations, they will feel
understandably annoyed.
Third, guaranteed symmetric algorithms open up simpler and more
elegant ways of managing secondary aspects of field of view or
lighting. Take the example of a lamp in a world with changeable
visibility (doors opening and closing, walls created and destroyed).
If that lamp uses an asymmetric FoV, it has mark every square that is
visible to it and say "If your opaqueness changes, let me know so I
can recalculate." This means potentially a list of points which you
have to manage and all kinds of complexities and inefficiencies.
But if you have a symmetric algorithm, you can just mark every square
as 'lit', a single boolean flag. Then whenever a square is about to
change opaqueness, you just run FoV from that square and tell every
light source you find to recalculate. You also avoid recalculating
lightsources that are not visible.
Similarly, an AI algorithm might want to be notified of a state change
in its FoV. Instead of adding a reference to the AI on the map square,
you just mark a single bit "AI_WATCHED" and notify the AI when there
is a state change by using FoV from the changing square. This can be
used even when the AI has to notice state change in a lot of mostly
static squares. You want your guard to notice when a wall turns to mud
or a cave-in happens just as much as when the player arrives.
That said, symmetry isn't the end-all and be-all of algorithms. There
are other trade-offs to keep in mind. And for stealth-type games,
asymmetry is often useful whether it is implemented through facing or
lighting or through the FoV algorithm itself.
-D
Xecutor
tweaked...
It's not recursive one.
In this algo corners are supposed to be a little roundish.
I don't know what is your api, so here is copy/paste from my sources.
Shouldn't be too difficult to adopt.
Position is class with int x,y;
getCell - get cell of level
canBeSeenThru - if cell blocks sight
[code]
struct VisCell{
int upper_count;
int upper_max;
int lower_count;
int lower_max;
bool visible;
bool lit;
bool plit;
bool lit_delay;
void init()
{
upper_count=0;
upper_max=0;
lower_count=0;
lower_max=0;
visible=true;
lit=true;
plit=true;
lit_delay=false;
}
bool zeroUpper()
{
return upper_max==0;
}
bool zeroLower()
{
return lower_max==0;
}
bool hasUpperMax()
{
return !zeroUpper() && upper_count+500>=upper_max &&
upper_count-500<=upper_max;
}
bool hasLowerMax()
{
return !zeroLower() && lower_count+500>=lower_max &&
lower_count-500<=lower_max;
}
};
struct VisCellArray{
VisCellArray(int n)
{
array=new VisCell[n];
size=n;
}
~VisCellArray()
{
delete [] array;
}
VisCell& operator[](int idx)
{
if(idx<0 || idx>=size)
{
static Logger* log=Logger::getLogger("vis.[]");
LOGWARN(log,"index out of array range:%{}",idx);
return array[0];
}
return array[idx];
}
VisCell* array;
int size;
};
void GameField::FOVGenerator(Level* lvl,const Position& pp,int
sr,void* data,void (*visfunc)(Level* lvl,const Position& src,const
Position& p,void* data))
{
VisCellArray Cell(sr+1);
int up_inc;
int low_inc;
int south;
bool blocker;
bool nblocker;
int sr2=sr*sr;
for(int oct=0;oct<8;oct++)
{
Cell[0].init();
int dx=0,dy=0;
bool swpxy=false;
switch(oct)
{
case 0:dx=1;dy=1;break;
case 1:dx=-1;dy=1;break;
case 2:dx=-1;dy=-1;break;
case 3:dx=1;dy=-1;break;
case 4:swpxy=true;dx=1;dy=1;break;
case 5:swpxy=true;dx=-1;dy=1;break;
case 6:swpxy=true;dx=-1;dy=-1;break;
case 7:swpxy=true;dx=1;dy=-1;break;
}
for(int column=1;column<=sr;column++)
{
bool visColumn=false;
for(int cell=0;cell<=column;cell++)
{
int lx=swpxy?pp.x+dy*cell:pp.x+dx*column;
int ly=swpxy?pp.y+dx*column:pp.y+dy*cell;
int nx=swpxy?lx-dy:lx-dx;
int ny=swpxy?ly-dx:ly-dy;
if(lx<0 || lx>=lvl->getWidth() || ly<0 || ly>=lvl->getHeight
())
{
continue;
}
if((column*column+cell*cell)>=sr2)continue;
blocker=!lvl->getCell(Position(lx,ly)).canBeSeenThru();
nblocker=nx>=0 && nx<lvl->getWidth() && ny>=0 && ny<lvl-
>getHeight()?
!lvl->getCell(Position(nx,ny)).canBeSeenThru():true;
up_inc=1000;
low_inc=1000;
south=cell-1;
Cell[cell].plit=Cell[cell].lit;
//1
if(cell<column)
{
if(Cell[cell].lit_delay)
{
if(!blocker)
{
if(Cell[south].lit)
{
if(!Cell[south].zeroLower())
{
Cell[cell].lit=false;
Cell[cell].lower_max=Cell[south].lower_max;
Cell[cell].lower_count=Cell[south].lower_count;
Cell[south].lower_count=0;
Cell[south].lower_max=0;
}else
{
Cell[cell].lit=true;
}
}
}
Cell[cell].lit_delay=false;
}
}else
{
Cell[cell].init();
}
//2
if(blocker)
{
if(Cell[cell].lit || (cell>0 && Cell[south].lit) || (cell>0
&& Cell[south].plit && !nblocker))
{
Cell[cell].lit=false;
Cell[cell].visible=true;
int upper=(column*1000-400)*1000;
upper/=(400+cell*1000);
if(upper<1000)
{
upper=1000;
}
int lower=(column*1000+400)*1000;
lower/=(cell*1000-400);
if(lower<0)
{
lower=1000000;
}
if(upper<Cell[cell].upper_max || Cell[cell].zeroUpper())
{
Cell[cell].upper_max=upper;
Cell[cell].upper_count=0;
up_inc=0;
}
if(lower>Cell[cell].lower_max || Cell[cell].zeroLower())
{
Cell[cell].lower_max=lower;
Cell[cell].lower_count=-1000;
low_inc=0;
if(lower<=3000)
{
Cell[cell].lit_delay=true;
}
}
}else
{
Cell[cell].visible=false;
}
}else
{
Cell[cell].visible=false;
}
//3
Cell[cell].upper_count+=up_inc;
Cell[cell].lower_count+=low_inc;
//4
if(cell>0)
{
if(Cell[south].hasUpperMax())
{
if(!Cell[cell].hasUpperMax())
{
Cell[cell].upper_max=Cell[south].upper_max;
Cell[cell].upper_count=Cell[south].upper_count-Cell
[south].upper_max;
}
Cell[cell].lit=false;
Cell[cell].visible=false;
}
//5
if(Cell[south].hasLowerMax())
{
Cell[cell].lower_max=Cell[south].lower_max;
Cell[cell].lower_count=Cell[south].lower_count-Cell
[south].lower_max;
Cell[south].lower_max=0;
Cell[south].lower_count=0;
}
if(!Cell[south].zeroLower() || (Cell[south].zeroLower() && !
Cell[south].lit))
{
Cell[cell].lower_count=Cell[cell].lower_max+10000;
}
}
//6
if(Cell[cell].hasLowerMax())
{
Cell[cell].lit=true;
}
//7
if(Cell[cell].lit || (blocker && Cell[cell].visible))
{
visfunc(lvl,pp,Position(lx,ly),data);
visColumn=true;
}
}
if(!visColumn)
{
break;
}
}
}
}
[/code]
jice
> Here is my implementation of Shadow Casting FOV algo, somewhat
> tweaked...
> It's not recursive one.
> In this algo corners are supposed to be a little roundish.
> I don't know what is your api, so here is copy/paste from my sources.
> Shouldn't be too difficult to adopt.
What is the visual impact on the fov compared to recursive
shadowcasting ? Indeed, I'll probably put it in my torture chamber...
I'll see what it can tell me ;)
--
jice
b0rsuk
> Note that contrary to what is said in the intro, digital fov is no
> more in libtcod because precise permissive seems to be a better
> alternative.
This is not targetted at you personally.
How hard do you think it would be to use post-processing to add
"pillar shadows" to "precise permissive" algorithm ? I suspect 1 line
wide, non-triangular shadows woudln't cause the FOV to become
assymetric ? Lack of pillar shadows is my main complaint about
"precise permissive". This algorithm and the "diamond" are my
favourites so far.
b0rsuk
jice
Well I don't know. Changing the shadow behaviour in a post-processing
step seems pretty difficult to do. Personnally, I don't really like
precise permissive because I think permissivity kills gameplay. The
less, the better. I'd love to use diamond, but right now, it has a few
issues that make me keep using basic/shadow stuff.
--
jice
Xecutor
> shadowcasting ?
For instance diagonal walls case looks like in BASIC.
Ray Dillinger
> Well I don't know. Changing the shadow behaviour in a post-processing
> step seems pretty difficult to do. Personnally, I don't really like
> precise permissive because I think permissivity kills gameplay. The
> less, the better. I'd love to use diamond, but right now, it has a few
> issues that make me keep using basic/shadow stuff.
I was actually sort of hoping someone would say that; I feel the same
way about "permissive" field of view. The suspense/fun comes from
knowing there are things you can't see.
I'm also not as sure about "symmetric" being a virtue as I once was.
Asymmetric view is good tactics. The problem is that the typical
implementation of shadowcasting, raycasting, etc, gets it exactly
backwards.
What's "sensible" and good asymmetric tactics is fire from cover;
where you are peeking around a corner and can see the enemy while
still exposing so little of yourself that you are not likely to be
seen. So, it happens when you can see the center of the enemy's
square from some corner of your square.
The shadowcasting/raycasting etc, gets this exactly backward, and
shows you squares that you can see corners of from the center of
your square. So when you have something which most tacticians
would call superior position, you get inferior FOV, and vice versa.
This kind of WRONG asymmetry breaks immersion and leads to exploits
that are nonsensical and therefore feel cheap or "cheesy", which
makes them a bad gameplay experience.
If it followed and matched our intuition about what ought to be
superior position, it wouldn't feel cheesy, it would just feel like
playing well. Anyway, this feeling of wrongness and cheap/nonsensical
exploits leads people to want symmetric FOV because the asymmetric
FOV they see is clearly wrong.
I'm not so convinced that asymmetric FOV can't be done right; only that
the asymmetric algorithms we've been using don't do it right.
Anyway, symmetric FOV has the property that a symmetric rule determines
which squares are visible from which others. If FOV being true depends
on the centers being mutually visible, then you get symmetric FOV. You
also get symmetric FOV if it depends on corners being mutually visible,
as in "precise permissive". If you have a situation where a corner of
one square is in FOV of another only if it's visible from the center of
that other square, or vice versa, then your FOV is non-symmetric
because the regions of the squares involved on each end aren't the same
regions.
Bear,
Installing fully functional linux with compilers, etc, on a new
160Gbyte atom-powered palmtop this morning, and sort of in awe
about how far handheld devices have come. It's so cute, and it
has wifi and an 8-hour battery life!
gribbly...@hotmail.com
>
> Well I don't know. Changing the shadow behaviour in a post-processing
> step seems pretty difficult to do. Personnally, I don't really like
> precise permissive because I think permissivity kills gameplay. The
> less, the better.
Not sure I really understand the adjective 'permissive' used in this
context. Is Diamond somewhat 'permissive' because it treats viewing
tiles as being the same size as non-viewing tiles? In my opinion there
are only two reasonable stances for an algorithm to take without
having additional information. Those are:
1. The viewing tile has tile width viewing capacity.
2. The viewing tile views from a single point at the center the tile.
Note that (2) is a bit weird because the viewer moves in 1 tile
increments and can't adjust its view within the tile. IMHO, if you
want an algorithm to supply wider shadows, you have to tell it how big
the viewer is compared to the blocking tiles. Only then it will know
what kind of arc to cast.
Cheese Lottery
> Not sure I really understand the adjective 'permissive' used in this
> context.
This article on roguebasin can explain it better than I can:
"A destination square is visible from a source square if there is any
unobstructed line from some point in the source square to some point
in the destination square."
tyre...@gmail.com
> jice wrote:
> > Well I don't know. Changing the shadow behaviour in a post-processing
> > step seems pretty difficult to do. Personnally, I don't really like
> > precise permissive because I think permissivity kills gameplay. The
> > less, the better. I'd love to use diamond, but right now, it has a few
> > issues that make me keep using basic/shadow stuff.
A post-processing step on FoV is a very bad idea in general. But see
below.
> I'm also not as sure about "symmetric" being a virtue as I once was.
> Asymmetric view is good tactics. The problem is that the typical
> implementation of shadowcasting, raycasting, etc, gets it exactly
> backwards.
I agree. To this end, in the demo I point to below, I have
incorporated reverse-shadowcasting FoV as one of the mechanisms. This
precisely reverses the asymmetries we see in shadowcasting. There are
some things I like about it. It would be interesting to base a game
around it and see how it plays.
> If it followed and matched our intuition about what ought to be
> superior position, it wouldn't feel cheesy, it would just feel like
> playing well. Anyway, this feeling of wrongness and cheap/nonsensical
> exploits leads people to want symmetric FOV because the asymmetric
> FOV they see is clearly wrong.
I mentioned this as one reason that symmetric FoV is good in my
previous post. There are others. But whether it is useful or not
depends on your game.
In response to this discussion, I have slightly tweaked my permissive
fov algorithm library so that it can do all kinds of different FoV
algorithms by changing parameters. This includes, shadowcasting,
reverse shadowcasting, and various levels of permissivity.
http://www.xmission.com/~tyrecius/fov-comparison-demo.zip
If you run it on the demo map, you can see each algorithm under
various conditions. You can move around and swap FoV algorithms at any
time.
--- ------
Key Action
--- ------
Num Pad Move
Num Pad 0 Exit
Num Pad 5 Clear Memory
0-8 Set permissive algorithm to k/8 permissiveness
s Use shadowcasting
r Use reverse-shadowcasting
reverse-shadowcasting is especially interesting to me to see how it
runs.
Note that atm, I have set it such that walls are visible if they block
your sight to things further regardless of settings. Before I set it
that way, you would only be able to see a small number of walls in a
room you were in rather than the whole room. This causes some oddities
where a square is visible if it is a wall and invisible if not.
-D
Jakub Debski
> reverse-shadowcasting is especially interesting to me to see how it
> runs.
Very interesting to me as well :)
It's very good for ranged combat games. I planned to change in Xenocide
the way monsters fire, to make them fire from the "neighbour squares"
if Line Of Fire is blocked, but reverse shadowcasting would solve it in
more elegant way. Or... maybe not. Using my idea you can stay in cover
and fire at monsters, without moving.
regards,
Jakub
jice
>
> In response to this discussion, I have slightly tweaked my permissive
> fov algorithm library so that it can do all kinds of different FoV
> algorithms by changing parameters. This includes, shadowcasting,
> reverse shadowcasting, and various levels of permissivity.
>
> http://www.xmission.com/~tyrecius/fov-comparison-demo.zip
>
> If you run it on the demo map, you can see each algorithm under
> various conditions. You can move around and swap FoV algorithms at any
> time.
>
Awesome ! Especially permissive with a medium permissiveness seems
very promising. If it keeps symmetry and it's current speed, it will
probably blow the competition :)
I have to check it further, and reverse shadowcasting too. As a
sidenote, am I the only one who has difficulties reading fov through
sets of green/white ascii characters ? It would be so much relaxing
for the eyes to have, say, the cells in fov with a grey
background... ;P
--
jice
Jakub Debski
> e to check it further, and reverse shadowcasting too. As a
> sidenote, am I the only one who has difficulties reading fov through
> sets of green/white ascii characters ? It would be so much relaxing
> for the eyes to have, say, the cells in fov with a grey
> background... ;P
Could you check my "mutual FOV" in your test environment?
The code is quite clear and shouldn't be hard use.
http://www.alamak0ta.republika.pl/mutual_fov.zip
regards,
Jakub
jice
Are you sure this code works ? I replaced the Lvl class by a TCODMap
and I get crazy results... What does the hardcoded 500 value in
hasLowerMax represent ?
--
jice
jice
Ok, here are a few early results (provided I didn't broke anything
while porting it to TCODMap) :
* it has nice, compact fovs, almost symmetric. There are a few
symmetry errors, but they are so rare than we can almost consider it
as symmetric
* I have some weird behavior in outdoors. Some rays seems to interrupt
and restart a few cells away. Thus, some branches of the standard star-
like outdoor fovs seems to be dotted lines...
* it is MUCH slower than others, even digital fov, especially on big
maps : 3.7 seconds per call for the 600x600 outdoor map! On more usual
maps (20x20 outdoor, 20x20 cave), it is broadly 2 to 3 times slower
than digital fov, around 500 microsecond per call. Note that it can
still be fast enough for reasonable usages.
I can send you png if you want to check the outdoor issue and see if
you reproduce it in your environment. Those issues and the speed might
be a side-effect of my modifications. Could you try to run it on a
600x600 empty map (almost 10 seconds per call on my bench) to see if
you get the same kind of performances ?
--
jice
Jakub Debski
> * I have some weird behavior in outdoors. Some rays seems to interrupt
> and restart a few cells away. Thus, some branches of the standard star-
> like outdoor fovs seems to be dotted lines...
maybe an implementation bug.
Could you show me a screenshot?
> * it is MUCH slower than others, even digital fov, especially on big
> maps : 3.7 seconds per call for the 600x600 outdoor map!
It wasn't made to be fast on a big maps. Interesting how slow it is :)
Does anyone use such a large maps.
> On more usual maps (20x20 outdoor, 20x20 cave),
> it is broadly 2 to 3 times slower
> than digital fov, around 500 microsecond per call. Note that it can
> still be fast enough for reasonable usages.
It's performance depends a lot on the map size, because it checks all
the corners.
> I can send you png if you want to check the outdoor issue and see if
> you reproduce it in your environment. Those issues and the speed might
> be a side-effect of my modifications. Could you try to run it on a
> 600x600 empty map (almost 10 seconds per call on my bench) to see if
> you get the same kind of performances ?
Sure. Send me the code/binary.
regards,
Jakub
Xecutor
> Are you sure this code works ? I replaced the Lvl class by a TCODMap
> and I get crazy results... What does the hardcoded 500 value in
Actually I never tried it on really big maps with really big sight
radius.
> hasLowerMax represent ?
I use x1000 scaled integers instead of original float.
500 is 0.5
jice
> > Are you sure this code works ? I replaced the Lvl class by a TCODMap
> Absolutely.
Ok, I have broken something then... I have to think harder... :/
--
jice
Xecutor
I tried it on 100x100 map and result is somewhat strange.
Looks like while scaled integer work fine for indoor environment,
in outdoors environment accumulated error does matter.
You can stop dealing with it for a while.
I'll try to make outdoors-optimized version.
Björn Ritzl
> I didn't manage to wikify the document on roguebasin due to an
> apparent limitation on the number of pictures per article, but you can
> get it in pdf format here :
> http://roguecentral.free.fr/libtcod/downloads/fov.pdf
>
> more in libtcod because precise permissive seems to be a better
> alternative.
>
> opinion you may have on the conclusions.
Excellent article Jice! This is a really huge contribution to r.g.r.d.
PS It's nice to see how surprisingly well my good old recursive
shadowcasting algorithm holds up!
> --
> jice
/Björn
jice
Indeed, it performs very well. At the beginning I though it was slower
because my first tests were on large outdoor environment and that's
where it has the worst performances. But on most other map types, it
rules ;)
PS : weren't you supposed to be named "bjorn bergstrom" ??
--
jice
Xecutor
implementation:
http://sc.tri-bit.com/Computing_LOS_for_Large_Areas
And I found one major bug :)
Lines:
if(!Cell[cell].hasUpperMax
())
{
Cell[cell].upper_max=Cell
[south].upper_max;
Cell[cell].upper_count=Cell[south].upper_count-Cell
[south].upper_max;
}
if(!Cell[cell].hasUpperMax
())
{
Cell[cell].upper_max=Cell
[south].upper_max;
Cell[cell].upper_count=Cell[south].upper_count-Cell
[south].upper_max;
Cell
Cell
[south].upper_count=0;
}
And at least one more present :(
I can tell for sure that regardless of anything else your research
have positive effect on me ;)
jice
Ok, I found what's wrong. When using limited range, everything's fine.
But with unlimited range, everything goes crazy. fov goes through
walls, stops in middle of rooms... The speed seems fine (a bit slower
than recursive shadowcasting), but the symmetry seems to be terrible.
To be confirmed.
--
jice
Gerry Quinn
says...
> I'm not so convinced that asymmetric FOV can't be done right; only that
> the asymmetric algorithms we've been using don't do it right.
Well, if the current methods get it exactly backward, you could in
principle solve the problem by calculating FOV the standard way from
every square in range, and then taking your improved FOV to be the set
of squares that can see you. Computationally intensive, of course, but
it might be interesting to try as an experiment to see how it looks.
- Gerry Quinn
--
Lair of the Demon Ape (a coffee-break roguelike)
<http://indigo.ie/~gerryq/lair/lair.htm>
Gerry Quinn
093e04...@s9g2000prg.googlegroups.com>, tyre...@gmail.com says...
> On Feb 1, 8:10 am, Ray Dillinger <b...@sonic.net> wrote:
> > jice wrote:
> > > Well I don't know. Changing the shadow behaviour in a post-processing
> > > step seems pretty difficult to do. Personnally, I don't really like
> > > precise permissive because I think permissivity kills gameplay. The
> > > less, the better. I'd love to use diamond, but right now, it has a few
> > > issues that make me keep using basic/shadow stuff.
>
> A post-processing step on FoV is a very bad idea in general. But see
> below.
Why? I do it and I like the results.
tyre...@gmail.com
> In article <4985c9e0$0$95530$742ec...@news.sonic.net>, b...@sonic.net
> says...
>
> > I'm not so convinced that asymmetric FOV can't be done right; only that
> > the asymmetric algorithms we've been using don't do it right.
>
> Well, if the current methods get it exactly backward, you could in
> principle solve the problem by calculating FOV the standard way from
> every square in range, and then taking your improved FOV to be the set
> of squares that can see you. Computationally intensive, of course, but
> it might be interesting to try as an experiment to see how it looks.
I posted a demo of this algorithm which I called 'reverse
shadowcasting' in my last post. Because of how it is calculated, it
turns out to be only slightly more computationally expensive than
normal shadowcasting. In that same demo, you can switch between it,
normal shadowcasting, and various levels of permissive FoV.
Post-processing on FoV is a bad idea because it breaks your model.
Raycasting without post-processing is an approximation of
shadowcasting. If it is insufficient, add more rays or just switch to
shadowcasting. There is no need to 'fix' it. The algorithm it
approximates is well known and well understood. When the approximation
fails, stop approximating. But it is not only unnecessary, it is
harmful.
Shadowcasting (and raycasting as an approximation) is a simple model
which the player can readily grasp. They look at the center of their
square and try to draw a line to an enemy square mentally. If there
are obstructions, then they cannot shoot at the other square. This
allows the player to plan their moves based on the simple model.
Suppose you add special cases: "A square is also visible if it is next
to a visible one, but only if it is a wall and the first square is a
floor." or "Keep tracing line if the angle is really low and adjacent
square is clear". Well, then that model goes out the window. Then
there are things the player can see which they shouldn't. And if you
are using raycasting as a base, that means there will still be things
the player cannot see which they should. This leads to confusion and
exploits. Especially when a player comes across situations which you
haven't contemplated and provided a 'fix' for.
In general, it is better to stick to a coherent model which just works
(like shadowcasting or others) than to take an approximation and try
to plaster over the cracks.
-D
Simon Richard Clarkstone
> Does it make sense to use a different condition to determine
> monsters/objects visibility and terrain visibility?
I too am considering using central vision for monsters and non-central
for terrain. It allows one to hide round corners more effectively for a
start. Also, monsters are smaller than a whole terrain square so it
makes sense.
> The fact that the vision-blocking terrain is blocking only with a
> fragment of the cell but is visible whenever a line of sight passes
> through any point of the cell is somewhat inconsistent, but I haven't
> noticed any practical problems yet. Also, currently I don't have any
> passable vision-blocking terrain - in such a case a monster might
> pass through a cell that is displayed to the player as terrain. Could
> be a feature, but needs testing.
There are now five levels of vision, rather than the usual three. There
is terrain-and-monster visibility, terrain visibility,
terrain-and-monster memory, terrain memory, and unexplored. These could
be done as bright colour, dark colour, bright grey, dark grey, and
blank. Monsters still have the full range of colours available, since
their visibility represents full visibility anyway.
Or, one could use consistent background colour to represent terrain, and
a foreground terrain or monster symbol in bright or dark to represent
visibility.
--
Simon Richard Clarkstone:
s.r.cl?rkst?n?@dunelm.org.uk / s?m?n_cl?rkst?n?@yahoo.co.uk
| My half-daughter went to the GMH riots |
| But all I got was this stupid ･-shirt. |
Simon Richard Clarkstone
> On 31 jan, 15:32, Simon Richard Clarkstone
> <s.r.clarkst...@dunelm.org.uk> wrote:
>> jice wrote:
[...]
>>> http://roguecentral.free.fr/libtcod/downloads/fov.pdf
[...]
>> A graph of % visibility (x) against speed (y) could be informative (with
>> both scales logarithmic).
>
> What do you call visibility(x) ? The size of the fov ?
By visibility I mean the number of tiles visible according to the
algorithm. "(x)" means that I guess it goes on the x-axis.
Kusi...@autorun.itvk.pl
> Kusigrosz wrote:
>> Does it make sense to use a different condition to determine
>> monsters/objects visibility and terrain visibility?
>
> I too am considering using central vision for monsters and non-central
> for terrain. It allows one to hide round corners more effectively for a
> start. Also, monsters are smaller than a whole terrain square so it
> makes sense.
wedge-shaped vision through diagonal openings, so the corners
are not as effective protection. Still, if the player stands in
the door of a room and the monster is one step inside and two steps
to the side, they don't see one another.
This (somewhat simplified) implementation:
http://tinyurl.com/cvrqzz
shows centrally visble walls as 'W' and floor as '_', non-centrally
visible walls as '#' and floor as '.', and unseen walls as 'o' and
floor as ' '. It is in C; I don't know if it could be put into the
test environment discussed in this thread. It is not as fast as I
would like, but as long as I use it only for the player vision and
all lighting (short-range) it seems OK.
--
Kusi...@AUtorun.itvk.pl To send mail, remove 'AU' from the address
You see here a scroll labeled "cV2NpPqIHnw"
jice
> jice presented the following explanation :
>
> > * I have some weird behavior in outdoors. Some rays seems to interrupt
> > and restart a few cells away. Thus, some branches of the standard star-
> > like outdoor fovs seems to be dotted lines...
>
> maybe an implementation bug.
> Could you show me a screenshot?
http://roguecentral.free.fr/outdoor_100x100_fov2.png
> > I can send you png if you want to check the outdoor issue and see if
> > you reproduce it in your environment. Those issues and the speed might
> > be a side-effect of my modifications. Could you try to run it on a
> > 600x600 empty map (almost 10 seconds per call on my bench) to see if
> > you get the same kind of performances ?
>
> Sure. Send me the code/binary.
>
No, I mean with your version of the program to see if my modifications
are in cause. But as you said, the exponential time is probably due to
the corner checks.
--
jice
Xecutor
> But with unlimited range, everything goes crazy. fov goes through
Arbitrary big number?
There is no sense in range greater than diagonal of map...
> walls, stops in middle of rooms... The speed seems fine (a bit slower
> than recursive shadowcasting), but the symmetry seems to be terrible.
> To be confirmed.
When you are peeking thru the fissure, you can
see a lot, but no one (from other side of fissure) can see you.
I found another issue, but haven't decided how to fix it correctly.
Jakub Debski
>> maybe an implementation bug.
>> Could you show me a screenshot?
>
> http://roguecentral.free.fr/outdoor_100x100_fov2.png
It's not a bug, it's a feature of this algorithm :)
> No, I mean with your version of the program to see if my modifications
> are in cause. But as you said, the exponential time is probably due to
> the corner checks.
All the "rays" are cast from the 4 corners of the starting cell,
therefore it's about 3-3 times more expensive than "normal" raycasting.
regards,
Jakub
Gelatinous Mutant Coconut
> When you are peeking thru the fissure, you can
> see a lot, but no one (from other side of fissure) can see you.
No, the field of view remains symmetric; if your eye is able to see
their eye, then their eye is able to see your eye. (Things like one-
way windows not withstanding.) What ISN'T symmetrical is how much of
the rest of your bodies will be visible. You're not going to be able
to have that be asymmetrical in a realistic way in a roguelike as long
as players and monsters fill single tiles that are either visible or
not visible.
You could handle FOV down to finer scales and use the fraction of the
cells that are visible as a measure of cover, perhaps. Or you could
map different cells of the tile to different body parts, or whatever.
Timofei Shatrov
<GelatinousM...@gmail.com> tried to confuse everyone with this message:
>> In real life FOV is terribly asymmetric :)
>> When you are peeking thru the fissure, you can
>> see a lot, but no one (from other side of fissure) can see you.
>
>No, the field of view remains symmetric; if your eye is able to see
>their eye, then their eye is able to see your eye.
This is not true. For Eye1 to see Eye2, the light coming from Light Source must
reflect from Eye2. If the path between Light Source and Eye2 is blocked then
Eye1 can't see Eye2. In this diagram 2 can see 1, but not vice versa. That's why
hiding in the shadows is effective.
O Light Source
/ \
/ x Obstacle
/ \
Eye1 O ===== O Eye2
Not to mention, in real life eyes don't have even 180 degree FOV, so you can
look at someone from the side without them noticing you.
--
|Don't believe this - you're not worthless ,gr---------.ru
|It's us against millions and we can't take them all... | ue il |
|But we can take them on! | @ma |
| (A Wilhelm Scream - The Rip) |______________|
Björn Ritzl
Hehe, I was until I married my wife and took her name. I made a post
here about two years ago when it happened... :-)
> --
> jice
/Björn
Gelatinous Mutant Coconut
> reflect from Eye2. If the path between Light Source and Eye2 is blocked then
> Eye1 can't see Eye2. In this diagram 2 can see 1, but not vice versa. That's why
> hiding in the shadows is effective.
You are completely right, of course. (Although Eye 2 might also be
visible if enough of Light Source is reflected off of Eye 1 to
illuminate Eye 2.) I suppose I was thinking in terms of what could be
seen assuming universal illumination, which is what FOV algorithms
generally handle, after which a second phase of light source
calculations (typically also based on the FOV algorithm) are applied
to the scene, and tiles are visible only if there is a line of sight
to their tile AND their tile is properly illuminated. All of which can
produce reasonably realistic looking results in a much shorter time
than is required to properly model the physics of the scene, but
doesn't exactly have much to do with realism.
Thinking more clearly about the problem, in a roguelike where stealth
and hiding in the shadows is the main focus, you might want to go
ahead and handle visibility in terms of raytracing a 2D scene instead.
A monster 'sees' you if enough light bounces directly from you to it
(or from you to a mirror to it), making it important to both keep in
the shadows and keep your distance. The world's first GPU-intensive
ASCII game?
> Not to mention, in real life eyes don't have even 180 degree FOV, so you can
> look at someone from the side without them noticing you.
Well, yes; I originally phrased my statements in terms of "if he can
see you, you can see him", but caught myself and realized that that
only works if you consider each of you to be point sources (which
roguelikes generally do, but anyways), but vantage points can vary, so
I tried phrasing it in terms of "if your eyes can see his eyes, his
eyes can see your eyes" (which can be approximated fairly reasonably
as point sources for each other eye), thinking that that would rule
out the case where one person is standing behind the other person as
well (roguelikes generally don't handle facing).
I guess I was thinking too much in terms of what
Kusigrosz
>> This is not true. For Eye1 to see Eye2, the light coming from Light
>> Source must reflect from Eye2. If the path between Light Source and
>> Eye2 is blocked then Eye1 can't see Eye2. In this diagram 2 can see
>> 1, but not vice versa. That's why hiding in the shadows is effective.
> You are completely right, of course. (Although Eye 2 might also be
> visible if enough of Light Source is reflected off of Eye 1 to
> illuminate Eye 2.)
if the player is carrying a light source, the eyes of these monsters
within his FOV are displayed (as a bright ") even if they are beyond
the illuminated area. The colour of the eyes gives some information
about the monster type.
Ray Dillinger
> In the game I'm working on, some monsters have eyes that shine back:
> if the player is carrying a light source, the eyes of these monsters
> within his FOV are displayed (as a bright ") even if they are beyond
> the illuminated area. The colour of the eyes gives some information
> about the monster type.
This is a good idea, and will be interesting.
ObTerminology: the reflective structure that makes the eyes of
many nocturnal creatures "glow" with reflected light is called
(in English and Latin) a Tappetum Lucidum. It's a reflective
layer behind the retina, which bounces light back for a second
chance to be caught by the light-sensitive cells there. It's
a design compromise in that the second time around the light is
less focused, so animals that have them have very light-sensitive
eyes (good night vision) but can't focus as sharply as animals
without them.
If your eyes had tappetum lucidi, like a cat's, you'd need to
double or triple your font sizes in order to read.
Bear
Gelatinous Mutant Coconut
> if the player is carrying a light source, the eyes of these monsters
> within his FOV are displayed (as a bright ") even if they are beyond
> the illuminated area. The colour of the eyes gives some information
> about the monster type.
Cool! Dwarf Fortress has monsters with glowing eyes (red " for
goblins, yellow " for kobolds), but doesn't currently handle light
sources; rooms are either lit or not lit, and if you have poor
eyesight in the dark (because you're a human adventurer or something)
you get a radius of maybe three cells visible in the dark, beyond
which you see nothing except maybe glowing eyes.
Given the extent of his ambition / obsessiveness, I imagine that Toady
One will probably make a distinction between glowing versus reflective
eyes whenever he gets around to implementing lighting. Which probably
won't be for a while, on account of other ambitious / compulsive
features that need implementing.
Xecutor
<GelatinousMutantCoco...@gmail.com> wrote:
> > In real life FOV is terribly asymmetric :)
> > When you are peeking thru the fissure, you can
> > see a lot, but no one (from other side of fissure) can see you.
>
> No, the field of view remains symmetric; if your eye is able to see
> their eye, then their eye is able to see your eye.
From common sense point of view - no.
It's really hard to see someone's eye thru small hole, especially from
afar.
You can see at page of book from several meters, but cannot
distinguish letters.
You can see at wall with hole from several meters, but cannot
distinguish eye behind the hole.
That's what I meant.
b0rsuk
> > No, the field of view remains symmetric; if your eye is able to see
> > their eye, then their eye is able to see your eye.
>
> From math/geometry point of view - yes.
> From common sense point of view - no.
> It's really hard to see someone's eye thru small hole, especially from
> afar.
I disagree. FOV should be symmetric unless creatures can't see what's
behind them. Things like exposing only your eyes and various shades of
hiding belong to the Stealth skill. When I have only my eyes exposed,
it's not because I can bend rays of light with my will or turn
invisible. It's because I'm trying to hide. Someone can still see me
if he knows where to look.
b0rsuk
Radomir Dopieralski
> If your eyes had tappetum lucidi, like a cat's, you'd need to
> double or triple your font sizes in order to read.
I always said that jumping spiders have the best eyes! Shame
their "brains" are too small to actually remember the whole
picture they see.
--
Radomir Dopieralski, http://sheep.art.pl
b0rsuk
> I always said that jumping spiders have the best eyes! Shame
> their "brains" are too small to actually remember the whole
> picture they see.
I've seen a documentary about jumping spiders, and they said jumping
spiders are actually the smartest spiders. They need better eyes to
land properly. The theory is that good eyes allowed them to see more
than just the landing spot, and they started to make use of that. For
example, they learned to mimic the mating calls (movement) of some
insect females to attract males and eat them (many insects can't see
as well). They even pull off this trick on other spiders. They also
use othe forms of deception and mimickry, but I can't remember all of
them.
b0rsuk
David Damerell
>I disagree. FOV should be symmetric unless creatures can't see what's
>behind them. Things like exposing only your eyes and various shades of
>hiding belong to the Stealth skill.
Let's take an extreme case; do I need Stealth skill to peer through an
arrow-slit and not expose my body?
Also, even if you _have_ a Stealth skill, FOV calculations might be useful
to identify where the player _can_ use cover effectively.
--
David Damerell <dame...@chiark.greenend.org.uk> Kill the tomato!
Today is First Wednesday, February.
Gelatinous Mutant Coconut
> arrow-slit and not expose my body?
You could model arrow slits as granting a situational bonus to Stealth
rolls when a monster tries to notice a player behind the arrow slit
tile, maybe?
> Also, even if you _have_ a Stealth skill, FOV calculations might be useful
> to identify where the player _can_ use cover effectively.
I don't think that anyone was arguing against using FOV, just in favor
of LOS symmetry.
b0rsuk
wrote:
> Quoting b0rsuk <jaze...@gmail.com>:
>
> >I disagree. FOV should be symmetric unless creatures can't see what's
> >behind them. Things like exposing only your eyes and various shades of
> >hiding belong to the Stealth skill.
>
> Let's take an extreme case; do I need Stealth skill to peer through an
> arrow-slit and not expose my body?
But if you're behind an arrow slit and looking at me, I _can_ see you.
You may be harder to _notice_, but if I know where to look for, I can
see you. Careful here - this is related to how brain works. Most
creatures have brains which are very good at noticing movement and
moving things. If you're behind an arrow slit, you'll be harder to
notice because 1) you're most likely standing still 2) even if you're
not, only part of your body is unobscured.
If I can't see you behind an arrow slit, it can mean one of two
things:
a) it's too dark in there
This is an issue with lightning, and it should never be treated
lightly (bleh, puns). It can add or substract from gameplay, but
should be carefully considered.
b) the arrow slit has some kind of reflective glass
Notice that at night, if you're indoors and the light is on, you won't
see much if you look through a window (with glass). Unless the area
outside is well lit. But generally, the glass can even work as a
mirror, allowing you to see your reflection. On the other hand,
someone standing outside will easily be able to see you.
b0rsuk
Gelatinous Mutant Coconut
I don't think the dark lord of the dungeon thought that one all the
way through. At least it keeps the glass makers busy.
b0rsuk
Perhaps he keeps basilisks behind the arrow slits ? Oh wait -
partially reflective ! Arrggh!!1
b0rsuk
David Damerell
>On 9 Lut, 16:51, David Damerell <damer...@chiark.greenend.org.uk>
>>>I disagree. FOV should be symmetric unless creatures can't see what's
>>>behind them. Things like exposing only your eyes and various shades of
>>>hiding belong to the Stealth skill.
>>Let's take an extreme case; do I need Stealth skill to peer through an
>>arrow-slit and not expose my body?
>But if you're behind an arrow slit and looking at me, I _can_ see you.
>You may be harder to _notice_, but if I know where to look for, I can
>see you.
Yes, but me appearing on the map / your AI's view of the world is
dependent on you noticing me, not on it being possible for you to see me.
--
David Damerell <dame...@chiark.greenend.org.uk> Oil is for sissies
Today is First Thursday, February.
jice
> In response to this discussion, I have slightly tweaked my permissive
> fov algorithm library so that it can do all kinds of different FoV
> algorithms by changing parameters. This includes, shadowcasting,
> reverse shadowcasting, and various levels of permissivity.
>
> http://www.xmission.com/~tyrecius/fov-comparison-demo.zip
>
Ok I eventually tested the variable-permissiveness algorithm. It's
available in libtcod 1.4.1rc3.
You can find the results here :
http://roguecentral.org/libtcod/fov/fov.pdf
Unfortunately, it does not kill the concurrence, but it's becoming a
real challenger to basic raycasting and recursive shadowcasting. The
fov graal has still not been found :).
--
jice
pende...@gmail.com
> Unfortunately, it does not kill the concurrence, but it's becoming a
> real challenger to basic raycasting and recursive shadowcasting. The
> fov graal has still not been found :).
I'm going to guess that the FOV grail will never be found. Even
setting aside performance issues completely, I think FOV symmetry is
fundamentally at odds with our (my?) notions of FOV aesthetics. In
particular, there are three ideals of FOV algorithms which are
unavoidably inconsistent with one another:
1) Standing adjacent to a pillar should cast a wedge-shaped shadow.
2) Standing at one end of a 1xN corridor should cast light all the way
down the corridor and on the cells occupied by walls on either side of
the corridor center.
3) FOV should be symmetrical in the sense that line of sight should be
reflexive (i.e. if A is visible from B, then B is visible from A).
We have algorithms that will accommodate any two of these three
ideals, but it is impossible to accommodate all three with current
methods. The only way to do it would be to violate our sense of what a
FOV algorithm may consider in deciding whether to light a cell. We
probably all agree, for example, that a particular cell's visibility
should not depend on the contents of cells that are not visible, or on
any cells that are not "arguably" between the player and the cell
being evaluated, and in fact all the variation in current FOV
algorithms comes from deciding which cells count as being "between"
points A and B. If you violated this principle, though, maybe there
would be a way to algorithmically ascertain whether a wall cell
represented a pillar (which should cast a wedge shadow) or the convex
corner of a T-intersection (which has to cast a laser-thin shadow to
satisfy conditions 2 and 3 simultaneously). In that case, perhaps all
three principles could be satisfied.
I haven't the faintest idea how one would attempt this, though, in a
way that takes into account all of the possibilities of dungeon
design. Maybe it would require substantial artificial intelligence. Or
maybe it would depend on the dungeon generation algorithm flagging
certain walls as "wedge shadow" walls and others as "laser-thin
shadow" walls -- and I imagine this would be an easy task only in
certain kinds of dungeons.
Short of that, it's going to remain up to us which of the three
conditions to sacrifice. I'm going to go out on a limb and suggest
that the best sacrifice in single-player implementations is condition
#3 -- and if some form of symmetry is required for gameplay reasons,
to approximate it with a post-processing procedure of considering all
cells visible from a point to be able to see the point in return.
Note: if you disagree with the desirability of any of these three
conditions, please disregard this post. I recognize that they're
matters of taste and that tastes can differ.
Ray Dillinger
> On Feb 19, 7:14 pm, jice <jice.nos...@gmail.com> wrote:
> I'm going to guess that the FOV grail will never be found. Even
> setting aside performance issues completely, I think FOV symmetry is
> fundamentally at odds with our (my?) notions of FOV aesthetics. In
> particular, there are three ideals of FOV algorithms which are
> unavoidably inconsistent with one another:
> 1) Standing adjacent to a pillar should cast a wedge-shaped shadow.
> 2) Standing at one end of a 1xN corridor should cast light all the way
> down the corridor and on the cells occupied by walls on either side of
> the corridor center.
> 3) FOV should be symmetrical in the sense that line of sight should be
> reflexive (i.e. if A is visible from B, then B is visible from A).
> We have algorithms that will accommodate any two of these three
> ideals, but it is impossible to accommodate all three with current
> methods.
This is simply not true. Spiral path can do this. In spiral-path
you're calculating the minimum and maximum lit angle of each square.
If you want symmetric FOV, you just have to check whether something
is or isn't a "wall" square. If it's wall, you display it if any
angle is lit. If it's non-wall you only display it if its center-
point angle is between the min and max lit angles.
Standing next to a pillar, you get one wedge-shaped shadow.
Looking down a 1xn corridor, every square on both sides is lit.
If a square is not visible, then it's an opening or doorway.
A monster may be standing on that square, but him you can't
see around the corner.
Bear
pende...@gmail.com
> Looking down a 1xn corridor, every square on both sides is lit.
> If a square is not visible, then it's an opening or doorway.
> A monster may be standing on that square, but him you can't
> see around the corner.
Then the cells on either side of the corridor -- the walls -- aren't
actually lit -- or perhaps they are "halfway" lit, if you will, since
rather than revealing their contents you are revealing only the "wall-
ness" of their contents. This is what I was trying to get at by
specifying in condition 2 that the "cells occupied by walls on either
side of the corridor" should be lit, rather than the "walls on either
side of the corridor."
jice
Are you saying that spiral path would get a green note on every
gameplay situation in the study ? This sounds interresting. I'll give
it a try.
--
jice
jice
> On Feb 19, 7:14 pm, jice <jice.nos...@gmail.com> wrote:
>
> > Unfortunately, it does not kill the concurrence, but it's becoming a
> > real challenger to basic raycasting and recursive shadowcasting. The
> > fov graal has still not been found :).
>
> I'm going to guess that the FOV grail will never be found. Even
> setting aside performance issues completely, I think FOV symmetry is
> fundamentally at odds with our (my?) notions of FOV aesthetics. In
> particular, there are three ideals of FOV algorithms which are
> unavoidably inconsistent with one another:
>
> 1) Standing adjacent to a pillar should cast a wedge-shaped shadow.
> 2) Standing at one end of a 1xN corridor should cast light all the way
> down the corridor and on the cells occupied by walls on either side of
> the corridor center.
> 3) FOV should be symmetrical in the sense that line of sight should be
> reflexive (i.e. if A is visible from B, then B is visible from A).
>
> We have algorithms that will accommodate any two of these three
> ideals, but it is impossible to accommodate all three with current
> methods.
I agree with that, but :
2) can be fixed with a cheap post-processing step that considerably
reduce the artifacts probability, so that's not really required from
the algorithm itself.
3) absolute symmetry is not required to me. Rather, the algorithm has
to be "symmetrical enough". Below 1% of symmetry issues on a map seems
fine. Gameplay issues that might result from such artifacts can easily
be by-passed by using a bidirectional (thus symmetrical) LOS.
My definition of the fov grail is :
- decent speed in both indoor/outdoor maps
- no show-killing artifact (like the basic raycasting behaviour in the
corner peaking case)
- good looking shadows in any situation, especially pillar/diagonal
--
jice
Mingos
> My definition of the fov grail is :
> - decent speed in both indoor/outdoor maps
> - no show-killing artifact (like the basic raycasting behaviour in the
> corner peaking case)
> - good looking shadows in any situation, especially pillar/diagonal
I'm more fussy. All the above, plus:
- doesn't stop at diagonal lines (troublesome in outdoor areas and
produces the room corner bug)
- the "good looking shadows" need to start right behind the pillar,
not a few cells away (the cells behind the pillar cannot be visible)
- has "natural looking" angles (like, shadowcasting has lots of 45º
angles, which just look unnatural)
Mingos
Ray Dillinger
> Are you saying that spiral path would get a green note on every
> gameplay situation in the study ? This sounds interresting. I'll give
> it a try.
With the added code so that *any* lighting is sufficient to reveal
the wall/non-wall status, but only *direct* (to the center of a square)
lighting is sufficient to reveal monsters, it conforms perfectly to
what *I* think are the important expectations. I have no problem with
walls being easier to see than monsters.
However, see elsethread for penderprime's reaction; he feels that
the difference in lighting for wall revealing and monster revealing
is in itself a violation of the three requirements he posted.
Bear
jice
In a true color roguelike, field of view and lighting are completely
distinct issues. FOV only gives you the potential visible set.
Lighting consists in accumulating light from any source in each cell,
then determinate if the amount of light is high enough for the
creature to be visible. This requires the light color whereas fov only
use only the position and range.
That's why I think creature revealing and wall/ground revealing, or
rather cell lighting and potential visible set determination should
not be correlated and fov algorithm should only deal with the latter.
--
jice
pende...@gmail.com
> In a true color roguelike, field of view and lighting are completely
> distinct issues. FOV only gives you the potential visible set.
> Lighting consists in accumulating light from any source in each cell,
> then determinate if the amount of light is high enough for the
> creature to be visible. This requires the light color whereas fov only
> use only the position and range.
>
> That's why I think creature revealing and wall/ground revealing, or
> rather cell lighting and potential visible set determination should
> not be correlated and fov algorithm should only deal with the latter.
Not quite sure what you mean. Agreed that lighting and FOV are
different issues although above I use "lit" as shorthand to refer to
the latter. Your first paragraph makes complete sense. Your second
paragraph is (to my eyes) a complete nonsequitur. Are you saying that
the visibility of walls should depend only on FOV and not on light,
whereas the visibility of creatures should depend on both? If so, why
on earth should walls be visible in pitch dark?
In my (true color) roguelike, a cell gets its IS_VISIBLE flag set only
if its IN_FIELD_OF_VIEW flag is set AND at least one of its light
color components is greater than zero. This is true whether it is a
wall or a creature. The player has an intrinsic "miner's light" that
follows him around with a radius that decreases as he delves deeper,
to recreate the claustrophobic feeling from Rogue of delving into the
dark depths of the earth. The FOV check, on the other hand, has no
maximum radius.
Mingos
> Not quite sure what you mean. Agreed that lighting and FOV are
> different issues although above I use "lit" as shorthand to refer to
> the latter. Your first paragraph makes complete sense. Your second
> paragraph is (to my eyes) a complete nonsequitur. Are you saying that
> the visibility of walls should depend only on FOV and not on light,
> whereas the visibility of creatures should depend on both? If so, why
> on earth should walls be visible in pitch dark?
I think what he meant was that the FOV algorithm should only calculate
the potential visible set of tiles, i.e. the ones that have a
straight, unobstructed line to the PC's position. While they're
POTENTIALLY visible, lack of light might negate the "visible" flag on
the tile (and the creature standing on it).
Or, to phrase it differently (perhaps easier to understand, since I
distrust my own skills of explaining stuff):
1. If tile is in FOV, it is "potentially visible",
2. If tile has sufficient light, it is "lit",
3. If tile is "potentially visible" and "lit", it's "visible".
A "visible" tile reveals all its contents: terrain, map features,
items lying on the ground and the creature occupying it.
Of course, I might be interpreting this wrongly, but it's how I
understood it.
Mingos
Radomir Dopieralski
> Are you saying that
> the visibility of walls should depend only on FOV and not on light,
> whereas the visibility of creatures should depend on both? If so, why
> on earth should walls be visible in pitch dark?
This might actually make some sense, if you consider it for a while.
It's never completely dark, there is ambient light reflected from the
environment, ultra-red radiation from warm objects changing its
wavelength when reflecting or passing through different parts of the
environment, etc. Walls are big and to see them you only need a very
vague picture -- you know that something is there blocking the way.
On the other hand, monsters are usually smaller than the full square,
move in sneaky way, and probably have some sort of camouflage, not to
mention their fur/skin is probably reflecting less than a -- possibly
wet -- wall. You might not be aware of this, but human beings also
detect walls with other means that sight, the most obvious of them is
probably hearing. The subtle differences in how the sound propagates
give you a pretty good idea on whether a corridor is a dead end, or
how far a bend is. This is mostly subconscious, though, so you "just
know".
jice
Indeed I mixed two different things. Mingos explained clearly the cell
lighting / potential visible set difference.
As for walls/creatures, it's a completely different issue related to
stealth : in penumbra, you can see walls and objects around you but
you may not see a goblin standing in the shadow. This is another
subtlety that should not be handled by the fov algorithm.
--
jice
Gelatinous Mutant Coconut
> As for walls/creatures, it's a completely different issue related to
> stealth : in penumbra, you can see walls and objects around you but
> you may not see a goblin standing in the shadow. This is another
> subtlety that should not be handled by the fov algorithm.
Actually, the gradient of "light" (potential visibility?) that is
"cast" by a non-point source observer might be a decent proxy for how
well hidden a monster is from the point of view of the observer; a
monster is always visible if it can be seen from any point that the
observer can observe, is always hidden if there is no way to observe
any of it, and if the monster is in the "penumbra" of the observation,
it becomes a probability.
I'm not very good at descriptions, so basically something like this is
what I was thinking about when I thought of this:
http://en.wikipedia.org/wiki/File:Diagram_of_umbra,_penumbra_%26_antumbra.png
(If this were to be done, it might make more sense to model walls with
polygons and the player/monsters/light-emitting items with circles,
instead of the traditional roguelike grid.)
pende...@gmail.com
If we must discuss realism, then yes, I agree that it's plausible that
you'd be able to perceive all walls immediately adjacent to you
regardless of light based on the echoes of your footsteps if nothing
else. But with enough accuracy to perceive an opening in the left wall
of a corridor forty feet away? Seriously unlikely unless your
superpower is echo-location.
Setting aside the realism, the bigger problem (I think) is that it's
not intuitive. If players see walls popping up on their display, they
will assume that means they can see that area and there is nothing in
it. Having monsters jump out of nowhere in such an environment is
likely to be frustrating, at least to the uninitiated.
pende...@gmail.com
> As for walls/creatures, it's a completely different issue related to
> stealth : in penumbra, you can see walls and objects around you but
> you may not see a goblin standing in the shadow. This is another
> subtlety that should not be handled by the fov algorithm.
But the proposal above is precisely that it be handled by the FOV
algorithm -- i.e. that assuming omnipresent light, certain cells'
visibility will depend on whether they are walls. I personally find
that to be a weird and counter-intuitive approach, although I am
willing to concede (pace Ray's explanation above) that it does have a
certain logical appeal to it.
jice
Well I didn't come with this with realism in mind. Rather a simple
game mechanism where the map is divided in three distinct region :
obscurity, penumbra, light. Penumbra zones are where the player or the
creatures can hide. You can extend/reduce penumbra zones by turning
lights off and on, so you really need map cells where walls/items are
visible and creatures not.
Anyway my point was rather about the potential visible cells / visible
cells distinction. I mentioned the wall/creatures issue only because
Ray mentioned it too.
--
jice
Xecutor
> It's never completely dark, there is ambient light reflected from the
> environment,
Somewhere in the middle of october I was returning
from the institute to the dormitory thru the forest.
It was pitch black night.
I was moving slowly while trying to follow the path.
Main source of sensory input was amount of grass and
deciduous leaves under my feet.
I had my arms stretchet in from of me, just in case.
And than I hit it.
The tree.
It had fallen right between my arms and I couldn't see
it even at rly close range despite the fact that it had
white/light bark.
And that was 'wilderness' :)