The New Line of Sight Thread - A Proposal

Non-bug comments, suggestions, and feature requests for BRPG and/or BGE
Post Reply
Balesir
General
Posts: 302
Joined: Sat Mar 25, 2006 2:29 pm

The New Line of Sight Thread - A Proposal

Post by Balesir » Tue Feb 06, 2007 9:17 am

So, how should the Fog of War Line of Sight feature work? Well, here's my vision of it; it's been a while since it was discussed so let's see if this kick-starts something.

First of all some concepts:
  • - a 'space' can be either a grid cell or a single pixel; the same rules apply to any space but what constitutes a 'space' depends on the grid type and whether 'snap to grid' is on or not. If snap to grid is on, a 'space' is one grid cell (square or hex). If snap to grid is off a space is one pixel.

    - a 'light source' is a point from which light is defined to issue. I suggest it could be either the centre or a corner of a figure or object base.

    - an 'observer' is a figure that gives its owner visibility of the game map.

    - a 'line of sight' is traced from an observer, a 'line of light' is traced from a light source. Lines of light determine whether a space is 'lit' or not - lines of sight determine whether an observer can see a space or not.

    - 'light' can be full or dim; a space is either 'lit', 'dimly lit' or 'unlit'.

    - a 'block' is a vector line that does not let lines of sight or lines of light pass. Optionally, a block might also apply to figures - i.e. figures may not move accross the line. A block goes from one space corner to another; in the case of spaces that are pixels, which corner is irrelevant...
Now what happens in outline is this:

Instead of assigning cells that are masked, the GM draws out the blocks for a particular map. If snap to grid is engaged, the blocks can run only from one cell corner to another (adjacent?) cell corner. Without snap to grid they just run from any one pixel to another. Individual blocks may be removed/deleted to allow for doors opening, etc.

As an additional enhancement (not essential but nice), objects could be defined as 'opaque' - this just means they have blocks defined for within them.

Rules are now applied for lines of light as follows:
  • If a space has at least half of its corners touched by a line of light at full light range, it is fully lit.

    If a space has any one corner touched by a line of light at full strength it is dimly lit.

    If a space has at least half its corners touched by a line of light at dim strength it is dimly lit.

    All other spaces are unlit.
To be valid a line of light must not touch a block at any point along its length. It is traced from the point of the light source to the space corners of the space being assessed for lighting.

Similar (but simpler) rules are now applied to lines of sight:
  • Any space that has at least one corner touched by a valid line of sight is visible to the observer with the applicable light level.

    Any other space is not visible to the observer.
To be valid, a line of sight must run from any one corner of the observer's base to the space corner being assessed without touching a block at any point along its path.

Lines of light and lines of sight obviously have to be separately assessed for each observer, which will increase processing load, but I suggest that the determination only need be done when a light source or a relevant observer (i.e. an observer 'owned' by the local client) moves.

Mixing observers with low-light (light range multiplying) vision or 'darkvision' and normal vision on the same client will be tricky - probably all light ranges would have to multiplied, regardless of which observer has line of sight (which is what happens now with light sources, in effect) - but for single figure clients it would work fine. A figure with 'darkvision' calculates line of sight as normal, but treats all spaces within the darkvision range as 'lit' regardless of their actual status.

Not knowing how the current coding works I have no real idea how much of a change this would entail, but this is functionally how I think it should work. Comments?
Balesir

User avatar
heruca
Developer
Posts: 9384
Joined: Sun Nov 20, 2005 11:58 pm
Location: Buenos Aires, Argentina
Contact:

Post by heruca » Tue Feb 06, 2007 1:59 pm

::runs away screaming::

Heheh, just kidding. It's a good post, and illustrates the complexity of the problem.

I'll tell you right now, though, there is NO WAY I'm going to be polling LOS from each observer point to every single pixel on a map. The performance hit would make it unusable. Just think, for one observer, you would need to test LOS to 5,953,599 other pixels! (assuming maps don't get larger than 2440 x 2440 pixels, which they will) Then repeat the process for every other figure on the map. What's that? You say you have 100 figures deployed? OK, come back in 10 days to see the updated FoW. :lol:

Handling LOS via cell-based polling is a completely different matter, though, and is well in the realm of possibility.
:arrow: Please help spread the word about BRPG and BGE, and never hesitate to tell me how I can make them better suit your gaming needs.

User avatar
Helizar
Sergeant
Posts: 41
Joined: Sat Jan 20, 2007 9:36 pm

Post by Helizar » Tue Feb 06, 2007 3:52 pm

heruca wrote:::runs away screaming::
LOL! My thoughts exactly. I thought there was going to be a physics discussion about light refraction in a minute. One of the things I like about Battlegrounds is it's simplicity. I looked at the other commercial products and didn't like the complexity of some of them. Battlegrounds is nice and simple, quick to use and universal, and much more 'artistic' when other programs like Dunjinni are used. I want to be able to just whip up a map in 2 seconds, export it into Battlegrounds, throw some figs on it, and play. Personally, I'm happy with the FoW as it is. It serves my purpose.

User avatar
Omnidon
Site Admin
Posts: 2186
Joined: Mon Feb 06, 2006 7:46 pm
Location: NY State, USA
Contact:

Post by Omnidon » Wed Feb 07, 2007 3:59 am

heruca wrote:I'll tell you right now, though, there is NO WAY I'm going to be polling LOS from each observer point to every single pixel on a map.
It actually isn't necessary to do that. Balesir's description was written with an additional feature in mind, and that was shadows. Shadows are a relatively new feature in software, and are not necessary for LoS.

It's called a Line of Sight because it's two dimensional, not three. You don't need to calculate it for every pixel. If you don't try to implement shadowing, then all you need to do is use vectors to determine the SHAPE of the visible area.

It is easiest to demonstrate LoS with a picture, since it's actually a rather intuitive concept.

Let's start with a lightsource, a torch (yellow star) casting a 15 foot radius of light, and a cornered wall (black).

Image

The translucent yellow area is the range of the light cast by the torch in this example.

Of course, light shouldn't be passing through our wall. So next we need to figure out what area is really receiving light. We do this by drawing lines between the light and each *end* of the wall, which is what Balesir meant by "Lines of Light".
And because we're using vectors, this cornered wall actually consists of two separate "Blocks".

Image

Image

Any Space that falls within that angle beyond the point where the lines intersect the wall is dark.

By combining the two images and removing the light from any area that is not lit in BOTH cases, we can determine what Space really is lit.

Image

Now that we've finished with Lines of Light (which is just a step up from the current FoW feature), we can move on to Line of Sight. Let's add three characters, named Green, Blue and Red.

Image

Once again, we draw lines, but this time from each character to each end of the wall.

Needless to say, both Red and Blue can see the entire lit area, but neither can see Green.

Thus I will use Green for the following example, since he has a fairly limited field of view. He can see Blue, but can see neither himself nor Red.

Image

As this demonstrates, LoS is not only feasible, but not all that processor intensive.

LoS could even be used for outdoor maps, where there is light everywhere. Simply skip the Line of Light step and darken any area that is not within the player character's line of sight.
Last edited by Omnidon on Wed Feb 07, 2007 4:16 am, edited 2 times in total.

User avatar
heruca
Developer
Posts: 9384
Joined: Sun Nov 20, 2005 11:58 pm
Location: Buenos Aires, Argentina
Contact:

Post by heruca » Wed Feb 07, 2007 4:15 am

Great explanation and diagrams. Thanks for taking the time, especially since I know you've got a lot of projects going on right now.

I'll need to think this over to see if there's any way I can use this method without scrapping the current FoW system entirely and having to start over from scratch.
:arrow: Please help spread the word about BRPG and BGE, and never hesitate to tell me how I can make them better suit your gaming needs.

Balesir
General
Posts: 302
Joined: Sat Mar 25, 2006 2:29 pm

Post by Balesir » Wed Feb 07, 2007 7:39 am

Thanks a million, Omnidon, for both providing the drawings I didn't have time to do in my lunchtime and describing a good algorithmic methodology for exactly the functional effect I was trying to describe! I should have said that what I had in mind was that some algorithmic method to exclude many/most calculations would be needed. Anything outside the radius of a light source, for example, will automatically be dark, so the 'edge defining' lines Omnidon describes for 'lines of light' need only be as long as the 'dim' light radius - etc., etc.

The beauty of this method is that for the user it's even simpler than what we have now (although the programming is more complex, of course). It has two very important (IMO) advantages over drawn FoW masks:
  • 1) It doesn't need to be drawn/redrawn as figures move around - it effectively redraws itself! This takes a lot of work off the GM.

    2) The unmasked area does not have to be the same for each figure - in fact, it rarely will be. Thus adversaries or isolated characters can be run without 'information bleed'. To run adversary parties, would you rather keep updating two different masks on the same map, or just have the system auto-calculate what each figure can see?
I imagine this functionality as a huge potential differentiator for BRPG; intuitive, easy to use and providing huge amounts of atmosphere and suspense in online games...
Balesir

User avatar
Omnidon
Site Admin
Posts: 2186
Joined: Mon Feb 06, 2006 7:46 pm
Location: NY State, USA
Contact:

Post by Omnidon » Wed Feb 07, 2007 9:17 am

So basically what Balesir wants in addition to what I described above is a feature that causes the light to gradually fade/dim as it moves further from the source.

That would definitely take more processor, but probably not as much as was at first thought, and would certainly look very nice. And, like all such features, it could have an on/off toggle for users with older computers.

Balesir
General
Posts: 302
Joined: Sat Mar 25, 2006 2:29 pm

Post by Balesir » Wed Feb 07, 2007 9:28 am

Er, no - although it would look cool... :twisted:

What I was thinking of was the full light/dim light double radius that is there already. My original post just had some 'rules' for determining, for grid cells, which ones are 'lit' and which are 'dimly lit'.
Balesir

User avatar
Helizar
Sergeant
Posts: 41
Joined: Sat Jan 20, 2007 9:36 pm

Post by Helizar » Wed Feb 07, 2007 12:07 pm

If heruca is able to make it work, and work good, I'm all for it. But from a customer standpoint, I want the program usable and reliable. Those are high marks for me. I don't want something that will take me a lot of preparation just for LoS. LoS is not high on my list, and with the FoW now, I'm happy. Please keep it user friendly and reliable. That's all I want. Thanks much.

trevor
Sergeant
Posts: 37
Joined: Wed Feb 07, 2007 12:36 pm
Contact:

Post by trevor » Wed Feb 07, 2007 4:27 pm

This is definitely a workable solution. It's how MapTool does it's light blocking layer (lbl). You can see the result of the culling in this way looks like in some screencaps here:

http://forums.rptools.net/viewtopic.php?p=14834#14834

about half way down, the white outline shows the current token's visible area (it actually looks more impressive from the player's perspective when the fog is visible)

Does Director have built in geometry functions to do this kind of thing or would you have to write your own ?

User avatar
heruca
Developer
Posts: 9384
Joined: Sun Nov 20, 2005 11:58 pm
Location: Buenos Aires, Argentina
Contact:

Post by heruca » Wed Feb 07, 2007 9:14 pm

trevor wrote:Does Director have built in geometry functions to do this kind of thing or would you have to write your own ?
Not built in, I'm afraid. At least not that I'm aware of.
:arrow: Please help spread the word about BRPG and BGE, and never hesitate to tell me how I can make them better suit your gaming needs.

Balesir
General
Posts: 302
Joined: Sat Mar 25, 2006 2:29 pm

Post by Balesir » Thu Mar 08, 2007 1:49 pm

Hi,

Been thinking more about this and realised that my 'rules' for lines of light as previously written do not work. As written, they read:
Rules are now applied for lines of light as follows:
  • If a space has at least half of its corners touched by a line of light at full light range, it is fully lit.

    If a space has any one corner touched by a line of light at full strength it is dimly lit.

    If a space has at least half its corners touched by a line of light at dim strength it is dimly lit.

    All other spaces are unlit.
To be valid a line of light must not touch a block at any point along its length. It is traced from the point of the light source to the space corners of the space being assessed for lighting.
This causes problems with corner squares and with lights that are on a blocking vector.

I suggest therefore that the following be substituted:
  • If the centre of the cell is touched by a valid line of light at full strength, the cell is fully lit.

    If the centre of the cell is touched by a valid line of light at dim strength, the cell is dimly lit.

    If neither of the above are true, but one of the cell corners is touched by a valid line of light at full strength, the cell is dimly lit.

    All other cells are unlit.
This has a very similar effect but does not give problems with corner cells. Light sources must be in cell centres, since light sources on blocking vectors still cause problems.

On the subject of algorithms, I found here algorithms for line intersections, so to test a line AB with A at (Ax,Ay) and B at (Bx,By) for intersection with line CD with C at (Cx,Cy) and D at (Dx,Dy), evaluate r and s like this:

Code: Select all

            (Ay-Cy)(Dx-Cx)-(Ax-Cx)(Dy-Cy)
        r = -----------------------------  (eqn 1)
            (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)

            (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)
        s = -----------------------------  (eqn 2)
            (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
If (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx) is zero the lines are parallel. If both r and s are in the range 0 - 1 then the lines touch. This is, I guess, the mathematically simplest test for a valid 'line of sight' or 'line of light' among 'blocking vectors'.

Hope that helps...
Balesir

Post Reply

Who is online

Users browsing this forum: Majestic-12 [Bot] and 3 guests