Optimizing overlapping units vision calculations in RTS using PyGame

Question

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!

    #-----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:
                rel_x, rel_y = unit.get_coord()

                for row in range(-unit.vision_range, unit.vision_range + 1):
                    for col in range(-unit.vision_range, unit.vision_range + 1):
                        loc_x = rel_x + row
                        loc_y = rel_y + 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

    #-----Get grid coordinates-----
    def get_coord(self):
        col = self.rect.centerx  // tile_size
        row = self.rect.centery // tile_size
        return (col, row)

Answer 1

Here is a suggestion:

Manage a unit number matrix like map_unit_num_matrix, The number of units on each tile is recorded. And manage a dirty mark list recording the tiles that change the number of units each frame.

Fake code for example:

#--- unit.py
class Unit:
    def __init__(self) -> None:
        pass  // your unit variables
        self.tilePos = [0,0]

    def move(self):
        pass  // your unit moving logic
        self.onMoving()

    def onMoving():
        newTilePos = self.get_coord()
        if newTilePos[0] == self.tilePos[0] and newTilePos[1] == self.tilePos[1]:
            return
        GameMapManager.instance.unit_move(self.tilePos,newTilePos) //name is just for example
        self.tilePos = newTilePos
        
#--- map.py
class GameMapManager: //it may not exist
    def __init__(self) -> None:
        self.map_vision_matrix = []
        self.map_explored_matrix = []
        self.map_unit_num_matrix = []
        self.map_dirty_mark_list = []

    def unit_move(self,tileFrom,tileTo):
        self.map_unit_num_matrix[tileFrom[0]][tileFrom[1]] -= 1
        self.map_unit_num_matrix[tileTo[0]][tileTo[1]] += 1
        self.map_dirty_mark_list.append(tileFrom)
        self.map_dirty_mark_list.append(tileTo)

    def update_vision(self):
        if not self.map_dirty_mark_list:
            return
        for tilePos in self.map_dirty_mark_list:
            hasUnit = self.map_unit_num_matrix[tilePos[0]][tilePos[1]] > 0
            pass // your vision/fog of war logic
        self.map_dirty_mark_list = []

If the units have different field of view, you can record a field of view list or a unit list rather than unit number in the matrix.