GLBasic forum

Codesnippets => Code Snippets => Topic started by: Wampus on 2010-Dec-12

Title: Line of Sight for 2D grid-based games
Post by: Wampus on 2010-Dec-12
MAJOR UPDATE

Changes:-


Still to do: -


Nearly there! The hardest parts are all done now.

(http://i904.photobucket.com/albums/ac242/wheeethefibble/webpics/lineofsightss-1.jpg)

-------------------------- 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]
Title: Re: Line of Sight for 2D grid-based games
Post by: erico 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:
Title: Re: Line of Sight for 2D grid-based games
Post by: Wampus 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.
Title: Re: Line of Sight for 2D grid-based games
Post by: Quentin 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.
Title: Re: Line of Sight for 2D grid-based games
Post by: matchy 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.
Title: Re: Line of Sight for 2D grid-based games
Post by: erico 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.
Title: Re: Line of Sight for 2D grid-based games
Post by: Wampus 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:-

Title: Re: Line of Sight for 2D grid-based games
Post by: matchy 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
 

  :|
Title: Re: Line of Sight for 2D grid-based games
Post by: Kitty Hello on 2010-Dec-13
AWESOME work! You need a "buy me a beer" button!
Title: Re: Line of Sight for 2D grid-based games
Post by: ampos 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]
Title: Re: Line of Sight for 2D grid-based games
Post by: Wampus 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.
Title: Re: Line of Sight for 2D grid-based games
Post by: Wampus on 2010-Dec-14
Few thoughts before I stop work on this until next week:-

Title: Re: Line of Sight for 2D grid-based games
Post by: erico 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]
    Title: Re: Line of Sight for 2D grid-based games
    Post by: bigsofty on 2010-Dec-14
    Looking good, it will be interesting to see it work at a specific angle with FOV.  :good:
    Title: Re: Line of Sight for 2D grid-based games
    Post by: Wampus 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.

    (http://i904.photobucket.com/albums/ac242/wheeethefibble/webpics/anglelos.jpg)
    Title: Re: Line of Sight for 2D grid-based games
    Post by: matchy on 2011-Jun-02
    Alright! I suppose it would also work for a side-view platform game like a cavern level.
    Title: Re: Line of Sight for 2D grid-based games
    Post by: Ian Price on 2011-Jun-02
    I'd give you two thumbs up, but you wouldn't be able to see, so here you go - :good: :good:
    Title: Re: Line of Sight for 2D grid-based games
    Post by: Wampus on 2011-Jun-02
    Alright! I suppose it would also work for a side-view platform game like a cavern level.

    Um, kinda. In theory it could be used for that but it would be prudent to only use it for a limited number of spawned entities, perhaps just the player character. Testing on a Intel Mobile 2 Duo 2.40GHz platform with a bad case scenario it takes only 75-77 entities with their line of sight set to 13 block radius (about right for a side-view platformer) to bring the refresh rate down below 60 FPS in a live action scenario. That's without much else but screen drawing going on. On slower machines like netbooks even 15 entities would be a lot.

    It was designed as a luxury line of sight routine for turn-based games. To get really nice looking line of sight results its best to use something akin to ray tracing but that is very slow, requiring many thousands to many tens of thousands of rays to be calculated for each change in location/environment. My routine precalculates the results of ray tracing and uses some tricks to simulate a more realistic field of view than would be possible if strictly keeping to a single point of origin. Even with the tricks and precalcuated results its still requires a hefty chunk of CPU cycles.

    For lighting effects in a side-view platform game it would be much faster to use a similar technique to something like Terraria (http://www.youtube.com/watch?v=UGo7iMUcxLc). Crude though that method is, it is extremely quick.
    Title: Re: Line of Sight for 2D grid-based games
    Post by: Wampus on 2011-Oct-21
    Ages ago I said I'd finished modifying my line of sight routine so that it could use limited angled arcs of light. Well, I never got around to writing up a simple demonstration routine to show what it was capable of. I also didn't complete the blast radius routine. I doubt I will get around to those things anytime soon since I've started work on a big project that I'm quietly excited about.

    Anyway, attached to this post is the proggy that generates the precalcuated field of vision data. That way anyone can compile and see how far I got. The code is a bit of a nightmare but the app itself is somewhat self explanatory when in use. As far as I know the approach I took is unique. For comparison some others are shown here: http://roguebasin.roguelikedevelopment.org/index.php/Comparative_study_of_field_of_view_algorithms_for_2D_grid_based_worlds (http://roguebasin.roguelikedevelopment.org/index.php/Comparative_study_of_field_of_view_algorithms_for_2D_grid_based_worlds)

    [attachment deleted by admin]