Posted November 30, 2023 by Unchain
#path-finding #top-down
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:
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: