# WFC系统基本设计 Rust重写设计文档 - 基于 petgraph
> 作者: amazcuter
> 日期: 2025-01-25
> 版本: 1.2 - 添加方向处理解决方案
## 概述
本文档描述了如何使用 Rust 和 petgraph 库重新实现现有的 C++ WFC（Wave Function Collapse）系统。主要涉及将原始的基于裸指针的设计转换为基于 petgraph 的类型安全设计。
**重要更新 (v1.2)**: 本版本解决了WFC算法中关键的方向识别问题，采用基于有向图和索引顺序的解决方案。
## 设计目标
1. **类型安全**: 消除裸指针，使用 Rust 的类型系统确保内存安全
2. **性能优化**: 利用 petgraph 的优化图算法
3. **可维护性**: 提供清晰的API接口，便于理解和扩展
4. **向后兼容**: 保持与原有C++代码类似的使用模式
5. **泛型支持**: 保持原有C++模板的灵活性
6. **方向感知**: 支持WFC算法所需的方向性约束检查
## 方向处理解决方案
### 问题背景
WFC算法需要知道单元格之间的连接方向（如北、南、东、西），以便进行正确的约束传播。原始C++代码通过指针和自定义逻辑处理方向，但petgraph作为通用图库，不直接提供方向信息。
### 方案选择过程
我们考虑了以下几种方案：
#### 1. 邻居顺序约定 ❌
**思路**: 利用`neighbors()`返回的顺序作为方向
**问题**: petgraph的邻居迭代顺序虽然稳定，但不能提供语义化的方向信息
#### 2. 边数据存储方向 ❌
**思路**: 在边上存储方向信息
**问题**: 增加复杂性，违背极简设计原则
#### 3. 外部方向映射 ❌
**思路**: 维护从EdgeIndex到方向的HashMap
**问题**: 增加内存开销和同步复杂性
#### 4. 应用层方向协议 ❌
**思路**: 库只提供图结构，应用层处理方向
**问题**: 推卸责任，不利于代码复用
#### 5. **基于有向图的索引方案** ✅ **(最终选择)**
### 最终方案详解
#### 核心思想
**重要概念澄清**：WFC系统本质上只需要**无向连接**（双向可达），我们使用有向图单向边是一种**方向识别的技术手段**，而不是因为网格本身需要有向连接。
1. **WFC网格的本质**：所有连接都是双向的，单元格A能到达B，B也能到达A
2. **技术实现策略**：使用有向图的单向边，通过边创建顺序来标记方向信息
3. **物理实现方式**：每个逻辑上的无向连接，用两条相对的有向边来表示
4. **方向识别机制**：利用petgraph有向图中邻居按**插入逆序**返回的特性
具体实现：
1. **使用有向图**: 从`Graph<Cell, GraphEdge, Undirected>`改为`Graph<Cell, GraphEdge, Directed>`
2. **双边创建**: 每个无向连接创建两条有向边：A→B 和 B→A
3. **有序创建**: 按固定的方向顺序创建边（如：东、南、西、北）
4. **方向推断**: 通过边的创建顺序和petgraph的逆序返回特性来识别方向
**重要澄清**: 虽然底层使用有向图和单向边，但这不意味着网格连接是单向的。对于需要双向连接的网格（如二维网格），应用层需要创建**双向的边对**来模拟无向连接。例如：
```rust
// 对于需要双向连接的单元格A和B，需要创建两条边：
grid.create_edge(cell_a, cell_b)?; // A -> B
grid.create_edge(cell_b, cell_a)?; // B -> A
```
**核心设计原理**: WFC系统本质上需要无向连接，但我们使用有向图的单向边来实现方向识别。因此，**每个逻辑连接都必须创建两条物理边**：
```rust
// 为无向连接AB创建两条有向边
grid.create_edge(cell_a, cell_b)?; // A → B (A的某个方向指向B)
grid.create_edge(cell_b, cell_a)?; // B → A (B的相应方向指向A)
```
**方向识别的工作原理**：
1. **无向连接的本质**：WFC网格中任何两个相邻单元格都是双向可达的
2. **有向边的作用**：仅用于通过创建顺序标记方向信息
3. **边对的必要性**：每个无向连接必须用边对表示，确保双向可达性
4. **顺序的重要性**：按固定方向顺序创建边（如东、南），利用petgraph逆序返回特性识别方向
**技术优势**：
1. 每个方向的连接都有明确的创建顺序和识别机制
2. 保持WFC算法需要的完整邻居信息
3. 零额外内存开销存储方向信息
4. 支持灵活的网格拓扑结构
#### 技术原理
petgraph在有向图中，`neighbors()`方法返回的邻居顺序遵循以下规律：
- **插入逆序**: 最后添加的边对应的邻居最先返回
- **稳定性**: 相同的图结构总是返回相同的顺序
- **确定性**: 顺序完全由边的添加顺序决定
**WFC系统中的应用**：
1. **边对创建**：每个无向连接创建两条有向边
2. **方向标记**：通过固定的边创建顺序（如东、南）来标记方向
3. **方向识别**：通过`neighbors()`的逆序返回和预定义的索引映射来识别方向
4. **双向可达**：确保WFC算法能够在任意方向上进行约束传播
#### 实现细节
```rust
use petgraph::{Graph, NodeIndex, EdgeIndex, Directed};
// 修改图类型为有向图
pub type WFCGraph = Graph<Cell, GraphEdge, Directed>;
impl GridSystem {
// 创建单向边，用于构建无向连接的一半
// 注意：每个WFC连接都需要调用两次此方法创建边对
pub fn create_edge(&mut self, from: CellId, to: CellId) -> Result<EdgeId, GridError> {
if from == to {
return Err(GridError::SelfLoop);
}
// 检查边是否已存在
if self.graph.find_edge(from, to).is_some() {
return Err(GridError::EdgeAlreadyExists);
}
// 创建单向边，方向从from指向to
// 这是无向连接的一半，还需要创建反向边to->from
let edge_id = self.graph.add_edge(from, to, ());
Ok(edge_id)
}
// 获取邻居，返回顺序用于方向识别
pub fn get_neighbors(&self, cell_id: CellId) -> Vec<CellId> {
// 返回该节点所有出边的目标节点
// 顺序为插入的逆序，用于WFC方向识别
self.graph.neighbors(cell_id).collect()
}
}
```
#### 方向约定
为了实现方向感知，我们需要与应用层约定边的创建顺序：
```rust
// 示例：构建2D网格时的边创建顺序约定
// 假设我们有一个3x3网格，坐标如下：
// (0,0) (1,0) (2,0)
// (0,1) (1,1) (2,1)
// (0,2) (1,2) (2,2)
// 对于每个单元格，按照固定顺序创建边：
// 1. 东边 (→)
// 2. 南边 (↓)
// 这样neighbors()返回的顺序就是：[南邻居, 东邻居] (逆序)
fn build_2d_grid_with_directions(&mut self, width: usize, height: usize) -> Result<Vec<Vec<CellId>>, GridError> {
let mut cells = vec![vec![]; height];
// 创建所有单元格
for y in 0..height {
for x in 0..width {
let cell_id = self.add_cell(());
cells[y].push(cell_id);
}
}
// 按约定顺序创建双向边
for y in 0..height {
for x in 0..width {
let current = cells[y][x];
// 1. 创建东向双向连接（如果有东邻居）
if x + 1 < width {
let east_neighbor = cells[y][x + 1];
self.create_edge(current, east_neighbor)?; // 东向
self.create_edge(east_neighbor, current)?; // 西向
}
// 2. 创建南向双向连接（如果有南邻居）
if y + 1 < height {
let south_neighbor = cells[y + 1][x];
self.create_edge(current, south_neighbor)?; // 南向
self.create_edge(south_neighbor, current)?; // 北向
}
}
}
Ok(cells)
}
// 基于方向获取特定邻居 - 新增的方向感知API
pub fn get_neighbor_by_direction<D>(&self, cell_id: CellId, direction: D) -> Option<CellId>
where
D: DirectionTrait
{
let neighbors = self.get_neighbors(cell_id);
// 根据方向trait的索引映射获取邻居
if let Some(index) = direction.to_neighbor_index() {
neighbors.get(index).copied()
} else {
// 如果索引映射返回None，可能需要反向查找
self.find_incoming_neighbor_by_direction(cell_id, direction)
}
}
// 查找反向邻居（指向当前节点的邻居）
fn find_incoming_neighbor_by_direction<D>(&self, cell_id: CellId, direction: D) -> Option<CellId>
where
D: DirectionTrait
{
// 对于需要反向查找的方向，遍历所有节点
for node_id in self.graph.node_indices() {
let neighbors = self.get_neighbors(node_id);
// 检查该节点是否通过特定方向指向当前节点
if let Some(opposite_direction) = direction.opposite() {
if let Some(index) = opposite_direction.to_neighbor_index() {
if let Some(&neighbor) = neighbors.get(index) {
if neighbor == cell_id {
return Some(node_id);
}
}
}
}
}
None
}
// 查找边 - 支持单向查找
pub fn find_edge(&self, from: CellId, to: CellId) -> Option<EdgeId> {
self.graph.find_edge(from, to)
}
// 获取所有单元格
pub fn get_all_cells(&self) -> impl Iterator<Item = CellId> + '_ {
self.graph.node_indices()
}
// 获取单元格数量
pub fn get_cells_count(&self) -> usize {
self.graph.node_count()
}
// 获取边数量
pub fn get_edges_count(&self) -> usize {
self.graph.edge_count()
}
// 添加命名查找支持（可选功能）
pub fn add_cell_with_name(&mut self, cell_data: Cell, name: String) -> CellId {
let cell_id = self.add_cell(cell_data);
self.cell_lookup.insert(name, cell_id);
cell_id
}
pub fn get_cell_by_name(&self, name: &str) -> Option<CellId> {
self.cell_lookup.get(name).copied()
}
```
## 基础概念重新设计 (WFCutil.h -> wfc_util.rs)
### 1. 类型定义重构
#### 原始 C++ 设计
```cpp
using CellID = Cell *;
template <typename EdgeData>
using TileID = Tile<EdgeData> *;
using EdgeID = GraphEdge *;
```
#### 新的 Rust 设计
```rust
use petgraph::{Graph, NodeIndex, EdgeIndex, Directed};
// 直接使用类型别名，简化设计
pub type CellId = NodeIndex;
pub type EdgeId = EdgeIndex;
pub type TileId = usize; // 基于索引的瓷砖ID
// 泛型类型别名
pub type Cells = Vec<CellId>;
pub type Tiles = Vec<TileId>;
pub type Edges = Vec<EdgeId>;
// 为WFC系统定义图类型别名 - 使用有向图
pub type WFCGraph = Graph<Cell, GraphEdge, Directed>;
// 错误处理类型 - 新增
#[derive(Debug, Clone, PartialEq)]
pub enum GridError {
/// 尝试创建自循环边
SelfLoop,
/// 边已存在
EdgeAlreadyExists,
/// 节点不存在
NodeNotFound,
/// 边不存在
EdgeNotFound,
/// 索引越界
IndexOutOfBounds,
/// 图容量不足
CapacityExhausted,
}
impl std::fmt::Display for GridError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
GridError::SelfLoop => write!(f, "Cannot create self-loop edge"),
GridError::EdgeAlreadyExists => write!(f, "Edge already exists"),
GridError::NodeNotFound => write!(f, "Node not found"),
GridError::EdgeNotFound => write!(f, "Edge not found"),
GridError::IndexOutOfBounds => write!(f, "Index out of bounds"),
GridError::CapacityExhausted => write!(f, "Graph capacity exhausted"),
}
}
}
impl std::error::Error for GridError {}
```
### 2. Cell 重新设计
#### 原始 C++ 设计
```cpp
class Cell {
public:
std::list<EdgeID> cellEdge;
};
```
#### 新的 Rust 设计
```rust
// 直接使用类型别名，Cell在petgraph中作为节点数据
// 不需要存储额外信息
pub type Cell = ();
// 如果确实需要存储数据，可以定义简单的数据结构：
#[derive(Debug, Clone, Default)]
pub struct CellData {
pub id: Option<u32>,
pub name: Option<String>,
}
```
### 3. GraphEdge 重新设计
#### 原始 C++ 设计
```cpp
class GraphEdge {
public:
Link link;
CellID getAnother(CellID id);
bool operator==(const GraphEdge &other) const;
};
```
#### 新的 Rust 设计
```rust
// 直接使用类型别名，边在petgraph中作为边数据
// 边不需要存储额外信息
pub type GraphEdge = (); // 空边，连接关系由petgraph管理
// 如果确实需要存储数据，可以定义简单的数据结构：
#[derive(Debug, Clone, PartialEq)]
pub struct EdgeData {
pub weight: f64,
pub edge_type: String,
}
```
### 4. Tile 重新设计
#### 原始 C++ 设计
```cpp
template <typename EdgeData>
class Tile {
public:
int weight;
std::vector<EdgeData> edge;
bool operator==(const Tile &other) const;
};
```
#### 新的 Rust 设计
```rust
#[derive(Debug, Clone, PartialEq)]
pub struct Tile<EdgeData>
where
EdgeData: Clone + PartialEq + std::fmt::Debug
{
pub id: TileId,
pub weight: i32,
pub edges: Vec<EdgeData>,
}
impl<EdgeData> Tile<EdgeData>
where
EdgeData: Clone + PartialEq + std::fmt::Debug
{
pub fn new(id: TileId, weight: i32, edges: Vec<EdgeData>) -> Self {
Self { id, weight, edges }
}
pub fn is_compatible_with(&self, other: &Self, direction: usize) -> bool {
// 实现兼容性检查逻辑
if direction < self.edges.len() && direction < other.edges.len() {
// 简单的边匹配检查，可以根据具体需求扩展
self.edges[direction] == other.edges[direction]
} else {
false
}
}
pub fn get_edge(&self, direction: usize) -> Option<&EdgeData> {
self.edges.get(direction)
}
}
```
## 瓷砖集系统重新设计 (TileSet.h -> tile_set.rs)
### 1. TileSet 核心设计
#### 原始 C++ 设计
```cpp
template <typename EdgeData>
class TileSet {
protected:
using Tiles = std::vector<TileID<EdgeData>>;
Tiles tiles_;
public:
virtual void buildTileSet() = 0;
virtual bool judgePossibility(std::vector<Tiles> neighborPossibility, TileID<EdgeData> possibility) = 0;
void addTile(const std::vector<EdgeData>& edges, int weight);
Tiles &getAllTiles();
};
```
#### 新的 Rust 设计 - 虚函数 Trait + 具体实现
```rust
/// 瓷砖集虚函数特性 - 仅包含C++的两个虚函数
pub trait TileSetVirtual<EdgeData>
where
EdgeData: Clone + PartialEq + std::fmt::Debug
{
/// 构建瓷砖集 - 对应C++的buildTileSet()虚函数
///
/// 这个方法负责初始化和填充瓷砖集合。
/// 具体的实现由各种不同的瓷砖集类型决定。
fn build_tile_set(&mut self);
/// 判断瓷砖可能性 - 对应C++的judgePossibility()虚函数
///
/// # 参数
/// * `neighbor_possibilities` - 邻居单元格的可能瓷砖列表
/// * `candidate` - 候选瓷砖ID
///
/// # 返回值
/// * `true` - 该瓷砖在当前邻居约束下是可能的
/// * `false` - 该瓷砖与邻居约束冲突
fn judge_possibility(
&self,
neighbor_possibilities: &[Vec<TileId>],
candidate: TileId
) -> bool;
}
/// 瓷砖集具体实现 - 包含所有固定方法和数据存储
#[derive(Debug, Clone)]
pub struct TileSet<EdgeData>
where
EdgeData: Clone + PartialEq + std::fmt::Debug
{
/// 瓷砖列表 - 对应C++的tiles_成员
tiles: Vec<Tile<EdgeData>>,
}
impl<EdgeData> TileSet<EdgeData>
where
EdgeData: Clone + PartialEq + std::fmt::Debug
{
/// 创建新的瓷砖集
pub fn new() -> Self {
Self {
tiles: Vec::new(),
}
}
/// 添加瓷砖 - 对应C++的addTile方法
///
/// # 参数
/// * `edges` - 边数据列表
/// * `weight` - 瓷砖权重
///
/// # 返回值
/// * 新创建瓷砖的ID
pub fn add_tile(&mut self, edges: Vec<EdgeData>, weight: i32) -> TileId {
let tile_id = self.tiles.len();
let tile = Tile::new(tile_id, weight, edges);
self.tiles.push(tile);
tile_id
}
/// 获取所有瓷砖 - 对应C++的getAllTiles()方法
pub fn get_all_tiles(&self) -> &[Tile<EdgeData>] {
&self.tiles
}
/// 获取所有瓷砖ID
pub fn get_all_tile_ids(&self) -> Vec<TileId> {
(0..self.tiles.len()).collect()
}
/// 根据ID获取瓷砖
pub fn get_tile(&self, tile_id: TileId) -> Option<&Tile<EdgeData>> {
self.tiles.get(tile_id)
}
/// 获取瓷砖数量
pub fn get_tile_count(&self) -> usize {
self.tiles.len()
}
/// 清空瓷砖集
pub fn clear(&mut self) {
self.tiles.clear();
}
}
```
### 2. 使用示例
以下是如何使用新的瓷砖集系统：
```rust
// 示例：具体的瓷砖集实现
struct MyTileSet {
tiles: TileSet<&'static str>,
}
impl MyTileSet {
pub fn new() -> Self {
Self {
tiles: TileSet::new(),
}
}
}
// 只需要实现两个虚函数
impl TileSetVirtual<&'static str> for MyTileSet {
fn build_tile_set(&mut self) {
// 清空现有瓷砖
self.tiles.clear();
// 添加具体的瓷砖
self.tiles.add_tile(vec!["A", "B", "C", "D"], 10);
self.tiles.add_tile(vec!["B", "A", "D", "C"], 15);
self.tiles.add_tile(vec!["C", "D", "A", "B"], 5);
}
fn judge_possibility(
&self,
neighbor_possibilities: &[Vec<TileId>],
candidate: TileId
) -> bool {
// 实现具体的兼容性判断逻辑
if let Some(candidate_tile) = self.tiles.get_tile(candidate) {
// 检查候选瓷砖与所有邻居的兼容性
for (direction, neighbors) in neighbor_possibilities.iter().enumerate() {
for &neighbor_id in neighbors {
if let Some(neighbor_tile) = self.tiles.get_tile(neighbor_id) {
// 检查在特定方向上的边兼容性
if !candidate_tile.is_compatible_with(neighbor_tile, direction) {
return false;
}
}
}
}
true
} else {
false
}
}
}
// 对外暴露固定方法，直接代理到内部TileSet
impl MyTileSet {
pub fn add_tile(&mut self, edges: Vec<&'static str>, weight: i32) -> TileId {
self.tiles.add_tile(edges, weight)
}
pub fn get_all_tiles(&self) -> &[Tile<&'static str>] {
self.tiles.get_all_tiles()
}
pub fn get_all_tile_ids(&self) -> Vec<TileId> {
self.tiles.get_all_tile_ids()
}
pub fn get_tile(&self, tile_id: TileId) -> Option<&Tile<&'static str>> {
self.tiles.get_tile(tile_id)
}
pub fn get_tile_count(&self) -> usize {
self.tiles.get_tile_count()
}
}
// 使用示例 - 与C++使用模式完全一致
fn example_usage() {
let mut tile_set = MyTileSet::new();
// 构建瓷砖集 - 对应C++的buildTileSet()调用
tile_set.build_tile_set();
// 获取所有瓷砖 - 对应C++的getAllTiles()调用
let all_tiles = tile_set.get_all_tiles();
println!("瓷砖数量: {}", all_tiles.len());
// 判断可能性 - 对应C++的judgePossibility()调用
let neighbor_possibilities = vec![vec![0, 1], vec![1, 2]];
let is_possible = tile_set.judge_possibility(&neighbor_possibilities, 0);
println!("瓷砖0可能性: {}", is_possible);
}
```
### 3. 设计优势
#### 与C++对比的优势
1. **内存安全**: 无需手动管理瓷砖内存，避免内存泄漏
2. **类型安全**: 编译时检查，避免运行时错误
3. **精确对应**: 只有虚函数在trait中，普通方法写死在具体实现中
4. **零成本抽象**: trait方法可以被内联优化
5. **简洁设计**: 最小化trait接口，避免不必要的虚函数开销
#### 兼容性保证
1. **API一致性**: 所有C++方法都有对应的Rust实现
2. **语义一致性**: 只有真正的虚函数通过trait实现多态
3. **使用模式**: 保持与C++完全一致的初始化和使用流程
4. **性能一致性**: 普通方法直接调用，无虚函数开销
## 网格系统重新设计 (GridSystem.h -> grid_system.rs)
### 1. GridSystem 核心结构
#### 原始 C++ 设计
```cpp
class GridSystem {
protected:
CellList cells_;
CellData edgelist_;
public:
void CreateEdge(CellID cellA, CellID cellB);
Cells getNeighbor(CellID id);
GraphEdge *findEdge(CellID a, CellID b);
};
```
#### 新的 Rust 设计 - 支持方向感知
```rust
use petgraph::{Graph, Directed};
use std::collections::HashMap;
pub struct GridSystem
{
// 使用有向图作为底层图存储，支持方向识别
graph: WFCGraph,
// 可选的索引映射，用于快速查找
cell_lookup: HashMap<String, CellId>,
}
impl GridSystem {
pub fn new() -> Self {
Self {
graph: Graph::new(),
cell_lookup: HashMap::new(),
}
}
// 添加单元格 - 与C++的cells_管理类似
pub fn add_cell(&mut self, cell_data: Cell) -> CellId {
self.graph.add_node(cell_data)
}
// 创建单向边，用于构建无向连接的一半
// 注意：每个WFC连接都需要调用两次此方法创建边对
pub fn create_edge(&mut self, from: CellId, to: CellId) -> Result<EdgeId, GridError> {
if from == to {
return Err(GridError::SelfLoop);
}
// 检查边是否已存在
if self.graph.find_edge(from, to).is_some() {
return Err(GridError::EdgeAlreadyExists);
}
// 创建单向边，方向从from指向to
// 这是无向连接的一半，还需要创建反向边to->from
let edge_id = self.graph.add_edge(from, to, ());
Ok(edge_id)
}
// 获取邻居，返回顺序用于方向识别
pub fn get_neighbors(&self, cell_id: CellId) -> Vec<CellId> {
// 返回该节点所有出边的目标节点
// 顺序为插入的逆序，用于WFC方向识别
self.graph.neighbors(cell_id).collect()
}
// 基于方向获取特定邻居 - 新增的方向感知API
pub fn get_neighbor_by_direction<D>(&self, cell_id: CellId, direction: D) -> Option<CellId>
where
D: DirectionTrait
{
let neighbors = self.get_neighbors(cell_id);
// 根据方向trait的索引映射获取邻居
if let Some(index) = direction.to_neighbor_index() {
neighbors.get(index).copied()
} else {
// 如果索引映射返回None，可能需要反向查找
self.find_incoming_neighbor_by_direction(cell_id, direction)
}
}
// 查找反向邻居（指向当前节点的邻居）
fn find_incoming_neighbor_by_direction<D>(&self, cell_id: CellId, direction: D) -> Option<CellId>
where
D: DirectionTrait
{
// 对于需要反向查找的方向，遍历所有节点
for node_id in self.graph.node_indices() {
let neighbors = self.get_neighbors(node_id);
// 检查该节点是否通过特定方向指向当前节点
if let Some(opposite_direction) = direction.opposite() {
if let Some(index) = opposite_direction.to_neighbor_index() {
if let Some(&neighbor) = neighbors.get(index) {
if neighbor == cell_id {
return Some(node_id);
}
}
}
}
}
None
}
// 查找边 - 支持单向查找
pub fn find_edge(&self, from: CellId, to: CellId) -> Option<EdgeId> {
self.graph.find_edge(from, to)
}
// 获取所有单元格
pub fn get_all_cells(&self) -> impl Iterator<Item = CellId> + '_ {
self.graph.node_indices()
}
// 获取单元格数量
pub fn get_cells_count(&self) -> usize {
self.graph.node_count()
}
// 获取边数量
pub fn get_edges_count(&self) -> usize {
self.graph.edge_count()
}
// 添加命名查找支持（可选功能）
pub fn add_cell_with_name(&mut self, cell_data: Cell, name: String) -> CellId {
let cell_id = self.add_cell(cell_data);
self.cell_lookup.insert(name, cell_id);
cell_id
}
pub fn get_cell_by_name(&self, name: &str) -> Option<CellId> {
self.cell_lookup.get(name).copied()
}
}
// 方向trait定义 - 泛型设计，适配各种网格系统
pub trait DirectionTrait: Clone + Copy + PartialEq + Eq + std::hash::Hash + std::fmt::Debug {
/// 将方向转换为邻居数组的索引
///
/// 返回Some(index)表示该方向对应neighbors()返回数组中的index位置
/// 返回None表示该方向需要通过反向查找获得（即查找指向当前节点的边）
///
/// # 重要说明
///
/// 由于petgraph的neighbors()返回的是插入逆序，索引映射需要考虑这一点。
/// 例如，如果边按顺序创建为[东, 南]，neighbors()返回[南, 东]，
/// 那么东方向应该映射到索引1，南方向映射到索引0。
fn to_neighbor_index(&self) -> Option<usize>;
/// 获取相反方向
///
/// 用于反向查找时确定对应关系。例如：
/// - 北 <-> 南
/// - 东 <-> 西
/// - 对于某些特殊方向可能没有相反方向，返回None
fn opposite(&self) -> Option<Self>;
/// 获取该方向系统的所有方向
///
/// 用于枚举和验证，按照边创建的标准顺序返回
fn all_directions() -> Vec<Self>;
/// 方向的显示名称（用于调试）
fn name(&self) -> &'static str;
}
// 四方向网格的示例实现
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Direction4 {
East, // 东
South, // 南
West, // 西
North, // 北
}
impl DirectionTrait for Direction4 {
fn to_neighbor_index(&self) -> Option<usize> {
match self {
// 由于neighbors()返回逆序，且创建顺序为[东, 南]
// 所以neighbors()返回[南, 东]，映射为：
Direction4::South => Some(0), // 南在索引0
Direction4::East => Some(1), // 东在索引1
// 西和北需要反向查找
Direction4::West | Direction4::North => None,
}
}
fn opposite(&self) -> Option<Self> {
match self {
Direction4::East => Some(Direction4::West),
Direction4::West => Some(Direction4::East),
Direction4::North => Some(Direction4::South),
Direction4::South => Some(Direction4::North),
}
}
fn all_directions() -> Vec<Self> {
vec![Direction4::East, Direction4::South, Direction4::West, Direction4::North]
}
fn name(&self) -> &'static str {
match self {
Direction4::East => "East",
Direction4::South => "South",
Direction4::West => "West",
Direction4::North => "North",
}
}
}
```
### 2. 应用层集成指导
**重要设计原则**: GridSystem作为算法库，只提供核心图操作API，具体的网格构建逻辑由应用层实现。这确保了库的通用性和灵活性。
#### 应用层职责
1. **定义方向类型**: 根据具体网格类型实现`DirectionTrait`
2. **网格构建逻辑**: 实现具体的单元格创建和边连接逻辑
3. **边创建顺序**: 确保方向一致性的边创建顺序
4. **约束检查**: 基于方向实现WFC算法的约束传播
#### 边创建顺序约定
为了确保方向的正确识别，应用层必须遵循一致的边创建顺序：
```rust
// 示例：4方向网格的边创建顺序
// 对于每个单元格，按固定顺序创建出边：
// 1. 东向边 (如果有东邻居)
// 2. 南向边 (如果有南邻居)
//
// 由于petgraph返回逆序，get_neighbors()将返回：
// [南邻居, 东邻居] (如果都存在)
// 应用层实现示例
fn build_4direction_grid(grid: &mut GridSystem, width: usize, height: usize) -> Result<Vec<Vec<CellId>>, GridError> {
let mut cells = vec![vec![]; height];
// 1. 创建所有单元格
for y in 0..height {
for x in 0..width {
let cell_id = grid.add_cell(());
cells[y].push(cell_id);
}
}
// 2. 按约定顺序创建边
for y in 0..height {
for x in 0..width {
let current = cells[y][x];
// 东向边 (第一个创建)
if x + 1 < width {
let east = cells[y][x + 1];
grid.create_edge(current, east)?;
}
// 南向边 (第二个创建)
if y + 1 < height {
let south = cells[y + 1][x];
grid.create_edge(current, south)?;
}
}
}
Ok(cells)
}
```
#### 验证和调试支持
应用层可以使用库提供的调试功能来验证网格构建的正确性：
```rust
// 应用层验证示例
fn validate_grid_construction<D: DirectionTrait>(
grid: &GridSystem,
expected_directions: &[D]
) -> Result<(), Box<dyn std::error::Error>> {
// 1. 验证图结构完整性
grid.validate_structure()?;
// 2. 验证方向映射
// grid.validate_directions(expected_directions)?;
// 3. 调试打印
// grid.debug_print_grid(Some(expected_directions));
// 4. 统计信息
let stats = grid.get_statistics();
println!("Grid validation passed: {}", stats);
Ok(())
}
```
#### 方向映射的维护
当扩展到新的网格类型时，必须更新方向映射：
## 性能考虑
### 1. 内存布局优化
- petgraph 使用连续内存存储，比指针链表更缓存友好
- 避免了原来的指针追踪开销
- 类型别名避免了额外的包装器开销
- 空类型 `()` 实现零内存开销
### 2. 算法复杂度分析
- **邻居查找**: O(出度) - petgraph直接遍历出边列表
- **边查找**: O(出度) - 需要遍历源节点的所有出边
- **方向查找**: O(1) - 基于预定义的索引映射
- **内存管理**: 自动管理 vs 原来的手动 new/delete
**注意**: 实际性能取决于具体的图结构和访问模式，建议在实际应用中进行基准测试。
### 3. 类型安全收益
- 编译时检查，避免空指针解引用
- 借用检查器确保内存安全
- 零成本抽象
- 强类型化的图操作
## 迁移策略
### 阶段1: 基础类型实现
1. 实现 `wfc_util.rs` 中的基础类型别名
2. 实现基本的类型转换和操作
3. 编写单元测试验证功能正确性
### 阶段2: 网格系统实现
1. 实现 `GridSystem` 核心功能
2. 提供基础的图操作API
3. 确保API兼容性和性能
### 阶段3: 瓷砖集系统实现
1. 实现 `TileSetBuilder` 和 `PossibilityJudge` traits
2. 实现 `TileSetStorage` 和 `TileSet` 组合结构
3. 提供与C++虚函数等价的功能
4. 编写瓷砖集相关的测试
### 阶段4: 集成测试和文档
1. 与 WFCManager 集成
2. 性能基准测试
3. 内存使用分析
4. 编写完整的API文档和使用示例
## 依赖项
在 `Cargo.toml` 中添加：
```toml
[dependencies]
petgraph = "0.6"
```
## 总结
使用 petgraph 和有向图索引方案重新实现 WFC 系统的网格部分将带来以下优势：
### 核心优势
1. **方向感知能力**: 通过有向图和边创建顺序约定，实现了零开销的方向识别
2. **完全向后兼容**: 与原C++代码的API和语义保持一致
3. **极简设计**: 使用类型别名和空类型实现零开销抽象
4. **类型安全**: 完全消除指针相关的运行时错误
5. **健壮的错误处理**: 提供完整的错误类型和处理机制
### 方向处理创新
1. **零内存开销**: 不需要额外存储方向信息
2. **确定性行为**: 边的顺序完全由创建顺序决定，可预测且稳定
3. **扩展性优异**: 支持任意网格拓扑（三角形、六边形、3D等）
4. **调试友好**: 提供完整的验证和调试工具
**WFC系统专门优化**：
- **无向连接支持**：所有连接都是双向可达的，满足WFC算法需求
- **方向识别机制**：通过边创建顺序和petgraph特性实现零成本方向识别
- **边对管理**：每个逻辑连接自动管理两条物理边，确保一致性
- **约束传播友好**：为WFC算法提供完整的双向邻居信息
### 设计哲学
1. **算法库定位**: 专注于提供核心图操作，具体构建逻辑由应用层实现
2. **最小可行设计**: 只包含必要功能，避免过度工程化
3. **可组合性**: 支持灵活的组合和扩展
4. **实用主义**: 平衡理论纯粹性和实际可用性
### 🚨 **关键设计约束：边创建顺序的重要性**
#### 为什么不提供自动双向连接方法
本库**故意不提供**诸如`create_undirected_connection()`之类的便捷方法，原因如下：
**问题核心**：方向识别完全依赖于边创建的**全局一致顺序**
```rust
// ❌ 危险的自动双向连接方法（我们不提供）
pub fn create_undirected_connection(cell_a: CellId, cell_b: CellId) -> Result<(EdgeId, EdgeId), GridError> {
let edge_ab = self.create_edge(cell_a, cell_b)?; // A -> B
let edge_ba = self.create_edge(cell_b, cell_a)?; // B -> A (❌ 顺序错误！)
Ok((edge_ab, edge_ba))
}
```
**具体问题**：
1. **A单元格**：按顺序创建 `东→B, 南→C`，`neighbors(A)` 返回 `[C, B]`（逆序）
2. **B单元格**：如果B之前创建了其他边，`西→A` 的插入位置就不符合预期顺序
3. **方向识别失败**：B的邻居顺序不再符合 `Direction4` 的索引映射
#### 正确的设计模式
**应用层责任**：必须在网格构建时按**全局一致的方向顺序**创建所有边
```rust
// ✅ 正确的网格构建方式（应用层实现）
impl GridBuilder for My2DGridBuilder {
fn build_grid_system(&mut self, grid: &mut GridSystem) -> Result<(), GridError> {
// 为每个单元格按相同的方向顺序创建边
for y in 0..self.height {
for x in 0..self.width {
let current = self.cells[y][x];
// 必须按固定顺序：东、南、西、北
// 1. 东向边
if x + 1 < self.width {
grid.create_edge(current, self.cells[y][x + 1])?;
}
// 2. 南向边
if y + 1 < self.height {
grid.create_edge(current, self.cells[y + 1][x])?;
}
// 3. 西向边
if x > 0 {
grid.create_edge(current, self.cells[y][x - 1])?;
}
// 4. 北向边
if y > 0 {
grid.create_edge(current, self.cells[y - 1][x])?;
}
}
}
Ok(())
}
}
```
**结果保证**：每个单元格的 `neighbors()` 都按 `[北, 西, 南, 东]` 的顺序返回（petgraph逆序）
#### 设计原则
1. **边创建顺序不可破坏**：任何便捷方法都可能破坏全局顺序一致性
2. **应用层完全控制**：网格构建逻辑完全由 `GridBuilder` 实现负责
3. **库提供基础操作**：只提供 `create_edge()` 等基础方法
4. **错误预防胜于修复**：通过设计约束防止错误，而不是事后检测
#### 🎯 **瓷砖边数据顺序约定**
为了实现高效的兼容性检查，**瓷砖的边数据必须与 `neighbors()` 返回顺序保持一致**：
```rust
// ✅ 正确：瓷砖边数据按 neighbors() 顺序排列
let tile_edges = vec![
"北边数据", // 索引 0 - 对应 neighbors()[0]
"西边数据", // 索引 1 - 对应 neighbors()[1]
"南边数据", // 索引 2 - 对应 neighbors()[2]
"东边数据", // 索引 3 - 对应 neighbors()[3]
];
tile_set.add_tile(tile_edges, weight);
```
**索引映射关系**：
```text
网格构建顺序：东 → 南 → 西 → 北
neighbors() 返回：[北, 西, 南, 东] (逆序)
瓷砖边数据索引：[0, 1, 2, 3]
Direction4 映射：北=0, 西=1, 南=2, 东=3
```
**高效兼容性检查**：
```rust
// judge_possibility() 中可以直接索引对应
fn judge_possibility(&self, neighbor_possibilities: &[Vec<TileId>], candidate: TileId) -> bool {
let candidate_tile = self.get_tile(candidate)?;
for (direction_index, neighbor_tiles) in neighbor_possibilities.iter().enumerate() {
let candidate_edge = &candidate_tile.edges[direction_index]; // 🎯 直接对应！
for &neighbor_id in neighbor_tiles {
let neighbor_tile = self.get_tile(neighbor_id)?;
let neighbor_opposite_index = get_opposite_direction_index(direction_index);
let neighbor_edge = &neighbor_tile.edges[neighbor_opposite_index];
if candidate_edge != neighbor_edge { // 边兼容性检查
return false;
}
}
}
true
}
```
### 技术亮点
1. **利用petgraph稳定特性**: 充分利用有向图邻居返回逆序的稳定行为
2. **双向连接支持**: 通过边对实现真正的双向连接
3. **完备的trait系统**: DirectionTrait提供灵活的方向抽象，TileSet统一接口完美替代C++虚函数
4. **统一设计**: 瓷砖集系统使用单一trait接口，保持概念的整体性
5. **零成本抽象**: trait方法内联优化，保持性能的同时提供灵活性
6. **全面的错误处理**: 从编译时到运行时的多层次错误防护
### 已解决的设计问题 ✅
- **错误类型**: 完整定义了GridError及其错误处理
- **petgraph行为**: 验证并正确利用了neighbors的逆序特性
- **双向连接**: 澄清了单向边vs双向连接的概念区别
- **性能声称**: 提供了客观的复杂度分析，避免无根据的性能声称
- **接口设计**: 简化并文档化了DirectionTrait，提供了完整示例
- **虚函数替代**: 通过trait系统完美替代C++虚函数，保持多态性和扩展性
- **内存管理**: 消除手动内存管理，避免C++中的内存泄漏问题
该设计成功实现了极简的代码结构，解决了WFC算法中的关键方向识别问题和虚函数替代问题，同时保持了与原有C++代码的完全兼容性。通过创新的索引方案、trait组合设计和完善的错误处理，我们实现了性能、简洁性、可靠性和功能性的完美平衡。
**瓷砖集系统创新点**:
- **精确虚函数映射**: 只有真正的虚函数在trait中，完美对应C++设计
- **性能优化**: 普通方法直接实现，避免不必要的动态分发开销
- **类型安全替代**: 提供比C++虚函数更强的编译时类型检查
- **最小化接口**: trait只包含必要的虚函数，保持设计简洁
- **内存安全**: 完全消除手动内存管理和潜在的内存泄漏风险
## 完整使用示例
以下是一个端到端的使用示例，展示如何使用新设计构建2D网格并进行方向查询：
```rust
use petgraph::{Graph, Directed};
use std::collections::HashMap;
// 完整的使用示例
fn main() -> Result<(), Box<dyn std::error::Error>> {
// 1. 创建网格系统
let mut grid = GridSystem::new();
// 2. 构建3x3双向网格
let cells = build_2d_grid_with_bidirectional_edges(&mut grid, 3, 3)?;
// 3. 测试中心单元格的所有方向
let center_cell = cells[1][1]; // 中心位置(1,1)
println!("=== 完整方向查询测试 ===");
// 现在所有方向都应该能找到邻居
if let Some(east) = grid.get_neighbor_by_direction(center_cell, Direction4::East) {
println!("东邻居: {:?}", east); // 应该是 cells[1][2]
}
if let Some(south) = grid.get_neighbor_by_direction(center_cell, Direction4::South) {
println!("南邻居: {:?}", south); // 应该是 cells[2][1]
}
if let Some(west) = grid.get_neighbor_by_direction(center_cell, Direction4::West) {
println!("西邻居: {:?}", west); // 应该是 cells[1][0] (通过反向查找)
}
if let Some(north) = grid.get_neighbor_by_direction(center_cell, Direction4::North) {
println!("北邻居: {:?}", north); // 应该是 cells[0][1] (通过反向查找)
}
// 4. 验证边的方向性
println!("=== 边创建顺序验证 ===");
let direct_neighbors = grid.get_neighbors(center_cell);
println!("直接邻居 (创建顺序的逆序): {:?}", direct_neighbors);
// 应该显示：[南邻居, 东邻居] (因为创建顺序是东, 南)
// 5. 验证网格统计
println!("=== 网格统计 ===");
println!("节点数: {}", grid.get_cells_count()); // 应该是 9
println!("边数: {}", grid.get_edges_count()); // 应该是 24 (12条连接 × 2方向)
Ok(())
}
// 构建带方向的2D网格（支持双向连接）
fn build_2d_grid_with_bidirectional_edges(
grid: &mut GridSystem,
width: usize,
height: usize
) -> Result<Vec<Vec<CellId>>, GridError> {
let mut cells = vec![vec![]; height];
// 1. 创建所有单元格
for y in 0..height {
for x in 0..width {
let cell_id = grid.add_cell(());
cells[y].push(cell_id);
}
}
// 2. 创建双向边（每个连接创建两条边）
for y in 0..height {
for x in 0..width {
let current = cells[y][x];
// 东向连接（双向）
if x + 1 < width {
let east = cells[y][x + 1];
grid.create_edge(current, east)?; // A -> B (东向)
grid.create_edge(east, current)?; // B -> A (西向)
}
// 南向连接（双向）
if y + 1 < height {
let south = cells[y + 1][x];
grid.create_edge(current, south)?; // A -> B (南向)
grid.create_edge(south, current)?; // B -> A (北向)
}
}
}
Ok(cells)
}
// 网格验证和调试工具
impl GridSystem {
/// 验证网格结构的完整性
pub fn validate_structure(&self) -> Result<(), GridError> {
// 验证所有边的端点都存在
for edge_id in self.graph.edge_indices() {
if let Some((source, target)) = self.graph.edge_endpoints(edge_id) {
if !self.graph.node_indices().any(|n| n == source) {
return Err(GridError::NodeNotFound);
}
if !self.graph.node_indices().any(|n| n == target) {
return Err(GridError::NodeNotFound);
}
}
}
Ok(())
}
/// 获取网格统计信息
pub fn get_statistics(&self) -> String {
format!(
"GridSystem Statistics:\n Nodes: {}\n Edges: {}\n Capacity: {:?}",
self.get_cells_count(),
self.get_edges_count(),
self.graph.capacity()
)
}
/// 调试打印网格信息
pub fn debug_print_neighbors(&self, cell_id: CellId) {
println!("Cell {:?} neighbors:", cell_id);
let neighbors = self.get_neighbors(cell_id);
for (i, neighbor) in neighbors.iter().enumerate() {
println!(" [{}]: {:?}", i, neighbor);
}
// 测试方向查询
for direction in Direction4::all_directions() {
if let Some(neighbor) = self.get_neighbor_by_direction(cell_id, direction) {
println!(" {}: {:?}", direction.name(), neighbor);
} else {
println!(" {}: None", direction.name());
}
}
}
}