用Threejs复刻崩铁梦境迷钟
前言
梦境迷钟是崩坏：星穹铁道中的一个小游戏，玩法类似纪念碑谷。通过操作使得钟表小子和零件的路径在视觉上联通即可过关。最近刚好学习了threejs，因此想用threejs简单复刻一下这个小游戏。
基础环境
采用正交摄像机。然后可以用TransformControls使得可以通过鼠标来缩放、平移等。
物体组件
根据实际游戏，我把游戏中的方块分为了如下几种：固定方块、可滑动方块、可旋转方块和镜子。固定的方块就是有固定位置的，不可移动的方块。可滑动方块就是可以通过操作进行平移的方块。可旋转方块就是可以绕轴旋转的方块。镜子是可以将物体反射的平面，也是可以进行平移的。
规定最小的物体边长是16的，并存放在常数unitWidth中。
一些基础算法
坐标的转化
因为物块坐标是根据中心点定位的，我们要把它转换为顶点的坐标，需要进行一定的转换。
// p是坐标，l是长度，tp是是否计算中心点
// 根据坐标算位置
const calcPos = (p: number, l: number = 1, tp: boolean = false): number => {
let ml = 1
if (tp)
ml = 0
return p * unitWidth + unitWidth * (l || 1) / 2 * ml
}
// 修正位置，让坐标为整数坐标。
const fixPos = (p: number, l: number = 1): number => {
return Math.round((p - unitWidth * (l || 1) / 2) / unitWidth)
}镜中物体坐标的计算
// p为物体坐标，m为镜子坐标，face为镜子的朝向
const calcMirrorPos = (p: [number, number, number], m: [number, number, number], face: number): [number, number, number] => {
const tmp = Array.from(p) as [number, number, number]
tmp[face] = 2 * m[face] - tmp[face] - 1
return tmp
}固定方块
固定方块很简单，只需要根据坐标来对中心位置进行定位就可以了。
核心代码
const cubeGeometry = new BoxGeometry(unitWidth, unitWidth, unitWidth)
const cubeMaterial = new MeshLambertMaterial({ color })
const cube = new Mesh(cubeGeometry, cubeMaterial)
cube.position.x = calcPos(pos[0], 1)
cube.position.y = calcPos(pos[1], 1)
cube.position.z = calcPos(pos[2], 1)
cube.applyMatrix4(new Matrix4().makeScale(1, 1, 1))
this.add(cube)可滑动方块
可滑动方块与固定方块类似。为了方便，我允许可滑动方块可以设定三边的边长，然后设定每个方向可以移动的范围，然后利用DragControl控制物块的移动即可。因为移动的时候可以连续变化，因此在滑动结束后还要取个整，确保物体在整数坐标位置。
核心代码
创建方块
创建方块和固定方块类似，这里就不贴了。
移动
onControlDrag(e: any) {
const tmp = e.object.position.toArray()
for (let i = 0; i < 3; ++i) {
// 限定移动的范围
if (this.range[i].length === 2 && this.range[i][0] < this.range[i][1]) {
if (tmp[i] <= calcPos(this.range[i][0], this.len[i]))
tmp[i] = calcPos(this.range[i][0], this.len[i])
if (tmp[i] >= calcPos(this.range[i][1], this.len[i]))
tmp[i] = calcPos(this.range[i][1], this.len[i])
}
else
tmp[i] = calcPos(this.pos[i], this.len[i])
this.pos[i] = fixPos(tmp[i], this.len[i])
}
e.object.position.fromArray(tmp)
// 对镜中的物体同步进行操作。
if (this.mirrorComponent) {
let tmpPos: [number, number, number] = [0, 0, 0]
for (let i = 0; i < tmpPos.length; ++i)
tmpPos[i] = (tmp[i] - unitWidth * (this.len[i] || 1) / 2) / unitWidth
tmpPos = calcMirrorPos(tmpPos, this.mirrorInfo.pos, this.mirrorInfo.face)
tmpPos[this.mirrorInfo.face] -= this.len[this.mirrorInfo.face] - 1;
this.mirrorComponent.setPos(tmpPos)
}
}结束移动
onControlDragEnd(e: any) {
// 修正位置，使坐标为整数。
const tmp = e.object.position.toArray()
for (let i = 0; i < 3; ++i) {
this.pos[i] = fixPos(tmp[i], this.len[i])
tmp[i] = calcPos(this.pos[i], this.len[i])
}
e.object.position.fromArray(tmp)
// 还需要同步修正镜中物体
if (this.mirrorComponent) {
const tmpPos = calcMirrorPos(this.pos, this.mirrorInfo.pos, this.mirrorInfo.face)
tmpPos[this.mirrorInfo.face] -= this.len[this.mirrorInfo.face] - 1;
this.mirrorComponent.setPos(tmpPos)
}
}可旋转方块
可旋转方块我设定的是一个L型的，然后可以选定一个轴，轴默认是过L的顶点的，可以旋转 $\frac{k}{2}\pi$。因为没发现threejs的DragControl还可以物体旋转，所以就自己写了一套逻辑[1]。
首先创建一个与旋转轴垂直的平面，转轴与平面的交点为 $O$，然后鼠标选中物体的时候计算与这个平面的交点 $A$。鼠标移动之后与平面的交点为 $B$，那么 $\overrightarrow{OA}$ 与 $\overrightarrow{OB}$ 的夹角就是最后旋转的角度。然后结束的时候再固定一下旋转的角度必须是 $\frac{\pi}{2}$ 的整数倍即可。
核心代码
创建物体
旋转开始
onDragStart(raycaster: Raycaster) {
if (!this.enabled)
return
this.angleAccumulate = this.angle * Math.PI / 2
// 这个pos就是上文所述的A点。
const pos = new Vector3()
raycaster.ray.intersectPlane(this.plane, pos)
// startVector就是OA向量
this.startVector = pos.sub({ x: calcPos(this.pos[0]), y: calcPos(this.pos[1]), z: calcPos(this.pos[2]) })
}旋转中
onDrag(raycaster: Raycaster) {
if (!this.enabled)
return
if (this.startVector === null)
return
// 计算OA'向量
const pos = new Vector3()
raycaster.ray.intersectPlane(this.plane, pos)
pos.sub({ x: calcPos(this.pos[0]), y: calcPos(this.pos[1]), z: calcPos(this.pos[2]) })
const tmpVector = new Vector3()
tmpVector.crossVectors(this.startVector, pos)
// 计算角度，并进行累计
let angle = this.startVector?.angleTo(pos) || 0
// 因为只计算累积的角度，所以把新向量赋值给startVector
this.startVector = pos
// 将物体位置移到原点，这样子旋转才是以过L顶点的轴进行旋转。
this.position.set(unitWidth / 2, unitWidth / 2, unitWidth / 2)
// 根据threejs确定的方向来判断当前旋转的角度，然后对物块进行旋转
angle *= (this.direction === 0 && tmpVector.x < 0) ||
(this.direction === 1 && tmpVector.y < 0) ||
(this.direction === 2 && tmpVector.z < 0) ? -1 : 1;
this.angleAccumulate += angle
this.angleAccumulate = (this.angleAccumulate % (Math.PI * 2) + Math.PI * 2) % (Math.PI * 2)
this.rotation.fromArray([0, 1, 2].map(d => this.angleAccumulate * Number(d === this.direction)) as [number, number, number])
this.position.set(unitWidth * (this.pos[0] + 1 / 2), unitWidth * (this.pos[1] + 1 / 2), unitWidth * (this.pos[2] + 1 / 2))
// 镜中的物体要同步进行旋转，但是旋转的角度以及位置需要重新设定过。
if (this.mirrorComponent) {
this.mirrorComponent.position.set(unitWidth / 2, unitWidth / 2, unitWidth / 2)
this.mirrorComponent.rotation.fromArray([0, 1, 2].map(d => this.angleAccumulate * Number(d === this.direction) * ((this.mirrorInfo.face === this.direction) ? 1 : -1)) as [number, number, number])
this.mirrorComponent.position.set(unitWidth * (this.mirrorComponent.pos[0] + 1 / 2), unitWidth * (this.mirrorComponent.pos[1] + 1 / 2), unitWidth * (this.mirrorComponent.pos[2] + 1 / 2))
}
}旋转结束
onDragEnd(raycaster: Raycaster) {
if (!this.enabled)
return
if (this.startVector === null)
return
// 同样的先处理旋转的逻辑
const pos = new Vector3()
raycaster.ray.intersectPlane(this.plane, pos)
pos.sub({ x: calcPos(this.pos[0]), y: calcPos(this.pos[1]), z: calcPos(this.pos[2]) })
const tmpVector = new Vector3()
tmpVector.crossVectors(this.startVector, pos)
let angle = this.startVector?.angleTo(pos) || 0
this.startVector = pos
this.position.set(-unitWidth / 2, -unitWidth / 2, -unitWidth / 2)
// 计算角度要求是 pi/2 的 整数倍。
angle *= (this.direction === 0 && tmpVector.x < 0) ||
(this.direction === 1 && tmpVector.y < 0) ||
(this.direction === 2 && tmpVector.z < 0) ? -1 : 1;
this.angleAccumulate += angle
this.angle = Math.round(this.angleAccumulate * 2 / Math.PI)
this.angle = (this.angle % 4 + 4) % 4
this.angleAccumulate = this.angle * Math.PI / 2
this.rotation.fromArray([0, 1, 2].map(d => this.angleAccumulate * Number(d === this.direction)) as [number, number, number])
this.position.set(unitWidth * (this.pos[0] + 1 / 2), unitWidth * (this.pos[1] + 1 / 2), unitWidth * (this.pos[2] + 1 / 2))
// 镜中的物体要同步旋转，不过角度要重新计算过。
this.mirrorComponent?.setAngle(this.angle * ((this.mirrorInfo.face === this.direction) ? 1 : -1))
}镜子
游戏中有一面镜子，镜子中的物体也可以作为路径联通。threejs提供的镜子只能在透视摄像机中使用，主要是通过镜子在背后构建一个虚拟的反射摄像机，然后将这个摄像机的内容贴图贴到镜子中。可惜这个方法在这里无法使用。
最后采用了一种较为暴力的方式实现这个镜子。那就是为每一个在镜子前面的物体，创建一个虚拟的镜中物体，然后再根据当前的视角和镜子的位置，来自行判断物体的遮挡。[2]
完成镜子有很多难点，第一个难点在于镜子上下左右四个边界的切平面比较难计算，第二个难点在于，镜中的旋转块和移动条也要和实际的物体同步运动，并且方向刚好要是镜像。因此，这些位置、朝向以及角度都需要重新计算过，比较麻烦。
核心代码
计算镜中旋转块的朝向
const calcMirrorAngle = (angle: number, face: number = 2) => {
if (face === 0)
return 3 - angle
if (angle <= 1)
return 1 - angle
return 5 - angle
}创建镜中物体
// 为每一个实际的物体创建一个镜中的物体。
this.realObjs.forEach((v: any) => {
let tmpObj: any
let tmpPos: [number, number, number]
switch (v.objectType) {
case "Cube":
tmpObj = new Cube(calcMirrorPos(v.pos, this.pos, face), v.color)
v.mirrorComponent = tmpObj
this.inMirrorObjs.push(tmpObj)
scene.add(tmpObj)
break
case "Rotator":
// 镜子中的Rotator和实际的Rotator要一起运动，并且方向刚好是镜像的，需要计算过。
tmpObj = new Rotator(calcMirrorPos(v.pos, this.pos, face), [v.len[0], v.len[1]], v.color, v.angle * ((v.direction === face) ? 1 : -1), v.direction,
[
(v.face[0][1] !== mirrorAxis ? v.face[0][0] : reverseFace(v.face[0][0] as ("+" | "-"))) + v.face[0][1],
(v.face[1][1] !== mirrorAxis ? v.face[1][0] : reverseFace(v.face[1][0] as ("+" | "-"))) + v.face[1][1],
])
tmpObj.enabled = false
v.mirrorComponent = tmpObj
v.mirrorInfo = {
face
}
this.inMirrorObjs.push(tmpObj)
scene.add(tmpObj)
break
case "Drawbox":
tmpPos = calcMirrorPos(v.pos, this.pos, face)
tmpPos[face] -= v.len[face] - 1
tmpObj = new DrawBox(tmpPos, v.len, v.color)
v.mirrorComponent = tmpObj
v.mirrorInfo = {
pos: this.pos,
face
}
this.inMirrorObjs.push(tmpObj)
scene.add(tmpObj)
break
}
})控制物体显示（通过镜子位置来计算ClippingPlane来切割物体）
// face是镜子的朝向，镜子的法向量可以是x轴也可以是z轴。
const face = this.len[0] === 0 ? 0 : 2
const mirror = this.children[0]
const left = (face === 2) ?
((mirror.position.x - unitWidth * this.len[0] / 2) / unitWidth) :
((mirror.position.z - unitWidth * this.len[2] / 2) / unitWidth)
const right = left + this.len[0] + this.len[2]
const bottom = (mirror.position.y - unitWidth * this.len[1] / 2) / unitWidth
const top = bottom + this.len[1]
// 计算出镜子上下左右四个边界的切平面
this.clippingPlanes = [
// Front
new Plane().setFromNormalAndCoplanarPoint(
(face === 2) ? new Vector3(0, 0, -1) : new Vector3(-1, 0, 0),
(face === 2) ?
new Vector3(0, 0, this.pos[2] * unitWidth) :
new Vector3(this.pos[0] * unitWidth, 0, 0)),
// Left
new Plane().setFromNormalAndCoplanarPoint(
(face === 2) ? new Vector3(1, 0, -1) : new Vector3(-1, 0, 1),
(face === 2) ?
new Vector3(left * unitWidth / 2, 0, this.pos[2] * unitWidth / 2) :
new Vector3(this.pos[0] * unitWidth / 2, 0, left * unitWidth / 2)),
// Right
new Plane().setFromNormalAndCoplanarPoint(
(face === 2) ? new Vector3(-1, 0, 1) : new Vector3(1, 0, -1),
(face === 2) ?
new Vector3(right * unitWidth / 2, 0, this.pos[2] * unitWidth / 2) :
new Vector3(this.pos[0] * unitWidth / 2, 0, right * unitWidth / 2)),
// Top
new Plane().setFromNormalAndCoplanarPoint(
(face === 2) ? new Vector3(0, -1, 1) : new Vector3(1, -1, 0),
(face === 2) ?
new Vector3(0, top * unitWidth / 2, this.pos[2] * unitWidth / 2) :
new Vector3(this.pos[0] * unitWidth / 2, top * unitWidth / 2, 0)),
// Bottom
new Plane().setFromNormalAndCoplanarPoint(
(face === 2) ? new Vector3(0, 1, -1) : new Vector3(-1, 1, 0),
(face === 2) ?
new Vector3(0, bottom * unitWidth / 2, this.pos[2] * unitWidth / 2) :
new Vector3(this.pos[0] * unitWidth / 2, bottom * unitWidth / 2, 0)),
]
// 镜中的物体只保留镜子内部的部分
this.inMirrorObjs.forEach(v => {
v.children.forEach((k: any) => {
k.material.clippingPlanes = this.clippingPlanes
k.material.clipIntersection = false
})
})
const reverseClippingPlanes: Plane[] = []
for (const i of this.clippingPlanes) {
reverseClippingPlanes.push(i.clone().negate())
}
// 镜子背后的物体只保留镜子外部的部分
this.realObjs.forEach(v => {
v.children.forEach((k: any) => {
k.material.clippingPlanes = reverseClippingPlanes
k.material.clipIntersection = true
})
})路径的计算
因为游戏是将物体的顶面作为路径，并且只要是在视觉上联通就可以联通。因此，我们把顶面来投射到一个2d的图中，编一个二维的坐标，然后只要判断两个点是否相邻就可以判断联通了。经过计算，最后是把 $(x,y,z)$ 投射成 $(z-y, x-y)$。同时，还需要判断一下是否有遮挡的问题，另外，还可能有遮一半的问题，这个根据坐标以及投射规则运算一下就行了，具体看代码。
class Point {
x: number;
y: number;
vis: boolean = false;
constructor(x?: number, y?: number) {
this.x = x || 0
this.y = y || 0
}
fromArray(p: [number, number, number, number?]) {
// 将(x,y,z)变成(z-y,x-y)
if (p.length === 3 || p.length === 4) {
this.x = -p[1] + p[2]
this.y = p[0] - p[1]
}
return this
}
}
// 因为滑动方块旋转方块是由多个小方块组成的，因此要把他们全部拆开来，然后记录一下坐标。
function getVirtualPos(arr: any[]) {
const res: [number, number, number][] = []
arr.forEach(v => {
if (v.isGroup) {
let d1: Vector3
let d2: Vector3
let rotQuaternion: Quaternion
const directionVectors = [
new Vector3(1, 0, 0),
new Vector3(0, 1, 0),
new Vector3(0, 0, 1)
];
//console.log(v)
switch (v.objectType) {
case "Cube":
res.push([
v.pos[0],
v.pos[1],
v.pos[2]
])
break
case "Drawbox":
for (let i = 0; i < v.len[0]; ++i)
for (let j = 0; j < v.len[1]; ++j)
for (let k = 0; k < v.len[2]; ++k) {
res.push([
v.pos[0] + i,
v.pos[1] + j,
v.pos[2] + k
])
}
break
case "Rotator":
d1 = new Vector3()
d2 = new Vector3()
d1[v.face[0][1] as ("x" | "y" | "z")] = v.face[0][0] === "-" ? -1 : 1
d2[v.face[1][1] as ("x" | "y" | "z")] = v.face[1][0] === "-" ? -1 : 1
//console.log(d1, d2)
rotQuaternion = new Quaternion().setFromAxisAngle(directionVectors[v.direction], v.angle * Math.PI / 2)
//console.log(directionVectors[v.direction])
d1.applyQuaternion(rotQuaternion).round()
d2.applyQuaternion(rotQuaternion).round()
for (let i = 0; i < v.len[0]; ++i) {
res.push([
v.pos[0] + d1.x * i,
v.pos[1] + d1.y * i,
v.pos[2] + d1.z * i
])
}
for (let i = 1; i < v.len[1]; ++i) {
res.push([
v.pos[0] + d2.x * i,
v.pos[1] + d2.y * i,
v.pos[2] + d2.z * i
])
}
}
}
})
return res
}
// 然后处理一下镜子的问题。
function filterObjs(pos: [number, number, number, number?][], mPos: [number, number, number], mLen: [number, number, number], type: number = 1) {
const face = mLen[0] === 0 ? 0 : 2
// 计算镜子四个边界的位置
const left = (face === 2) ? (mPos[2] - mPos[0] - mLen[0] + 1) : (mPos[2] - mPos[0] + 1)
const right = (face === 2) ? (mPos[2] - mPos[0] - 1) : (mPos[2] + mLen[2] - mPos[0] - 1)
const bottom = (face === 2) ? (mPos[2] - mPos[1] - mLen[1] + 1) : (mPos[0] - mPos[1] - mLen[1] + 1)
const top = (face === 2) ? (mPos[2] - mPos[1]) : (mPos[0] - mPos[1])
pos.forEach(v => {
let res = 0
const x = v[2] - v[1], y = v[0] - v[1]
const row = x - y, col = (face === 2) ? x : y
// 0没有被镜子遮挡，1被镜子遮挡了左边，2被镜子遮挡了右边，3完全被遮挡。
// 在镜子的前面
if (v[face] >= mPos[face])
res = 0
else if (bottom <= col && col <= top) {
// 完全被镜子遮挡
if (left <= row && row <= right)
res = 3
// 遮挡了右边一半
else if (row + 1 === left)
res = 2
// 遮挡了左边一半
else if (row === right + 1)
res = 1
// 在镜子外面，没有被遮挡
else
res = 0
}
// 没有被镜子遮挡
else
res = 0
// 如果是镜子中的虚拟物体，情况刚好和实际的物体反过来。
if (type !== 1)
res = 3 - res
if (v.length === 4)
v[3] = res
else
v.push(res)
})
}
function calcRoute(levelObjs: { objs: any[], mirror?: { pos: [number, number, number], len: [number, number, number], objs: any[] } }, start: Vector3, end: Vector3): Vector3[] | null {
let realPoints: [number, number, number, number?][] = getVirtualPos(levelObjs.objs)
const points: Point[] = []
let st = -1, ed = -1
// 算出起点和终点的坐标。
const startPoint = new Point().fromVector3(start),
endPoint = new Point().fromVector3(end)
const addPoint = (p: Point) => {
let flag = false
for (let i = 0; i < points.length; ++i)
if (p.equal(points[i])) {
flag = true
break
}
if (!flag) {
points.push(p)
if (p.equal(startPoint))
st = points.length - 1
if (p.equal(endPoint))
ed = points.length - 1
}
}
// 如果有镜子，还需要处理镜子的遮挡等问题。
if (levelObjs.mirror !== undefined) {
// 处理实际物体被镜子的遮挡情况
filterObjs(realPoints, levelObjs.mirror.pos, levelObjs.mirror.len, 1)
const mirrorPoints: [number, number, number, number?][] = getVirtualPos(levelObjs.mirror.objs)
// 处理镜子中的虚拟物体被镜子的遮挡情况
filterObjs(mirrorPoints, levelObjs.mirror.pos, levelObjs.mirror.len, 0)
realPoints = realPoints.concat(mirrorPoints)
}
// Build Vertex
// 处理块与块之间的遮挡问题
const tmp = []
for (let i = 0; i < realPoints.length; ++i) {
let flag = true
const d1x = realPoints[i][0] - realPoints[i][1] // -2
const d1y = realPoints[i][2] - realPoints[i][1] // -3
// s1是镜子处理后的遮挡情况，0未被遮挡，1左边被遮挡，2右边被遮挡，3完全被遮挡
const s1 = realPoints[i][3] || 0
// 完全被遮挡了就不用管了
if (s1 === 3)
continue
for (let j = 0; j < realPoints.length; ++j) {
const d2x = realPoints[j][0] - realPoints[j][1] // -3
const d2y = realPoints[j][2] - realPoints[j][1] // -3
const s2 = realPoints[j][3] || 0
if (s2 === 3)
continue
// 判断当前的物体有没有被其他物体遮住。
// 这个判断的时候要注意，也许从坐标计算上看一个物体可以被另一个物体遮住，但是如果这个遮住物体本身只有一半的话，可能遮不住了，因此，除了判断坐标，还要判断上层的物体的状态，到底能不能进行遮住。
// 突然感觉这里有一个问题，被遮住一半的是不是还要加进去去判断另一半？
if ((realPoints[j][1] > realPoints[i][1]) &&
(((d1x === d2x) && (d1y === d2y + 1) && (s2 <= 1) && (s1 !== 1)) || // 从右上遮住
((d1x === d2x + 1) && (d1y === d2y) && ((s2 & 1) === 0) && (s1 !== 2)) || // 从左上遮住
((d1x === d2x + 1) && (d1y === d2y + 1) && (s2 < 3) && ((s2 === 0) || (s2 === s1))))) { // 从正上方遮住
flag = false
break
}
}
// 没有被遮住就把他加进来
if (flag) {
tmp.push(realPoints[i])
}
}
// 最后再过滤一遍，把完全遮住的去掉，把遮住一半的找是不是能够找到另一半拼起来变成完整的一块。
for (let i = 0; i < tmp.length; ++i) {
let flag = false
const status = tmp[i][3] || 0
// 完全被遮住的就不用管
if (status === 3)
continue
else if (status > 0) {
// 如果只遮住一半的去
for (let j = 0; j < tmp.length; ++j)
if (((tmp[j][3] || 0) + status === 3) &&
(tmp[j][2] - tmp[j][1] === tmp[i][2] - tmp[i][1]) &&
(tmp[j][0] - tmp[j][1] === tmp[i][0] - tmp[i][1])) {
flag = true
break
}
}
else
flag = true
if (flag)
addPoint(new Point().fromArray(tmp[i]))
}
if (st === -1)
return null
if (ed === -1)
return null
// 给相邻的两个点进行连边。
const edges = new Array(points.length)
for (let i = 0; i < edges.length; ++i)
edges[i] = []
for (let i = 0; i < points.length; ++i)
for (let j = 0; j < points.length; ++j) {
if (points[i].manhattanDist(points[j]) === 1)
edges[i].push(j)
}
// 用SPFA算法来计算两个点的路径
const vis = new Array(points.length)
const dis = new Array(points.length)
const pre = new Array(points.length)
const que: number[] = []
for (let i = 0; i < points.length; ++i) {
vis[i] = false
dis[i] = 0x3f3f3f3f
pre[i] = -1
}
vis[st] = true
dis[st] = 0
que.push(st)
let head = 0, tail = 1
while (head < tail) {
const u = que[head]
head++
vis[u] = false
for (let i = 0; i < edges[u].length; ++i) {
const v = edges[u][i]
if (dis[v] > dis[u] + 1) {
dis[v] = dis[u] + 1
pre[v] = u
if (!vis[v]) {
vis[v] = true
que.push(v)
tail++
}
}
}
}
if (dis[ed] === 0x3f3f3f3f)
return null
else {
const ret: Vector3[] = []
let p = ed
while (p !== st) {
ret.push(points[p].toVector3())
p = pre[p]
}
ret.push(startPoint.toVector3())
return ret.reverse()
}
}TODO
- 上面代码中提到的，关于遮挡的一个小问题处理。
- 碰撞体积