A new line of sight algorithm
not...@gmail.com
Anyways, I have a huge pet peeve with roguelike line of sight
algorithms. When player A can see monster B, it is not guaranteed that
monster B can see player A. This keeps me up at night. This drives me
crazy. It annoys me so much that I spent the last six months thinking
about line of sight algorithms.
What kept me up during the day, when I really should have been
sleeping, is how exactly to define what constitutes a line of sight
from player A to monster B. The "is it generated by Bresenham's
algorithm" approach doesn't work for me, because this definition
(strangely enough) doesn't have the property that A sees B iff B sees
A. Shockingly (to me at least), I'm not the only one who has this
insane obsession with exactly defining a discrete version of a
straight line - back in the 70s or 80s, this was a big topic in
computer vision (for estimating perimeters of two dimensional objects
to "sub-pixel" accuracy or something).
The definition of a "digital line" that they gave is very beautiful,
and I think it fits in perfectly with the geometry of Roguelikes.
First, we restrict to lines with slop between 1 and 0, and think of
the line as a path along the grid. At every step of the path, if we
move to the right, we write down a "0", and if we move to the up-
right, we write down a "1". If the number of 1s in every subsequence
of what we wrote is at most one off from the number of 1s in every
other subsequence of the same length, then we say that the sequence of
0s and 1s is balanced, and that the path forms a digital line.
Obviously, if a sequence of 0s and 1s is balanced, then when you
reverse it you get another balanced sequence, so if there is a digital
line from A to B, then there is from B to A.
As it turns out, every path generated by Bresenham's algorithm is a
digital line, and all digital lines can be generated by a slight
modification to Bresenham's algorithm with the proper parameters (the
modification is changing the initial height of the line).
Alternatively, every digital line is a subset of some line generated
by Bresenham's algorithm.
Unfortunately, the number of balanced sequences of length N is about
N^3 (as is the number of digital lines of length N). This makes it a
little bit tricky to write efficient field of vision or line of sight
algorithms that use this definition (or even to check if a path forms
a digital line)... which is what I've been working on all this time.
The first field of view algorithm was very naive, and took N^4 steps
(walk along each line)... then I realized that it's not hard to turn
that into N^3 by being a little more clever. N^2, however, took me
until now.
I made a little demo program that lets you test out the algorithms,
you can get it at http://reflexivelos.googlecode.com/svn/trunk/los2.cpp
(uses the cursed library). Any feedback would be great, and of course,
I'd be flattered if you used the code (or just the concept) in your
own roguelikes.
Krice
> Any feedback would be great,
The source code is.. eh.. poor.
> and of course, I'd be flattered if you used the code (or just
> the concept) in your own roguelikes.
The big question is does it work. If so then it's probably
possible to use it if one can actually make something
out of that awful mess of source code..
Jeff Lait
> This is my first ever Usenet post!
>
> Anyways, I have a huge pet peeve with roguelike line of sight
> algorithms. When player A can see monster B, it is not guaranteed that
> monster B can see player A. This keeps me up at night. This drives me
> crazy. It annoys me so much that I spent the last six months thinking
> about line of sight algorithms.
I hope you aren't too offended by simple solutions then...
> What kept me up during the day, when I really should have been
> sleeping, is how exactly to define what constitutes a line of sight
> from player A to monster B. The "is it generated by Bresenham's
> algorithm" approach doesn't work for me, because this definition
> (strangely enough) doesn't have the property that A sees B iff B sees
> A.
Given *any* LOS function: hasLOS(A, B), you can make it symmetric in
two simple ways:
// Generous interpretation
bool symmetricHasLOS(A, B)
{
return hasLOS(A, B) || hasLOS(B, A);
}
// Conservative interpretation
bool symmetricHasLOS(A, B)
{
return hasLOS(A, B) && hasLOS(B, A);
}
And, for those of us who care about speed but not physical realism:
bol symmetricHasLOS(A, B)
{
if (A < B) // Some arbitrary, consistent, sort of A's
return hasLOS(A, B);
else
return hasLOS(B, A);
}
Defining LOS as the existence of *any* digital line is quite a
challenge. The primary feature of such a system would be its
permissiveness, not its symmetry, however, as symmetry alone is
achievable with simpler methods.
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)
Altefcat
Krice, you would do such a better job working on Kaduria, instead of
roaming groups bashing Usenet newbies with your trollish club...
jice
>
[ ... digital line source code ...]
> Any feedback would be great,
The interest of the algorithm apart, if your problem is just the LOS
reflexivity, I have a much simpler proposition :
bool standard_bresenham_non_reflexive_los(int xa, int ya, int xb, int
yb) { ... }
bool reflexivelos(int xa, int ya, int xb, int yb) {
if ( xa + ya * 100000 < xb + yb * 100000 ) return
standard_bresenham_non_reflexive_los(xa,ya,xb,yb);
else return standard_bresenham_non_reflexive_los(xb,yb,xa,ya);
}
Or with words : if your algorithm cannot return the same value for
LOS(A,B) and LOS(B,A), order your points so that you always call
LOS(A,B)...
--
jice
jice
oops, sorry Jeff, didn't see your post. Same solution...
--
jice
mike3
Does this mean the result from the Bresenham algorithm when
going from A to B is not the same as going from B to A, ie.
it is not commutative?
Martin Read
>Does this mean the result from the Bresenham algorithm when
>going from A to B is not the same as going from B to A, ie.
>it is not commutative?
Precisely so. Hence the LOS abuses that plagued the *bands for so long.
(MPRHB is going to stick with line-of-fire down roguespace cardinals
only, and keep the vision-and-explosions code I wrote for MPRDB 1.99,
which has its infelicities but is Good Enough For Me. Yes, it's even
going to keep the obscene preprocessor construct and manually precomputed
vision tables.)
--
\_\/_/ some girls wander by mistake into the mess that scalpels make
\ / are you the teachers of my heart? we teach old hearts to break
\/ --- Leonard Cohen, "Teachers"
not...@gmail.com
> Given *any* LOS function: hasLOS(A, B), you can make it symmetric in
> two simple ways:
>
> // Generous interpretation
> bool symmetricHasLOS(A, B)
> {
> return hasLOS(A, B) || hasLOS(B, A);
>
> }
>
> // Conservative interpretation
> bool symmetricHasLOS(A, B)
> {
> return hasLOS(A, B) && hasLOS(B, A);
>
> }
>
> And, for those of us who care about speed but not physical realism:
> bol symmetricHasLOS(A, B)
> {
> if (A < B) // Some arbitrary, consistent, sort of A's
> return hasLOS(A, B);
> else
> return hasLOS(B, A);
>
> }
>
> Defining LOS as the existence of *any* digital line is quite a
> challenge. The primary feature of such a system would be its
> permissiveness, not its symmetry, however, as symmetry alone is
> achievable with simpler methods.
> --
> Jeff Lait
> (POWDER:http://www.zincland.com/powder)
This is true... however, as soon as I started with the concept of
digital lines, it was hard to go back or give up.
To Krice: I realize that my coding style is disgusting. On the other
hand, I did think the "slower" algorithm was pretty easy to
understand, copy and paste. The new one is more of a proof that it's
possible to get it in N^2... but I'd be happy to explain the new one
if you like.
I just found out about "permissive field of view". Although the
definition is very different from mine (my geometry corresponds to
diamond shaped players and beveled edges, so they can squeeze between
corners), the general idea is similar. Has an exact version of PFOV
ever been implemented?
Gamer_2k4
> Does this mean the result from the Bresenham algorithm when
> going from A to B is not the same as going from B to A, ie.
> it is not commutative?
Yep. Consider a point two tiles away:
@..
...
.X.
Now consider the line between the two:
@.. @..
#.. OR .#.
.#. .#.
Generally, you'll only calculate one of them, and it will probably be
the same. For the sake of argument, we'll use the first one. Now,
let's say that the destination point is a monster, and that we need to
see if he can see you:
1.. 2..
#.. AND .#. (the LOS is draw vertically first)
.2. .1.
The problem is clear: If we have an obstruction in the center tile,
you can see the monster, but it cannot see you. If there is an
obstruction in the left center tile, we have the opposite problem.
That's what Jeff's symmetricHasLOS functions fix.
--
Gamer_2k4
tyrec...@yahoo.com
> I just found out about "permissive field of view". Although the
> definition is very different from mine (my geometry corresponds to
> diamond shaped players and beveled edges, so they can squeeze between
> corners), the general idea is similar. Has an exact version of PFOV
> ever been implemented?- Hide quoted text -
Yes. Here is a link to a description of how to implement precise
permissive field of view:
http://roguebasin.roguelikedevelopment.org/index.php?title=Precise_Permissive_Field_of_View
And here is a link to a library implmenting that algorithm in C/C++:
http://roguebasin.roguelikedevelopment.org/index.php?title=Permissive-fov
There are now ports in Java, Python, and even for Flash.
-D
not...@gmail.com
> On Jan 21, 11:31 pm, not...@gmail.com wrote:
>
> > I just found out about "permissive field of view". Although the
> > definition is very different from mine (my geometry corresponds to
> > diamond shaped players and beveled edges, so they can squeeze between
> > corners), the general idea is similar. Has an exact version of PFOV
> > ever been implemented?- Hide quoted text -
>
> Yes. Here is a link to a description of how to implement precise
> permissive field of view:
>
>
> And here is a link to a library implmenting that algorithm in C/C++:
>
>
> There are now ports in Java, Python, and even for Flash.
>
> -D
In that case, I consider myself one upped... that looks incredibly
complicated. My algorithm is just a simple ray-casting algorithm at
heart (yet it never produces artifacts).
You know, I wouldn't mind setting up some wiki pages describing my
algorithm and definitions. How can I sign up with RogueBasin?
not...@gmail.com
> You know, I wouldn't mind setting up some wiki pages describing my
> algorithm and definitions. How can I sign up with RogueBasin?
Come to think of it, where should I put such an article if I write it?
RogueBasin, here, a website of my own, or somewhere else?
Also: how many people compiled and ran the code? Or are a significant
number of you running windows? If you did run the code, do you have
any opinions on the aesthetic, counterintuitive behavior, etc.?
Gamer_2k4
> On Jan 22, 4:48 pm, not...@gmail.com wrote:
>
> > You know, I wouldn't mind setting up some wiki pages describing my
> > algorithm and definitions. How can I sign up with RogueBasin?
>
> Come to think of it, where should I put such an article if I write it?
> RogueBasin, here, a website of my own, or somewhere else?
Put the article on Roguebasin, definitely. To sign up, just click the
"Login/Create Account" link at the top right of the Roguebasin pages.
--
Gamer_2k4
not...@gmail.com
> Put the article on Roguebasin, definitely. To sign up, just click the
> "Login/Create Account" link at the top right of the Roguebasin pages.
>
> --
> Gamer_2k4
Alright, I gave it a shot. They still need polishing (and pictures -
lots of pictures!), but you can find them by following links from
http://roguebasin.roguelikedevelopment.org/index.php?title=Digital_field_of_view.
And that was my first time editing a wiki! Man, there's a first time
for everything!
tyrec...@yahoo.com
> Alright, I gave it a shot. They still need polishing (and pictures -
> lots of pictures!), but you can find them by following links fromhttp://roguebasin.roguelikedevelopment.org/index.php?title=Digital_fi....
>
> And that was my first time editing a wiki! Man, there's a first time
> for everything!
It looks good. The one thing you still need to do is add links from
the FoV and LoS pages to your pages. Otherwise people won't be able to
find it after it scrolls off the 'recent changes' list. Ignore this if
you've already done it and I haven't noticed.
I'm still confused about why digital lines are guaranteed to be
symmetric. Lets look at the following situation:
..#
@..
Now it seems that both 01 and 10 are balanced digital lines from the
'@' to the '#'. So how do you ensure that the reverse path (properly
reflected, of course), makes the same decision? Or does my question
demonstrate a more fundamental ignorance?
One other thing, it would be really good if you modified your demo so
that it took a file as input for the map rather than randomly
generating it as it seems to do. That will allow me to easily compare
your algorithm and the permissive-fov variant there-of to the one from
the library.
-D
not...@gmail.com
> It looks good. The one thing you still need to do is add links from
> the FoV and LoS pages to your pages. Otherwise people won't be able to
> find it after it scrolls off the 'recent changes' list. Ignore this if
> you've already done it and I haven't noticed.
Thanks! I added a link from the FoV page. I'm not sure how I should
modify the LoS page though, and which article I should link to if I
do, though.
> I'm still confused about why digital lines are guaranteed to be
> symmetric. Lets look at the following situation:
>
> ..#
> @..
>
> Now it seems that both 01 and 10 are balanced digital lines from the
> '@' to the '#'. So how do you ensure that the reverse path (properly
> reflected, of course), makes the same decision? Or does my question
> demonstrate a more fundamental ignorance?
Well, the path producing 01, when suitably rotated/reflected, becomes
a path producing 10 - the chain code of the path back from B to A
(after rotating/reflecting) is just the chain code from A to B written
backwards. Just by looking at the definitions, it's clear that
reversing a balanced word doesn't unbalance it.
Alternatively, if there is a line connecting diamond A to diamond B
that doesn't touch any obstructing diamonds, then the same line
connects diamond B to diamond A without touching obstructing diamonds.
I have the feeling that I'm misinterpreting your question though...
> One other thing, it would be really good if you modified your demo so
> that it took a file as input for the map rather than randomly
> generating it as it seems to do. That will allow me to easily compare
> your algorithm and the permissive-fov variant there-of to the one from
> the library.
>
> -D
I'll make sure to check how the library reads from files, copy that,
and then randomly generate maps when I'm not given a file to read from
(because I doubt everyone wants to draw a map by hand just to test out
a demo program).
Um, I haven't yet implemented the PFOV variant (you might have meant
that you've already implemented the PFOV variant, but I highly doubt
it), though. I'll get started on that right away, because I'm getting
curious now...
tyrec...@yahoo.com
> Thanks! I added a link from the FoV page. I'm not sure how I should
> modify the LoS page though, and which article I should link to if I
> do, though.
I'd add at least a link to the 'digital lines' page from there. Just
add it to the bottom of the list.
> Well, the path producing 01, when suitably rotated/reflected, becomes
> a path producing 10 - the chain code of the path back from B to A
> (after rotating/reflecting) is just the chain code from A to B written
> backwards. Just by looking at the definitions, it's clear that
> reversing a balanced word doesn't unbalance it.
>
> Alternatively, if there is a line connecting diamond A to diamond B
> that doesn't touch any obstructing diamonds, then the same line
> connects diamond B to diamond A without touching obstructing diamonds.
I guess I'm still thinking of it as a raycasting type of algorithm.
Given that both routes are balanced, if your ray 'chooses' one route,
why would a ray going in the other direction choose that same route.
Shadowcasting and permissive-fov work by taking account of both
possibilities at the same time. The light propogates along all lines
radiating from the center square. I don't see how a raycasting
algorithm can have that same effect since you cast a finite number of
rays. That is why I still can't wrap my head around it.
> I'll make sure to check how the library reads from files, copy that,
> and then randomly generate maps when I'm not given a file to read from
> (because I doubt everyone wants to draw a map by hand just to test out
> a demo program).
Its not in the library itself, but it is pretty simple. Just read a
bunch of lines and for every character, if that character is a '#',
set that location to be a wall. If that character is an '@', set that
location to be the starting location for the player. And otherwise,
just set it to be empty (though it would be even better if it were
empty and showed that character on the map when you were exploring).
This is handy because then it is easy to compare two algorithms on the
same map, whether it is generated by hand or not. I have a couple of
maps that I use when I'm exploring a new LoS algorithm. They let me
move around the map and see a number of specific corner cases. It is
already obvious to me that digital-fov and permissive-fov give very
similar results in most situations. What I'd like to do is run around
on my demo maps and see how they differ in the corner cases (sometimes
literally corners :)).
> Um, I haven't yet implemented the PFOV variant (you might have meant
> that you've already implemented the PFOV variant, but I highly doubt
> it), though. I'll get started on that right away, because I'm getting
> curious now...
I hadn't implemented that. But I wanted to see how both your original
algorithm and your PFOV variant differed from my precise permissive
fov algorithm.
-D
not...@gmail.com
> I'd add at least a link to the 'digital lines' page from there. Just
> add it to the bottom of the list.
Done.
> I guess I'm still thinking of it as a raycasting type of algorithm.
> Given that both routes are balanced, if your ray 'chooses' one route,
> why would a ray going in the other direction choose that same route.
> Shadowcasting and permissive-fov work by taking account of both
> possibilities at the same time. The light propogates along all lines
> radiating from the center square. I don't see how a raycasting
> algorithm can have that same effect since you cast a finite number of
> rays. That is why I still can't wrap my head around it.
Well, it's closer to a beam casting algorithm than a ray casting
algorithm. Actually, it's just weird - it basically runs an entire FOV
algorithm on a parallelogram of height one, in O(N) time. It then
covers the plane with parallelograms. I really have to put pictures on
that wiki page...
I added support for reading from files (it reads space if there's a
space though, so your map demo.txt looks pretty empty).
I also implemented the PFOV variant! It's at
http://reflexivelos.googlecode.com/svn/trunk/pfov.cpp. Hopefully there
are no bugs...
tyrec...@yahoo.com
> Well, it's closer to a beam casting algorithm than a ray casting
> algorithm. Actually, it's just weird - it basically runs an entire FOV
> algorithm on a parallelogram of height one, in O(N) time. It then
> covers the plane with parallelograms. I really have to put pictures on
> that wiki page...
I think that I'm starting to understand. In some sense what you do to
get LoS to a square is to iterate through every possible balanced
digital line from the source square to the destination square. And if
any match, then that square is visible. Buy why concern yourself with
square boundaries? Why not just iterate through every balanced digital
line in the octant and touch things as you visit them? That way, there
won't be any overlapping. And it also occurs to me that you could
precalculate a tree for the octant. There was another FoV type system
that did this not long ago (and I actually think Stone Soup does
something similar). But in your case, the tree represents all possible
balanced digital lines in the octant.
I'm also trying to figure out a geometrical interpretation of your
system. Shadowcasting can be thought of as a point light source.
Permissive-fov can be thought of as an area light source. How should I
think of digital-fov in terms of light? In what ways is the digital-
fov more permissive than permissive-fov as you've said it is?
One suggestion. It is usually pretty easy to use a tool like Inkscape
to come up with crude diagrams. That is what I tend to use.
> I also implemented the PFOV variant! It's athttp://reflexivelos.googlecode.com/svn/trunk/pfov.cpp. Hopefully there
> are no bugs...
I played around with this quite a bit. And you have indeed implemented
PFOV. It seems to be completely isomorphic with my own algorithm. This
makes me want to understand things even more, because now I'm in the
position so many others have been in. I am looking at a permissive-fov
algorithm which doesn't yet make sense. :)
-D
IsaacKuo
> The definition of a "digital line" that they gave is very beautiful,
> and I think it fits in perfectly with the geometry of Roguelikes.
> First, we restrict to lines with slop between 1 and 0, and think of
> the line as a path along the grid. At every step of the path, if we
> move to the right, we write down a "0", and if we move to the up-
> right, we write down a "1". If the number of 1s in every subsequence
> of what we wrote is at most one off from the number of 1s in every
> other subsequence of the same length, then we say that the sequence of
> 0s and 1s is balanced, and that the path forms a digital line.
> Obviously, if a sequence of 0s and 1s is balanced, then when you
> reverse it you get another balanced sequence, so if there is a digital
> line from A to B, then there is from B to A.
Personally, I don't think this definition is "very beautiful". It is
a workable definition for something that is useful, but the
definition itself is seemingly arbitrary and bizarre, unless one
is already familiar with what's useful about the concept it's
describing.
> As it turns out, every path generated by Bresenham's algorithm is a
> digital line, and all digital lines can be generated by a slight
> modification to Bresenham's algorithm with the proper parameters (the
> modification is changing the initial height of the line).
> Alternatively, every digital line is a subset of some line generated
> by Bresenham's algorithm.
I prefer a more geometrical definition. First off, what the heck
is the Bresenham algorithm supposed to be doing, anyway?
Obviously, it's an algorithm to draw a line...but NOT in the
obvious way. The obvious way to draw a line is to put a
straightedge between two points on the grid and color in all
of the squares that it crosses. This generally produces a
"line" which steps horizontally or vertically, and only sometimes
steps diagonally.
But things are different if you start with a grid of diamonds
instead of a grid of squares. Take a square grid and draw
a diamond in each grid space. (The result looks like a
checkerboard square grid turned 45 degrees.) Now, if you
draw a line between two points, you can see which diamonds
are crossed. Assuming the line doesn't pass exactly through
a shared corner, the result will always be a Bresenham line.
To me, this definition for a "digital line" is more elegant. It's
a simple and intuitive geometrical definition. In this definition,
a "digital line" is simply the set of diamonds touched by a
line segment, where the line segment does not pass exactly
through a corner.
Isaac Kuo
not...@gmail.com
> I think that I'm starting to understand. In some sense what you do to
> get LoS to a square is to iterate through every possible balanced
> digital line from the source square to the destination square. And if
> any match, then that square is visible. Buy why concern yourself with
> square boundaries? Why not just iterate through every balanced digital
> line in the octant and touch things as you visit them? That way, there
> won't be any overlapping. And it also occurs to me that you could
> precalculate a tree for the octant. There was another FoV type system
> that did this not long ago (and I actually think Stone Soup does
> something similar). But in your case, the tree represents all possible
> balanced digital lines in the octant.
That was my first idea, but there are O(N^3) lines! This means that
the tree you describe has O(N^4) nodes, counting internal nodes. The
algorithm has to be clever to even run in O(N^3) time.
> One suggestion. It is usually pretty easy to use a tool like Inkscape
> to come up with crude diagrams. That is what I tend to use.
I ended up using Gimp.
> > I also implemented the PFOV variant! It's athttp://reflexivelos.googlecode.com/svn/trunk/pfov.cpp. Hopefully there
> > are no bugs...
>
> I played around with this quite a bit. And you have indeed implemented
> PFOV. It seems to be completely isomorphic with my own algorithm. This
> makes me want to understand things even more, because now I'm in the
> position so many others have been in. I am looking at a permissive-fov
> algorithm which doesn't yet make sense. :)
>
> -D
Yay!
I finally took the time to understand your algorithm, and the main
ideas seem very similar. We both store a line of least slope along
with a line of greatest slope for each "visible field". Even our
"check if a point is on, above, or below a line" subroutines are
(almost) the exact same. The only real difference is that I store the
corresponding convex hull of obstructions as an array, while you store
all of the convex hulls simultaneously in a spaghetti stack of
"bumps" (the trick I use to avoid storing all convex hulls
simultaneously is restricting to one parallelogram at a time - there
is at most one visible field per parallelogram).
The problem I see with the spaghetti stack implementation is updating
the lines, because suddenly, adding a bump becomes an O(size of convex
hull) operation (I've proved the size of the convex hull is at most
O(N^1/2), and conjecture that it's O(N^1/3))... interestingly enough,
though, the maximum possible number of visible bumps seems to be
around O(N^5/3), so it looks like your algorithm might really be
O(N^2). Even if it isn't, there's a small change you can make to your
algorithm to speed up adding a bump to O(log N) time - instead of each
bump just storing its parent, have it also store its grandparent, its
grandparent's grandparent (4 generations up), its great-great-
grandparents great-great-grandparent (8 generations up), etc. Once you
do that, updating the two lines can be done with a binary search type
algorithm. Hmm... I guess we could call the resulting data structure
something like a "spaghetti skip-list"...
Of course, in practice, your algorithm is up to ten times faster than
mine, because mine has to consider all possible parallelograms, even
if only two or three squares are visible.
> I'm also trying to figure out a geometrical interpretation of your
> system. Shadowcasting can be thought of as a point light source.
> Permissive-fov can be thought of as an area light source. How should I
> think of digital-fov in terms of light? In what ways is the digital-
> fov more permissive than permissive-fov as you've said it is?
Isaac Kuo gave the geometric interpretation, which is equivalent to
the one I put on the "digital lines" page (I guess great minds think
alike?).
To prove that digital lines are more permissive than regular lines, I
actually invented a version of digital line that I call a "permissive
line", along with a way of encoding it with 0s, 2s, and (02)s (right
moves, up moves, and diagonal moves, respectively) - this is also on
the digital lines page. Once I did this, I could prove that every
unblocked permissive line from A to B contains an unblocked digital
line from A to B. (The mapping of words sending 0 to 0 and 1 to 02
preserves balanced words, as does the one sending 0 to 0 and 1 to 20.
So do the inverse mappings, when the line is in the correct octant.
Once you map the encoding of a permissive line to an encoding of a
digital line, the digital line you get goes through most, but not all,
of the squares the permissive line went through.)
I guess the reason I fell in love with the "balanced word" definition
so easily, and completely disregarded geometry at first, was because I
had just learned what a balanced word was right before I started
working on the field of view problem. Then I stumbled upon those
papers from the 80s, and it was too late for me... I have found,
however, that debugging my code was much easier than debugging the
permissive version of it, because it is incredibly easy to check if
there is a digital line connecting two points by hand - just pick a
likely looking path, encode it as you walk along it, and check if it's
balanced, and if it isn't, you can generally see why no path
connecting the two points is balanced.
not...@gmail.com
Permissive Field of View algorithm is asymptotically optimal as it is.
I did this by proving that the AddSteepBump function takes at most
O(N^1/2) time (not that hard - in fact, it's probably easy to find a
much better bound), and that the AddSteepBump function is called at
most O(N^3/2) times - that is, there are at most O(N^3/2) *visible*
obstructions. I also proved that you can find situations where there
are at least N^3/2 visible obstructions.
The method I used to prove that there are at most O(N^3/2) visible
obstructions is, perhaps not surprisingly, to find bounds on the
number of visible obstructions in individual parallelograms. In the
end, the problem somehow reduced to proving that every number coprime
to N could be represented as a ratio of two positive or negative
numbers less than root(N), mod N. A simple computer calculation based
on the proof gives an upper bound of 662,855,856 for the number of
visible obstructions in a single octant of a 200,000 by 200,000 grid,
and a computer constructed lower bound managed to fit 33,417,718
visible obstructions into the same octant.
tyrec...@yahoo.com
> If anyone's interested, I've finally proved that the Precise
> Permissive Field of View algorithm is asymptotically optimal as it is.
> I did this by proving that the AddSteepBump function takes at most
> O(N^1/2) time (not that hard - in fact, it's probably easy to find a
> much better bound), and that the AddSteepBump function is called at
> most O(N^3/2) times - that is, there are at most O(N^3/2) *visible*
> obstructions. I also proved that you can find situations where there
> are at least N^3/2 visible obstructions.
So overall, it is O(N^2) in the radius? That is good news. Though, of
course, the constants might be awful. :)
> The method I used to prove that there are at most O(N^3/2) visible
> obstructions is, perhaps not surprisingly, to find bounds on the
> number of visible obstructions in individual parallelograms. In the
> end, the problem somehow reduced to proving that every number coprime
> to N could be represented as a ratio of two positive or negative
> numbers less than root(N), mod N. A simple computer calculation based
> on the proof gives an upper bound of 662,855,856 for the number of
> visible obstructions in a single octant of a 200,000 by 200,000 grid,
> and a computer constructed lower bound managed to fit 33,417,718
> visible obstructions into the same octant.
I would be very interested in a more complete writeup of your proof
and what the worst case number of obstructions looks like. When I
first developed the algorithm, I played around with this a little bit
before giving up. The reduction to proving things about relatively
prime numbers is especially interesting and non-intuitive for me.
-D