Quake地图编译器中图数据结构的名称及Rust实现替代方案咨询

1. 该数据结构的特定名称 #

这个结构本质上是带双向链表边的无向图，是Quake引擎为BSP树门户遍历、场景裁剪等需求定制的变体邻接表结构——每条边（Portal）不仅记录连接的两个节点（Node），还为每个节点维护了指向同节点其他边的链表指针（nexts数组）。它没有通用的标准学术名称，通常可称为门户连接图（Portal Connection Graph）或双向邻接链表图。

2. Rust中的实现方案与替代方案 #

受Rust所有权机制限制，无法直接复刻C++裸指针链表的写法，但可以通过以下方式保留原结构的核心特性（快速分离/插入门户、访问对侧节点）：

方案1：索引替代指针（最推荐） #

用整数索引代替裸指针，将Node和Portal存储在全局Vec中，通过索引关联：

#[derive(Debug)]
struct Node {
    first_portal: Option<usize>, // 指向首个Portal的索引
    // 其他节点属性
}

#[derive(Debug)]
struct Portal {
    nodes: [usize; 2], // 连接的两个Node索引
    nexts: [Option<usize>; 2], // 每个节点侧的下一个Portal索引
    // 其他门户属性
}

struct PortalGraph {
    nodes: Vec<Node>,
    portals: Vec<Portal>,
}

impl PortalGraph {
    // 遍历指定节点的所有门户
    fn iterate_portals(&self, node_idx: usize) -> impl Iterator<Item = &Portal> {
        let mut current_portal = self.nodes[node_idx].first_portal;
        std::iter::from_fn(move || {
            current_portal.map(|idx| {
                let portal = &self.portals[idx];
                let side = if portal.nodes[0] == node_idx { 0 } else { 1 };
                current_portal = portal.nexts[side];
                portal
            })
        })
    }
}

该方案完全符合Rust安全规则，且保留了原结构的遍历、插入/删除效率，是生产环境的首选。

方案2：智能指针实现动态结构 #

若需更灵活的内存管理，可使用Rc<RefCell<T>>实现共享可变：

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct Node {
    portals: Option<Rc<RefCell<Portal>>>,
    // 其他节点属性
}

#[derive(Debug)]
struct Portal {
    nodes: [Rc<RefCell<Node>>; 2],
    nexts: [Option<Rc<RefCell<Portal>>>; 2],
    // 其他门户属性
}

注意需配合Weak指针避免循环引用，该方案会引入运行时借用检查开销，适合动态性要求高但性能压力较小的场景。

方案3：借助第三方图库 #

使用petgraph等成熟图结构库快速实现，无需手动维护底层关联：

use petgraph::graph::{Graph, NodeIndex};

#[derive(Debug)]
struct NodeData { /* 节点属性 */ }

#[derive(Debug)]
struct PortalData { /* 门户属性 */ }

// 创建门户图
let mut graph = Graph::<NodeData, PortalData>::new();
let node_a = graph.add_node(NodeData {});
let node_b = graph.add_node(NodeData {});
let _portal_1 = graph.add_edge(node_a, node_b, PortalData {});

// 遍历节点的邻接门户
for edge in graph.edges(node_a) {
    let other_node = if edge.source() == node_a { edge.target() } else { edge.source() };
    // 处理门户与对侧节点逻辑
}

该方案适合快速开发，但若需要完全复刻Quake结构的细粒度控制，自定义索引方案更合适。

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