Currently I'm developing a RTS game using Python/PyGame and I got some problems with fps drops when there are many units on the screen.

Using Snakeviz profiling I found out that the function update_vision() takes up a big majority of the processing.

This is because the function is checking every tile inside a radius of each unit (depending on the units defined vision range). When there are many units there are a lot of calculations that need to happen.

I'd like to optimize this somehow. Currently it's checking the same tiles over and over if the units vision ranges are overlapping. However I'm not sure how to go about this and would appreciate any help!

Below is the function used for inputting 1s into the matrixes that represent the map. 1s represent vision in both cases. At the start of every frame the matrixes are reset with 0s.

    #-----Update vision & explored matrixes-----
    def update_vision(self):

        for i, group in enumerate(all_p_unit_sprite_list):
            if i+1 != self.player:
                continue
            
            for unit in group:
                for row in range(-unit.vision_range, unit.vision_range + 1):
                    for col in range(-unit.vision_range, unit.vision_range + 1):
                        loc_x = unit.x_coord + row
                        loc_y = unit.y_coord + col
                        if 0 <= loc_x < matrix_width and 0 <= loc_y < matrix_height:
                            if abs(row) + abs(col) <= unit.vision_range:
                                map_vision_matrix[loc_y][loc_x] = 1
                                map_explored_matrix[loc_y][loc_x] = 1

Zoler1337 said:
I'd like to optimize this somehow. Currently it's checking the same tiles over and over if the units vision ranges are overlapping. However I'm not sure how to go about this and would appreciate any help!

I do not understand the purpose and function of ‘vision’. Is it to give each unit some sense of what enemies are nearby? Or is it to determine the explored and known territory for a whole faction?

However, independent of that, the easy solution might be to time slice the calculation. So instead doing the calculations every frame for all units, you do it only for 10% of units, next frame for another 10% and so on.

Looks like fog-of-war to me JoeJ.

Some small fish:

for row in range(-unit.vision_range, unit.vision_range + 1):
    # for col in range(-unit.vision_range, unit.vision_range + 1):
        loc_x = unit.x_coord + row
        # loc_y = unit.y_coord + col
        if 0 <= loc_x < matrix_width # and 0 <= loc_y < matrix_height:

You're doing row range detection "2 * unit.vision_range" times, namely once for every column. As column has no influence at all, move that code above the "for col…" loop

if abs(row) + abs(col) <= unit.vision_range:

Similarly, “abs(row)” doesn't change with column, and neither does “unit.vison_range”. In other words, you can compute lower and upper boundary of the columns exactly before entering the “col” loop.

Another way to do the area around a unit is to pre-compute a list of (row, column) pairs that are within vision range once. Then by using those pairs you know the vision range is ok, and the checks can be dropped. You'll getting something along the lines of

for row, col in row_col_pairs_in_vision_range:
	# compute x and y, check they are in matrix range.
	# set the map vision.

I don't know what the “map_…” thing is. If it is a list of lists that's fine. If you use a dictionary of dictionaries, consider using (x, y) keys, as in “map_vision_matrix[(x, y)] = 1”.

The bigger fish can be obtained by exploiting some properties of your game:

If most of the units are stationary, there isn't much point in computing vision every time. You can create “dirty” rectangles, rectangles in the map that must be updated. You add new rectangles whenever a unit leaves or arrives, and process the areas of the new rectangles when you update the vision area. Afterwards the new rectangles can be deleted (since the vision data matches reality again). If nothing moves then you are done in an instant then.

Another option is not to do perform the computation by calling “update_vision” but do it while moving a unit. Instead of booleans (0/1) values in the map, use a count. The value represents the number of units that can see the x,y location. So 0 means no unit can see the x,y location and any positive value means there is at least one unit that can see it.

Attach updating the counts to movement of a unit. When a unit leaves, it decreases all counts of x, y positions that it can see by 1 (it no longer observes the area around it), and when arriving at the new spot, it increases the counts of the map around it again (it starts to observe its area again).

Obviously, when all units move all the time, you don't gain much. In such a case, updating a part of the units may work as JoeJ suggested. Effectively, it takes time before a unit can fully observe its area.

If the matrix size is bigger than what the user can see, another path is to only update the part that is visible to the user. Whether this is feasible depends on what the function of vision is in the game.

Alberth said:
Looks like fog-of-war to me JoeJ.

Ha ok, then it's the latter of my assumptions, about calculating known territory.
That's basically the same as calculating the distance to the closest unit for each grid cell, so we could look at algorithms to generate signed distance fields.
The common solution here seems ‘Jump Flooding Algorithm’, which i've learned from here: https://blog.demofox.org/2016/02/29/fast-voronoi-diagrams-and-distance-dield-textures-on-the-gpu-with-the-jump-flooding-algorithm/

… It's an hierarchical approach, but does not require mip maps. It's also not perfectly accurate but a very good approximation. And it's a really big speed up over brute force.

I'm not sure if it's only useful if we recalculate a solution from scratch, or if it also can be used to refine and update a already existing solution from the previous frame with little work.

Having distance, but not just a binary result, could be useful for AI as well. You could find the closest unit from every point easily by following the distance gradient.

Since this is highly tied to rendering fog of war over a 3D terrain, you could probably render a circle at the center of every unit, top down into a visibility map that is 2048x2048 (should probably be enough resolution since you linearly blend. Read the texture back to the CPU if you must, but CPU logic can just literally use distance checks to other units to see if they can fight each other. You separate visibility rendering and AI logic.

A slightly late reply from me but I wrote up some slightly rough notes on implementing fog of war here if it helps. I only update fog cells for units that have moved. I also linked & discussed some other peoples fog-of-war implementations.

jdtec01 said:
A slightly late reply

Three months necro. Thread locked.