Godot实现维诺图区域划分

简介

维诺图（Voronoi Diagram，又称泰森多边形）是一种空间划分算法：给定平面上一组种子点，将平面划分为若干区域，每个区域内的任意点到该区域种子点的距离，小于到其他任何种子点的距离。

在游戏开发中，维诺图有广泛的应用场景：

• 程序化地图生成：生物群系划分、势力范围、程序化城市
• 关卡设计：难度区域划分、房间布局、资源点分布
• 渲染特效：Worley 噪声纹理、细胞材质、水面泡沫
• 游戏玩法：最近资源点查询、区域占领系统、AI 领地感知

本教程将展示如何在 Godot 4 中从零构建一个支持加权模式的交互式维诺图。

实现方式

实现思路

整个维诺图系统分为三个核心模块：

1. 种子点生成 — 使用泊松圆盘采样，保证种子点均匀分布而不扎堆
2. 维诺计算 — 对每个采样点，计算到所有种子的距离，取最近者确定所属区域（暴力距离场法）
3. 可视化渲染 — 将计算结果渲染到 Image 纹理，绘制种子点和区域边界

最终效果：鼠标左键添加种子、右键删除最近种子、W 键切换加权模式、P 键切换泊松/随机采样。

泊松圆盘采样

直接随机撒点会产生"扎堆"——部分区域过于密集、部分区域大片空白。泊松圆盘采样保证任意两个种子点之间距离不小于指定半径 r，在随机性和均匀性之间取得平衡。

核心原理：

• 活跃列表：一个动态收缩的待扩展点队列。从列表中随机选点，在其周围尝试生成候选点；成功则候选点入队，失败 k 次则该点出队
• 网格加速：将地图划分为边长为 r/√2 的网格（对角线恰好 = r），候选点只需检查周围 5×5 个格子内的已有点
• 环形候选：候选点落在当前点 r~2r 的圆环内——< r 太近，> 2r 浪费空间
• k=30：来自 Bridson 2007 年原版论文，2D/3D 下均接近理论最大密度

# poisson_disk_sampling.gd
# 泊松圆盘采样 - 生成均匀分布的种子点

func poisson_disk_sampling(size: Vector2, radius: float, k: int = 30) -> Array[Vector2]:
	var cell_size := radius / sqrt(2.0)
	var cols: int = ceili(size.x / cell_size)
	var rows: int = ceili(size.y / cell_size)

	# 网格：存 points 数组索引，-1 表示空
	var grid: Array[int] = []
	grid.resize(cols * rows)
	grid.fill(-1)

	var points: Array[Vector2] = []
	var active: Array[Vector2] = []

	# 随机第一个点
	var first := Vector2(randf_range(0, size.x), randf_range(0, size.y))
	_poisson_insert(first, points, active, grid, cell_size, cols)

	# 主循环：活跃列表为空时结束
	while not active.is_empty():
		var ai := randi() % active.size()
		var center := active[ai]
		var found := false

		for _i in range(k):
			var angle := randf_range(0, TAU)
			var dist := randf_range(radius, radius * 2.0)
			var candidate: Vector2 = center + Vector2(cos(angle), sin(angle)) * dist

			if candidate.x < 0 or candidate.x >= size.x:
				continue
			if candidate.y < 0 or candidate.y >= size.y:
				continue

			var gx: int = int(candidate.x / cell_size)
			var gy: int = int(candidate.y / cell_size)
			var valid := true

			# 检查周围 5×5 网格
			for dx in range(-2, 3):
				for dy in range(-2, 3):
					var nx := gx + dx
					var ny := gy + dy
					if nx < 0 or nx >= cols or ny < 0 or ny >= rows:
						continue
					var ni := grid[ny * cols + nx]
					if ni != -1 and candidate.distance_to(points[ni]) < radius:
						valid = false
						break
				if not valid:
					break

			if valid:
				_poisson_insert(candidate, points, active, grid, cell_size, cols)
				found = true
				break

		if not found:
			active.remove_at(ai)

	return points


func _poisson_insert(point: Vector2, points: Array[Vector2], active: Array[Vector2],
		grid: Array[int], cell_size: float, cols: int) -> void:
	var idx: int = points.size()
	points.append(point)
	active.append(point)
	grid[int(point.y / cell_size) * cols + int(point.x / cell_size)] = idx

何时不用泊松： 种子点 < 50 时，完全随机采样加简单距离检查即可，泊松的网格和活跃列表开销不值得。

维诺计算：暴力距离场法

暴力距离场法直接对应维诺图的数学定义：对地图上每个采样点，计算到所有种子的距离，归属距离最近的种子。

优势是直观、实现简单，适合种子数 < 500 的场景。种子数更多时建议使用 Fortune's Sweepline 算法或 Bowyer-Watson 算法。

# voronoi_compute.gd
# 暴力距离场法计算维诺图

# 配置
const DIAGRAM_W := 720
const DIAGRAM_H := 440
const SAMPLE_STEP := 4  # 采样步长（像素），越小精度越高

var _grid_w: int = int(DIAGRAM_W / float(SAMPLE_STEP))
var _grid_h: int = int(DIAGRAM_H / float(SAMPLE_STEP))
# _owner_grid[y * _grid_w + x] = 所属种子索引，-1 表示无种子
var _owner_grid: PackedInt32Array


func compute_voronoi(seeds: Array[Dictionary], is_weighted: bool) -> void:
	_owner_grid.resize(_grid_w * _grid_h)

	for gy in range(_grid_h):
		for gx in range(_grid_w):
			# 采样点（取格子中心）
			var wx := gx * SAMPLE_STEP + SAMPLE_STEP * 0.5
			var wy := gy * SAMPLE_STEP + SAMPLE_STEP * 0.5

			var nearest := -1
			var d_min := INF

			for si in seeds.size():
				var s: Dictionary = seeds[si]
				var d: float = Vector2(wx, wy).distance_squared_to(s.pos)

				if is_weighted:
					# 加权维诺：距离除以权重，权重越大势力越大
					d /= (s.weight * s.weight)

				if d < d_min:
					d_min = d
					nearest = si

			_owner_grid[gy * _grid_w + gx] = nearest

加权维诺图： 标准维诺图下所有种子"势力均等"。加权模式下，种子权重越大，在距离比较中"看起来更近"，占据区域越大。此时区域边界也从直线变为双曲线弧。

渲染到纹理

计算完成后，将归属信息渲染到 Image 纹理，并检测区域边界。

# voronoi_render.gd
# 将维诺计算结果渲染到 Image 纹理

var _voronoi_image: Image
var _voronoi_texture: ImageTexture

const BG_COLOR := Color(0.12, 0.12, 0.16)


func render_to_texture(seeds: Array[Dictionary], owner_grid: PackedInt32Array) -> ImageTexture:
	_image = Image.create(DIAGRAM_W, DIAGRAM_H, false, Image.FORMAT_RGBA8)
	_texture = ImageTexture.create_from_image(_image)

	for gy in range(_grid_h):
		for gx in range(_grid_w):
			var owner_idx: int = owner_grid[gy * _grid_w + gx]
			var color: Color = BG_COLOR if owner_idx < 0 else seeds[owner_idx].color

			# 填充 SAMPLE_STEP × SAMPLE_STEP 像素块
			var px := gx * SAMPLE_STEP
			var py := gy * SAMPLE_STEP
			for dx in range(SAMPLE_STEP):
				for dy in range(SAMPLE_STEP):
					_image.set_pixel(px + dx, py + dy, color)

	_texture.update(_image)
	return _texture


func _draw() -> void:
	# 1. 绘制纹理
	draw_texture(_texture, Vector2(30, 50))

	# 2. 绘制边界线（相邻格子种子不同则画线）
	var sw := _grid_w
	var sh := _grid_h

	for gy in range(sh):
		for gx in range(sw):
			var idx := gy * sw + gx
			var owner_idx: int = owner_grid[idx]
			if owner_idx < 0:
				continue

			var px := 30.0 + gx * SAMPLE_STEP
			var py := 50.0 + gy * SAMPLE_STEP

			# 上方不同 → 水平边界线
			if gy > 0 and owner_grid[(gy - 1) * sw + gx] != owner_idx:
				draw_line(Vector2(px, py), Vector2(px + SAMPLE_STEP, py), Color.BLACK, 1.5)
			# 左方不同 → 垂直边界线
			if gx > 0 and owner_grid[gy * sw + (gx - 1)] != owner_idx:
				draw_line(Vector2(px, py), Vector2(px, py + SAMPLE_STEP), Color.BLACK, 1.5)

	# 3. 绘制种子点
	for sd in seeds:
		var sp: Vector2 = Vector2(30, 50) + sd.pos
		draw_circle(sp, 6, Color(1, 1, 1, 0.9))     # 白色描边
		draw_circle(sp, 5, sd.color)                 # 种子色

交互控制

# 交互处理（在 _input 中调用）
func handle_input(event: InputEvent, seeds: Array[Dictionary], diagram_pos: Vector2) -> void:
	if not (event is InputEventMouseButton and event.pressed):
		return

	var pos: Vector2 = event.position - diagram_pos
	var in_diagram: bool = pos.x >= 0 and pos.x < DIAGRAM_W and pos.y >= 0 and pos.y < DIAGRAM_H

	match event.button_index:
		MOUSE_BUTTON_LEFT:
			# 在点击位置添加一个种子
			if in_diagram:
				seeds.append({
					pos = pos,
					weight = randf_range(0.5, 2.0),
					color = SEED_COLORS[seeds.size() % SEED_COLORS.size()]
				})
				update()

		MOUSE_BUTTON_RIGHT:
			# 删除点击位置最近的种子
			if in_diagram and not seeds.is_empty():
				var nearest := -1
				var d_min := INF
				for si in seeds.size():
					var d: float = pos.distance_squared_to(seeds[si].pos)
					if d < d_min:
						d_min = d
						nearest = si
				if nearest >= 0 and d_min < 400.0:
					seeds.remove_at(nearest)
					update()

		MOUSE_BUTTON_WHEEL_UP:
			regenerate(seeds.size() + 5)
		MOUSE_BUTTON_WHEEL_DOWN:
			regenerate(seeds.size() - 5)

性能与优化建议

暴力距离场法的复杂度为 O(采样格数 × 种子数)。在 720×440、采样步长 4（180×110 = 19800 个采样格）、50 个种子的典型配置下，单次计算约 50ms，适合交互式使用。

策略	说明	适用场景
预计算	地图加载时一次生成，运行时只查询	静态地图
GDExtension	核心算法迁移到 C++	种子 > 1000
分块生成	只生成玩家周围区域	开放世界
Shader 替代	视觉图案直接用 Worley 噪声 Shader	纯视觉效果

在线演示

• 泊松圆盘采样 / 随机采样切换
• 标准维诺 / 加权维诺切换
• 20 种区分色 + 黑色边界线渲染

操作说明：左键添加种子 | 右键删除最近 | 滚轮增减数量 | R 随机生成 | W 切换加权模式 | P 切换泊松采样