Author Topic: Line of Sight for 2D grid-based games  (Read 11254 times)

Offline Wampus

  • Prof. Inline
  • *****
  • Posts: 1004
    • View Profile
    MAJOR UPDATE

    Changes:-

    • Varied levels of visibility (0 - hidden to 8 - fully viewable)
    • Basic Fog of War added
    • Smoothed the edges of the view area
    • Perfect symmetry of view angles
    • No more light leaking through 45 degree edges
    • Greatly improved angles of vision - more natural
    • Radius up to 30 squares (max 20 for uploaded demo)

    Still to do: -

    • Allow for multiple light sources to combine as one
    • Add some nice features like 'keep area permanently viewable'
    • Make it even simpler to plug into a game map with just a few function calls
    • Tidy up the precalculation routine so I can give it to others to modify for themselves

    Nearly there! The hardest parts are all done now.



    -------------------------- Old originals post below --------------------------------


    After seeing that awesome random map generator routine :good: I did some work on a line of sight algorithm...

    The algorithm does a lot more than basic line of sight and solves a couple of problems with the typical approach to line of sight.
    If anyone can think of some useful features to add then say so in this thread. If I think its a good idea I'll add it (and I'll explain why if I don't).

    Also, any ideas about line of sight related stuff in general just post 'em.  :)

    Oh, and use the up and down arrow keys to increase or decrease the line of sight radius in the example.[/list]

    [attachment deleted by admin]
    « Last Edit: 2010-Dec-13 by Ragaril »

    Offline erico

    • Community Developer
    • Prof. Inline
    • ******
    • Posts: 4212
      • View Profile
      • Portfolio
    Re: Line of Sight for 2D grid-based games
    « Reply #1 on: 2010-Dec-12 »
    mygod! that looks wonderful!

    can't really think well as I bable but...

    -you can have multiples of those right? so to have a fog of war?
    -can it be directional? like character facing each of the 8 directions or any direction (more analogic).
    -you work with either see or don't see, can it have a degree as it falls off (half height objects, trees)?
    -angle of sight, shorter angle sees further, wide angle sees less?

    now I guess someone can do a proper xcom...
    I once thought of a haunted house game...but could not come out with such a line of sight code...

    congrats! :good:

    Offline Wampus

    • Prof. Inline
    • *****
    • Posts: 1004
      • View Profile
    Re: Line of Sight for 2D grid-based games
    « Reply #2 on: 2010-Dec-12 »
    Thanks  =D

    -you can have multiples of those right? so to have a fog of war?
    Absolutely. A very necessary feature. Multiple light maps for different players, computer or human, will be vital. Also you can mix many agent's fields of view together so their lines of sight combine into a cohesive whole.
     
    -can it be directional? like character facing each of the 8 directions or any direction (more analogic).
    Brilliant. Thanks for the great idea. I hadn't thought of that because I don't need it for the two games I'm going to use this for but I'll definitely include it as an option in the new version. I'll implement it as being able to select facing angle plus width of view.

    -you work with either see or don't see, can it have a degree as it falls off (half height objects, trees)?
    Hmm. At one point I was thinking of working with width and height of object, and based upon that and the angle available to view, the amount of it that be seen clearly (variable brightness) because it wouldn't be that hard to add it to what I was already doing. Its definitely a possibility but for my purposes its easier for the game AI I've designed so far to work with seen or unseen. Maybe I can work on threshold light levels and just get my game to register as seen or unseen based on that. I'll definitely give this a thought but if it doesn't make the next version, its because it was harder to accomplish than I antipate.

    -angle of sight, shorter angle sees further, wide angle sees less?
    Again, great idea. I'll add this and make it something that can be adjusted easily.

    now I guess someone can do a proper xcom...
    Heh. Well I started with GLBasic because I wanted to remake Lords of Chaos (a forerunner to XCOM) and now I'm doing it.  :happy: I am writing an implementation of A* path finding algorithm that can work with 8 directions (so diagonals as well as the normal 4 directions) as well as fog of war alongside the line of sight stuff too. That will be made available as soon as I'm finished.

    Offline Quentin

    • Prof. Inline
    • *****
    • Posts: 915
      • View Profile
    Re: Line of Sight for 2D grid-based games
    « Reply #3 on: 2010-Dec-12 »
    Wow! Great work.
    I was always wondering how to make rounded edges at the borders of the FOW. Perhaps you have an idea how to implement it.

    Offline matchy

    • Prof. Inline
    • *****
    • Posts: 1543
      • View Profile
    Re: Line of Sight for 2D grid-based games
    « Reply #4 on: 2010-Dec-12 »
    That's interesting and I suppose it would look better with a tiled or analog radius gradient/alpha for simulated explorer range fog.

    Offline erico

    • Community Developer
    • Prof. Inline
    • ******
    • Posts: 4212
      • View Profile
      • Portfolio
    Re: Line of Sight for 2D grid-based games
    « Reply #5 on: 2010-Dec-12 »
    Hmm. At one point I was thinking of working with width and height of object, and based upon that and the angle available to view, the amount of it that be seen clearly (variable brightness) because it wouldn't be that hard to add it to what I was already doing. Its definitely a possibility but for my purposes its easier for the game AI I've designed so far to work with seen or unseen. Maybe I can work on threshold light levels and just get my game to register as seen or unseen based on that. I'll definitely give this a thought but if it doesn't make the next version, its because it was harder to accomplish than I antipate.

    I get the idea, but, lets say the game is turn based, like batttletech for examle, you can have a RND dice going to check if important object was see or not behind trees, smoke,fire,something and increase the impropability as line of sight passes through more obstacle objects. This way something is still see or not see.

    Not sure if it adds to the current games you are doing but it would make it more difficult to spot that locust behind a forest...

    post some more screenies when you get time! those are inspiring.

    Offline Wampus

    • Prof. Inline
    • *****
    • Posts: 1004
      • View Profile
    Re: Line of Sight for 2D grid-based games
    « Reply #6 on: 2010-Dec-12 »
    I should point out that, while interesting, version 1 is basically somewhat broken. I'm moving on with version 2. It might only take me until tomorrow or it might be more than a week, depending on other work loads. Anyway...

    Quentin, I think I do know how to implement something like rounded edges to Fog Of War. You'll be able to see it in version 2.

    Matchy, I'm not 100% sure I understood what you meant but if I did, its a brilliant idea! And yes it would look a lot better. I am going to include it in version 2.

    Erico, a random chance of seeing something based on visibility is something I hadn't thought of. Thanks, that's an interesting gameplay dynamic that I'm bound to use at some point. I don't know if its worth posting more screenies yet because I'm now working on version 2 of this routine, which will be better in many ways.

     :zzz: I was not able to sleep at all last night because my brain was whirrrrring, solving the horrible problems with the old version and working out how to add new features. I now think I finally have a perfectly working algorithm that is nicely flexible. Some points:-

    • Variable visibility is definitely going to be a feature now. I am thinking of 16 levels of visibility. 0 is totally hidden from view. 15 is full visibility. This seem ok? I could change it to 256 levels of visibility but that is probably overkill.
    • Unfortunately I'm not going to add directional angle and field of view because I realise it would require a big and relatively complex change to the fast way the routine determines visibility.
    • I realised I could add levels of height, i.e. add a Z axis as well as an X and Y axis and it would work very nicely in some game scenarios. The trouble is for every level the amount of code loops that need to be done increases a lot. As an example for two levels (e.g. ground and air) the calculations are 6x more. For three levels the calculations are 12x more. Because it would be a great feature for my Lords of Chaos remake I will add this to version 3, when I get round to it.

    Offline matchy

    • Prof. Inline
    • *****
    • Posts: 1543
      • View Profile
    Re: Line of Sight for 2D grid-based games
    « Reply #7 on: 2010-Dec-12 »
    Perhaps something as simple but useful is just setting the vectors in each tile. eg.:

    Code: GLBasic [Select]
    lightmap[0][x][y][z].radar_vec_x
    lightmap[0][x][y][z].radar_vec_y
    lightmap[0][x][y][z].radar_vec_z
     

      :|

    Offline Kitty Hello

    • code monkey
    • Administrator
    • Prof. Inline
    • *******
    • Posts: 10709
    • here on my island the sea says 'hello'
      • View Profile
      • http://www.glbasic.com
    Re: Line of Sight for 2D grid-based games
    « Reply #8 on: 2010-Dec-13 »
    AWESOME work! You need a "buy me a beer" button!

    Offline ampos

    • Prof. Inline
    • *****
    • Posts: 1594
      • View Profile
      • AMpostata Website
    Re: Line of Sight for 2D grid-based games
    « Reply #9 on: 2010-Dec-13 »

      • Variable visibility is definitely going to be a feature now. I am thinking of 16 levels of visibility. 0 is totally hidden from view. 15 is full visibility. This seem ok? I could change it to 256 levels of visibility but that is probably overkill.
      • Unfortunately I'm not going to add directional angle and field of view because I realise it would require a big and relatively complex change to the fast way the routine determines visibility.
      • I realised I could add levels of height, i.e. add a Z axis as well as an X and Y axis and it would work very nicely in some game scenarios. The trouble is for every level the amount of code loops that need to be done increases a lot. As an example for two levels (e.g. ground and air) the calculations are 6x more. For three levels the calculations are 12x more. Because it would be a great feature for my Lords of Chaos remake I will add this to version 3, when I get round to it.

      For FoV and angle, place 2 hiddens blocks of highrt level in front of the guy, or a circle of blocks around with a "window"  :zzz:

      #####
      # x  -----> FoV
      #####

      If the "tunnel" in the window is longer, you get less FoV...

      [/list]
      « Last Edit: 2010-Dec-13 by ampos »
      check my web and/or my blog :D
      http://diniplay.blogspot.com (devblog)
      http://www.ampostata.org
      http://ampostata.blogspot.com
      I own PC-Win, MacBook 13", iPhone 3G/3GS/4G and iPAC-WinCE

      Offline Wampus

      • Prof. Inline
      • *****
      • Posts: 1004
        • View Profile
      Re: Line of Sight for 2D grid-based games
      « Reply #10 on: 2010-Dec-13 »
      Matchy, yes that would work. The hardest part with a Z axis might be the precalculations for what areas should be lit and when. Just the 2D precalculations took me the longest by far, I had to try all sorts of weird and wonderful ways to do it before finding a counter-intuitive one that worked perfectly (for my purposes). In theory it shouldn't be that hard to add an extra dimension, and I will try this, just not until I have the 2D version working to satisfaction.

      Gernot, thanks.  :happy: I will have a "buy me a beer" button in about a week to two weeks time, once I've completed my website. You can expect a lot of (hopefully helpful) game material stuff like this from me over the next year.

      Ampos, yes that's important and that now works as expected in the version of the code I uploaded.

      Offline Wampus

      • Prof. Inline
      • *****
      • Posts: 1004
        • View Profile
      Re: Line of Sight for 2D grid-based games
      « Reply #11 on: 2010-Dec-14 »
      Few thoughts before I stop work on this until next week:-

      • Erico's idea of having settings for direction angle and scope of view will now be implemented. I realised how useful it could be in some situations, e.g. security cameras, spotlights, auto-turrets, etc.
      • Instead of just Line of Sight in an XCOM style scenario the routine can also be used to calculate the lighted areas on a map. Example: You could use it to calculate how well lit a 2D tile-based map was by having electric lights, fire, computer screens and the outdoors as sources of light of varying brightness.
      • It can be used to calculate blast radius of explosives. Example: If you throw a grenade through a door and get behind a wall, so long as the wall is sturdy and survives the blast, you won't get hurt. However, someone standing in the doorway would.
      • If I double the amount of data the routine needs to work with and increase calculations it needs to do by roughly a third I can now do shadows for objects that partially block light, e.g. pillars, trees, rocks of limited height and maybe certain large PCs and NPCs too. Does this sound useful?
      • Because its somewhat CPU expensive I am finding ways to optimise the routine but the new features will cancel out the gains.

      Offline erico

      • Community Developer
      • Prof. Inline
      • ******
      • Posts: 4212
        • View Profile
        • Portfolio
      Re: Line of Sight for 2D grid-based games
      « Reply #12 on: 2010-Dec-14 »

        • Variable visibility is definitely going to be a feature now. I am thinking of 16 levels of visibility. 0 is totally hidden from view. 15 is full visibility. This seem ok? I could change it to 256 levels of visibility but that is probably overkill.
        • Unfortunately I'm not going to add directional angle and field of view because I realise it would require a big and relatively complex change to the fast way the routine determines visibility.
        • I realised I could add levels of height, i.e. add a Z axis as well as an X and Y axis and it would work very nicely in some game scenarios. The trouble is for every level the amount of code loops that need to be done increases a lot. As an example for two levels (e.g. ground and air) the calculations are 6x more. For three levels the calculations are 12x more. Because it would be a great feature for my Lords of Chaos remake I will add this to version 3, when I get round to it.

        For FoV and angle, place 2 hiddens blocks of highrt level in front of the guy, or a circle of blocks around with a "window"  :zzz:

        #####
        # x  -----> FoV
        #####

        If the "tunnel" in the window is longer, you get less FoV...

        god almighty! it makes me recall that pencil/pen russians/americans space program joke... :D
        great!


        • If I double the amount of data the routine needs to work with and increase calculations it needs to do by roughly a third I can now do shadows for objects that partially block light, e.g. pillars, trees, rocks of limited height and maybe certain large PCs and NPCs too. Does this sound useful?

        nice, will get the stealth improved!
        last pic with fading view looks wonderful too! keep up! :good:[/list]

        Offline bigsofty

        • Community Developer
        • Prof. Inline
        • ******
        • Posts: 2626
          • View Profile
        Re: Line of Sight for 2D grid-based games
        « Reply #13 on: 2010-Dec-14 »
        Looking good, it will be interesting to see it work at a specific angle with FOV.  :good:
        Cheers,

        Ian.

        “It is practically impossible to teach good programming style to students that have had prior exposure to BASIC.  As potential programmers, they are mentally mutilated beyond hope of regeneration.”
        (E. W. Dijkstra)

        Offline Wampus

        • Prof. Inline
        • *****
        • Posts: 1004
          • View Profile
        Re: Line of Sight for 2D grid-based games
        « Reply #14 on: 2011-Jun-02 »
        Just a quick note to say I finally got round to making it possible for line of sight to be restricted by angle and field of view today. Also support for multiple players, entities per player and player map sharing is now possible. Screenshot of 40 degree angle with 50 degree field of view is below.

        I need to write another little example routine and simplify the code that handles the angles a bit. After that I'll post the updated code.