怎么求出被包围的部分

歌者文明清理员

rt，玩了 https://tileman.io，有感而发，准备也写一个。



现在遇到了一个最大的问题，如何求出被包围的部分？

FishC

求出被包围的部分，可以用一些常见的计算几何算法。以下是一个相对简单的方法，适合处理一些基本的情况：

### 步骤：

1. **标记所有的边界点**：首先需要标记所有作为边界的点（即那些不被四面八方包围的点）。

2. **遍历标记的点**：从一个边界点开始，进行遍历。

3. **使用洪水填充算法**：
   - 类似于油漆桶工具的工作原理。
   - 选取一个未被包围的区域进行填充，这样就可以找出所有连通的区域。

4. **判断被包围区域**：
   - 如果一个区域在填充的过程中没有接触到边界点，那么它就是被包围的。
   - 如果一个区域在填充过程中接触到了边界点，那么它就是未被包围的。

### 伪代码：
下面是一个简化的伪代码，用来解释以上步骤：

1. def find_enclosed_areas(grid):
   
2.     # 获取网格的尺寸
   
3.     rows, cols = len(grid), len(grid[0])
   
4.    
   
5.     # 定义四个方向：上下左右
   
6.     directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
   
7.    
   
8.     def is_valid(x, y):
   
9.         # 检查坐标是否在网格内
   
10.         return 0 <= x < rows and 0 <= y < cols
    
11.    
    
12.     def bfs(start):
    
13.         # 使用队列进行广度优先搜索
    
14.         queue = [start]
    
15.         enclosed = True
    
16.         region = []
    
17.         
    
18.         while queue:
    
19.             x, y = queue.pop(0)
    
20.             if (x, y) in visited:
    
21.                 continue
    
22.             visited.add((x, y))
    
23.             region.append((x, y))
    
24.             
    
25.             for dx, dy in directions:
    
26.                 nx, ny = x + dx, y + dy
    
27.                 if is_valid(nx, ny):
    
28.                     if grid[nx][ny] == 0:
    
29.                         queue.append((nx, ny))
    
30.                 else:
    
31.                     enclosed = False
    
32.         
    
33.         return region if enclosed else []
    
34.    
    
35.     visited = set()
    
36.     enclosed_areas = []
    
37.    
    
38.     for i in range(rows):
    
39.         for j in range(cols):
    
40.             if grid[i][j] == 0 and (i, j) not in visited:
    
41.                 enclosed_area = bfs((i, j))
    
42.                 if enclosed_area:
    
43.                     enclosed_areas.append(enclosed_area)
    
44.    
    
45.     return enclosed_areas
    
46. 
    
47. # 示例网格：0 代表空白区域，1 代表边界
    
48. grid = [
    
49.     [1, 1, 1, 1, 1],
    
50.     [1, 0, 0, 0, 1],
    
51.     [1, 0, 1, 0, 1],
    
52.     [1, 0, 0, 0, 1],
    
53.     [1, 1, 1, 1, 1],
    
54. ]
    
55. 
    
56. print(find_enclosed_areas(grid))

复制代码

### 解释：
- `grid` 是一个表示地图的二维列表，1 代表边界，0 代表空白区域。
- `bfs` 是一个广度优先搜索函数，用于查找连通区域。
- `enclosed_areas` 是一个存储被包围区域的列表。

希望这些步骤和代码能够帮助你解决如何找出被包围区域的问题！祝你写游戏顺利！如果遇到更多问题，欢迎随时提问哦~

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

歌者文明清理员

FishC 发表于 2024-7-1 17:52
求出被包围的部分，可以用一些常见的计算几何算法。以下是一个相对简单的方法，适合处理一些基本的情况：
...

怎么求出 bfs 起始点呢？

FishC

歌者文明清理员 发表于 2024-07-01 17:55
怎么求出 bfs 起始点呢？

要找出 BFS（广度优先搜索）的起始点，首先要明确我们寻找的是哪个特定点。这通常取决于你在实现什么功能。这里有几种常见的场景和解决方法：

### 场景1：在一个二维网格中找一个起始点，例如未访问的第一个点
假设你有一个二维网格，其中某些点是已经访问过的，而你想从一个未访问的点开始进行 BFS。网格中的未访问点可以用特定值表示（例如0表示未访问，1表示已访问）。

1. def find_starting_point(grid):
   
2.     rows, cols = len(grid), len(grid[0])
   
3.     for i in range(rows):
   
4.         for j in range(cols):
   
5.             if grid[i][j] == 0:  # 0表示未访问
   
6.                 return (i, j)
   
7.     return None  # 如果所有点都已访问过，返回None

复制代码

### 场景2：在迷宫中找起点和终点
假设你在一个迷宫中，起点和终点可能有特定的标记（例如'S'表示起点，'E'表示终点）。

1. def find_start_and_end(grid):
   
2.     start = None
   
3.     end = None
   
4.     rows, cols = len(grid), len(grid[0])
   
5.     for i in range(rows):
   
6.         for j in range(cols):
   
7.             if grid[i][j] == 'S':  # 'S'表示起点
   
8.                 start = (i, j)
   
9.             if grid[i][j] == 'E':  # 'E'表示终点
   
10.                 end = (i, j)
    
11.     return start, end

复制代码

### 场景3：在图中找到一个指定的起点
如果你在一个图（使用邻接表表示）中寻找一个指定的起点，起点可能由某些属性或标记确定。

1. def find_specific_start(graph, start_label):
   
2.     if start_label in graph:
   
3.         return start_label
   
4.     return None  # 如果没有找到起点，返回None

复制代码

### 使用 BFS 进行搜索
一旦你找到了起始点，可以使用 BFS 进行搜索。以下是一个简单的 BFS 实现：

1. from collections import deque
   
2. 
   
3. def bfs(grid, start):
   
4.     rows, cols = len(grid), len(grid[0])
   
5.     directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 上下左右
   
6.     queue = deque([start])
   
7.     visited = set([start])
   
8.    
   
9.     while queue:
   
10.         x, y = queue.popleft()
    
11.         for dx, dy in directions:
    
12.             nx, ny = x + dx, y + dy
    
13.             if 0 <= nx < rows and 0 <= ny < cols and (nx, ny) not in visited and grid[nx][ny] == 0:
    
14.                 queue.append((nx, ny))
    
15.                 visited.add((nx, ny))
    
16.                 # 可以在这里处理访问逻辑，例如标记访问或记录路径
    
17.     return visited  # 返回所有访问过的点

复制代码

这个 BFS 示例从一个起始点开始，访问所有可能到达的点并返回所有访问过的点。你可以根据具体需求在BFS过程中添加额外的处理逻辑，例如标记被包围的区域等。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

陈尚涵

？什么意思

歌者文明清理员

陈尚涵 发表于 2024-7-1 18:25
？什么意思

就是图上那个意思啊

陈尚涵

歌者文明清理员 发表于 2024-7-1 18:28
就是图上那个意思啊

？面积吗

歌者文明清理员

陈尚涵 发表于 2024-7-1 19:04
？面积吗

求出每个点坐标

苗生海海

想问，这个是个什么游戏

学习编程中的Ben

我觉得吧他是先绘制地图然后在进行游戏部署的。所以每个点的坐标都是确定的

歌者文明清理员

学习编程中的Ben 发表于 2024-7-2 10:07
我觉得吧他是先绘制地图然后在进行游戏部署的。所以每个点的坐标都是确定的

对，怎么求出围起来的部分

python爱好者.

问题表述不清，很难针对回答

歌者文明清理员

python爱好者. 发表于 2024-7-2 13:51
问题表述不清，很难针对回答

获取图中被框住的部分每个点的坐标，已知旁边线条的坐标

学习编程中的Ben

歌者文明清理员 发表于 2024-7-2 11:46
对，怎么求出围起来的部分

坐标减去坐标呗

python爱好者.

歌者文明清理员 发表于 2024-7-2 14:33
获取图中被框住的部分每个点的坐标，已知旁边线条的坐标

这不就坐标吗，你学一下建系，这种游戏常用