Intriguing new Line Of Sight algorithm (Java, Python)
b0rsuk
have been having trouble implementing it. Especially that the
description is somewhat vague and links to Java implementation were
notoriously down. But I've recently found the implementation !
I've found it on Rogue Basin, it's labeled as 'Modelling Rays for Line
of Sight in an Object-Rich World'
http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision
Of two pages describing it, neither has a working link to
implementation:
http://www.geocities.com/temerra/los_rays.html
http://rana-rama.blogspot.com/2007/10/raycasting-easy-way.html
It's nothing a little cunning won't fix, though. If you examine the
links closely you know what to google for: raymulticast3 . And indeed,
someone has uploaded the Java implementation to Rapidshare ! Here it
is.
http://rapidshare.com/files/88383450/raymulticast3.zip
The algorithm is quite interesting. I'm only starting to understand
it, but it's somehow based on casting rays, and once obstruction is
detected the information about it is passed to other rays, so each
tile is actually visited only once. It's supposed to be quite fast and
has some other benefits too. Some become apparent if you use the
commented out method 'displayText' in ResultsDisplayer . It prints
stuff to terminal instead of using awt, swing and other windowed crap.
By default, V represents origin of view, O is unobstructed square, W
is wall (obstruction), stuff behind 'I' is ignored, dot (.) represents
obstructed stuff. Additionally, letters like A, B, X, Z, C represent
various degrees of obscurity. If you spend a while looking at the
results, you realise it would be very useful for ranged combat and
explosions, because it makes partial obscurity/cover possible. Just
letters 'A' and 'B' look like partial obscurity. I like this, because
- for me - the algorithm used by Dungeon Crawl Stone Soup (my
favourite roguelike at the moment) is too permissive. It makes it very
hard to withdraw from ranged combat.
I'd be very grateful if someone could help me rewrite the algorithm in
Python. I've already done a Python version, but it's a bit buggy
(almost everything works, but walls a bit away and ABOVE the player
don't "cast shadow" properly. Walls to the left, right, down etc
behave normally. So far, I'm unable to track it down. The bug is not
present in the original Java implementation. Other than that, both
Java version and my implementation produce identical results, as far
as I can tell.
Is anyone interested in helping with my Python implementation ? Should
I post it here ?
There's an additional issue, too. Currently it seems to draw
obstructions behind other obstructions (but obscures empty squares
properly). It may be just for debug purposes and to make it easier to
see the results. It may be a trivial fix, but I can't figure out how
turn it off.
b0rsuk
pau...@mbnet.fi
> New is relative, of course. It has been posted in 2007, but people
> have been having trouble implementing it.
This is classical los-programming in roguelike world. If it
doesn't need any corrections then it's too difficult to
understand and implement.
b0rsuk
I don't understand - you mean if it doesn't, or if it _does_ need
corrections ?
b0rsuk
pau...@mbnet.fi
> I don't understand - you mean if it doesn't, or if it _does_ need
> corrections ?
Let me say that in swedish. What is "if" in swedish? I need to
improve my swedish..
Jotaf
You need to improve your English. :)
---
Seems straightforward. The main advantage then would be the partial
obscurity thing. I had a quick look at the code and the main algorithm
seems to be easy enough to understand. I don't program in python
though, so I can't help you. But it would be quite handy for my RL and
other true-color RLs, because partial obscurity is easy to display to
the user. Could be a nice addition to lib-tcod. :)
Jotaf
Grim
>
> I'd be very grateful if someone could help me rewrite the algorithm in
> Python. I've already done a Python version, but it's a bit buggy
> (almost everything works, but walls a bit away and ABOVE the player
> don't "cast shadow" properly. Walls to the left, right, down etc
> behave normally. So far, I'm unable to track it down. The bug is not
> present in the original Java implementation. Other than that, both
> Java version and my implementation produce identical results, as far
> as I can tell.
> Is anyone interested in helping with my Python implementation ? Should
> I post it here ?
>
I am, if the request is still valid...
I'm developing a roguelike in python and a couple of weeks ago I read
about this algorithm on roguebasin. I've got some working code
already, but its not tested very well. I can send it to you, or post
it somewhere, if anyone else is interested. Room corners are a
problem, but I think the original Java implementation has that too.
Grim
P.S. This is my first post here, so big hello to everyone!
dominik...@gmail.com
A year and a few months ago I tried to understand this algorithm, but
failed. The description seemed insufficient to me, I didn't get the
idea behind what the algorithm actually does. I tried drawing all
that, doing the calculations in my head... nothing. If you try to
implement the algorithm from scratch in a different language, maybe
you could write a more thorough description of how it actually works?
Implementing it in C might be a cool idea (as Jotaf mentioned, for
true colour RLs, it might be extremely interesting).
Mingos
Grim
I won't pretend that I fully understand the algorithm. I got the
general idea.
I referenced the java example for some of the details when I was
writing
the python version.
Anyway, I've put the python code here:
http://code.google.com/p/nofate/
It has some comments with my current understanding of how it works.
I'll try to do a C version as soon as I find a bit of time...
Grim
jice
>
> > > On 27 Gru 2008, 14:57, b0rsuk <jaze...@gmail.com> wrote:
>
> > > > I'd be very grateful if someone could help me rewrite the algorithm in
> > > > Python. I've already done a Python version, but it's a bit buggy
> > > > (almost everything works, but walls a bit away and ABOVE the player
> > > > don't "cast shadow" properly. Walls to the left, right, down etc
> > > > behave normally. So far, I'm unable to track it down. The bug is not
> > > > present in the original Java implementation. Other than that, both
> > > > Java version and my implementation produce identical results, as far
> > > > as I can tell.
> > > > Is anyone interested in helping with my Python implementation ? Should
> > > > I post it here ?
>
> general idea.
> I referenced the java example for some of the details when I was
> writing
> the python version.
>
> Anyway, I've put the python code here:http://code.google.com/p/nofate/
> It has some comments with my current understanding of how it works.
>
> I'll try to do a C version as soon as I find a bit of time...
>
> Grim
FYI, I added this fov algorithm in the latest beta of libtcod. I
called it "diamond raycasting"... How poetic ;). The current version
in svn is not optimized. But once optimized, I have an unexpected
result. It's still a bit slower than the basic, braindead raycasting
default libtcod algorithm. Here are the latest performance results, on
a 600x600 map with 5000 random obstacles (same map for every
algorithm, not measured on the same pc as the results on my blog) :
CIRCULAR FOV 242.809 call/s 4ms/call
DIAMOND FOV 14.6736 call/s 68ms/call
OPTIMIZED DIAMOND FOV 80.1292 call/s 12ms/call
I'll put the optimized version in svn tonight. Why is it slower than
standard raycasting while it visits only once each cell ? I think
there are two main reasons :
* the cell visiting is really fast in libtcod (only a bool test). If
you have a much slower "can we see through the cell ?" test, diamond
will probably be much faster
* there are much more function calls in diamond. In standard
raycasting, one function call per cell on the perimeter of the map
(one per ray casted). In diamond, up to 3 function calls for each cell
in the fov. Since the benchmark test has a rather big fov, diamond is
not at its best.
Also note that the two algorithms don't produce the same fov. Diamond
is a bit more permissive, so you might prefer to use it even if it's a
bit slower.
Last point, I didn't figure out how to put walls in the fov with
diamond raycasting, so I apply the same post-processing step as with
the standard algorithm. libtcod fov module has allways put walls in
the fov along with the ground cells. Now, it's optional. For the
benchmark above, this step is disabled.
unoptimized implementation (starts at line 280) :
http://code.google.com/p/libtcod/source/browse/trunk/src/fov_c.c
libtcod 1.4.1b4 with samples allowing you to compare the two
algorithms results :
http://jice.nospam.googlepages.com/thedoryenlibrary
--
jice
jice
>
> FYI, I added this fov algorithm in the latest beta of libtcod. I
> called it "diamond raycasting"... How poetic ;). The current version
> in svn is not optimized. But once optimized, I have an unexpected
> result. It's still a bit slower than the basic, braindead raycasting
> default libtcod algorithm. Here are the latest performance results, on
> a 600x600 map with 5000 random obstacles (same map for every
> algorithm, not measured on the same pc as the results on my blog) :
>
> CIRCULAR FOV 242.809 call/s 4ms/call
> DIAMOND FOV 14.6736 call/s 68ms/call
> OPTIMIZED DIAMOND FOV 80.1292 call/s 12ms/call
>
You can review the optimized version here :
http://code.google.com/p/libtcod/source/browse/trunk/src/fov_diamond_raycasting.c
Note that even with smaller fields of view (for example when limiting
the fov range to 10 cells), diamond is still slower than standard
raycasting, even though the difference is much smaller.
--
jice
b0rsuk
> > Is anyone interested in helping with my Python implementation ? Should
> > I post it here ?
>
> I am, if the request is still valid...
>
Oh. So someone cares, after all.
I'll clean it up slightly and post it once I get back home.
b0rsuk
b0rsuk
>
> FYI, I added this fov algorithm in the latest beta of libtcod. I
> called it "diamond raycasting"... How poetic ;). The current version
> in svn is not optimized. But once optimized, I have an unexpected
> result. It's still a bit slower than the basic, braindead raycasting
> default libtcod algorithm.
!!!!!!!!!!!
What kind of optimisations did you make ? What was your input data /
test obstruction layout ?
!!!!!!!!!!!!!
I'm asking because I've been debugging the algorithm yesterday and
noticed something interesting.
As you've already mentioned, there's no easy way to draw walls except
to use post-processing and just take them from obstruction table.
Unless I'm missing something. This is not a problem if you want all
walls visible, but if you only want to show walls in player's view it
gets tricky. By default, all walls are visible.
I wanted to only display walls player can see. So I changed the
_order_ of checks in displayText method. Put wall drawing after
displaying other characters 'ABXY....' in original implementation.
This worked, but:
(asterisk represents chars after an 'I')
input @...#..#..
output @...#i****
input @...##...#..
output @...##i*****
In short: if first wall player can see is thick, player can see walls
which should be obscured by walls. "ignoring" only kicks in after ray
exits the first wall in line. Note that in second example the second
wall is igored properly - it's in the shadow of first wall.
The author probably never noticed that, because he was printing all
walls anyway (walls can't obscure walls), and well, didn't test too
hard.
Note that ignoring / cutting off rays works properly if there's an
empty space - but not a wall - behind the first wall . The algorithm
shows more walls than it should IF the first wall is thick.
This surely has performance implications. Normally, ignored rays (i
and * in my example) speed things up because * doesn't need to be
visited. In roguelikes, the first wall player can see will often be
thick
While I currently don't have a solution for showing only walls player
should be able to see, I know how to make the 'ignore ray' feature
kick in faster, before the first thick wall ends. It may not be a
perfect solution (try to come up with better !) but here it is:
- make all walls hollow ! No, seriously. Make "deep" walls not count
as obstructions for purposes of FOV calculation. Deep wall - a wall
that is only connected to other walls and player can't see it anyway.
This should speed things up. No, you don't actually have to generate
levels with hollow walls. It's enough to generate an obstruction data
table which contains only outer walls. It can be shared between
monsters, between turns, and only needs to be updated each time the
level layout changes. Which is not very often.
b0rsuk
b0rsuk
> > Is anyone interested in helping with my Python implementation ? Should
> > I post it here ?
>
> I am, if the request is still valid...
Here's the code. Yes, it's a /rough/ translation.
In my defense, I'm not an experienced programmer and I didn't
understand the code I was translating from Java. I only made sure it's
functionally correct and seems to produce identical results. It's
pretty much Java code in Python, almost no Python-specific idioms or
techniques used. There might be some Javadoc comments here and there.
Almost all function names are identical, etc.
Your implementation looks much cleaner. I'll have a look at it,
compare, and see if there's a speed difference...
It will be there for 1 month. If there's demand and/or a place where I
can host it forever, please let me know.
I was writing it in Python3, but after minor changes it works in
Python 2.x too. (from __future__ import division, print_function). In
one of last lines, random obstacle placement is 'commented out' - the
amount multiplier is zero. It's after hasty cleanup, straight from
debugging.
b0rsuk
b0rsuk
I've left some static obstacles in that file, to illustrate the vision
bug. The wall to the left from '@' is thin, 1 square wide and it casts
shadow like it should. The wall to the right is 2 square thick, and
both wall squares are displayed. Only once the wall ends the algorithm
realises this line can be ignored. Something should be done about it.
Current workaround I'm considering - feed it prepared data which
doesn't contain obstacles surrounded only by other obstacles (from all
8 directions).
(if you run the file, it prints output from TWO method - scroll the
terminal up. One method - displayDebug - is very similar to the
original Java implementation, and good for debugging because it shows
even obscured walls. The other method - displayText - is my
interpretation of the results. I try not to display obscured walls
(works, but not in all cases). I also treat 'a' and 'b' characters
like partial obscurity.
b0rsuk
jice
> On 12 Sty, 11:30, jice <jice.nos...@gmail.com> wrote:
>
> > FYI, I added this fov algorithm in the latest beta of libtcod. I
> > called it "diamond raycasting"... How poetic ;). The current version
> > in svn is not optimized. But once optimized, I have an unexpected
> > result. It's still a bit slower than the basic, braindead raycasting
> > default libtcod algorithm.
>
> !!!!!!!!!!!
> What kind of optimisations did you make ? What was your input data /
> test obstruction layout ?
> !!!!!!!!!!!!!
>
I'm using the same test layout as described in the original article :
a 600x600 map with 5000 random 1x1 obstacles. I didn't optimized the
algorithm itself. It's still exactly the same as the Java version. I
only removed any C specific costly operation, like memory allocations
and inadapted container operations. Note that I don't say it' s slow.
It can calculate the 600x600 fov 56 times/seconds on my old Athlon 64
2800+. It's only slower than basic raycasting, but produce more
elegant fields of view.
--
jice
b0rsuk
> On 14 jan, 12:33, b0rsuk <jaze...@gmail.com> wrote:
>
> > On 12 Sty, 11:30, jice <jice.nos...@gmail.com> wrote:
>
> > > FYI, I added this fov algorithm in the latest beta of libtcod. I
> > > called it "diamond raycasting"... How poetic ;). The current version
> > > in svn is not optimized. But once optimized, I have an unexpected
> > > result. It's still a bit slower than the basic, braindead raycasting
> > > default libtcod algorithm.
>
> > !!!!!!!!!!!
> > What kind of optimisations did you make ? What was your input data /
> > test obstruction layout ?
> > !!!!!!!!!!!!!
>
> I'm using the same test layout as described in the original article :
> a 600x600 map with 5000 random 1x1 obstacles. I didn't optimized the
> algorithm itself. It's still exactly the same as the Java version. I
> only removed any C specific costly operation, like memory allocations
> and inadapted container operations.
I see. I've examined the other Python implementation (seems much
nicer, by the way) and it seems that it's not too hard to modify it to
stop expanding into thick walls. You may want to check it if you're
interested in improving it.
(I'm not sure if it actually speeds things up in some cases. Probably
yes. By the way, the workaround I proposed is not actually changing
the implementation, but the data you feed into it. Hopefully made
obsolete by that other version, I'll have a closer look.
Note that I don't say it' s slow.
> It can calculate the 600x600 fov 56 times/seconds on my old Athlon 64
> 2800+. It's only slower than basic raycasting, but produce more
> elegant fields of view.
I see. Calculating the same field (600x600 with 5000 random
obstructions) once takes about 1.8 sec with my Python translation, and
0.9 sec with the other Python implementation. I agree about the field
of view. Fortunatelly I'm not planning to use the algorithm on fields
this big. And if most of the view is obscured with obstacles (5000 /
600x600 doesn't do that) it takes much less time.
By the way:
- is there a comparison of various FOV algorithms anywhere ? Things
like complexity/speed, artifacts/is it perfectly symmetric, etc...
- do I remember correctly that simple, dumb raycasting produces some
artifacts and/or is not symmetric ?
Strangely, wikipedia doesn't have much on this. Is this (FOV
algorithms) really such a niche topic ?
dominik...@gmail.com
> By the way:
> - is there a comparison of various FOV algorithms anywhere ? Things
> like complexity/speed, artifacts/is it perfectly symmetric, etc...
I don't remember seeing one. Most algorithms are described separately.
I've also seen a Java roguelike library that did contain various
implementations of the FOV algorithm, which you could compare in a
test minigame, but there was no data about speeds. It might be
interesting to run such a test.
> - do I remember correctly that simple, dumb raycasting produces some
> artifacts and/or is not symmetric ?
I don't know about it being symmetric or not, but it does produce
artifacts. The problem is well described on Jice's page:
http://jice.nospam.googlepages.com/visibilitydetermination
The artifacts mentioned there are removed by a post processing
algorithm. Of course, they DO produce other artifacts, but much less
frequent and not that annoying (i.e. a visible closed door might
become invisible when opened).
Simon Richard Clarkstone
I think he means:
"There are two sorts of LoS algorithms in the world: ones that need
corrections, and ones that are too complicated to understand."
--
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. |
Grim
> I see. I've examined the other Python implementation (seems much
> nicer, by the way) and it seems that it's not too hard to modify it to
> stop expanding into thick walls. You may want to check it if you're
> interested in improving it.
> (I'm not sure if it actually speeds things up in some cases. Probably
> yes. By the way, the workaround I proposed is not actually changing
> the implementation, but the data you feed into it. Hopefully made
> obsolete by that other version, I'll have a closer look.
>
I think going one tile behind walls is what this algorithm needs to
work properly. Only then, after merging inputs from potentially more
than one tile, it can decide if it should terminate the ray or not.
Anyway, I couldn't find a way to make it stop on the first wall tile
without breaking it...
The original implementation assumes that all obstacles are visible,
and the algorithm is used to determine what other tiles are visible,
not which obstacles. The obscure() method returns true for all walls,
visible or not (like those "deep" walls behind other walls). That's
why instead of a boolean value I've got 3 possible values (the FOV_*
constants): visible, visible obstacle, and obscured. For FOV
calculation, the last 2 values are the equivalent of the original
obscure() returning true, but from visibility point of view, the first
two values designate a visible tile.
I haven't had much time lately to look into libtcod's implementation
but I'm looking forward to it. The post processing step sounds
interesting. My current code produces artifacts - missing room
corners.
Grim
b0rsuk
> I haven't had much time lately to look into libtcod's implementation
> but I'm looking forward to it. The post processing step sounds
> interesting. My current code produces artifacts - missing room
> corners.
I wouldn't call that bad. There are artifacts either way, even with
'classic' style. You're just too used to them to care anymore. In this
algorithm, rays don't pass between two walls which are adjacent
diagonally. In classic roguelikes (those that allow diagonal movement)
you can travel between two diagonally adjacent walls, which is strange
to say at least. It gets even stranger when there's a checkboard made
of water and floor tiles. You can step between two water squares.
Fishes can swim between two land squares.
In a classic roguelike, if you want to make a wall that can't be
passed diagonally, you need *two* layers of wall.
In other words, I think it's a matter of definition, of convention. If
you make a roguelike that disallows going between two diagonally
adjacent wall tiles, it's all ok.
Some comments on your code.
- using tab characters for indentation causes problems, as different
editors and operating systems display them differently. Some programs
destroy tabs while copying text etc. Many people recommend using 4
spaces for indent, and limiting yourself to 79 character lines. Good
editors can be configured to insert 4 spaces when you press Tab.
mcedit, for example, highlights your code improperly.
- The 'dump()' method could probably be written like this:
def dump(self):
line = [self, self.state, '/', self.active, 'S',
self.shadowedBy, 'O:, self.offset, 'xln:' ...]
return ' '.join([str(word) for word in line])
I wanted to say __str__(self) should be used for this, but then
noticed you print 'self' as the first argument. Strange.
- in struct.py:
def __add__(self, p):
return Point( (self.x + p[0], self.y + p[1]) )
- you're using 'map' as a variable name, and 'abs' as a method. This
is confusing because map and abs are built-in functions.
def __radd__(self, p):
return Point( (self.x + p[0], self.y + p[1]) )
This is redundant. You can define only the first method, then do:
__radd__ = __add__
in class definition. Of course, it only makes sense for addition
because the order doesn't matter.
b0rsuk
b0rsuk
1) you can write only the first addition method then use the
__radd__ = __add__
trick
2) It's best to avoid using names of builtin methods and functions
(map, abs) for your own methods and objects.
Ray Dillinger
One thing here is that Bresenham's line algorithm isn't quite
the right line algorithm for raycasting, because it will cross
corners diagonally, like this:
_________
|X|X| | |
| | |X|X|
---------
And in the proper algorithm for raycasting you want to only
cross edges, like this. (change either X or Y but not both
at once). This may involve jogging the theoretical line a
few hundredths of a square up or down to avoid ever exactly
crossing a corner.
_________
|X|X| | |
| |X|X|X|
---------
Bear
Grim
>
> - The 'dump()' method could probably be written like this:
>
> def dump(self):
> line = [self, self.state, '/', self.active, 'S',
> self.shadowedBy, 'O:, self.offset, 'xln:' ...]
> return ' '.join([str(word) for word in line])
>
> I wanted to say __str__(self) should be used for this, but then
> noticed you print 'self' as the first argument. Strange.
>
What I really meant, was to use parent class (Point) str() method() to
display coordinates, so something like this:
def __str__(self):
return Point.__str__(self) + ' ' + str(self.state) + '/' + str
(self.active) \
+ ' S:' + str(self.shadowedBy) + ' O:' + str(self.offset) \
+ ' xIn:' + str(self.xInput) + ' yIn:' + str(self.yInput)
... but I can't use ' '.join(...) this way.
>
> - you're using 'map' as a variable name, and 'abs' as a method. This
> is confusing because map and abs are built-in functions.
Good point. Same goes for struct.py, struct is a standard python
module. These kind of errors can be really annoying to debug...
Thanks for all your comments. I've made some changes and updated the
code in svn repository.
Grim
pende...@gmail.com
> If you make a roguelike that disallows going between two diagonally
> adjacent wall tiles, it's all ok.
I did this, and I really recommend it. Diagonal moves and attacks are
permitted as usual, but not if either of the adjacent squares are wall
tiles. You can still step between (impassable) monsters diagonally,
and the "checkerboard liquid" thing that you talked about would work
the same for a person as long as the liquid is at all passable for him
(in my game, it is allowed with a speed penalty). But the problems it
solves, for me, are (1) the weirdness of being able to squeeze cat-
like through the infinitesimal crack between diagonally adjacent
walls, and (2) the counter-intuitive newbie-unfriendliness of
penalizing you for not cutting corners in a hallway that turns 90
degrees. It feels very natural to me.
nick.w...@gmail.com
> On 15 Sty, 14:25, b0rsuk <jaze...@gmail.com> wrote:
>
> > By the way:
> > - is there a comparison of various FOV algorithms anywhere ? Things
> > like complexity/speed, artifacts/is it perfectly symmetric, etc...
Yes, there is at http://roguebasin.roguelikedevelopment.org/index.php?title=Category:FOV
nick.w...@gmail.com
...You can view the working algorithm as an interactive applet.