Extremely fast simplified LOS

From RogueBasin
(Difference between revisions)
Jump to: navigation, search
m
m (Removed spam)
Line 1: Line 1:
[http://groups.ku.edu/cgi-bin/cgiwrap/kuksa/forum/ezboard.cgi?db=general&action=read&dbf=66 lisinopril online] [http://www.bc.edu/apps/bookstore/cards/jun7-225942359494.html nokia ringtones] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=277 paxil online] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=248 didrex online] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,51 buy ultracet] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,47 sonyericsson ringtones] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=267 free mono ringtones] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=304 valium online] [http://www.bc.edu/apps/bookstore/cards/jun7-225151929462.html diazepam] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=243 cheap clomid] [http://www.bc.edu/apps/bookstore/cards/jun7-224862564330.html cheap fioricet] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,37 order paxil] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=259 kyocera ringtones] [http://climate.msrc.sunysb.edu/1984/messages/323.html mp3 ringtones] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,31 mp3 ringtones] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=235 alprazolam online] [http://climate.msrc.sunysb.edu/1984/messages/290.html alltel ringtones] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=8 alprazolam online] [http://groups.ku.edu/cgi-bin/cgiwrap/kuksa/forum/ezboard.cgi?db=general&action=read&dbf=68 buy lipitor] [http://groups.ku.edu/cgi-bin/cgiwrap/kuksa/forum/ezboard.cgi?db=general&action=read&dbf=56 buy hydrocodone] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,54 free verizon ringtones] [http://climate.msrc.sunysb.edu/1984/messages/314.html cheap levitra] [http://www.bc.edu/apps/bookstore/cards/jun7-223882830478.html tramadol online] [http://climate.msrc.sunysb.edu/1984/messages/311.html buy hydrocodone] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=65 sprint ringtones] [http://climate.msrc.sunysb.edu/1984/messages/363.html order xanax] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,43 free real ringtones] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=67 tracfone ringtones] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,40 buy propecia] [http://groups.ku.edu/cgi-bin/cgiwrap/kuksa/forum/ezboard.cgi?db=general&action=read&dbf=50 order ativan] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=290 samsung ringtones] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,50 tramadol online] [http://climate.msrc.sunysb.edu/1984/messages/303.html didrex online] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=14 but clomid] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=263 cheap lorazepam] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,42 free samsung ringtones] [http://climate.msrc.sunysb.edu/1984/messages/289.html cheap albuterol] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=81 cheap zyban] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=293 order soma] [http://climate.msrc.sunysb.edu/1984/messages/299.html but clonazepam] [http://climate.msrc.sunysb.edu/1984/messages/331.html cheap paxil] [http://www.bc.edu/apps/bookstore/cards/jun7-226532801730.html free real ringtones] [http://climate.msrc.sunysb.edu/1984/messages/344.html sildenafil online] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,45 soma online] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=9 ambien online] [http://climate.msrc.sunysb.edu/1984/messages/361.html order wellbutrin] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=5 adipex online] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=282 buy propecia] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=286 real ringtones] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=249 diethylpropion online] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=50 free polyphonic ringtones] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=56 cheap rivotril] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=258 free jazz ringtones] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=261 but lipitor] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=34 lorazepam online] [http://climate.msrc.sunysb.edu/1984/messages/336.html cheap prozac] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=239 order carisoprodol] [http://climate.msrc.sunysb.edu/1984/messages/334.html free polyphonic ringtones] [http://groups.ku.edu/cgi-bin/cgiwrap/kuksa/forum/ezboard.cgi?db=general&action=read&dbf=70 tenuate] [http://groups.ku.edu/cgi-bin/cgiwrap/kuksa/forum/ezboard.cgi?db=general&action=read&dbf=43 cheap valium] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=281 polyphonic ringtones] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=32 lipitor online] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=24 free free ringtones] [http://climate.msrc.sunysb.edu/1984/messages/333.html phentermine online] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=57 sagem ringtones] [http://groups.ku.edu/cgi-bin/cgiwrap/kuksa/forum/ezboard.cgi?db=general&action=read&dbf=75 free free ringtones] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=302 buy ultracet] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=276 buy ortho] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=308 vigrx online] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,33 nexium] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,28 buy meridia] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=291 free sharp ringtones] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=42 free music ringtones] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,20 diazepam online] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=11 cheap carisoprodol] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=75 but wellbutrin] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=36 meridia online] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,23 free free ringtones] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,57 buy xanax] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=270 free mtv ringtones] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=251 cheap fioricet] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=269 mp3 ringtones] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=273 nextel ringtones] [http://climate.msrc.sunysb.edu/1984/messages/288.html adipex online] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=311 cheap xanax] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,41 sagem ringtones] [http://climate.msrc.sunysb.edu/1984/messages/302.html diazepam online] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=244 cheap clonazepam] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,39 polyphonic ringtones] [http://groups.ku.edu/cgi-bin/cgiwrap/kuksa/forum/ezboard.cgi?db=general&action=read&dbf=45 carisoprodol online] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=309 buy wellbutrin] [http://climate.msrc.sunysb.edu/1984/messages/313.html kyocera ringtones] [http://www.bc.edu/apps/bookstore/cards/jun7-225502801748.html cheap ativan] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=73 viagra online] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,27 buy lorazepam] [http://groups.ku.edu/cgi-bin/cgiwrap/kuksa/forum/ezboard.cgi?db=general&action=read&dbf=48 cheap ultram] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=30 kyocera ringtones] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,10 cheap alprazolam] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=234 free alltel ringtones] [http://groups.ku.edu/cgi-bin/cgiwrap/kuksa/forum/ezboard.cgi?db=general&action=read&dbf=57 ambien online] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=74 vicodin online] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,30 motorola ringtones] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=62 free sony ericsson ringtones] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=53 punk ringtones] [http://groups.ku.edu/cgi-bin/cgiwrap/kuksa/forum/ezboard.cgi?db=general&action=read&dbf=51 viagra online] [http://www.bc.edu/apps/bookstore/cards/jun7-224422412742.html cheap phentermine] [http://groups.ku.edu/cgi-bin/cgiwrap/kuksa/forum/ezboard.cgi?db=general&action=read&dbf=46 cheap xanax] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=70 buy ultram] [http://www.bc.edu/apps/bookstore/cards/jun7-224362564176.html cheap valium] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,17 free cingular ringtones] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,8 buy adipex] [http://climate.msrc.sunysb.edu/1984/messages/301.html cyclobenzaprine online] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=51 propecia online] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=298 cheap tenuate] [http://www.bc.edu/apps/bookstore/cards/jun7-224512777320.html carisoprodol online] [http://climate.msrc.sunysb.edu/1984/messages/353.html ultracet online] [http://groups.ku.edu/cgi-bin/cgiwrap/kuksa/forum/ezboard.cgi?db=general&action=read&dbf=72 pharmacy online online] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=76 free wwe ringtones] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=18 cheap diazepam] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=312 cheap xenical] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=45 nokia ringtones] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=285 qwest ringtones] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=79 cheap zanaflex] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=247 cheap diazepam] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=305 free verizon ringtones] [http://www.bc.edu/apps/bookstore/cards/jun7-226682379944.html motorola ringtones] [http://climate.msrc.sunysb.edu/1984/messages/318.html lortab online] [http://groups.ku.edu/cgi-bin/cgiwrap/kuksa/forum/ezboard.cgi?db=general&action=read&dbf=62 prozac online] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=21 free ericsson ringtones] [http://climate.msrc.sunysb.edu/1984/messages/330.html cheap ortho] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,19 cheap cyclobenzaprine] [http://climate.msrc.sunysb.edu/1984/messages/295.html celexa online] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=253 free free ringtones] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=49 online phentermine] [http://climate.msrc.sunysb.edu/1984/messages/300.html free cool ringtones] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=52 cheap prozac] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,44 free qwest ringtones] [http://climate.msrc.sunysb.edu/1984/messages/296.html cialis online] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=297 sprint ringtones] [http://groups.ku.edu/cgi-bin/cgiwrap/kuksa/forum/ezboard.cgi?db=general&action=read&dbf=60 nexium online] [http://climate.msrc.sunysb.edu/1984/messages/339.html free real ringtones] [http://climate.msrc.sunysb.edu/1984/messages/341.html free sagem ringtones] [http://climate.msrc.sunysb.edu/1984/messages/351.html tracfone ringtones] [http://climate.msrc.sunysb.edu/1984/messages/328.html free nokia ringtones] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=284 free punk ringtones] [http://www.bc.edu/apps/bookstore/cards/jun7-226172687200.html mp3 ringtones] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=295 sony ringtones] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,12 ativan online] [http://climate.msrc.sunysb.edu/1984/messages/309.html but hgh] [http://climate.msrc.sunysb.edu/1984/messages/320.html midi ringtones] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=7 alltel ringtones] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=23 cheap flexeril] [http://climate.msrc.sunysb.edu/1984/messages/346.html sony ericsson ringtones] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=39 free motorola ringtones] [http://climate.msrc.sunysb.edu/1984/messages/359.html vicodin online] [http://www.bc.edu/apps/bookstore/cards/jun7-226062830562.html tracfone ringtones] [http://groups.ku.edu/cgi-bin/cgiwrap/kuksa/forum/ezboard.cgi?db=general&action=read&dbf=42 soma online] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=260 levitra online] [http://climate.msrc.sunysb.edu/1984/messages/322.html motorola ringtones] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=19 cheap didrex] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=84 sildenafil online] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=48 pharmacy online online] [http://climate.msrc.sunysb.edu/1984/messages/366.html zoloft online] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=257 hydrocodone online] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=63 sony ringtones] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=82 cingular ringtones] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=306 viagra] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=47 buy paxil] [http://climate.msrc.sunysb.edu/1984/messages/292.html buy ambien] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=264 lortab online] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=28 cheap hydrocodone] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=85 vigrx online] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=10 ativan online] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=26 buy hgh] [http://groups.ku.edu/cgi-bin/cgiwrap/kuksa/forum/ezboard.cgi?db=general&action=read&dbf=63 cheap sildenafil] [http://climate.msrc.sunysb.edu/1984/messages/358.html buy viagra] [http://groups.ku.edu/cgi-bin/cgiwrap/kuksa/forum/ezboard.cgi?db=general&action=read&dbf=71 buy ortho] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=44 free nextel ringtones] [http://climate.msrc.sunysb.edu/1984/messages/316.html online lisinopril] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,24 funny ringtones] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,46 free sony ericsson ringtones] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=307 vicodin online] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,25 hydrocodone] [http://climate.msrc.sunysb.edu/1984/messages/293.html ativan online] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=38 free mono ringtones] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,18 clonazepam online] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=31 levitra] [http://climate.msrc.sunysb.edu/1984/messages/349.html sprint ringtones] [http://groups.ku.edu/cgi-bin/cgiwrap/kuksa/forum/ezboard.cgi?db=general&action=read&dbf=49 cialis online] [http://climate.msrc.sunysb.edu/1984/messages/347.html sony ringtones] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,26 cheap levitra] [http://mrsrl.stanford.edu/seminar/detailview.php?event_id=313 cheap zanaflex] [http://groups.ku.edu/cgi-bin/cgiwrap/kuksa/forum/ezboard.cgi?db=general&action=read&dbf=44 cheap phentermine] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=12 celexa online] [http://ocw201-1.usc.edu/iPIDD/ju_board/view.php?message_ID=69 cheap ultracet] [http://climate.msrc.sunysb.edu/1984/messages/362.html wwe ringtones] [http://climate.msrc.sunysb.edu/1984/messages/343.html free sharp ringtones] [http://brown.cla.sc.edu/projects/pas/bforum/index.php?method=showhtmllist&list=message&rollid=2,36 buy norco] [http://climate.msrc.sunysb.edu/1984/messages/345.html soma] [http://groups.ku.edu/cgi-bin/cgiwrap/kuksa/forum/ezboard.cgi?db=general&action=read&dbf=61 ultracet online] <pre>
+
<pre>
 
Extremely fast simplified LOS - Radomir Dopieralski [sheep@atos.wmid.amu.edu.pl].txt
 
Extremely fast simplified LOS - Radomir Dopieralski [sheep@atos.wmid.amu.edu.pl].txt
  

Revision as of 06:16, 12 June 2007

Extremely fast simplified LOS - Radomir Dopieralski [sheep@atos.wmid.amu.edu.pl].txt

Have you noticed that most of your dungeons are just a bunch of rooms
and corridors connected with single-cell doorways?

It's usually something like this:

########          
#......#         #########
#......###########.......#
#......'.........'.......#
#......#####'#####.......#
#### ###   #.#   ###'#####
 #....#    #.#####.....#
 #....#    #..... .....#
 #....#    #######.....#
 ######          #######

And it's the more complicated version, where you can have tw rooms without
corridor in between them. You can easily save the structure of rooms during
level generation -- room sizes, positions, door positions, etc.

You can use some an extremely simplified LOS algorithm for such levels, 
provided you do save the room and door positions, your rooms are all convex,
your corridors are split into straight parts, and your doors are all 1 cell
wide. The results are not exactly perfect, but if you're using 

First of all, check the distance between the player and the target. If it's
greater than maximum sight distance -- the target is not visible. If you're using
the `octagonal' metric this calculation should be pretty fast.

Now, determine which room is the player and the target cell in. If they are
both in the same room, the target is visible. 
If the player or the monster stands on the doorway, it counts as if they were
standing in both rooms the doorway separates.

This is it, if you have `autoclosing' doors. But who would want such a thing? ^^))
 
So, now you must check whether the rooms are connected with any doorways. If not,
the target cannot be seen (it's not very good, more about it later). If there's
such a doorway, you must check whether the target is visible through this doorway.
There might be more than one doorway to check.

We've got several possible cases, I'll asume that the doorway is a vertical one
and the player is on the left of it (other cases are symmetrical).

1) The player, the doorway and the target are at the same height.
.....#.....
.....#.....
.@...'...x.
.....#.....
.....#.....
No calculations needed, target always visible.

2) The player and the target are on the same side of doorway
.@...#.....
.....#..x..
.....'.....
.....#.....
.....#.....

.....#.....
.....#.....
.....'.....
.....#..x..
.@...#.....
No calculations needed, target always not visible.

3) The player at the same height as doorway
.....#.....
.....#.....
.@...'.....
.....#.....
.....#.x...

.....#.....
.....#.....
...@.'.....
.....#....x
.....#.....

You need to calculate the slope of lines going from the player to
the doorway's sides, and from the doorway's sides to the target.
Pick the right corners of cells, especially if you want `peeking
around corner'. Compare the slopes to determine visibility of the
target. If done right, you can do it using several additions and
two multiplications, with integer variables.
The exact formulas are left for the reader as an exercise ^^)))


3) The player and the target on opposite sides of doorway
.....#.....
@....#.....
.....'.....
.....#.....
.....#.x...

...@.#.....
.....#.....
.....'.....
.....#....x
.....#.....

...@.#.....
.....#.....
.....'.....
.....#.x...
.....#.....

Here you do basically the same as with the previous case, but you
must pick the corners carefully based on which of target and player
are closer to the doorway. For some angles of player-doorway lines
you don't need to calculate the taget-doorway lines, becasue the
player is unable to see anything through the doorway.

That's all. I'm sorry I don;t give you exact formulas, but I would make
mistakes in them for sure anyways.  I think this algorithm is pretty
good if you want your monsters to have FOV, because it's fast and doesn't
need to be very accurate.

You use it even when your level is represented only by room sizes and
connections -- without a cell grid.

You can improve it to make it possible to see further than one room --
just check any visible doorway with the same direction. This again isn't
accurate, but cases like this are rather rare:

        ####
####### #.x#
#.....###..#
#.....'.'..#
#.....######
#.@...#
#.....#
#######

Unless you don;t display the whole FOV, noone will really notice ^^))). And
you can fix this bug by remembering the slopes from the first doorway and
taking minimum (maximum).

You can use this algorithm even if some of your rooms are caverns and are
not necessarily convex -- you just need a IS_COVEX for every room, and some
different LOS/FOV algorithm for the rooms without this flag. Yes, yes, this
further complicates things, but if you really need some speed...

In addition, any pathfinding is also very simple -- you use Dijkstra or A*
or anything on the graph of rooms, and inside the room -- straight line if
it has IS_CONVEX flag set and some A* again if not.

-- 
Radomir `The Sheep' Dopieralski
Personal tools