一、传送门机制对最短路径的颠覆
在经典寻路中，两点间最短路径是直线。但Portal引入空间传送后，图论模型发生质变：两个远距离位置通过传送门建立零权边，最短路径可能”折叠”空间穿越。
本文构建一个传送门增强图（Portal-Augmented Graph），核心算法：
– 图变换：将传送门建模为跨空间边
– Dijkstra扩展：在含传送门的非欧空间中求最短路径
– 传送门对最优放置：用几何计算寻找最大距离缩减的 portal placement
二、基础图结构与坐标映射
import java.util.*;
/**
* Portal游戏世界的图论建模
* 节点 = 可站立位置，边 = 可达路径（步行或传送）
*/
public class PortalGraph {
/** 图中的节点：代表房间中的一个可站立位置 */
static class Node {
int id;
double x, y, z; // 3D世界坐标
String room; // 所属房间ID（不同房间可能几何上重叠但逻辑隔离）
boolean isPortalSurface; // 是否为可放置传送门的墙面
List<Edge> edges = new ArrayList<>();
public Node(int id, double x, double y, double z, String room) {
this.id = id; this.x = x; this.y = y; this.z = z; this.room = room;
}
/** 欧几里得距离 */
double distanceTo(Node other) {
return Math.sqrt(sq(x - other.x) + sq(y - other.y) + sq(z - other.z));
}
double sq(double v) { return v * v; }
}
/** 边：步行边（距离为权重）或传送边（权重≈0） */
static class Edge {
Node to;
double weight;
boolean isPortal; // 是否为传送门边
String type; // "walk" | "portal_blue" | "portal_orange"
public Edge(Node to, double weight, boolean isPortal, String type) {
this.to = to; this.weight = weight; this.isPortal = isPortal; this.type = type;
}
}
Map<Integer, Node> nodes = new HashMap<>();
/** 添加步行边（双向） */
void addWalkEdge(int from, int to) {
Node a = nodes.get(from), b = nodes.get(to);
double dist = a.distanceTo(b);
a.edges.add(new Edge(b, dist, false, "walk"));
b.edges.add(new Edge(a, dist, false, "walk"));
}
/** 添加传送门边：蓝色portal端 → 橙色portal端，权重为传送延迟（近似0） */
void addPortalEdge(int blueNode, int orangeNode) {
Node blue = nodes.get(blueNode), orange = nodes.get(orangeNode);
// 传送门边权重极小，表示瞬间传送（设为0.001避免Dijkstra零环问题）
double epsilon = 0.001;
blue.edges.add(new Edge(orange, epsilon, true, "portal"));
orange.edges.add(new Edge(blue, epsilon, true, "portal"));
}
}
三、传送门增强的最短路径算法
标准Dijkstra可直接运行在传送门增强图上，因为传送门边的正权重保证算法正确性。关键是动态建边：传送门位置由玩家实时决定，图结构随之变化。
public class PortalGraph {
/**
* 带传送门的最短路径（Dijkstra）
* @param start 起点
* @param goal 终点
* @return 最短路径上的节点序列
*/
public List<Node> shortestPath(int start, int goal) {
Node src = nodes.get(start), dst = nodes.get(goal);
// Dijkstra标准结构
Map<Node, Double> dist = new HashMap<>();
Map<Node, Node> prev = new HashMap<>();
PriorityQueue<NodeDist> pq = new PriorityQueue<>(Comparator.comparingDouble(nd -> nd.dist));
for (Node n : nodes.values()) dist.put(n, Double.POSITIVE_INFINITY);
dist.put(src, 0.0);
pq.add(new NodeDist(src, 0.0));
Set<Node> visited = new HashSet<>();
while (!pq.isEmpty()) {
NodeDist cur = pq.poll();
if (visited.contains(cur.node)) continue;
visited.add(cur.node);
if (cur.node == dst) break; // 找到目标
for (Edge e : cur.node.edges) {
if (visited.contains(e.to)) continue;
double alt = dist.get(cur.node) + e.weight;
if (alt < dist.get(e.to)) {
dist.put(e.to, alt);
prev.put(e.to, cur.node);
pq.add(new NodeDist(e.to, alt));
}
}
}
// 回溯路径
return reconstructPath(prev, dst);
}
List<Node> reconstructPath(Map<Node, Node> prev, Node goal) {
List<Node> path = new ArrayList<>();
Node cur = goal;
while (cur != null) {
path.add(cur);
cur = prev.get(cur);
}
Collections.reverse(path);
return path;
}
static class NodeDist {
Node node; double dist;
NodeDist(Node n, double d) { node = n; dist = d; }
}
/**
* 关键：计算放置传送门后的"路径增益"
* 增益 = 原最短路径距离 - 新最短路径距离
* 用于AI自动寻找最优portal placement
*/
public double pathGain(int start, int goal, int blueSurface, int orangeSurface) {
double original = shortestPathDistance(start, goal);
// 临时添加传送门边
addPortalEdge(blueSurface, orangeSurface);
double withPortal = shortestPathDistance(start, goal);
// 移除临时边（实际实现需更精细的rollback）
removePortalEdge(blueSurface, orangeSurface);
return original - withPortal;
}
double shortestPathDistance(int start, int goal) {
List<Node> path = shortestPath(start, goal);
if (path.size() < 2) return Double.POSITIVE_INFINITY;
double total = 0;
for (int i = 0; i < path.size() - 1; i++) {
total += path.get(i).distanceTo(path.get(i + 1));
}
return total;
}
void removePortalEdge(int a, int b) {
Node na = nodes.get(a), nb = nodes.get(b);
na.edges.removeIf(e -> e.to == nb && e.isPortal);
nb.edges.removeIf(e -> e.to == na && e.isPortal);
}
}
四、射线投射与Portal表面检测
Portal只能放置在特定的墙面/平面上。需要射线投射（Ray Casting）计算视线与表面的交点。
/**
* 射线与平面/矩形相交检测
* 用于确定玩家视线与可放置portal表面的交点
*/
public class RayCasting {
/** 3D射线 */
static class Ray {
double ox, oy, oz; // 起点
double dx, dy, dz; // 方向（需归一化）
public Ray(double ox, double oy, double oz, double dx, double dy, double dz) {
this.ox = ox; this.oy = oy; this.oz = oz;
double len = Math.sqrt(dx*dx + dy*dy + dz*dz);
this.dx = dx/len; this.dy = dy/len; this.dz = dz/len;
}
/** 射线上的点：origin + t * direction */
double px(double t) { return ox + t * dx; }
double py(double t) { return oy + t * dy; }
double pz(double t) { return oz + t * dz; }
}
/** 可放置portal的矩形表面 */
static class PortalSurface {
double x, y, z; // 表面中心
double nx, ny, nz; // 法向量（朝外）
double width, height; // 半宽高
// 表面的局部坐标轴（构建正交基）
double ux, uy, uz; // u轴（表面水平方向）
double vx, vy, vz; // v轴（表面垂直方向）
public PortalSurface(double x, double y, double z,
double nx, double ny, double nz,
double w, double h) {
this.x = x; this.y = y; this.z = z;
this.nx = nx; this.ny = ny; this.nz = nz;
this.width = w; this.height = h;
buildBasis();
}
/** 从法向量构建局部正交基（Gram-Schmidt） */
void buildBasis() {
// 选择不与法向量平行的参考向量
double refX = (Math.abs(nx) < 0.9) ? 1 : 0;
double refY = (Math.abs(nx) < 0.9) ? 0 : 1;
double refZ = 0;
// u = ref × n（水平轴）
ux = refY * nz - refZ * ny;
uy = refZ * nx - refX * nz;
uz = refX * ny - refY * nx;
double uLen = Math.sqrt(ux*ux + uy*uy + uz*uz);
ux /= uLen; uy /= uLen; uz /= uLen;
// v = n × u（垂直轴）
vx = ny * uz - nz * uy;
vy = nz * ux - nx * uz;
vz = nx * uy - ny * ux;
}
/**
* Moller-Trumbore射线-三角形相交（简化为射线-平面 + 矩形边界检测）
* @return t值（射线参数），若不相交返回-1
*/
double intersect(Ray ray) {
// 射线与平面相交：dot(ray.origin + t*ray.dir - surface.center, normal) = 0
double denom = ray.dx * nx + ray.dy * ny + ray.dz * nz;
if (Math.abs(denom) < 1e-6) return -1; // 射线与平面平行
double t = ((x - ray.ox) * nx + (y - ray.oy) * ny + (z - ray.oz) * nz) / denom;
if (t < 0) return -1; // 交点在射线后方
// 计算交点在世界坐标中的位置
double ix = ray.px(t), iy = ray.py(t), iz = ray.pz(t);
// 将交点转换到表面局部坐标系
double dx = ix - x, dy = iy - y, dz = iz - z;
double u = dx * ux + dy * uy + dz * uz;
double v = dx * vx + dy * vy + dz * vz;
// 矩形边界检测
if (Math.abs(u) <= width && Math.abs(v) <= height) {
return t;
}
return -1;
}
}
/**
* 从玩家视角投射射线，寻找所有可放置portal的表面交点
* 返回最近的合法表面
*/
public static PortalSurface findBestSurface(Ray ray, List<PortalSurface> surfaces) {
PortalSurface best = null;
double bestT = Double.POSITIVE_INFINITY;
for (PortalSurface s : surfaces) {
double t = s.intersect(ray);
if (t >= 0 && t < bestT) {
bestT = t;
best = s;
}
}
return best;
}
}
五、传送门对的最优放置策略
Portal的精髓是”用一对portal缩短长距离”。最优放置问题可建模为：给定起点s、终点t、候选表面集合B和O，选择(b, o)使得 shortest_path(s, t) 最小。
public class PortalGraph {
/**
* 传送门最优放置算法（暴力枚举 + Dijkstra评估）
*
* 复杂度：O(|B| × |O| × (V + E) log V)
* 对于小规模关卡（V<1000）可实时计算
*/
public PortalPlacement findOptimalPortalPlacement(
int start, int goal,
List<Integer> blueCandidates,
List<Integer> orangeCandidates) {
double bestGain = 0;
int bestBlue = -1, bestOrange = -1;
double originalDist = shortestPathDistance(start, goal);
for (int b : blueCandidates) {
for (int o : orangeCandidates) {
if (b == o) continue; // 同一节点不需要传送门
double gain = pathGain(start, goal, b, o);
if (gain > bestGain) {
bestGain = gain;
bestBlue = b;
bestOrange = o;
}
}
}
return new PortalPlacement(bestBlue, bestOrange, bestGain, originalDist - bestGain);
}
/**
* 启发式加速：只评估" promising "候选对
* 策略：选择能使"起点到蓝色端" + "橙色端到终点"最短的组合
*/
public PortalPlacement findOptimalFast(
int start, int goal,
List<Integer> blueCandidates,
List<Integer> orangeCandidates) {
// 预计算：起点到所有蓝候选的距离、橙候选到终点的距离
Map<Integer, Double> distFromStart = new HashMap<>();
Map<Integer, Double> distToGoal = new HashMap<>();
for (int b : blueCandidates) distFromStart.put(b, shortestPathDistance(start, b));
for (int o : orangeCandidates) distToGoal.put(o, shortestPathDistance(o, goal));
// 按距离排序，只评估Top-K组合
blueCandidates.sort(Comparator.comparingDouble(distFromStart::get));
orangeCandidates.sort(Comparator.comparingDouble(distToGoal::get));
int K = Math.min(10, Math.min(blueCandidates.size(), orangeCandidates.size()));
double bestGain = 0;
int bestBlue = -1, bestOrange = -1;
for (int i = 0; i < K; i++) {
for (int j = 0; j < K; j++) {
int b = blueCandidates.get(i);
int o = orangeCandidates.get(j);
if (b == o) continue;
double gain = pathGain(start, goal, b, o);
if (gain > bestGain) {
bestGain = gain;
bestBlue = b;
bestOrange = o;
}
}
}
return new PortalPlacement(bestBlue, bestOrange, bestGain,
shortestPathDistance(start, goal) - bestGain);
}
static class PortalPlacement {
int blueNode, orangeNode;
double gain, newDistance;
PortalPlacement(int b, int o, double g, double d) {
blueNode = b; orangeNode = o; gain = g; newDistance = d;
}
@Override
public String toString() {
return String.format("Portal(blue=%d, orange=%d, gain=%.2f, newDist=%.2f)",
blueNode, orangeNode, gain, newDistance);
}
}
}
六、动量守恒与传送门变换矩阵
Portal的物理不仅改变路径，还改变物体的朝向与动量。穿越portal时，速度向量需根据两个portal表面的法向量进行旋转变换。
/**
* 传送门穿越的向量变换
* 核心：将速度向量从蓝色portal的局部坐标系转换到橙色portal的局部坐标系
*/
public class PortalPhysics {
/**
* 计算portal穿越后的新速度向量
* @param velocity 进入蓝色portal前的速度
* @param blueNormal 蓝色portal法向量（朝外，物体进入方向）
* @param orangeNormal 橙色portal法向量（朝外，物体离开方向）
* @return 从橙色portal射出时的速度
*/
static double[] transformVelocity(double[] velocity,
double[] blueNormal,
double[] orangeNormal) {
// 1. 分解速度：垂直于portal的分量 + 平行于portal的分量
double vDotN = dot(velocity, blueNormal);
double[] vParallel = {
velocity[0] - vDotN * blueNormal[0],
velocity[1] - vDotN * blueNormal[1],
velocity[2] - vDotN * blueNormal[2]
};
// 2. 垂直分量翻转（进入portal = 穿过平面）
double[] vPerpOut = {
-vDotN * orangeNormal[0],
-vDotN * orangeNormal[1],
-vDotN * orangeNormal[2]
};
// 3. 平行分量需要旋转：从蓝色portal的切平面旋转到橙色portal的切平面
// 计算旋转轴：blueNormal × orangeNormal
double[] rotAxis = cross(blueNormal, orangeNormal);
double rotAxisLen = Math.sqrt(dot(rotAxis, rotAxis));
double[] vParallelOut;
if (rotAxisLen < 1e-6) {
// 两portal平行，平行分量不变（或取反取决于方向）
double dir = dot(blueNormal, orangeNormal) > 0 ? -1 : 1;
vParallelOut = new double[]{vParallel[0]*dir, vParallel[1]*dir, vParallel[2]*dir};
} else {
// Rodrigues旋转公式
double angle = Math.acos(Math.max(-1, Math.min(1, dot(blueNormal, orangeNormal))));
vParallelOut = rodriguesRotate(vParallel, rotAxis, angle);
}
return new double[]{
vPerpOut[0] + vParallelOut[0],
vPerpOut[1] + vParallelOut[1],
vPerpOut[2] + vParallelOut[2]
};
}
/** Rodrigues旋转公式：向量v绕轴k旋转角度θ */
static double[] rodriguesRotate(double[] v, double[] k, double theta) {
double cosT = Math.cos(theta);
double sinT = Math.sin(theta);
double[] kCrossV = cross(k, v);
double kDotV = dot(k, v);
return new double[]{
v[0] * cosT + kCrossV[0] * sinT + k[0] * kDotV * (1 - cosT),
v[1] * cosT + kCrossV[1] * sinT + k[1] * kDotV * (1 - cosT),
v[2] * cosT + kCrossV[2] * sinT + k[2] * kDotV * (1 - cosT)
};
}
static double dot(double[] a, double[] b) {
return a[0]*b[0] + a[1]*b[1] + a[2]*b[2];
}
static double[] cross(double[] a, double[] b) {
return new double[]{
a[1]*b[2] - a[2]*b[1],
a[2]*b[0] - a[0]*b[2],
a[0]*b[1] - a[1]*b[0]
};
}
}
七、完整演示：关卡求解器
public class PortalMain {
public static void main(String[] args) {
PortalGraph graph = new PortalGraph();
// 构建一个简单测试关卡：两个房间通过走廊连接
// 房间A: 节点0~3, 房间B: 节点4~7, 走廊: 节点8~9
// 在房间A的远端墙(节点2)和房间B的远端墙(节点6)可放portal
for (int i = 0; i < 10; i++) {
double x = (i < 4) ? i * 5 : (i < 8) ? (i - 4) * 5 + 50 : 20 + (i - 8) * 30;
double z = (i < 4 || i >= 8) ? 0 : 20;
graph.nodes.put(i, new PortalGraph.Node(i, x, 0, z,
(i < 4) ? "A" : (i < 8) ? "B" : "hallway"));
}
// 步行边
graph.addWalkEdge(0, 1); graph.addWalkEdge(1, 2); graph.addWalkEdge(2, 3);
graph.addWalkEdge(4, 5); graph.addWalkEdge(5, 6); graph.addWalkEdge(6, 7);
graph.addWalkEdge(3, 8); graph.addWalkEdge(8, 9); graph.addWalkEdge(9, 4);
// 无portal时的最短路径
System.out.println("=== Without Portal ===");
List<PortalGraph.Node> path = graph.shortestPath(0, 7);
printPath(path);
// 添加portal：节点2（房间A远端）↔ 节点6（房间B远端）
System.out.println("\n=== With Portal (2↔6) ===");
graph.addPortalEdge(2, 6);
path = graph.shortestPath(0, 7);
printPath(path);
// 最优放置分析
System.out.println("\n=== Optimal Placement Analysis ===");
List<Integer> blues = Arrays.asList(0, 1, 2, 3);
List<Integer> oranges = Arrays.asList(4, 5, 6, 7);
PortalGraph.PortalPlacement best = graph.findOptimalFast(0, 7, blues, oranges);
System.out.println(best);
}
static void printPath(List<PortalGraph.Node> path) {
double total = 0;
for (int i = 0; i < path.size(); i++) {
System.out.print(path.get(i).id);
if (i < path.size() - 1) {
double d = path.get(i).distanceTo(path.get(i+1));
System.out.printf(" -(%.1f)-> ", d);
total += d;
}
}
System.out.printf(" | Total: %.1f\n", total);
}
}
运行结果预期：
– 无portal：0→1→2→3→8→9→4→5→6→7，距离约100
– 有portal(2↔6)：0→1→2 【传送】 6→7，距离骤降至约35
八、复杂度分析
| 模块 | 时间复杂度 | 关键说明 |
|---|---|---|
| Dijkstra最短路径 | O((V+E) log V) |
含传送门边的标准复杂度 |
| 射线-表面相交 | O(1) |
平面方程直接求解 |
| 最优portal放置（暴力） | O(\|B\|·\|O\|·(V+E) log V) |
候选表面数决定 |
| 最优portal放置（启发式） | O(K²·(V+E) log V) |
K=10时大幅加速 |
| 速度向量变换 | O(1) |
固定次数向量运算 |
核心收获：
1. 传送门 = 零权边：将Portal机制直接建模为图论边，Dijkstra无需修改即可求解
2. 非欧空间路径折叠：传送门使”物理距离”与”图距离”解耦，最优策略往往违反直觉
3. 射线-平面相交：Molller-Trumbore算法是3D拾取的核心
4. Rodrigues旋转：portal穿越保持动量守恒的关键数学工具
Portal用最简单的图论概念——添加一条边——创造了游戏史上最令人称奇的空间谜题。
