三消（上）：网格、交换与匹配算法

const EMPTY := -1             ## 空格（刚被消掉，还没补上）
const RAINBOW := 99           ## 同色炸弹没有颜色，用一个不会参与匹配的值表示
const NO_CELL := Vector2i(-1, -1)

enum Special { NONE, LINE_H, LINE_V, BOMB, COLOR }

var width := 8
var height := 8
var kinds := 6                ## 宝石颜色种类数
var specials_enabled := true
## 一维数组存二维棋盘：格子 (x, y) 的下标是 y * width + x
var cells := PackedInt32Array()     # 每格的颜色 0..kinds-1，EMPTY 或 RAINBOW
var special := PackedInt32Array()   # 每格的特殊类型 Special
var rng := RandomNumberGenerator.new()   # 自己的随机数发生器：种子相同，整局就完全相同


func _init(w := 8, h := 8, k := 6, seed_value := 1) -> void:
	width = w
	height = h
	kinds = k
	rng.seed = seed_value
	cells.resize(w * h)
	cells.fill(EMPTY)
	special.resize(w * h)
	special.fill(Special.NONE)

func _test_scan_and_merge() -> void:
	var b := _board_from([
		"11123",
		"45163",
		"23145",
		"54321",
	])
	var groups := b.find_matches()
	_check(groups.size() == 1, "L 形应合并成 1 组，实际 %d 组" % groups.size())
	if groups.size() == 1:
		var g: Dictionary = groups[0]
		_check(g.cells.size() == 5, "L 形 5 格（拐点只算一次），实际 %d" % g.cells.size())
		_check(g.corner == Vector2i(2, 0), "拐点应是 (2,0)，实际 %s" % g.corner)
		_check(b.classify(g) == Board.Special.BOMB, "L 形应生成范围炸弹")
	var line5 := _board_from(["22222", "13131", "31313"])
	_check(b.classify(line5.find_matches()[0]) == Board.Special.COLOR, "5 连应生成同色炸弹")
	var line4 := _board_from(["1", "1", "1", "1", "2"])
	_check(line4.classify(line4.find_matches()[0]) == Board.Special.LINE_V, "竖 4 连应生成竖向直线炸弹")

## 格子 → 像素：格子中心点。
func cell_to_pixel(c: Vector2i) -> Vector2:
	return (Vector2(c) + Vector2(0.5, 0.5)) * cell_size


## 像素 → 格子：除以格子大小再向下取整。负数也要向下取整，所以用 floori 而不是 int()。
func pixel_to_cell(p: Vector2) -> Vector2i:
	return Vector2i(floori(p.x / cell_size), floori(p.y / cell_size))

## 用 _unhandled_input 而不是 _input：HUD 上的按钮先处理点击，没被界面吃掉的才轮到棋盘。
## 触屏在 Web 和手机上默认会被模拟成鼠标事件（emulate_mouse_from_touch），所以只处理鼠标即可。
func _unhandled_input(event: InputEvent) -> void:
	if event is InputEventMouseButton and event.button_index == MOUSE_BUTTON_LEFT:
		var local := view.make_input_local(event) as InputEventMouseButton   # 换算到棋盘坐标
		if event.pressed:
			_on_press(view.pixel_to_cell(local.position), local.position)
		else:
			_drag_from = Board.NO_CELL
	elif event is InputEventMouseMotion and _drag_from != Board.NO_CELL:
		var local := view.make_input_local(event) as InputEventMouseMotion
		_on_drag(local.position)


func _on_press(cell: Vector2i, pos: Vector2) -> void:
	if _busy or _game_over or not board.in_bounds(cell):
		_selected = Board.NO_CELL
		overlay.selected = _selected
		return
	_idle = 0.0
	if _selected != Board.NO_CELL and board.is_adjacent(_selected, cell):
		var from := _selected      # 第二次点击：和已选中的相邻格交换
		_selected = Board.NO_CELL
		overlay.selected = _selected
		_play_turn(from, cell)
		return
	_selected = cell               # 第一次点击：选中，同时准备拖动
	overlay.selected = cell
	_drag_from = cell
	_drag_start = pos


## 拖动：位移超过阈值后，按 |dx| 和 |dy| 谁大决定方向，只取上下左右四个方向之一。
func _on_drag(pos: Vector2) -> void:
	var d := pos - _drag_start
	if d.length() < view.cell_size * drag_threshold:
		return
	var dir := Vector2i(signi(roundi(d.x)), 0) if absf(d.x) > absf(d.y) else Vector2i(0, signi(roundi(d.y)))
	var from := _drag_from
	_drag_from = Board.NO_CELL
	if board.in_bounds(from + dir) and not _busy:
		_selected = Board.NO_CELL
		overlay.selected = _selected
		_play_turn(from, from + dir)

## 判断交换 a、b 之后能不能形成消除（不真的改棋盘：换过去、看一眼、换回来）。
func is_valid_swap(a: Vector2i, b: Vector2i) -> bool:
	if not (in_bounds(a) and in_bounds(b) and is_adjacent(a, b)):
		return false
	if kind_at(a) == RAINBOW or kind_at(b) == RAINBOW:
		return true                 # 同色炸弹和谁换都能炸
	if kind_at(a) == kind_at(b):
		return false
	swap(a, b)
	var ok := _match_through(a) or _match_through(b)
	swap(a, b)
	return ok


## 只看经过 c 的那一横一竖：往两边数同色，加上自己 ≥ 3 就是三连。
func _match_through(c: Vector2i) -> bool:
	var k := kind_at(c)
	if not _matchable(k):
		return false
	var h := 1 + _count(c, Vector2i.LEFT, k) + _count(c, Vector2i.RIGHT, k)
	var v := 1 + _count(c, Vector2i.UP, k) + _count(c, Vector2i.DOWN, k)
	return h >= 3 or v >= 3


func _count(c: Vector2i, dir: Vector2i, k: int) -> int:
	var n := 0
	var p := c + dir
	while kind_at(p) == k:
		n += 1
		p += dir
	return n

## 扫描所有横向、纵向长度 ≥ 3 的同色连续段（run）。
## 每一行、每一列各走一遍，每个格子被看两次，复杂度 O(W·H)。
func find_runs() -> Array[Dictionary]:
	var runs: Array[Dictionary] = []
	for y in height:
		_scan_line(Vector2i(0, y), Vector2i.RIGHT, width, true, runs)
	for x in width:
		_scan_line(Vector2i(x, 0), Vector2i.DOWN, height, false, runs)
	return runs


## 沿 step 方向走 length 格，用"段起点 + 段终点"两个下标找连续段。
func _scan_line(start: Vector2i, step: Vector2i, length: int, horizontal: bool, runs: Array[Dictionary]) -> void:
	var i := 0
	while i < length:
		var k := cells[idx(start + step * i)]
		var j := i + 1
		while j < length and cells[idx(start + step * j)] == k:
			j += 1
		# [i, j) 是一段同色，长度 j - i
		if j - i >= 3 and _matchable(k):
			var run: Array[Vector2i] = []
			for t in range(i, j):
				run.append(start + step * t)
			runs.append({"cells": run, "kind": k, "horizontal": horizontal})
		i = j    # 直接跳到下一段，不回头

## 把共享格子的连续段合并成一组：L 形、T 形、十字形都是"一横一竖"共用一个格子。
## 组里的格子用 Dictionary 当集合存（键是 Vector2i，值随便），同一个格子只会出现一次。
## 返回 Array[Dictionary]：{cells: {Vector2i: true}, kind, h, v, longest, corner}
func find_matches() -> Array[Dictionary]:
	var groups: Array[Dictionary] = []
	for run in find_runs():
		var merged := {"cells": {}, "kind": run.kind, "h": 0, "v": 0, "longest": 0, "corner": NO_CELL}
		for g in groups.duplicate():
			if _shares_cell(g.cells, run.cells):
				_absorb(merged, g)
				groups.erase(g)
		for c: Vector2i in run.cells:
			if merged.cells.has(c):
				merged.corner = c      # 这个格子同时属于横段和竖段：L/T 的拐点
			merged.cells[c] = true
		merged.h += 1 if run.horizontal else 0
		merged.v += 0 if run.horizontal else 1
		merged.longest = maxi(merged.longest, run.cells.size())
		groups.append(merged)
	return groups


func _shares_cell(set_a: Dictionary, run_cells: Array[Vector2i]) -> bool:
	for c in run_cells:
		if set_a.has(c):
			return true
	return false


func _absorb(into: Dictionary, g: Dictionary) -> void:
	into.cells.merge(g.cells)
	into.h += g.h
	into.v += g.v
	into.longest = maxi(into.longest, g.longest)
	if g.corner != NO_CELL:
		into.corner = g.corner

## 根据组的形状决定生成哪种特殊宝石。优先级：5 连 > L/T > 4 连。
func classify(g: Dictionary) -> int:
	if g.longest >= 5:
		return Special.COLOR
	if g.h > 0 and g.v > 0:
		return Special.BOMB
	if g.longest == 4:
		return Special.LINE_H if g.h > 0 else Special.LINE_V
	return Special.NONE

## 生成一个开局就没有三连的棋盘。按从左到右、从上到下的顺序填：
## 填 (x, y) 时只有左边两格和上面两格已经确定，所以只要避开
## "左边两格同色"和"上面两格同色"的那个颜色，就不可能凑成三连。
## 每格最多排除 2 种颜色，kinds ≥ 3 时一定有得选。
func fill_without_matches() -> void:
	for attempt in 100:
		for y in height:
			for x in width:
				var banned: Array[int] = []
				if x >= 2 and cells[idx(Vector2i(x - 1, y))] == cells[idx(Vector2i(x - 2, y))]:
					banned.append(cells[idx(Vector2i(x - 1, y))])
				if y >= 2 and cells[idx(Vector2i(x, y - 1))] == cells[idx(Vector2i(x, y - 2))]:
					banned.append(cells[idx(Vector2i(x, y - 1))])
				var choices: Array[int] = []
				for k in kinds:
					if k not in banned:
						choices.append(k)
				cells[idx(Vector2i(x, y))] = choices[rng.randi_range(0, choices.size() - 1)]
				special[idx(Vector2i(x, y))] = Special.NONE
		# 没有三连还不够：开局至少要有一步能走，否则重新生成
		if not find_valid_moves().is_empty():
			return

## 所有可行的交换。每个格子只试"右"和"下"两个方向，避免同一对算两次。
func find_valid_moves() -> Array[Array]:
	var moves: Array[Array] = []
	for y in height:
		for x in width:
			var a := Vector2i(x, y)
			for d in [Vector2i.RIGHT, Vector2i.DOWN]:
				if is_valid_swap(a, a + d):
					moves.append([a, a + d])
	return moves

## 提示一步：从所有可行步里随机挑一个（用特效专用的随机数，不影响棋盘的随机序列）。
func _show_hint() -> void:
	var moves := board.find_valid_moves()
	if not moves.is_empty():
		_set_hint(moves[_fx_rng.randi_range(0, moves.size() - 1)])