Flow field Path-finding based on BFS

Previously, the enemy avoiding obstacles was implemented by going in a random direction when it is not able to move. This method is simple and works when the map is not so complex, but will immediately have trouble when there are relatively large obstacles. Thus, path-finding is necessary in this case.

Besides, I need the path-finding algorithm to enable all the enemies to use it at the same time, meaning that there would be a performance concern. Since my map has a grid layout designed for placing objects, I would like to use it as the basis for the path-finding algorithm. To traverse through every grid, breath-first-search is chosen instead of A star.

In summary, the path-finding algorithm has the following steps:

1. Breath-first search: calculate the distances (in terms of how many grids) from any grid to the player's grid. The value is reversed. The smaller the value is, the further from the player. This design allows me to easily set the value for the grid when there is an object placed on it.
2. For each grid, check eight grids surrounding it, the direction is set to be pointing to the largest value (towards the player). The result is a grid-based vector field.
3. When using it, an enemy gets the director from the vector field based on their current position.

PS: The path-finding function is called every 0.5s for performance concerns. The placed walls are not considered in the path-finding function as they can be easily destroyed.

The code is pasted here for you to check:

    @staticmethod
    def field_path_finding(p_x: float,
                           p_y: float,
                           grid: dict,
                           grid_w: int,
                           grid_h: int,
                           dir_field: dict) -> dict:
        min_dist = -(grid_w * grid_h) - 10
        # Destination position
        dst_x = math.floor(p_x / Utils.WALL_SIZE)
        dst_y = math.floor(p_y / Utils.WALL_SIZE)
        dst = (dst_x, dst_y)
        # BFS
        frontier = collections.deque()
        frontier.append(dst)
        dist_grid = dict()
        dist_grid[dst] = 0
        while len(frontier) > 0:
            cur = frontier.popleft()
            for next in [(cur[0] - 1, cur[1]),
                         (cur[0] + 1, cur[1]),
                         (cur[0], cur[1] - 1),
                         (cur[0], cur[1] + 1)]:
                if next not in dist_grid:
                    if next[0] < 0 or next[0] >= grid_w:
                        dist_grid[next] = min_dist
                    elif next[1] < 0 or next[1] >= grid_h:
                        dist_grid[next] = min_dist
                    elif grid[next] == 1: # a real wall in the map
                        dist_grid[next] = min_dist
                    elif grid[next] == 3: # barrel
                        dist_grid[next] = min_dist / 2
                    else:
                        frontier.append(next)
                        dist_grid[next] = dist_grid[cur] - 1
        # Calculate gradient for vector field
        for k in grid:
            max_dis = min_dist
            dir = Vec2(1.0, 0)
            for pos in [(k[0] - 1, k[1]), (k[0] + 1, k[1]),
                        (k[0], k[1] - 1), (k[0], k[1] + 1),
                        (k[0] + 1, k[1] + 1), (k[0] + 1, k[1] - 1),
                        (k[0] - 1, k[1] + 1), (k[0] - 1, k[1] - 1)]:
                if dist_grid.get(pos, min_dist) > max_dis:
                    max_dis = dist_grid[pos]
                    dir = Vec2(pos[0] - k[0], pos[1] - k[1])
            dir_field[k] = dir.normalize()
        return dist_grid

Reference:

• https://www.redblobgames.com/pathfinding/tower-defense/

New character

New map