LIne of Sight/Illumination Algorithms

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Have been working on my roguelike for a while, and I have a really good
dungeon generation algorithm defined. Time to move on and add
illumination - torches, lanterns, lamps, etc....


Anyone have a good implementation of an illumination algorith?? Not
really worried about the language - I can always hammer it into my code
- as long as it's commented and/or easily decipherable.


Basic hypotenuse formula's seem to work well when firing a weapon or
such, but when I have a large light source - say 10 cell radius -
calculating the path to each of these cells every turn is crippling the
game's performance.


I would really appreciate some constructive help from someone who has
tackled this before. I have read a little about precalculating the path
to each cell from the origin, but I have no idea how to implement this
idea.


Help!!!



And, thanks in advance...

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Although I haven't implemented that code yet either, one way to
implement it is to have a maximum-sized light source (say 12 cell
radius), and build a tree so that cells in the front are higher than
cells in the back. Each turn, iterate through the tree, heading down
each branch until you're either at the current radius, or the cell is
blocked. Worst-case has you checking every cell if there is nothing
blocking the first n rows.

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Brigand wrote:
> Have been working on my roguelike for a while, and I have a really good
> dungeon generation algorithm defined. Time to move on and add
> illumination - torches, lanterns, lamps, etc....
>
>
> Anyone have a good implementation of an illumination algorith?? Not
> really worried about the language - I can always hammer it into my code
> - as long as it's commented and/or easily decipherable.
>
>
> Basic hypotenuse formula's seem to work well when firing a weapon or
> such, but when I have a large light source - say 10 cell radius -
> calculating the path to each of these cells every turn is crippling the
> game's performance.
>
>
> I would really appreciate some constructive help from someone who has
> tackled this before. I have read a little about precalculating the path
> to each cell from the origin, but I have no idea how to implement this
> idea.
>
>
> Help!!!
>
>
>
> And, thanks in advance...

do remember, it doesn't matter if a space is illuminated or not, if LOS
from the PC to it is obstructed. That should decrease the load
significantly.

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

jasonnorthrup@yahoo.com wrote:

> do remember, it doesn't matter if a space is illuminated or not, if LOS
> from the PC to it is obstructed. That should decrease the load
> significantly.
that is, unless things are going on beyond PC's perception which depend
on the determination of light and dark ( like things deciding to move
to and hide in the dark, or stumbling about making noise)

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

> do remember, it doesn't matter if a space is illuminated or not, if LOS
> from the PC to it is obstructed. That should decrease the load
> significantly.


That's exactly where I am stumbling. Calculating an actual angle and
distance to a cell is no problem at all; it's determining what is
blocking line of sight.


This would be no problem in a system where direction is infinitely
dividable - ie, 45.2 degrees, 45.25 degrees, and so on....

Unfortunately, in this finite grid system, within a quadrant, no 2
square have the same angle other than those on a horizontal/vertical
axis, or a perfect 45 degree diagonal.

The best suggestion I have seen so far is to make a tree, ie, an inner
block will always block the next 2 cells in the tree, which will block
the next 4...This is a crude way to do it, but seems to work.

Does anyone else know a good way to do this, which doesn't totally
destroy performance calculating angles to each cell every time?

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

I think using shadow-casting with a pre-computed look-up table would be
your best bet. Again, restricting the size of the array would be a good
idea, and that can be cut down considerably with octants. I suggest
limiting the radius to around 50 cells. This gives you a suitable upper
limit even for VERY open spaces with VERY bright sources of light. For
each cell, calculate two angles - upper left and lower right. Every
time you encounter an obstacle, you can compare the upper and lower
angles of each cell behind it in your look-up table to see if it is
obstructed.

 

[Thomas]

Archived from groups: rec.games.roguelike.development (More info?)

Should the torch or whatever terrain or item object (assuming OO)
actually be the source itself or should it create a Light object that
both a vector on the map (for generation/los) and the torch or terrain
object (for moving/throwing/modifying/deleting) has a pointer too?

The second might be easyer and offer more control... but unnessessary?
how would you do it otherwise.

class map{
private:
std::vector<Object*> lightemmiters;

public:
std::vector<Object*>& get_lightemmiters(){return lightemmiters;}

}

for (all lights...)
world->get_lightemmiters()->get_luminocity();

something like that?

the objects themsleves have light lum routines... or at least hold the
values?... or is that too heavy for most objects. I think a separate
light object would be best but it increases the rigid structure with
all of the pointers hanging around.

Thoughts?...

-Thomas
RL: CHAZM

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

In article <1123550296.565365.38700@z14g2000cwz.googlegroups.com>, "Brigand" <markashall@hotmail.com> wrote:
>> do remember, it doesn't matter if a space is illuminated or not, if LOS
>> from the PC to it is obstructed. That should decrease the load
>> significantly.
>
>
>That's exactly where I am stumbling. Calculating an actual angle and
>distance to a cell is no problem at all; it's determining what is
>blocking line of sight.
>
>
>This would be no problem in a system where direction is infinitely
>dividable - ie, 45.2 degrees, 45.25 degrees, and so on....
>
>Unfortunately, in this finite grid system, within a quadrant, no 2
>square have the same angle other than those on a horizontal/vertical
>axis, or a perfect 45 degree diagonal.
>
How did Nox do it, I wonder? Not a roguelike, but it had really
brilliant and fast LOS and shadows.

Alan

 

[Thomas]

Archived from groups: rec.games.roguelike.development (More info?)

Of course ont the top the drawing would also extend over a little...


I didn't add the squares inthere to start so its a limited view...

and in case i need to mention it... set width text required to view the
above ascii drawings...

-Thomas
RL: CHAZM

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

At 8 Aug 2005 09:56:46 -0700,
Brigand wrote:

> I would really appreciate some constructive help from someone who has
> tackled this before. I have read a little about precalculating the path
> to each cell from the origin, but I have no idea how to implement this
> idea.

There are several pretty effective algorithm for this.

You could search this group for things like shadowcasting, beam casting,
recursive shadowcasting, etc.

Note also that there's pretty good (well, actually very good) C library
written by this group's reader. It uses recursive shadowcasting and is
pretty fast. Since it's C, there should be no problem to link it and use
with any language that permits linking.

It's called libfov and you can find it here:
<http://members.optushome.com.au/puyo/libfov.html>

While looking for this page, I incidentally found an announcment I skipped
before:
<http://64.233.183.104/search?q=cache:7BnBlWvfAzkJ:www.xasa.com/grupos/en/rec/games/article/23303/rec.games.roguelike.development+pyfov&hl=en>

Might be worth taking a look

--
Radomir `The Sheep' Dopieralski @**@_
(TT) 3 Waaah!
. . . ..v.vVvVVvVvv.v.. .

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

At Tue, 9 Aug 2005 13:17:46 +0000 (UTC),
The Sheep wrote:

> At 8 Aug 2005 09:56:46 -0700,
> Brigand wrote:
>
>> I would really appreciate some constructive help from someone who has
>> tackled this before. I have read a little about precalculating the path
>> to each cell from the origin, but I have no idea how to implement this
>> idea.
>
> There are several pretty effective algorithm for this.
>
> You could search this group for things like shadowcasting, beam casting,
> recursive shadowcasting, etc.

You might also want ot chek out this page:
<http://www.roguelikedevelopment.org/php/category/showCategory.php?path=development/&category=LOS>

--
Radomir `The Sheep' Dopieralski @**@_
($s) 3 Ching!
. . . ..v.vVvVVvVvv.v.. .

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

In article <1123568576.618163.239730@z14g2000cwz.googlegroups.com>,
comments@foresightsagas.com says...
> Should the torch or whatever terrain or item object (assuming OO)
> actually be the source itself or should it create a Light object that
> both a vector on the map (for generation/los) and the torch or terrain
> object (for moving/throwing/modifying/deleting) has a pointer too?

I was just thinking along those lines. A terrain square holds a list
of vectors that represent the light falling on it from each of eight
directions. It passes this light, slightly weaker, divided among up to
three neighbouring cells in each direction, with the middle one getting
the most (will need tweaking). In turn, each of these three adds the
light to its appropriate vector.

Not sure how it would work out in practice. It might be necessary for
the source to be implemented as a series of light vectors in a number
of surrounding squares.

Monsters could cast shadows - you might notice a flickering even if you
couldn't see the monster, for example at the door of a room.

Just an idea, for anyone who wants to try it.

- Gerry Quinn

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

You also need to be careful with how you round. 1/2 rounded up equals
1. That can easily be fixed with a simple statement though. More
important is that your algorithm could be used with gradient colorings,
something Im looking to implement.

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Thomas wrote:
> Some guy:
>
>>In turn, each of these three adds the light to its appropriate vector.
>
>
[snnip Thomas post]

Is it just my newsreader or does Thomas replies show up as replies to
totally different "branches" of the thread tree? If it is Thomas who
replies in the wrong way, then please stop, it is confusing.

>
> -Thomas
> RL: CHAZM
>

BR,
Björn

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

At Wed, 10 Aug 2005 08:47:46 +0200,
Björn Bergström wrote:

> Thomas wrote:
>> Some guy:
>>
>>>In turn, each of these three adds the light to its appropriate vector.
>>
>>
> [snnip Thomas post]
>
> Is it just my newsreader or does Thomas replies show up as replies to
> totally different "branches" of the thread tree? If it is Thomas who
> replies in the wrong way, then please stop, it is confusing.

Probably another victim of Google Groups's forum-like interface

--
Radomir `The Sheep' Dopieralski @**@_
(..) 3 Bee!
. . . ..v.vVvVVvVvv.v.. .

 

[Thomas]

Archived from groups: rec.games.roguelike.development (More info?)

Oh, I'm really sorry. Yeah... i am forced to use google groups....

If anyone knows how to setup a free newsgroup server then i could do
that on my thunderbird (i just _switched_ from outlook.. woohoo!) email
and news client (at home at least, at work i would still have to use
google but i am out of a job as of this friday so it doesent matter for
too much longer... it was just an internship...)

on google you just quote by adding >'s

> this
> is
> a
> quote

or something...

again, really sorry if i confused someones newsreader ...

-Thomas
RL: CHAZM

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

On 10 Aug 2005 10:51:34 -0700, Thomas wrote:

>Oh, I'm really sorry. Yeah... i am forced to use google groups....
>
>If anyone knows how to setup a free newsgroup server then i could do
>that on my thunderbird (i just _switched_ from outlook.. woohoo!) email
>and news client (at home at least, at work i would still have to use
>google but i am out of a job as of this friday so it doesent matter for
>too much longer... it was just an internship...)

Well., you can try Yottanews, but you only get 1.25GB/month, so watch
the binary downloads:
http://www.yottanews.com/freeaccount.php

Note that you must give them a valid email address, and your account
with them relies on your IP address not changing (usually ok for
broadband, not so good for dialup).

There's also Teranews - no IP address limit and 50MB/day on a free
account - but they require a 1-time payment of US$3.95:
http://www.teranews.com/createaccount.html

Me, I use one provided by my ISP (they have four, I'm supposed to limit
myself to the "west" server).

>on google you just quote by adding >'s
>
>> this
>> is
>> a
>> quote
>
>or something...

Quoting *should* be automatic. I haven't posted through Google in a few
years - not since *long* before they announced the "upgrade" - but ISTR
that it quoted correctly.

>again, really sorry if i confused someones newsreader ...

I'm confused by the fact that your post showed up in the wrong branch -
you apparently replied to The Sheep but your post shows up as a reply to
Gerry...
--
auric underscore underscore at hotmail dot com
*****
Beat your head repeatedly with a steel post.

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

In article <1123607349.279305.172150@g49g2000cwa.googlegroups.com>,
comments@foresightsagas.com says...
> Some guy:
> > In turn, each of these three adds the light to its appropriate vector.
>
> So i was thinking right after i wrote my last post about how to do it
> recursivly. It sounds a little like how you were saying...

>
> And then if you moved one square then the light would do the same thing
> with -9 on the square and erase them and then move forward and add 9 to
> that square...
>
> seems inneficiant!...

Probably inefficient, but it might have some merits if you throw
processor power at it. Flickering shadows due to moving monsters, that
kind of thing.

- Gerry Quinn

 

[Thomas]

Archived from groups: rec.games.roguelike.development (More info?)

> Groups ie *evil*, I tell ya!

To each his own.... but really. Google gives to much away free to be
"evil". I am sure that its just a little buggy. i mean they host so
many groups and usenet groups that its amazing to me it hasn't just
died.... It is a beta i suppose...

Then again... it is a company... and does make money... oh, your
right... then it MUST be evil

> I use one provided by my ISP.

Yeah... I am sure i have one... i use quest dsl. I just done know what
it is...

I'll look it up sometime...

Uhemhem... what were you saying about "Llne of Sight/Illumination
Algorithms"...?


-Thomas
RL: CHAZM

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

At 10 Aug 2005 10:51:34 -0700,
Thomas wrote:

> Oh, I'm really sorry. Yeah... i am forced to use google groups....

Lots of people new to Usent have similar problems recently. Google Groups
ie *evil*, I tell ya!

> If anyone knows how to setup a free newsgroup server then i could do
> that on my thunderbird (i just _switched_ from outlook.. woohoo!) email
> and news client (at home at least, at work i would still have to use
> google but i am out of a job as of this friday so it doesent matter for
> too much longer... it was just an internship...)

<http://news.aioe.org/en/article-diaporama.php3?id_article=26>


--
Radomir `The Sheep' Dopieralski @**@_
(==) 3 Yawn?
. . . ..v.vVvVVvVvv.v.. .

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Thomas wrote:
> Oh, I'm really sorry. Yeah... i am forced to use google groups....
>
> If anyone knows how to setup a free newsgroup server then i could do
> that on my thunderbird (i just _switched_ from outlook.. woohoo!) email
> and news client (at home at least, at work i would still have to use
> google but i am out of a job as of this friday so it doesent matter for
> too much longer... it was just an internship...)

I'd recommend news.sunsite.dk. They require registration, but it's free,
fast and reliable.

> on google you just quote by adding >'s
>
>
>>this
>>is
>>a
>>quote
>
>
> or something...
>
> again, really sorry if i confused someones newsreader ...
>
> -Thomas
> RL: CHAZM
>

BR,
Björn

 

[Edward]

Archived from groups: rec.games.roguelike.development (More info?)

Bj?rn Bergstr?m <bjorn.bergstrom@roguelikedevelopment.org> wrote:
<something regarding news servers>

Incidentally, thankyou very much for your article on recursive
shadowcasting. I recently implemented a FOV algorithm using that doc as
a guide, and it was helpful.

Can be found through www.roguelikedevelopment.org if the original poster
is looking for it. Recursive shadowcasting is good.

--jude hungerford.