Need help to implement a Line-of-Sight algorithm for a roguelike in VB6

[vdweller]

Greetings,

I am an amateur programmer from Greece who is currently trying to develop a roguelike resembling ADOM. I would like to implement an interesting algorithm that I found here:
http://www.geocities.com/temerra/los_rays.html
This is an algorithm about the Line of Sight (LOS) of the game entities, which means it calculates what an entity can and can't see (eg behind a column). It looks pretty fast and accurate, but alas it is poorly described in detail (especially towards the "end" of the algorithm) and the JAVA code link doesn't work any more.

I could really use some help, either with a piece of code with the above algorithm, or further explanation with steps on precisely what it does.

For those of you who have read the article: I actually understand what happens in diagrams a, b and c of the article, but I can't figure out how things evolve later, eg when and where a "pink obstruction" stops. Can it be when the x or y coord of the obstruction vector becomes less than zero? Anyway some VB code always helps!

Thank you in advance,
vdweller
http://vdweller.awardspace.com

[Brigand]

I'm programming my roguelike in VB as well, and struggled with an effective LOS algorithm as you are. I eventually came to 2 conclusions that had a huge impact on program performance:

Conclusion 1) The algorithm - I beat myself to death on how to implement this for a long time. I browsed a bunch of sites that descrbed how they implemented it,  including the files at roguebasin and dungeondweller, and pleaded (pled?? /shrug) for help at rgrd,. After several false starts, I initially settled on a rather elegant (at least to me) piece of code with calculated line of sight in a spiral out from the player. However.... this tended to actually NOT be the fastest way to do it, and it had the side effect of calculating some squares rather questionably at long distances. So, I tried other methods, including ray casting, and a weird flood-fill one. In the end, I chose a brute force method, which, while laughable looking at it in the code, actually improved my performance considerably at the cost of having to use bulkier (but faster) code.

What I did was simply divide the players field of view up into 8 octants (or 4 quarters if you're so inclined), and hard-code the view algorithm in that little piece of the pie for each square. Checking LOS on the other octants was simply a matter of flipping the sign on one of the coordinates. And it ended up working wonderfully. I was quite pleased with it.

I am far from an expert programmer (I even stress the definition of intermediate), but if I have learned 1 thing, it's that having an elegant, optimized algorithm is not always the best way to do something. I started this program wanting it to be compact, beautiful code, with no chunks of if-then blocks repeating when a single algorithm would work. Sometimes, brute force code can produce a better result - brute force code ensures you get exactly what you want, whereas an algortihm saves you coding work, but may not work exactly as you like in all cases.


Conclusion 2) I don't know how 'realistic' you want your code to be, but I made one other decision that DRASTICALLY affected performance. ONLY calculate LOS for the player, unless you are trying to create a pretty advanced AI for your monsters. Let's face it...the old saying 'If I can't see you, then you can't see me' holds very true for a game which is represented in a rather coarse, non-granular grid format. If I can't see that goblin behind a piller, then he can't see me either, so there is absolutely NO need to recalculate LOS on that monster.

I did actually start calculating LOS on every single creature in the game on every turn that passed. Performance was abyssmal. I reduced it only to 'active/awake' creature. Performance improved, but was still pretty bad. In addition, I ran into problems with creatures simply not responding when you came into sight. Tried to work around it with an altered algorithm which only calculated LOS on creatures within a certain distance of the player (yet another calculation). This was more realistic, but I ended up with monsters which 'went to sleep' when they left range.

In the end, I simply calculate 1 LOS for the player, and MAYBE 1 for each of the players pets/allies. It exponentially improves performance, and ranged combat works absolutely fine.

Your mileage will vary on these ideas, and I am probably regurgitating what every good programmer on this site already knows (and there seem to be a lot of good programmers here), but they are 2 of the bigger problems I faced and eventually overcame. If you are going for absolute realism (well, as realistic as a fantasy/sci-fi game can be), then my ideas are pretty much useless to you.

Sorry so long winded. I'm on lunch break and reading some forums for some ideas myself, and thought I'd drop a thing or 2 I've learned during my programming crash-course!

Brigand

[Brigand]

Oh, and if you are interested in what I came up with (keep in mind I'm an amateur too, so be gentle!!), this is a cut/paste of the entirety of my Line-of-sight code:


variables:
intCurrentX and intCurrentY are the players current coordinates
intCurrentVisualRange is the distance you can see (as a radius)

I have a function called (Passable(X1, Y1) as Boolean) which simple returns True/False based on whether you can see/move through the square or not, and I also wrote a little distance calculating function (Distance(X1, Y1, X2, Y2) as single).

I try to keep my code fairly readable, as being an amateur I often have to refigure my logic months later when I am changing something.

    'LINE OF SIGHT
   
    'first, show everything in the light radius (and later subtract out what can't be seen)
    For intXCounter = (intCurrentX - intCurrentVisualRange) To (intCurrentX + intCurrentVisualRange)
        For intYCounter = (intCurrentY - intCurrentVisualRange) To (intCurrentY + intCurrentVisualRange)
            'make sure you don't calcualte off the edge of the map
            If (intXCounter > 0) And (intXCounter < MAX_MAP_DIMENSION + 1) And (intYCounter > 0) And (intYCounter < MAX_MAP_DIMENSION + 1) Then
                If Distance(intCurrentX, intCurrentY, intXCounter, intYCounter) < intCurrentVisualRange Then
                    With Tile(intCurrentLevel, intXCounter, intYCounter)
                        If .TileType <> STONE Then .Visible = True
                    End With
                End If
            End If
        Next intYCounter
    Next intXCounter



    'next, blank out squares which are blocked by .Passable = false tiles
    'the 8 tiles nearest the player are always visible, so don't change them


            For intCounter = 1 To intCurrentVisualRange
                For intSectionCounter = 0 To intCounter

                        If Tile(intCurrentLevel, intCurrentX + intCounter, intCurrentY + intSectionCounter).Passable = False Or Tile(intCurrentLevel, intCurrentX + intCounter, intCurrentY + intSectionCounter).Visible = False Then
                            If intSectionCounter <> intCounter Or intCounter = 1 Then Tile(intCurrentLevel, intCurrentX + intCounter + 1, intCurrentY + intSectionCounter).Visible = False
                            If intSectionCounter > 0 Then Tile(intCurrentLevel, intCurrentX + intCounter + 1, intCurrentY + intSectionCounter + 1).Visible = False
                        End If
                       
                        If Tile(intCurrentLevel, intCurrentX - intCounter, intCurrentY + intSectionCounter).Passable = False Or Tile(intCurrentLevel, intCurrentX - intCounter, intCurrentY + intSectionCounter).Visible = False Then
                            If intSectionCounter <> intCounter Or intCounter = 1 Then Tile(intCurrentLevel, intCurrentX - intCounter - 1, intCurrentY + intSectionCounter).Visible = False
                            If intSectionCounter > 0 Then Tile(intCurrentLevel, intCurrentX - intCounter - 1, intCurrentY + intSectionCounter + 1).Visible = False
                        End If
                       
                        If Tile(intCurrentLevel, intCurrentX + intCounter, intCurrentY - intSectionCounter).Passable = False Or Tile(intCurrentLevel, intCurrentX + intCounter, intCurrentY - intSectionCounter).Visible = False Then
                            If intSectionCounter <> intCounter Or intCounter = 1 Then Tile(intCurrentLevel, intCurrentX + intCounter + 1, intCurrentY - intSectionCounter).Visible = False
                            If intSectionCounter > 0 Then Tile(intCurrentLevel, intCurrentX + intCounter + 1, intCurrentY - intSectionCounter - 1).Visible = False
                        End If
                       
                        If Tile(intCurrentLevel, intCurrentX - intCounter, intCurrentY - intSectionCounter).Passable = False Or Tile(intCurrentLevel, intCurrentX - intCounter, intCurrentY - intSectionCounter).Visible = False Then
                            If intSectionCounter <> intCounter Or intCounter = 1 Then Tile(intCurrentLevel, intCurrentX - intCounter - 1, intCurrentY - intSectionCounter).Visible = False
                            If intSectionCounter > 0 Then Tile(intCurrentLevel, intCurrentX - intCounter - 1, intCurrentY - intSectionCounter - 1).Visible = False
                        End If


                        If Tile(intCurrentLevel, intCurrentX + intSectionCounter, intCurrentY + intCounter).Passable = False Or Tile(intCurrentLevel, intCurrentX + intSectionCounter, intCurrentY + intCounter).Visible = False Then
                            If intSectionCounter <> intCounter Or intCounter = 1 Then Tile(intCurrentLevel, intCurrentX + intSectionCounter, intCurrentY + intCounter + 1).Visible = False
                            If intSectionCounter > 0 Then Tile(intCurrentLevel, intCurrentX + intSectionCounter + 1, intCurrentY + intCounter + 1).Visible = False
                        End If
                       
                        If Tile(intCurrentLevel, intCurrentX - intSectionCounter, intCurrentY + intCounter).Passable = False Or Tile(intCurrentLevel, intCurrentX - intSectionCounter, intCurrentY + intCounter).Visible = False Then
                            If intSectionCounter <> intCounter Or intCounter = 1 Then Tile(intCurrentLevel, intCurrentX - intSectionCounter, intCurrentY + intCounter + 1).Visible = False
                            If intSectionCounter > 0 Then Tile(intCurrentLevel, intCurrentX - intSectionCounter - 1, intCurrentY + intCounter + 1).Visible = False
                        End If
                       
                        If Tile(intCurrentLevel, intCurrentX + intSectionCounter, intCurrentY - intCounter).Passable = False Or Tile(intCurrentLevel, intCurrentX + intSectionCounter, intCurrentY - intCounter).Visible = False Then
                            If intSectionCounter <> intCounter Or intCounter = 1 Then Tile(intCurrentLevel, intCurrentX + intSectionCounter, intCurrentY - intCounter - 1).Visible = False
                            If intSectionCounter > 0 Then Tile(intCurrentLevel, intCurrentX + intSectionCounter + 1, intCurrentY - intCounter - 1).Visible = False
                        End If
                       
                        If Tile(intCurrentLevel, intCurrentX - intSectionCounter, intCurrentY - intCounter).Passable = False Or Tile(intCurrentLevel, intCurrentX - intSectionCounter, intCurrentY - intCounter).Visible = False Then
                            If intSectionCounter <> intCounter Or intCounter = 1 Then Tile(intCurrentLevel, intCurrentX - intSectionCounter, intCurrentY - intCounter - 1).Visible = False
                            If intSectionCounter > 0 Then Tile(intCurrentLevel, intCurrentX - intSectionCounter - 1, intCurrentY - intCounter - 1).Visible = False
                        End If
                       
                       
                Next intSectionCounter
            Next intCounter





And that's it. As you can see, I make everything in the view radius visible first, and then blank out blocked squares manually. For small view radii (under 10), it works great. Larger radii seem to produce some anomalies due to me forcing 45 degree checks on light from each square. (My code doesn't look at shallower angles and block vision if a tiny piece of a blocked square impedes vision.)  It's a bit bulky and brute force, and not flexible at all, but it works.  I wish I was good enough to come up with something small and efficient, but for my skill level I am happy.
   

[zzo38]

Here is a different line-of-sight algorithm, in QBASIC instead of VB (QBASIC is a bit similar to VB):

Code: [Select]

SUB LineOfSight (s(), si(), BYVAL dx, BYVAL dy)
 counter = 0: i = 0: e = 0: x = 0: y = 0
 steep = (dy > dx)
 IF steep THEN SWAP dy, dx
 e = 2 * dy - dx
 FOR i = 0 TO dx - 1
  IF steep THEN
   si(y, x) = -1
   IF s(y, x) THEN EXIT SUB
  ELSE
   si(x, y) = -1
   IF s(x, y) THEN EXIT SUB
  END IF
  WHILE e >= 0
   y = y + 1: e = e - 2 * dx
  WEND
  x = x + 1: e = e + 2 * dy
 NEXT i
END SUB

SUB PlayerSightQ (BYVAL rd, BYVAL cd)
 DIM s(0 TO 7, 0 TO 7), si(0 TO 7, 0 TO 7)
 pr = MapData.row: pc = MapData.col
 FOR r = 0 TO 7
  FOR c = 0 TO 7
   mr = pr + r * rd: mc = pc + c * cd
   IF mr >= 1 AND mr <= 22 AND mc >= 1 AND mc <= 60 AND r + c > 0 THEN
    dark = ASC(MID$(MapData.floor(mr, mc), 2)) AND 16
    j = ASC(MapData.floor(mr, mc))
    s(r, c) = (j = 10 OR j = 178)
    IF dark <> 0 AND r + c <> 0 THEN s(r, c) = -1
   END IF
  NEXT c
 NEXT r
 FOR i = 0 TO 7
  LineOfSight s(), si(), 7, i
  LineOfSight s(), si(), i, 7
 NEXT i
 FOR r = 0 TO 7
  FOR c = 0 TO 7
   mr = pr + r * rd: mc = pc + c * cd
   IF mr >= 1 AND mr <= 22 AND mc >= 1 AND mc <= 60 THEN
    dist = r * r + c * c
    IF si(r, c) AND dist < 49 THEN DrawSquare mr, mc
   END IF
  NEXT c
 NEXT r
END SUBYou have to call PlayerSightQ for each quadrant, and then it will calculate which squares are visible in that quadrant.

It is possible to use this one instead if you want to. It does work OK, I have test it.

[vdweller]

@ Brigand:

When you say that the algorithm hindered your performance, how many milliseconds it took to operate? With what sight range? On what system?

I managed to make a simple LOS program. On a P2.3 Ghz it takes a whopping 50 milliseconds to expand to a sight radius of ~20 in totally open space, and this time drops by a lot when many obstacles are placed around the entity (ie if the player is in a corridor)-say about 10 milliseconds.

I used a pre-computed line set (70 KB) which loads into an array, and also some *cough* *cough* graphic operations.

Jeez, in a map with 30 monsters it would take forever to LOS each and every one of them, so I'm probably taking your advice for the NPC's sight capabilities. That is, unless I figure out how the hell the algorithm in my first post works 

Here's the program (source and .exe) - 48 KB:

http://www.mediafire.com/?njgytjmtgkm

PS You think of yourself as being far from an expert, eh? What about taking a look at my code. Or taking a look at the code of every complete game I've written. I'm still trying to figure out why they work 

PS2 Oh and single obstructions aren't treated nicely in my program:

Not that I planned to use any single obstructions, though.

[zzo38]

This is a better way of dealing with darkness than the above PlayerSightQ codes:

Code: [Select]

SUB PlayerSightQ (BYVAL rd, BYVAL cd)
 DIM s(0 TO 7, 0 TO 7), si(0 TO 7, 0 TO 7)
 pr = MapData.row: pc = MapData.col
 FOR r = 0 TO 7
  FOR c = 0 TO 7
   mr = pr + r * rd: mc = pc + c * cd
   IF mr >= 1 AND mr <= 22 AND mc >= 1 AND mc <= 60 AND r + c > 0 THEN
    j = ASC(MapData.floor(mr, mc))
    s(r, c) = (j = 10 OR j = 178)
   END IF
  NEXT c
 NEXT r
 FOR i = 0 TO 7
  LineOfSight s(), si(), 7, i
  LineOfSight s(), si(), i, 7
 NEXT i
 FOR r = 0 TO 7
  FOR c = 0 TO 7
   mr = pr + r * rd: mc = pc + c * cd
   IF mr >= 1 AND mr <= 22 AND mc >= 1 AND mc <= 60 THEN
    dark = ASC(MID$(MapData.floor(mr, mc), 2)) AND 16
    dist = r * r + c * c
    IF dark <> 0 AND dist > 3 THEN
     IF ASC(MapData.floor(mr, mc)) <> 250 THEN
      dark1 = ASC(MID$(MapData.floor(mr - rd, mc), 2)) AND 16
      dark2 = ASC(MID$(MapData.floor(mr, mc - cd), 2)) AND 16
      IF (dark1 AND dark2) <> 0 THEN si(r, c) = 0
     ELSE
      si(r, c) = 0
     END IF
    END IF
    IF si(r, c) AND dist < 49 THEN DrawSquare mr, mc
   END IF
  NEXT c
 NEXT r
END SUB

[BirdofPrey]

Greetings,

I am an amateur programmer from Greece who is currently trying to develop a roguelike resembling ADOM. I would like to implement an interesting algorithm that I found here:
http://www.geocities.com/temerra/los_rays.html
This is an algorithm about the Line of Sight (LOS) of the game entities, which means it calculates what an entity can and can't see (eg behind a column). It looks pretty fast and accurate, but alas it is poorly described in detail (especially towards the "end" of the algorithm) and the JAVA code link doesn't work any more.

I could really use some help, either with a piece of code with the above algorithm, or further explanation with steps on precisely what it does.

For those of you who have read the article: I actually understand what happens in diagrams a, b and c of the article, but I can't figure out how things evolve later, eg when and where a "pink obstruction" stops. Can it be when the x or y coord of the obstruction vector becomes less than zero? Anyway some VB code always helps!

Thank you in advance,
vdweller
http://vdweller.awardspace.com

Hey there! (first post!  ) I've been developing a roguelike of my own for the past couple of months, and I just recently made it over this hump. I actually used the same algorithm you're attempting to use, so maybe I can be of help!

I originally posted about it in my own little development diary thread here, but since that post is somewhat out of context and the code I uploaded is c++ I'll just give a general summary of how I got that shit to work.

Seeing that his Java implementation was a broken link, I googled for the file and found that someone had saved a version, so I downloaded that and attempted to use it. Unfortunately, it didn't work for me at all. Basically, he had made it much more complicated than it needed to be.

Here is the way he had it: When a checked node is found to be an obstruction, its 'obstruction' information is filled with the coordinate of the tile relative to the source. (i.e. if an obstruction is found 2 tiles down and 1 tile to the right, its obstruction data would be (1, 2)). Note that there is no need to remember which direction it is in, so you can use the absolute values of the coordinates.
Here's where things got unnecessarily tricky. His 'error data' was also a coordinate, and when an obstruction was found he would set that information equal to the obstruction data. Then he used some overly complicated, completely unintuitive system for adjusting the error data as the ray spread outward, and an equally unintuitive method for determining whether a node's error data classified the tile as obscured or not.

The way I ended up doing it is much easier. Instead of having the error data be a coordinate, I made it into a single integer. If the integer was positive, it meant the shadow cast by the obstruction was further along on the x-axis. If negative it meant it was further along on the y-axis.

So for a concrete example, let's say you're searching outwards and you find an obstruction on (3, 2). We fill the obstruction data of that node with (3, 2), and we set the error data to 0. an error data of 0 means that the current tile is directly in the shadow of the obstruction (or in this case, it is the obstruction itself).
When you later spread out rays from that point when expanding the perimeter, you're going to be creating 2 search nodes from that point, (4, 2) and (3, 3). The horizontal node, (4, 2), will have the same obstruction data, but the error data will have obstructionY subracted from it, making its error data -2. The vertical node, (3, 3), will similarly have the same obstruction data, but with obstructionX added to it, making its error data 3.

Now to check at the end whether a certain tile is obscured or not, just check its error data. The closer the error data is to 0, the more obscured it is. My program currently only classifies a tile as obscure if its error data is 0. While it works perfectly find for enclosed spaces and walls, I suspect it may cause some oddities in the case of a single obstruction. There are ways around that though, either by increasing the range that marks a tile as obscure, or other workarounds.

Anyway, I have no idea if any of this is helpful at all to you, or if it even came close to answering your questions, but it's almost 4 AM over here and I'm barely coherent in the first place. If you need more explanation (and you probably will ), just let me know.

[vdweller]

@Birdofprey:

Great post! I will study your code (although I don't know sh** about C++). Also one remark about why this guy you're talking about used 2 coords for representing error data: In another forum/usenet/whatever he mentioned that error data could just as easily be an integer, positive or negative, just as you did, but he wanted his algorithm to be more "ready" for representing LOS in a 3D environment, hence the 2 coords (not that I actually understand why).

Anyway, back to my algorithm, after some more optimizations, i managed to make it really fast (30 repetitions in 120 milliseconds on a P2.4 GHz is quite good for a LOS of 20), but I discovered a severe inconsistency on what is seen ahead eg. in a narrow corridor:

If you notice what's happening on the far right wall at the end of the corridor,and the adjacent floor tiles, well...it's bad. So I guess I'm going for something else, like the method you used. I'll notify you for any problems I encounter 

[BirdofPrey]

Haha! That is an odd problem! I just reread your original post, and basically realized I didn't answer your question very well at all.

I'm not sure exactly what you mean by asking "when and where a pink obstruction stops", but maybe this'll help:

Most of the search nodes that are being created have 2 inputs - an input from the x side and an input from the y side. The exceptions are any nodes created on the horizontal/vertical lines from the source, which will only have one input, but the same rules apply to all of them.

Here are the rules I used for determining how the information is passed on:

If the new node only has a single input, if that single input is obscured itself, we can 'cut' the new one. Cutting it means we don't add it to the list of nodes to check. This is the part of the code that makes it run more efficiently the more obstructions there are.
Example - node (3, 0) is an obstruction. When we create new nodes from that one, when we check (4, 0) we see that it only has one input (from the x direction), and we see that that single input is obscured, so we cut (4, 0), and no nodes are created from it.

If the new node has 2 inputs, if both of the inputs are obscure we can also cut the new tile. It is important to note here that if you do this by the book, your character will not be able to see through diagonal spaces. You can work around this by checking the diagonal space of the new tile. If that is also obscured,  you can cut the new one, but otherwise don't.

If we find that the new node is not cut, that is the time that we'll copy any data over and check the tile itself for obstructions, and then add it to the list of nodes to expand from.


Another bit of info you might find useful is when to stop copying obstruction and error data. Remember how if you're moving horizontally from an obstruction, you subtract from it? Well, if the error data of the node is already negative, if you move horizontally from that space there is no need to make it more negative, since it is obvious that the point is not going to be obscured, so in that case you simply don't copy over the obstruction and error data. You would do the same thing when moving vertically from a node that already has positive error data.

Again, let me know if you could use any more assistance. I was completely enamored with this algorithm when I saw it, but implementing it so it worked was definitely the hardest thing I've had to do in development so far.

[vdweller]

Well, during the weekend, I did some work with the algorithm in VB. Here are some images from what I've managed to do. The squares display the error data (ignore the 100's-it's the error data for an empty node with no obstruction data).




I didn't write any "cut nodes" code and any "obstruction data propagation stoppage" code. So, this far, is what is displayed by any means correct? What I did is the following:

1) Expand the perimeter.
2) For a given perimeter, check the obstruction nodes first and give data to adjacent nodes
3) Then expand the perimeter with the no-obstruction nodes.

NO node data overwriting occurs. When a node B is created from node A, only node A is responsible for giving data to node B, and no other node ever interferes with node B. This is why I am checking obstruction nodes first: If obstruction node at (3,3) can create 2 nodes with obstruction data at (2,3) and (3,4), the (2,3) node may already have been spawned by the "free" node of (2,4) first, and no obstruction data will be passed this way.

So for node (5,6) which is an obstruction, the obstructionX/obstructionY/error data is:

Node (5,6): (5,6) , error:0

And for node (4,6):

Node (4,6): (5,6) , error:-6

And for node (3,6):

Node (3,6): (5,6) , error:-12

And so on. So far, I don't see anything like "if a node's error data is ><=X then the node is obscure" which can be applied universally. For obstructions on the left/right side of the map, if the error is negative, then a shadow is SOMEWHAT correctly applied. THe same goes for obstructions on the upper/lower side of the map with positive error data. But I suspect this is not the way you did it, and surely isn't accurate as of now.

[BirdofPrey]

What you have right now seems to be workable in the case of a single obstruction, but the data you have isn't making that much sense for large blocks of obstructions. The thing is, the real strength of the code is in its ability to exclude (cut) nodes from being expanded. That's the part of the code that makes it extremely efficient in that it doesn't check nodes that it knows are out of the picture, and this exclusion makes a natural shadow almost as a side-effect. In order to have the ability to know when to cut nodes, however, you need to take into account both inputs.

edit - On a side-note, I'm still trying to figure out a better way to determine if a tile is obscure or not than just (errordata == 0). I think any definite range isn't going to work very well. The range needs to increase depending on how far away the obstruction is. I'll definitely post it here when I track it down.

[vdweller]

Given the error data in my calculations, I fail to see how cut nodes will transform those values into something which resembles a true shadow cast behind an obstruction. And this data in my algorithm just don't work precisely even for a single obstruction.

For example, in my attachment, the blue node creates the 2 yellow nodes, which are both negative. If I cut the blue node, what do I gain?

Well, I'm disappointed. I'd better forget 1 year of work on my game and study some Quantum Mechanics for my exams. I suspect this is easier than any LOS algorithm.

[BirdofPrey]

Given the error data in my calculations, I fail to see how cut nodes will transform those values into something which resembles a true shadow cast behind an obstruction. And this data in my algorithm just don't work precisely even for a single obstruction.

For example, in my attachment, the blue node creates the 2 yellow nodes, which are both negative. If I cut the blue node, what do I gain?

Well, I'm disappointed. I'd better forget 1 year of work on my game and study some Quantum Mechanics for my exams. I suspect this is easier than any LOS algorithm.

You've got it backwards. It's not that if the two nodes that the blue node creates are obscure, the blue node is cut. The idea is that if both the horizontal input and the vertical input to the blue node are obscure, you can cut the blue node. That would be the node below and to the right of the blue node.
And the point of cutting nodes is not to create errordata that will make sense. The point is that if you cut a node, no data is passed on at all. The node is not added to the next perimeter to check. Because of this a shadow will naturally be cast.

I definitely understand your frustration though. The drawback of its efficiency is that it's really hard to understand and implement properly. You could definitely get away with a less efficient but far easier FoV system for your roguelike. In fact, I think most of them do. You may have to make a few concessions though, like not calculating the FoV for every monster for every turn, as discussed earlier in the thread.

[vdweller]

Hmmm...it seems like I need to study more about the order of what does what in this algorithm.

In the meanwhile, I toyed with a Recursive Shadowcasting FOV, found here:
http://roguebasin.roguelikedevelopment.org/index.php?title=FOV_using_recursive_shadowcasting_-_improved
which works alright, but has 1 major flaw which I don't know how to fix yet:

As you can see in the attachment (only the 1st octant is processed), behind a single obstruction, at some specific spots, the "shadow" line is not consistent. So behind eg. a pillar, other tiles are visible while others are not. This happens especially when the obstruction tile approaches the y-axis. The code (for the 1st octant only) is:

Code: [Select]

Public Sub RecursiveVisibility(px As Single, py As Single, oct As Long, depth As Long, slopeA As Single, slopeB As Single)
Dim mw As Long
mw = range ^ 2
Dim x As Single, y As Single

Select Case oct

Case 1:
      y = py - depth
      x = Int(px - slopeA * depth)

Do While GetSlopeStd(x, y, px, py) >= slopeB

If GetVisDistance(x, y, px, py) <= mw Then
    If room(x, y) = 1 Then
        If room(x - 1, y) = 0 Then RecursiveVisibility px, py, 1, depth + 1, slopeA, GetSlopeStd(x - 0.5, y + 0.5, px, py)
    Else
        If room(x - 1, y) = 1 Then slopeA = GetSlopeStd(x - 0.5, y - 0.5, px, py)
    End If
vismap(x, y) = 1
End If
x = x + 1
Loop
x = x - 1

End Select

If depth < range And room(x, y) = 0 Then
RecursiveVisibility startx, starty, oct, depth + 1, slopeA, slopeB
End If


End Sub
Are there any workarounds for these "blind spots" behind single obstructions?

Or, an even better question: Is this "flaw" important? How many roguelikes have been out there having these kind of issues and yet being fun as hell?