Visibility map construction

[techbear]

I'm working on my turn-based, cell-based game engine, and it's time to implement "fog of war", also called a visibility map. This is a map overlay that doesn't allow you to see enemy units until one of your units can "see" them.

I want to implement something simple and fast (cause I'll have to update it every step of every movement), but I need a reality check.

The real issue is opaque tiles, like forests or walls, that units cannot see PAST. I could simply seed a map with the start locations of all my units, and then iteratively spread those seeds out to the limits of the units' vision, but that won't handle opaque tiles.

I could seed the map with the units, then iteratively spread out AROUND the opaque tiles, but that would mean seeing AROUND objects, which isn't the result I want.

I could also start from each unit, and "paint" rays outward until vis distance or an opaque tile are hit. However, the longer the range, the more rays I'll have to paint, so this approach, while giving correct results, would seem to be very slow.

What do you think?

[ggambett]

I could also start from each unit, and "paint" rays outward until vis distance or an opaque tile are hit. However, the longer the range, the more rays I'll have to paint, so this approach, while giving correct results, would seem to be very slow.
I think that's the (only?) way to go. About the speed, depending on the particular problem, you could partially or totally precompute the visibility of each tile in the map - if the terrain doesn't change, you can save a lot of processing there. Then, get each unit, do a boolean union of the visibility sets of each of the current positions, and you get the complete set of visible tiles.

If vision is blocked by buildings or other stuff that can be built dinamically, things are more complicated. You could still precompute terrain visibility ("static visibility") and update a copy each time a building is created or destroyed. Note that if there is no line of sight between A and B due to the terrain, adding a building won't change anything, so you should only recalculate the visibility of tile pairs which are visible in your static visibility map.

You could do some kind of optimization using zones, since vision has a finite range.

This is off the top of my head so it may or may not work :) Never done this kind of thing.

[Hamumu]

You definitely should google up "line of sight algorithm". The algorithms are REALLY simple, you wouldn't expect them to work. I use them to do the lighting effects in my games. They only measure whether all tiles (or all tiles in a given radius) are visible from a given tile, but using that to provide info to an overall visibility map would be trivial.

[lexaloffle]

I was about to say - if you think doing line of sight per frame is expensive, have a look at Supreme with Cheese (:

[Screwball]

You are better off not doing line of sight check with each frame, you are better off doing line of sight check each time a unit moves. As you are doing a turn based game, I am assuming you are using this method so check out the following:

Amit's Line of Sight Algorithm (http://www-cs-students.stanford.edu/~amitp/Articles/LineOfSight.html)

Definatly a good read as is his other articles on his site HERE (http://www-cs-students.stanford.edu/~amitp/gameprog.html).

[techbear]

Thanks, everyone. This page helped me immensely!

http://www.roguelikedevelopment.org/php/category/showCategory.php?path=development/&category=LOS