Godot中2D程序化岛屿生成：如何判断点是否为表面点？

核心思路 #

要判断一个点是否为表面点（定义为上方无其他点），关键是快速检索每个点的正上方是否存在已生成的点。通过建立「位置-点对象」的映射字典，可实现O(1)时间复杂度的位置查询，避免嵌套遍历的低效问题。

具体实现步骤 #

1. 建立位置索引字典：生成所有点后，用字典存储每个点的pos与点对象的映射，方便后续快速查找。
2. 遍历检查每个点：对每个点，计算其正上方的预期位置（Godot默认Y轴向下，因此上方对应Y值减小的方向），若该位置存在于字典中，则当前点不是表面点；反之则标记为表面点。
3. 可选：底部点判断：同理，检查正下方是否无点，将符合条件的点标记为底部点。

修改后的生成代码 #

@export var noise: FastNoiseLite
@export var world_size: Vector2i = Vector2i(100, 100)
@export var chunk_size: Vector2i = Vector2i(10, 10)
@export var block_size: Vector2i = Vector2i(22, 22)


func generate_points() -> Array[GenerationPoint]:
    var points: Array[GenerationPoint]
    var pos_to_point: Dictionary = {}  # 存储位置到点的映射，用于快速查询

    var total_world_size = world_size * block_size

    # 第一步：生成所有点并建立索引
    for x in range(-total_world_size.x, total_world_size.x, block_size.x):
        for y in range(-total_world_size.y, total_world_size.y, block_size.y):
            var noise_val: float = noise.get_noise_2d(x*0.1, y*0.1)
            if noise_val > -0.2:
                continue
            
            var point = GenerationPoint.new(Vector2i(x, y))
            points.append(point)
            pos_to_point[point.pos] = point  # 将点存入字典

    # 第二步：遍历所有点，判断表面点与底部点
    for point in points:
        # 计算正上方点的位置（Y轴向上为Y值减小方向）
        var above_pos = Vector2i(point.pos.x, point.pos.y - block_size.y)
        # 上方存在点则不是表面点
        point.is_surface = not pos_to_point.has(above_pos)

        # 可选：判断底部点（正下方无点）
        var below_pos = Vector2i(point.pos.x, point.pos.y + block_size.y)
        point.is_bottom = not pos_to_point.has(below_pos)

    return points

关键细节说明 #

• 坐标系适配：若你的项目中Y轴向上为正方向，需将上方位置的计算改为point.pos.y + block_size.y，请根据实际坐标系调整。
• 性能优化：使用字典索引替代嵌套遍历，在大尺寸世界（如100x100）下能大幅降低时间复杂度，避免性能瓶颈。
• 红色标记点处理：所有被上方点遮挡的点（即正上方存在其他生成点）会被自动标记为is_surface = false，正好解决你提到的红色标记部分的需求。

内容的提问来源于stack exchange，提问作者unwritten_k