Fog of War and 2D Grid

Question

First of all, I am working on a 2D strategy using the XNA infrastructure.

I use 2D fog of war for my game. The graphic part has already been completed and works pretty well, but now I'm trying to implement the "logical" part of this fog of war.

I created a 2D grid representing my level. Each frame, each block updates the cells in a circle around it, using the Breshenem algorithm (which seems to be the best way to find out which cells are in a given circle). It really works ... When I want to know if a given position is visible or not, I just need to get the state of the cell ...

The problem is that when I have a large number of units generated, my game runs so slowly ... The first reason for this performance problem is that since each block updates the cells around it, many cells are updated several times ... But I do not see any solution for this ...

So ... Perhaps I was mistaken in implementing it this way, or maybe I lack the obvious optimization, but I was kind of stuck ...

Here is the code:

class LevelGridCell { public void SetVisible(float a_time) { if (m_visibleTime < a_time) m_visibleTime = a_time; } public bool IsVisible(float a_time) { return (m_visibleTime != 0f && m_visibleTime >= a_time); } float m_visibleTime = 0; } class LevelGrid { public LevelGridCell GetAt(int a_x, int a_y) { return m_grid[a_x + a_y * m_width]; } public void SetVisible(float a_time, int a_x, int a_y, float a_radius) { GetAt(a_x, a_y).SetVisible(a_time); int intRadius = (int)(a_radius / m_cellSize); int x = 0, y = intRadius, p = 1 - intRadius; PlotSetVisible(a_x, a_y, x, y, a_time); while (x < y) { x++; if (p < 0) p += 2 * x + 1; else { y--; p += 2 * (x - y) + 1; } PlotSetVisible(a_x, a_y, x, y, a_time); } } private void SafeSetVisible(int a_x, int a_y, float a_time) { if (a_x >= 0 && a_x < m_width && a_y >= 0 && a_y < m_height) { GetAt(a_x, a_y).SetVisible(a_time); } } private void PlotSetVisible(int xctr, int yctr, int x, int y, float a_time) { for (int i = xctr - x; i <= xctr + x; ++i) { SafeSetVisible(i, yctr + y, a_time); SafeSetVisible(i, yctr - y, a_time); } for (int i = xctr - y; i <= xctr + y; ++i) { SafeSetVisible(i, yctr + x, a_time); SafeSetVisible(i, yctr - x, a_time); } } List<LevelGridCell> m_grid = new List<LevelGridCell>(); float m_cellSize; int m_width; int m_height; } 

Answer 1

Without seeing our code, we must guess what the problem is. If you have profiled your code, you should find out which part is especially slow; Given this information, you can attack the problem directly.

Here are some hints about which bits might be slow:

• A circle is a circle. Do you follow the Bresenham Circle algorithm for each division? It looks like you could only compute a circle once, relative to (0,0). Then, for a unit at the point (x, y), you can simply look at the circle and shift the points in the circle to (x, y), and then apply your fog of military logic to this device.

• The fog of war only changes for recently displaced units. If the device is stationary, you may not need to calculate its visibility again. Can you apply this optimization to your rules for the fog of war visibility?

• The Bresenham Circle algorithm helps you build a circle border. How do you fill the inside of a circle? If you find the best algorithm for filling the range interval?

The comments asked in more detail about using a single generated circle, so here I am adding some notes about this. (Editing the answer how to do this?) Sorry, I'm relatively new to Stack Exchange.)

"Fog of war" usually means that a unit can see a certain radius around it. What is the radius for your units? Does each type of device have a different radius? How many units are there?

Let's say one type of unit has a radius of 5 squares for its range of visibility. This leaves us with a circle that looks like this:

 00001110000 00010001000 00100000100 01000000010 10000000001 10000x00001 10000000001 01000000010 00100000100 00010001000 00001110000 

Since we have a circle, we know that we don’t need to do anything too complicated to fill it. A simple algorithm would move through each line filling between the rightmost 1 and leftmost 1. This will be much faster than resolving the Breshenem algorithm for all internal points.

With a filled circle, we will find this array, and then:

 00001110000 00011111000 00111111100 01111111110 11111111111 11111x11111 11111111111 01111111110 00111111100 00011111000 00001110000 

Now, if we have a unit with a radius of visibility of 5 squares, applying the fog of war to this unit means only applying this precomputed array to the fog of the military array, so the center of this precomputed array is on the unit we are processing. You can do this with a simple nested loop as soon as you calculate the offsets from the center and copy the borders of the array to the edge of your map.

If you have several different radii for the fog of war visibility, you can pre-compute several different arrays. If you have rules that say that your fog of war varies depending on obstacles (such as terrain or buildings or terrain), you need to do a bit more processing, but the idea of ​​precalculation can still be applied.

Answer 2

KISS

Why do you need to calculate a circle every time? It is expensive.

Think of it this way. When you edit the picture in paint.exe, with the big brush selected, do you think that the calculation of this circle happens every time? How about when you select a mosaic or custom brush in Photoshop, how does it work?

You just need to calculate the circle once, even if (I would hard code it, buddy there already gave you a quick way)

 const char circle[] = { 00001110000 00011111000 00111111100 01111111110 11111111111 11111x11111 <-- put this into a static C array 11111111111 01111111110 00111111100 00011111000 00001110000 } 

There, now you can simply use this array to compare with your total fog of the military array. If you click on this 0, do nothing (you may have an overlap) if you have 1, and then set one in your fog of the military array.

If you need modules with a different range of sites, you can simply compute or hard-code the array for this. At best, you will have a kilobyte of memory, but you are going to save as many cycles.

But what if there is an obstacle? You might need to make another map spanning an array with heights (do you already have this?) Or with viewing block areas. Let me just say that this is a view lock area (height does not matter, it just blocks the view). Instead of directly comparing your view environment array (see above). You need to compare it again with a view lock array (also 1 and 0). If you come across one, which would mean that the view is locked, you need to use the Bresenham function to take a line from the device where you encountered one in the view lock array, and with that you will have an area that should be set as visible.

I kind of worked badly, talking there, if you don’t understand, I’ll get back to you.

So this may be a bad method. It would be easy to implement if you just recounted the entire grid every time the unit moved, but it would be terribly slow and inefficient. To do this, you will need to clear the brand of units in your FOW array after moving it. (Think 2d animation without screen cleaning or double buffering)