Fog of War and LoS
by baylor wetzel · in Torque Game Builder · 07/22/2008 (8:15 pm) · 6 replies
I was about to write my fog of war prototype which means i was about to write my line of sight code and then realized that i should check to see if this wheel has already been invented
This is my first project using a tile map (or is it tile layer? i always get them confused) and i'm still reading up on those. For the fog, my plan was to use one tile layer with black squares and modify the alpha as necessary. i did a search on GG and see other people are doing the same thing
That's the easy part. How have other people handled the line of sight bit?
Since i'm using a tile map, line of sight is tile to tile, not pixel to pixel, so there's less data to check, but i think this means i can't use pickLine. i wrote an influence map prototype a year or two ago that implements (in TorqueScript) Bresenham's line algorithm on a tile map (in that case, a custom one, not the TGB one). If no one has a better idea, i'll just use that to see if one tile can be seen by another one
That would solve the "can Bob see tile 12,5" question. But i have to color the fog for every tile. For argument's sake, let's assume the map is 20x20. The naive solution is to loop through every tile and do the "can he see me" check but with 400 LoS checks, that's not super efficient. How are other people handling this?
Off the top of my head, here's my solution - my line of sight function (which is really a line drawing function) returns all the tiles on the line and the position of the first obstacle. Maybe i could just do the LoS test on the tiles at the edge of the screen. Then i'd only be checking 60 tiles rather than 400. i just need to see if doing that might skip some tiles in the middle. i'm guessing there's a more efficient way to do this
i'll have to handle view cones. Not sure how i'm going to handle that. Maybe not allow LoS checks to any tile more than x degrees from the orientation of my guy (in my case, he only has 8 directions he can face). Not sure how to do that - a t2dVectorSub maybe? (i'm bad at math) Since it's on a tilemap, i might have to map everyone to world coordinates to check (again, i'm not sure)
If a tile isn't seen, either it's never been seen before or it has (i'm using that 3-state fog of war). To know whether to set alpha to 1 or 0.5, i'll have to know it's previous state which means i need a table to track each tiles previous view state. Or maybe i could just assign alpha to min(1, currentAlpha)
So before each turn, loop through all tiles and set alpha to min(1, currentAlpha), max(currentAlpha, 0.5). The first makes previously viewed tiles gray, the second makes tiles i'm looking at gray (in case they fell out of the view cone)
This game is a 4 vs. 4 game so i'll have multiple view cones. For each person, i suppose i'd only set the alpha of the tiles i can see (so, set alpha=0). That way they shouldn't step over each other
i have no idea if doing it this way will flicker so i suppose i could store the alphas in a matrix and then update only those tiles that've changed
i have no idea how fast doing the above in TorqueScript will be. In my case, i'm planning on a turn based game (even though they've fallen out of popularity) so i think i'll be OK
Is this how other people are doing it? Better ideas?
This is my first project using a tile map (or is it tile layer? i always get them confused) and i'm still reading up on those. For the fog, my plan was to use one tile layer with black squares and modify the alpha as necessary. i did a search on GG and see other people are doing the same thing
That's the easy part. How have other people handled the line of sight bit?
Since i'm using a tile map, line of sight is tile to tile, not pixel to pixel, so there's less data to check, but i think this means i can't use pickLine. i wrote an influence map prototype a year or two ago that implements (in TorqueScript) Bresenham's line algorithm on a tile map (in that case, a custom one, not the TGB one). If no one has a better idea, i'll just use that to see if one tile can be seen by another one
That would solve the "can Bob see tile 12,5" question. But i have to color the fog for every tile. For argument's sake, let's assume the map is 20x20. The naive solution is to loop through every tile and do the "can he see me" check but with 400 LoS checks, that's not super efficient. How are other people handling this?
Off the top of my head, here's my solution - my line of sight function (which is really a line drawing function) returns all the tiles on the line and the position of the first obstacle. Maybe i could just do the LoS test on the tiles at the edge of the screen. Then i'd only be checking 60 tiles rather than 400. i just need to see if doing that might skip some tiles in the middle. i'm guessing there's a more efficient way to do this
i'll have to handle view cones. Not sure how i'm going to handle that. Maybe not allow LoS checks to any tile more than x degrees from the orientation of my guy (in my case, he only has 8 directions he can face). Not sure how to do that - a t2dVectorSub maybe? (i'm bad at math) Since it's on a tilemap, i might have to map everyone to world coordinates to check (again, i'm not sure)
If a tile isn't seen, either it's never been seen before or it has (i'm using that 3-state fog of war). To know whether to set alpha to 1 or 0.5, i'll have to know it's previous state which means i need a table to track each tiles previous view state. Or maybe i could just assign alpha to min(1, currentAlpha)
So before each turn, loop through all tiles and set alpha to min(1, currentAlpha), max(currentAlpha, 0.5). The first makes previously viewed tiles gray, the second makes tiles i'm looking at gray (in case they fell out of the view cone)
This game is a 4 vs. 4 game so i'll have multiple view cones. For each person, i suppose i'd only set the alpha of the tiles i can see (so, set alpha=0). That way they shouldn't step over each other
i have no idea if doing it this way will flicker so i suppose i could store the alphas in a matrix and then update only those tiles that've changed
i have no idea how fast doing the above in TorqueScript will be. In my case, i'm planning on a turn based game (even though they've fallen out of popularity) so i think i'll be OK
Is this how other people are doing it? Better ideas?
About the author
#2
i haven't heard anything on the rest of the material so i went ahead and wrote a fog of war system from scratch. i'm pretty happy with it, although it's entirely in TorqueScript and i haven't really tuned it so i have no idea how well it'll scale. i tried it with a turn based game (move one tile at a time) on a 20x15 map and it works fine for that
07/25/2008 (12:17 pm)
James, i forgot to mention, your isVisible code was really helpfuli haven't heard anything on the rest of the material so i went ahead and wrote a fog of war system from scratch. i'm pretty happy with it, although it's entirely in TorqueScript and i haven't really tuned it so i have no idea how well it'll scale. i tried it with a turn based game (move one tile at a time) on a 20x15 map and it works fine for that
#3
07/25/2008 (12:24 pm)
Cool, sounding good! Btw, if you have some arrays of data you need to keep track of (and it sounds like you might), consider taking a look at this TScriptArray Resource.
#4
On a different topic, i wrote a turn based game and needed a way to track whose turn it was. Each piece was stored in a SimSet but i needed a way to sort it. Not sure that that could be added to TScriptArray since it requires some extra data, specifically the object field to use as the key in sorting. As a gameplay mechanic, i also needed a way to randomize the order when there were ties - if two pieces had a speed 7, which one went first varied round to round
Another item i've needed several times was the ability to have an array of numbers or strings. Oddly, you can't do that with a SimSet (it only takes SimObjects) so i had to extend SimSet with addPrimitive/getPrimitive functions. Looks like i wouldn't have had that problem if i had used TScriptArray
07/25/2008 (12:36 pm)
I got the fog of war working pretty quickly except for a couple of hours i spent trying to figure out why line of sight couldn't see the end walls when moving left. Eventually i remembered something i should have thought about sooner - i used Bresenham's algorithm to calculate line of sight and to make the calculations easier, if the end point is above or behind the start point, it flips the line. So the line i got back was a path from end to start, not start to end. Solution - i had to write a SimSet::reverse() function. i was surprised one didn't already exist. Maybe it's something you want to consider for TScriptArray?On a different topic, i wrote a turn based game and needed a way to track whose turn it was. Each piece was stored in a SimSet but i needed a way to sort it. Not sure that that could be added to TScriptArray since it requires some extra data, specifically the object field to use as the key in sorting. As a gameplay mechanic, i also needed a way to randomize the order when there were ties - if two pieces had a speed 7, which one went first varied round to round
Another item i've needed several times was the ability to have an array of numbers or strings. Oddly, you can't do that with a SimSet (it only takes SimObjects) so i had to extend SimSet with addPrimitive/getPrimitive functions. Looks like i wouldn't have had that problem if i had used TScriptArray
#5
Reverse would be straightforward to add...
It would also be easy to add some sorting methods. For example a sortAlph and a sortNumeric that each take a bool for ascending/descending. Since TScriptArray doesn't store the array as a SimSet it wouldn't be necessary to specify a "key" field, there is only one field, %this.array. But that would make sense if you were adding a sort method to the SimSet namespace.
GetRandom and PopRandom would also be straightforward to add...
Perhaps I'll write those up and add them tonight.
07/25/2008 (12:44 pm)
Hmm sounds like some good candidates for adding to TScriptArray.Reverse would be straightforward to add...
It would also be easy to add some sorting methods. For example a sortAlph and a sortNumeric that each take a bool for ascending/descending. Since TScriptArray doesn't store the array as a SimSet it wouldn't be necessary to specify a "key" field, there is only one field, %this.array. But that would make sense if you were adding a sort method to the SimSet namespace.
GetRandom and PopRandom would also be straightforward to add...
Perhaps I'll write those up and add them tonight.
#6
07/25/2008 (11:33 pm)
Just posted some additions to the resource. 
Associate James Ford
Sickhead Games