Visibility map construction

Discussion in 'Game Development (Technical)' started by techbear, Aug 22, 2004.

  1. techbear

    Original Member

    Joined:
    Aug 10, 2004
    Messages:
    251
    Likes Received:
    0
    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?
     
  2. ggambett

    Moderator Original Member Indie Author

    Joined:
    Jul 26, 2004
    Messages:
    1,982
    Likes Received:
    6
    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.
     
  3. Hamumu

    Indie Author

    Joined:
    Jul 26, 2004
    Messages:
    557
    Likes Received:
    0
    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.
     
  4. lexaloffle

    Indie Author

    Joined:
    Jul 27, 2004
    Messages:
    207
    Likes Received:
    0
    I was about to say - if you think doing line of sight per frame is expensive, have a look at Supreme with Cheese :)
     
  5. Screwball

    Original Member

    Joined:
    Aug 2, 2004
    Messages:
    84
    Likes Received:
    0
    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

    Definatly a good read as is his other articles on his site HERE.
     
  6. techbear

    Original Member

    Joined:
    Aug 10, 2004
    Messages:
    251
    Likes Received:
    0

Share This Page

  • About Indie Gamer

    When the original Dexterity Forums closed in 2004, Indie Gamer was born and a diverse community has grown out of a passion for creating great games. Here you will find over 10 years of in-depth discussion on game design, the business of game development, and marketing/sales. Indie Gamer also provides a friendly place to meet up with other Developers, Artists, Composers and Writers.
  • Buy us a beer!

    Indie Gamer is delicately held together by a single poor bastard who thankfully gets help from various community volunteers. If you frequent this site or have found value in something you've learned here, help keep the site running by donating a few dollars (for beer of course)!

    Sure, I'll Buy You a Beer