一、游戏背景
《纪念碑谷》（Monument Valley）是一款以 不可能图形（Impossible Figures）为核心的解谜游戏。游戏通过旋转、错位、视觉错觉让玩家引导主角艾达在看似不可能的空间中移动到终点。
游戏背后的算法涉及：
– 透视投影变换（Perspective Projection）
– 三维到二维的几何映射
– 基于图论的路径搜索
– 不可能图形的几何约束检测
二、核心思想
2.1 不可能图形的数学基础
游戏中典型的”彭罗斯三角形”（Penrose Triangle）效果，本质上是 多视角投影不一致 的视觉欺骗。算法实现需要：
- 维护3D世界坐标：建筑在3D空间中的真实位置
- 维护2D屏幕投影：将3D坐标投影到屏幕时，根据相机角度产生视觉欺骗
- 路径可达性判定：判断艾达在视觉上能通过的路径，在3D世界是否真的可行
2.2 投影变换
使用 透视投影：
$$P_{screen} = \begin{pmatrix} \frac{f \cdot x}{z} \ \frac{f \cdot y}{z} \end{pmatrix}$$
其中 $f$ 是焦距参数。通过调整相机位置、目标点和旋转角，可以让两个不相连的3D点在屏幕上看起来相邻。
三、Java实现
3.1 3D向量与透视投影
import java.util.*;
/**
* 纪念碑谷风格的几何与路径规划算法
* 实现透视投影、不可能图形渲染与图论路径搜索
*/
public class MonumentValleySolver {
/**
* 3D点或向量
*/
static class Vec3 {
double x, y, z;
Vec3(double x, double y, double z) {
this.x = x; this.y = y; this.z = z;
}
Vec3 add(Vec3 o) { return new Vec3(x + o.x, y + o.y, z + o.z); }
Vec3 sub(Vec3 o) { return new Vec3(x - o.x, y - o.y, z - o.z); }
Vec3 scale(double s) { return new Vec3(x * s, y * s, z * s); }
double dot(Vec3 o) { return x * o.x + y * o.y + z * o.z; }
Vec3 cross(Vec3 o) {
return new Vec3(
y * o.z - z * o.y,
z * o.x - x * o.z,
x * o.y - y * o.x
);
}
double length() { return Math.sqrt(x * x + y * y + z * z); }
Vec3 normalize() {
double l = length();
return l > 0 ? scale(1.0 / l) : this;
}
@Override
public boolean equals(Object o) {
if (!(o instanceof Vec3)) return false;
Vec3 v = (Vec3) o;
return Math.abs(x - v.x) < 1e-6 &&
Math.abs(y - v.y) < 1e-6 &&
Math.abs(z - v.z) < 1e-6;
}
@Override
public int hashCode() {
return Objects.hash(x, y, z);
}
}
/**
* 2D屏幕点
*/
static class Vec2 {
double x, y;
Vec2(double x, double y) { this.x = x; this.y = y; }
@Override
public boolean equals(Object o) {
if (!(o instanceof Vec2)) return false;
Vec2 v = (Vec2) o;
return Math.abs(x - v.x) < 1e-6 && Math.abs(y - v.y) < 1e-6;
}
@Override
public int hashCode() { return Objects.hash(x, y); }
}
/**
* 透视投影：将3D点投影到2D屏幕
* @param point 3D世界坐标点
* @param cameraPos 相机位置
* @param focalLength 焦距
* @return 2D屏幕坐标
*/
public static Vec2 perspectiveProject(Vec3 point, Vec3 cameraPos, double focalLength) {
Vec3 rel = point.sub(cameraPos);
if (Math.abs(rel.z) < 1e-6) return new Vec2(rel.x, rel.y);
return new Vec2(focalLength * rel.x / rel.z, focalLength * rel.y / rel.z);
}
3.2 旋转矩阵与相机控制
/**
* 围绕X轴的旋转矩阵
*/
public static Vec3 rotateX(Vec3 v, double angle) {
double c = Math.cos(angle), s = Math.sin(angle);
return new Vec3(v.x, c * v.y - s * v.z, s * v.y + c * v.z);
}
/**
* 围绕Y轴的旋转矩阵
*/
public static Vec3 rotateY(Vec3 v, double angle) {
double c = Math.cos(angle), s = Math.sin(angle);
return new Vec3(c * v.x + s * v.z, v.y, -s * v.x + c * v.z);
}
/**
* 围绕Z轴的旋转矩阵
*/
public static Vec3 rotateZ(Vec3 v, double angle) {
double c = Math.cos(angle), s = Math.sin(angle);
return new Vec3(c * v.x - s * v.y, s * v.x + c * v.y, v.z);
}
/**
* 相机（视点）配置
*/
static class Camera {
Vec3 position;
Vec3 target;
Vec3 up;
double focalLength;
Camera(Vec3 pos, Vec3 target, Vec3 up, double f) {
this.position = pos;
this.target = target;
this.up = up;
this.focalLength = f;
}
/**
* 计算相机正交基
*/
Vec3[] getBasis() {
Vec3 forward = target.sub(position).normalize();
Vec3 right = forward.cross(up).normalize();
Vec3 newUp = right.cross(forward);
return new Vec3[]{right, newUp, forward};
}
}
3.3 建筑与不可能图形
/**
* 建筑物：3D世界中的可移动平台
*/
static class Building {
Vec3 position;
Vec3[] vertices; // 顶点
Vec3[] platformPath; // 平台可到达的路径点
double rotation; // 当前旋转角度
Building(Vec3 position, Vec3[] vertices, Vec3[] path) {
this.position = position;
this.vertices = vertices;
this.platformPath = path;
this.rotation = 0;
}
/**
* 应用旋转
*/
void rotate(Vec3 axis, double angle) {
this.rotation += angle;
for (int i = 0; i < vertices.length; i++) {
if (axis.x != 0) vertices[i] = rotateX(vertices[i], angle);
else if (axis.y != 0) vertices[i] = rotateY(vertices[i], angle);
else vertices[i] = rotateZ(vertices[i], angle);
}
for (int i = 0; i < platformPath.length; i++) {
if (axis.x != 0) platformPath[i] = rotateX(platformPath[i], angle);
else if (axis.y != 0) platformPath[i] = rotateY(platformPath[i], angle);
else platformPath[i] = rotateZ(platformPath[i], angle);
}
}
}
/**
* 创建一个彭罗斯三角形效果的不可能图形
* 三个立方体在视觉上首尾相连，但3D空间中并不真正相连
*/
public static Building[] createPenroseTriangle(double size) {
Building[] cubes = new Building[3];
for (int i = 0; i < 3; i++) {
double angle = i * Math.PI * 2 / 3;
Vec3 pos = new Vec3(Math.cos(angle) * size, 0, Math.sin(angle) * size);
// 每个立方体有8个顶点
Vec3[] verts = new Vec3[8];
int idx = 0;
for (int sx = -1; sx <= 1; sx += 2)
for (int sy = -1; sy <= 1; sy += 2)
for (int sz = -1; sz <= 1; sz += 2) {
verts[idx++] = new Vec3(sx * size/2, sy * size/2, sz * size/2);
}
// 平台路径：绕立方体顶面一周
Vec3[] path = {
new Vec3(-size/2, size/2 + 0.1, -size/2),
new Vec3(size/2, size/2 + 0.1, -size/2),
new Vec3(size/2, size/2 + 0.1, size/2),
new Vec3(-size/2, size/2 + 0.1, size/2)
};
cubes[i] = new Building(pos, verts, path);
}
return cubes;
}
3.4 路径规划算法
/**
* 使用BFS/DFS在3D空间中寻找从起点到终点的路径
* 关键：路径必须考虑建筑物旋转和视觉欺骗
*/
public static List<Vec3> findPath(Vec3 start, Vec3 end,
List<Building> buildings,
Camera camera) {
// 构建图：每个建筑物的每个路径点作为一个节点
// 如果两个路径点在3D空间中真实可达，则连边
Map<Vec3, List<Vec3>> graph = new HashMap<>();
for (Building b : buildings) {
for (Vec3 p : b.platformPath) {
graph.computeIfAbsent(p, k -> new ArrayList<>());
}
}
// 添加起点和终点
graph.put(start, new ArrayList<>());
graph.put(end, new ArrayList<>());
// 真实几何连接：仅当两个平台真实物理连接时建边
for (Building b1 : buildings) {
for (Building b2 : buildings) {
if (b1 == b2) continue;
for (Vec3 p1 : b1.platformPath) {
for (Vec3 p2 : b2.platformPath) {
if (isPhysicallyConnected(p1, p2, b1, b2)) {
graph.get(p1).add(p2);
graph.get(p2).add(p1);
}
}
}
}
}
// 检查起点/终点到平台的连接
for (Building b : buildings) {
for (Vec3 p : b.platformPath) {
if (isPhysicallyConnected(start, p, null, b)) {
graph.get(start).add(p);
graph.get(p).add(start);
}
if (isPhysicallyConnected(end, p, null, b)) {
graph.get(end).add(p);
graph.get(p).add(end);
}
}
}
// BFS搜索
return bfs(start, end, graph);
}
/**
* 判断两个平台是否在3D空间中真实物理连接
* 与视觉欺骗无关，仅看绝对位置
*/
private static boolean isPhysicallyConnected(Vec3 p1, Vec3 p2,
Building b1, Building b2) {
double distance = p1.sub(p2).length();
return distance < 0.5; // 距离小于0.5个单位视为可通行
}
private static List<Vec3> bfs(Vec3 start, Vec3 end,
Map<Vec3, List<Vec3>> graph) {
Queue<Vec3> queue = new LinkedList<>();
Map<Vec3, Vec3> parent = new HashMap<>();
Set<Vec3> visited = new HashSet<>();
queue.offer(start);
visited.add(start);
while (!queue.isEmpty()) {
Vec3 cur = queue.poll();
if (cur.equals(end)) {
// 重建路径
List<Vec3> path = new ArrayList<>();
while (cur != null) {
path.add(0, cur);
cur = parent.get(cur);
}
return path;
}
for (Vec3 next : graph.getOrDefault(cur, Collections.emptyList())) {
if (!visited.contains(next)) {
visited.add(next);
parent.put(next, cur);
queue.offer(next);
}
}
}
return Collections.emptyList();
}
/**
* 视觉欺骗检测：判断两个点是否在屏幕上看起来相邻
* 这用于游戏中的"魔法移动"判定
*/
public static boolean looksAdjacent(Vec3 p1, Vec3 p2, Camera camera, double threshold) {
Vec2 screen1 = perspectiveProject(p1, camera.position, camera.focalLength);
Vec2 screen2 = perspectiveProject(p2, camera.position, camera.focalLength);
double screenDist = Math.sqrt(
Math.pow(screen1.x - screen2.x, 2) +
Math.pow(screen1.y - screen2.y, 2)
);
double worldDist = p1.sub(p2).length();
// 屏幕距离小但3D距离大 = 视觉欺骗
return screenDist < threshold;
}
3.5 完整游戏逻辑
/**
* 完整游戏状态
*/
static class GameState {
Vec3 playerPosition;
List<Building> buildings;
Vec3 goalPosition;
Camera camera;
GameState(Vec3 player, Vec3 goal, List<Building> b, Camera c) {
playerPosition = player;
goalPosition = goal;
buildings = b;
camera = c;
}
/**
* 玩家移动：基于视觉欺骗
* 玩家点击屏幕上某点，游戏根据视觉位置决定移动
*/
public void movePlayer(Vec2 screenTarget) {
// 找到屏幕上看起来最接近 target 的点
Vec3 closest = null;
double minDist = Double.MAX_VALUE;
for (Building b : buildings) {
for (Vec3 p : b.platformPath) {
Vec2 screenP = perspectiveProject(p, camera.position, camera.focalLength);
double dist = Math.sqrt(
Math.pow(screenP.x - screenTarget.x, 2) +
Math.pow(screenP.y - screenTarget.y, 2)
);
if (dist < minDist) {
minDist = dist;
closest = p;
}
}
}
if (closest != null) {
// 真实移动前验证3D路径可行性
if (canMoveIn3D(playerPosition, closest)) {
playerPosition = closest;
}
// 否则使用"魔法移动"：通过视觉欺骗直接跳转
else if (looksAdjacent(playerPosition, closest, camera, 0.5)) {
playerPosition = closest; // 不可能移动！
}
}
}
private boolean canMoveIn3D(Vec3 from, Vec3 to) {
// 简化的3D路径检查：直线距离 < 阈值
return from.sub(to).length() < 1.0;
}
public boolean isGoalReached() {
return playerPosition.sub(goalPosition).length() < 0.3;
}
}
public static void main(String[] args) {
System.out.println("=== 纪念碑谷算法演示 ===\n");
// 创建不可能图形
Building[] penrose = createPenroseTriangle(2.0);
List<Building> buildings = Arrays.asList(penrose);
// 创建相机
Vec3 cameraPos = new Vec3(0, 3, 8);
Vec3 target = new Vec3(0, 0, 0);
Vec3 up = new Vec3(0, 1, 0);
Camera camera = new Camera(cameraPos, target, up, 1.5);
// 创建游戏状态
Vec3 player = new Vec3(0, 1.1, -1);
Vec3 goal = new Vec3(0, 1.1, 1);
GameState game = new GameState(player, goal, buildings, camera);
System.out.println("初始玩家位置：" + game.playerPosition);
System.out.println("目标位置：" + game.goalPosition);
// 演示透视投影
System.out.println("\n=== 透视投影示例 ===");
Vec3 worldPoint = new Vec3(0, 0, 5);
Vec2 screenPoint = perspectiveProject(worldPoint, cameraPos, 1.5);
System.out.println("3D点 " + worldPoint + " -> 屏幕点 " + screenPoint);
// 演示视觉欺骗
System.out.println("\n=== 视觉欺骗检测 ===");
Vec3 p1 = new Vec3(-2, 0, 3);
Vec3 p2 = new Vec3(2, 0, 7);
System.out.println("3D距离：" + p1.sub(p2).length());
System.out.println("看起来相邻？" + looksAdjacent(p1, p2, camera, 0.5));
// 路径规划
System.out.println("\n=== 路径规划 ===");
List<Vec3> path = findPath(player, goal, buildings, camera);
System.out.println("找到路径，长度：" + path.size());
for (int i = 0; i < path.size(); i++) {
System.out.println(" 步骤 " + (i+1) + ": " + path.get(i));
}
}
}
四、复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 透视投影 | $O(1)$ | $O(1)$ |
| 旋转矩阵 | $O(1)$ | $O(1)$ |
| 路径搜索（BFS） | $O(V + E)$ | $O(V + E)$ |
| 视觉欺骗检测 | $O(1)$ | $O(1)$ |
其中 $V$ 为路径点数，$E$ 为物理连接数。
五、算法扩展
- 四元数旋转：避免万向节锁，实现平滑动画
- 光线追踪：增强视觉欺骗的真实性
- 真实物理引擎：实现艾达的坠落、爬坡
- 可访问性设计：为色盲玩家提供替代方案
纪念碑谷的算法核心在于 “3D世界与2D视觉的不一致”。掌握这个思想，你就可以构建出无限多富有创意的不可能图形谜题。
