来自中心的3d数组遍历
Luk*_*kas 15 arrays algorithm 3d gpu
我试图找到一个具有统一维度的3d数组的n遍历顺序.因此,遍历顺序应该按它到立方体中心的距离递增(具有相同索引的单元格的顺序是任意的).2d阵列的示例:
7 4 8
3 0 1
6 2 5
2 1 2
1 0 1
2 1 2
遍历作为相对于原点的相对坐标:
[ 0, 0]
[ 1, 0]
[ 0,-1]
[-1, 0]
[ 0, 1]
[ 1,-1]
[-1,-1]
[-1, 1]
[ 1, 1]
我知道解决这个问题的一些方法,例如预先计算所有索引并根据它们与原点的距离对它们进行排序.但是,由于此算法旨在在GPU上执行,因此存在一些限制:
- 没有递归(我知道将递归解析为迭代算法的可能性 - 但根据我的经验,维护堆栈不是一个合适的解决方案)
- 无离线计算(=计算CPU并将结果传输到GPU).解决方案需要尽可能灵活
在寻找解决方案时,我偶然发现了这个问题,这正是我倾向于解决的问题,虽然包含了一个不符合指定要求的树结构,但是接受的答案是:不同顺序的3D数组遍历
我还想到了一种使用球面坐标创建索引的方法,遗憾的是,这种方法不会产生正确的顺序.生成3d数组的给定遍历顺序的适当算法是什么？
编辑:暴风城为给定的问题提供了一个很好的替代描述:"[问题]实际上是关于将寻址从一个空间转换到另一个空间.在1维和2维之间转换很简单,如1,2,3. ..到(1,1),(1,2)(2,1)......但这更像是从上升的1维(或至少是正方形)转换为"上升的八面体分层"空间,除了每层表面的现有(尽管是任意的)递增顺序之外,"升序"意味着"最内层第一".
想了一会儿后,我想出了一个主意,表示3D阵列为节点与方向上的序列:+i,-i,+j,-j,+k,-k.
途径
对于二维数组,只有三个规则就足够了:
- 每个节点上的每次迭代都沿着它的轴向其移动,即节点
+j将递增第二个索引,节点-i将递减第一个索引. - 有两种节点:
Main和Secondary.主轴有一个索引0.每个迭代结束Maini和j轴节点(我将它们称为I和J)产生Secondary节点顺时针旋转90度:+I -> -j-J -> -i-I -> +j+J -> +i
- 每个节点都有生命周期,每次迭代都会减少.节点的生命周期等于
(n-1)/2奇数值n(对于偶数值,请参见下面的代码).在生命周期变为0之后,应该删除节点.
要启用第三维,应该应用另一个规则:
- 沿
k轴方向(此处为深度)的第三类节点在每次迭代中产生一组轴I和J轴:+K -> +I, -J, -I, +J-K -> +I, -J, -I, +J
以下是它的外观:
通过这种方法,elemnts将按照Arturo Menchaca解决方案自动按曼哈顿距离排序.
履行
这是我所描述的python代码.有很多改进的空间,这只是一个概念证明.它没有排序,没有递归,我没有看到任何离线计算.它还包含一些测试.Run
NO = ( 0, 0, 0, 2, 0)
Pi = (+1, 0, 0, 0, 0)
PI = (+1, 0, 0, 0, 1)
Pj = ( 0,+1, 0, 0, 0)
PJ = ( 0,+1, 0, 0, 1)
PK = ( 0, 0,+1, 0, 2)
Mi = (-1, 0, 0, 1, 0)
MI = (-1, 0, 0, 1, 1)
Mj = ( 0,-1, 0, 1, 0)
MJ = ( 0,-1, 0, 1, 1)
MK = ( 0, 0,-1, 1, 2)
# i j k ^ ^
# | Id for comparison
# Lifetime index
PRODUCE = {
PI: [ Mj ], # +I -> -j
MJ: [ Mi ], # -J -> -i
MI: [ Pj ], # -I -> +j
PJ: [ Pi ], # +J -> +i
NO: [ NO ],
Pi: [ NO ],
Pj: [ NO ],
Mi: [ NO ],
Mj: [ NO ],
PK: [ PI, MI, PJ, MJ ], # +K -> +I, -J, -I, +J
MK: [ PI, MI, PJ, MJ ], # -K -> +I, -J, -I, +J
}
class Index:
LastDistance = 0
NumberOfVisits = 0
MinIndex = 0
MaxIndex = 0
def __init__(self, i, j, k, lifetime, direction):
self.globalLifetime = lifetime
self.direction = direction
# Assign parent's position
self.i = i
self.j = j
self.k = k
# Step away from parent
self.lifetime = lifetime[direction[3]]
self.step()
def isLive(self):
return self.lifetime > 0
def visit(self):
Index.NumberOfVisits += 1
distance = self.distance()
if distance < Index.LastDistance:
raise NameError("Order is not preserved")
Index.LastDistance = distance
Index.MinIndex = min(self.i, Index.MinIndex)
Index.MinIndex = min(self.j, Index.MinIndex)
Index.MinIndex = min(self.k, Index.MinIndex)
Index.MaxIndex = max(self.i, Index.MaxIndex)
Index.MaxIndex = max(self.j, Index.MaxIndex)
Index.MaxIndex = max(self.k, Index.MaxIndex)
print("[{}, {}, {}]".format(self.i, self.j, self.k))
def step(self):
# Move in your direction
self.i += self.direction[0]
self.j += self.direction[1]
self.k += self.direction[2]
def iterate(self):
self.lifetime -= 1
def produce(self, result):
for direction in PRODUCE[self.direction]:
self.create(direction, result)
def create(self, direction, result):
index = Index(self.i, self.j, self.k, self.globalLifetime, direction)
if index.isLive():
result.append(index)
def distance(self):
# Manhattan Distance
return abs(self.i) + abs(self.j) + abs(self.k)
def Traverse(N):
TotalNumber = N*N*N
halfA = halfB = (N-1)/2
if N % 2 == 0:
halfA = N/2
halfB = N/2-1
MinIndex = -min(halfB, halfA)
MaxIndex = max(halfB, halfA)
lifetime = (halfA, halfB, 0)
SecondaryNodes = []
MainNodes = []
KNodes = []
# visit center
center = Index(0, 0, 0, lifetime, NO)
center.visit()
center.create(PI, MainNodes)
center.create(MI, MainNodes)
center.create(PJ, MainNodes)
center.create(MJ, MainNodes)
center.create(PK, KNodes)
center.create(MK, KNodes)
while len(SecondaryNodes) + len(MainNodes) + len(KNodes) > 0:
# First - visit all side nodes
temp = []
for m in SecondaryNodes:
m.visit()
m.step()
m.iterate()
# Save node only if it is alive
if m.isLive():
temp.append(m)
SecondaryNodes = temp
# Second - visit all main nodes as they may produce secondary nodes
temp = []
for m in MainNodes:
m.visit() # 1 - Visit
m.produce(SecondaryNodes) # 2 - Produce second
m.step() # 3 - Step
m.iterate() # 4 - Lose a life
if m.isLive():
temp.append(m)
MainNodes = temp
# Third - visit all K nodes as they may produce main nodes
temp = []
for m in KNodes:
m.visit()
m.produce(MainNodes)
m.step()
m.iterate()
if m.isLive():
temp.append(m)
KNodes = temp
if TotalNumber != Index.NumberOfVisits:
raise NameError("Number of visited elements does not match {}/{}".format(Index.NumberOfVisits, TotalNumber))
if MinIndex != Index.MinIndex:
raise NameError("Minimal index is out of bounds {}/{}".format(Index.MinIndex, MinIndex))
if MaxIndex != Index.MaxIndex:
raise NameError("Maximal index is out of bounds {}/{}".format(Index.MaxIndex, MaxIndex))
Traverse(6)
实施简化
助手类存储索引:
class Index:
def __init__(self, i, j, k, lifetime):
self.i = i
self.j = j
self.k = k
self.lifetime = lifetime
def visit(self):
print("[{}, {}, {}]".format(self.i, self.j, self.k))
用于Main以正确方向迭代节点的函数集:
def StepMainPlusI(mainPlusI, minusJ, lifetime):
result = []
for m in mainPlusI:
if lifetime > 0:
minusJ.append(Index(m.i, m.j-1, m.k, lifetime))
m.lifetime -= 1
m.i += 1
if m.lifetime > 0:
result.append(m)
return result
def StepMainMinusJ(mainMinusJ, minusI, lifetime):
result = []
for m in mainMinusJ:
if lifetime > 0:
minusI.append(Index(m.i-1, m.j, m.k, lifetime))
m.lifetime -= 1
m.j -= 1
if m.lifetime > 0:
result.append(m)
return result
def StepMainMinusI(mainMinusI, plusJ, lifetime):
result = []
for m in mainMinusI:
if lifetime > 0:
plusJ.append(Index(m.i, m.j+1, m.k, lifetime))
m.lifetime -= 1
m.i -= 1
if m.lifetime > 0:
result.append(m)
return result
def StepMainPlusJ(mainPlusJ, plusI, lifetime):
result = []
for m in mainPlusJ:
if lifetime > 0:
plusI.append(Index(m.i+1, m.j, m.k, lifetime))
m.lifetime -= 1
m.j += 1
if m.lifetime > 0:
result.append(m)
return result
用于迭代第三维K节点的函数集:
def StepMainPlusK(mainPlusK, mainPlusI, mainMinusI, mainPlusJ, mainMinusJ, lifetimeA, lifetimeB):
result = []
for m in mainPlusK:
if lifetimeA > 0:
mainPlusI.append(Index(+1, 0, m.k, lifetimeA))
mainPlusJ.append(Index(0, +1, m.k, lifetimeA))
if lifetimeB > 0:
mainMinusI.append(Index(-1, 0, m.k, lifetimeB))
mainMinusJ.append(Index(0, -1, m.k, lifetimeB))
m.lifetime -= 1
m.k += 1
if m.lifetime > 0:
result.append(m)
return result
def StepMainMinusK(mainMinusK, mainPlusI, mainMinusI, mainPlusJ, mainMinusJ, lifetimeA, lifetimeB):
result = []
for m in mainMinusK:
if lifetimeA > 0:
mainPlusI.append(Index(+1, 0, m.k, lifetimeA))
mainPlusJ.append(Index(0, +1, m.k, lifetimeA))
if lifetimeB > 0:
mainMinusI.append(Index(-1, 0, m.k, lifetimeB))
mainMinusJ.append(Index(0, -1, m.k, lifetimeB))
m.lifetime -= 1
m.k -= 1
if m.lifetime > 0:
result.append(m)
return result
这两个函数具有两个不同的寿命参数,用于n奇数时的情况,一半可以小于另一个.我用符号划分它们 - 负面导向将有一半的索引.
迭代Secondary节点的函数集:
def StepPlusI(plusI):
result = []
for m in plusI:
m.i += 1
m.lifetime -= 1
if m.lifetime > 0:
result.append(m)
return result
def StepMinusI(minusI):
result = []
for m in minusI:
m.i -= 1
m.lifetime -= 1
if m.lifetime > 0:
result.append(m)
return result
def StepPlusJ(plusJ):
result = []
for m in plusJ:
m.j += 1
m.lifetime -= 1
if m.lifetime > 0:
result.append(m)
return result
def StepMinusJ(minusJ):
result = []
for m in minusJ:
m.j -= 1
m.lifetime -= 1
if m.lifetime > 0:
result.append(m)
return result
主要功能:
def Traverse(N):
halfA = halfB = (N-1)/2
if N % 2 == 0: # size is even
halfA = N/2
halfB = N/2-1
# visit center
Index(0,0,0,0).visit()
# Secondary nodes
PlusI = []
MinusI = []
PlusJ = []
MinusJ = []
# Main nodes
MainPlusI = []
MainMinusI = []
MainPlusJ = []
MainMinusJ = []
MainPlusK = []
MainMinusK = []
# Add Main nodes
if halfA > 0:
MainPlusI.append( Index(+1, 0, 0, halfA) )
MainPlusJ.append( Index(0, +1, 0, halfA) )
MainPlusK.append( Index(0, 0, +1, halfA) )
if halfB > 0:
MainMinusI.append( Index(-1, 0, 0, halfB) )
MainMinusJ.append( Index(0, -1, 0, halfB) )
MainMinusK.append( Index(0, 0, -1, halfB) )
# Finish condition flag
visited = True
while visited:
visited = False
# visit all Main nodes
for m in MainPlusI:
m.visit()
visited = True
for m in MainMinusI:
m.visit()
visited = True
for m in MainPlusJ:
m.visit()
visited = True
for m in MainMinusJ:
m.visit()
visited = True
for m in MainPlusK:
m.visit()
visited = True
for m in MainMinusK:
m.visit()
visited = True
# Visit all Secondary nodes
for m in PlusI:
m.visit()
visited = True
for m in MinusI:
m.visit()
visited = True
for m in PlusJ:
m.visit()
visited = True
for m in MinusJ:
m.visit()
visited = True
# Iterate Secondary nodes first
PlusI = StepPlusI(PlusI)
MinusI = StepMinusI(MinusI)
PlusJ = StepPlusJ(PlusJ)
MinusJ = StepMinusJ(MinusJ)
# Iterate all Main nodes as they might generate Secondary nodes
MainPlusI = StepMainPlusI(MainPlusI, MinusJ, halfB)
MainMinusJ = StepMainMinusJ(MainMinusJ, MinusI, halfB)
MainMinusI = StepMainMinusI(MainMinusI, PlusJ, halfA)
MainPlusJ = StepMainPlusJ(MainPlusJ, PlusI, halfA)
# Iterate K nodes last as they might produce Main nodes
MainPlusK = StepMainPlusK(MainPlusK, MainPlusI, MainMinusI, MainPlusJ, MainMinusJ, halfA, halfB)
MainMinusK = StepMainMinusK(MainMinusK, MainPlusI, MainMinusI, MainPlusJ, MainMinusJ, halfA, halfB)
和现场的例子 Code
八度对称
位于距离中心某个曼哈顿距离的立方矩阵中的单元形成八面体,其关于穿过立方体中心的xy,xz和yz平面对称.
这意味着您只需要在立方体的第一个八分圆中找到形成八面体一面的单元格,并镜像它们以获得其他7个八分圆中的单元格.因此,从中心(距离0)到角落单元(最大距离= 3×n/2),问题被简化为从对角线穿过立方体的第一个八分圆(其本身是立方体).
查找坐标的算法
从第一个八分圆中的(0,0,0)单元(即形成八面体的一个面,垂直于立方体的对角线的单元)中找到与某个曼哈顿距离的单元,意味着找到其单元坐标(x,y,z)与该距离的总和.因此,在5x5x5八分圆的示例中,距离3处的单元格是具有坐标的单元格:
(3,0,0)(2,1,0)(1,2,0)(0,3,0)
(2,0,1)(1,1,1)(0,2,1)
( 1,0,2)(0,1,2)
(0,0,3)
你会注意到与距离分区的相似性(实际上,它是一个所谓的弱组合,有限长度为3).
使用三个嵌套循环可以轻松找到这些组合; 唯一的复杂因素是每个维度的距离被限制为n/2,因此你必须跳过x和/或y的值,这些值对于z没有值,所以x,y和z与距离相加; 这是什么min(),并max()在JavaScript代码示例,以及xmin,xmax,ymin并ymax在C代码示例变量是.
在一个偶数大小的立方体中镜像细胞是直截了当的; 在奇数大小的立方体中,单元不在其坐标为零的维度中镜像(即,当单元位于对称平面时).这就是在代码示例中检查x,y或z是否等于零的原因.
并行编程
我对GPU编程知之甚少,但我认为你可以完全平行算法.对于外循环的每次迭代(即对于每个距离),一旦计算出x的最小值和最大值,就可以并行运行具有不同x值的迭代.然后,对于x的每个值,一旦计算出y的最小值和最大值,就可以并行运行具有不同y值的迭代.最后,对于(x,y,z)的每个坐标集,可以并行运行与其他八分圆的镜像.
代码示例1(JavaScript)
(运行代码片段以查看9x9x9矩阵的内向外遍历,如图所示.)
function insideOut(n) {
var half = Math.ceil(n / 2) - 1;
for (var d = 0; d <= 3 * half; d++) {
for (var x = Math.max(0, d - 2 * half); x <= Math.min(half, d); x++) {
for (var y = Math.max(0, d - x - half); y <= Math.min(half, d - x); y++) {
document.write("<br>distance " + d + " (±" + x + ",±" + y + ",±" + (d - x - y) + ") → ");
n % 2 ? mirrorOdd(x, y, d - x - y) : mirrorEven(x, y, d - x - y);
}
}
}
function mirrorEven(x, y, z) {
for (var i = 1; i >= 0; --i, x *= -1) {
for (var j = 1; j >= 0; --j, y *= -1) {
for (var k = 1; k >= 0; --k, z *= -1) {
visit(half + x + i, half + y + j, half + z + k);
}
}
}
}
function mirrorOdd(x, y, z) {
for (var i = 0; i < (x ? 2 : 1); ++i, x *= -1) {
for (var j = 0; j < (y ? 2 : 1); ++j, y *= -1) {
for (var k = 0; k < (z ? 2 : 1); ++k, z *= -1) {
visit(half + x, half + y, half + z);
}
}
}
}
function visit(x, y, z) {
document.write("(" + x + "," + y + "," + z + ") " );
}
}
insideOut(9);代码示例2(C)
为简单起见,可以展开镜像功能.实际上,整个算法只包含3个嵌套循环和简单的整数计算.
void mirrorEven(unsigned int x, unsigned int y, unsigned int z, unsigned int h) {
visit(h+x+1, h+y+1, h+z+1);
visit(h+x+1, h+y+1, h-z);
visit(h+x+1, h-y, h+z+1);
visit(h+x+1, h-y, h-z);
visit(h-x, h+y+1, h+z+1);
visit(h-x, h+y+1, h-z);
visit(h-x, h-y, h+z+1);
visit(h-x, h-y, h-z);
}
void mirrorOdd(unsigned int x, unsigned int y, unsigned int z, unsigned int h) {
visit(h+x, h+y, h+z);
if ( z) visit(h+x, h+y, h-z);
if ( y ) visit(h+x, h-y, h+z);
if ( y && z) visit(h+x, h-y, h-z);
if (x ) visit(h-x, h+y, h+z);
if (x && z) visit(h-x, h+y, h-z);
if (x && y ) visit(h-x, h-y, h+z);
if (x && y && z) visit(h-x, h-y, h-z);
}
void insideOut(unsigned int n) {
unsigned int d, x, xmin, xmax, y, ymin, ymax, half = (n-1)/2;
for (d = 0; d <= 3*half; d++) {
xmin = d < 2*half ? 0 : d-2*half;
xmax = d < half ? d : half;
for (x = xmin; x <= xmax; x++) {
ymin = d < x+half ? 0 : d-x-half;
ymax = d > x+half ? half : d-x;
for (y = ymin; y <= ymax; y++) {
if (n%2) mirrorOdd(x, y, d-x-y, half);
else mirrorEven(x, y, d-x-y, half);
}
}
}
}
[我在解决方案中使用曼哈顿距离]
为了简单起见，我们开始假设奇数维度的 3D 数组 ( [2N+1, 2N+1, 2N+1])
使用曼哈顿距离，中心 ( [0,0,0]) 与点之间的最大距离为3N( [N,N,N], [ N,N,-N], ...)
因此，基本上的想法是找到一种方法来生成具有特定距离的所有坐标。然后从距离开始0生成3N这些坐标。
为了生成到[X,Y,Z]中心的距离为某个值的坐标K，我们需要的是X、Y、Z之间的所有数字-N，N使得ABS(X) + ABS(Y) + ABS(Z) == K。这可以通过以下方式完成：
FUNC COORDS_AT_DIST(K)
FOR X = -MIN(N, K) TO MIN(N, K)
FOR Y = -MIN(N, K - ABS(X)) TO MIN(N, K - ABS(X))
LET Z = K - ABS(X) - ABS(Y)
IF Z <= N
VISIT(X, Y, Z)
IF Z != 0
VISIT(X, Y, -Z)
然后，像这样使用这个函数：
FOR K = 0 TO 3N
COORDS_AT_DIST(K)
此代码访问值介于 之间的所有坐标[-N,-N,-N]，并[N,N,N]根据到 的距离排序[0,0,0]。
现在，为了处理偶数维度，我们需要一些额外的检查，因为维度的坐标值L介于[-(L/2-1),-(L/2-1),-(L/2-1)]和之间[L/2,L/2,L/2]。
像这样的东西：
FUNC VISIT_COORDS_FOR_DIM(L)
LET N = L/2 //Integer division
FOR K = 0 TO 3N
FOR X = -MIN(N - REM(L+1, 2), K) TO MIN(N, K)
FOR Y = -MIN(N - REM(L+1, 2), K - ABS(X)) TO MIN(N, K - ABS(X))
LET Z = K - ABS(X) - ABS(Y)
IF Z <= N
VISIT(X, Y, Z)
IF Z != 0 && (REM(L, 2) != 0 || Z < N)
VISIT(X, Y, -Z)
只是为了清楚起见：
MIN(X, Y): Minimum value between X and Y
ABS(X): Absolute value of X
REM(X, Y): Remainder after division of X by Y
VISIT(X, Y, Z): Visit the generated coordinate (X, Y, Z)
使用VISIT_COORDS_FOR_DIM函数L=3你会得到这个：
1. [0, 0, 0] DISTANCE: 0
2. [-1, 0, 0] DISTANCE: 1
3. [0, -1, 0] DISTANCE: 1
4. [0, 0, -1] DISTANCE: 1
5. [0, 0, 1] DISTANCE: 1
6. [0, 1, 0] DISTANCE: 1
7. [1, 0, 0] DISTANCE: 1
8. [-1, -1, 0] DISTANCE: 2
9. [-1, 0, -1] DISTANCE: 2
10. [-1, 0, 1] DISTANCE: 2
11. [-1, 1, 0] DISTANCE: 2
12. [0, -1, -1] DISTANCE: 2
13. [0, -1, 1] DISTANCE: 2
14. [0, 1, -1] DISTANCE: 2
15. [0, 1, 1] DISTANCE: 2
16. [1, -1, 0] DISTANCE: 2
17. [1, 0, -1] DISTANCE: 2
18. [1, 0, 1] DISTANCE: 2
19. [1, 1, 0] DISTANCE: 2
20. [-1, -1, -1] DISTANCE: 3
21. [-1, -1, 1] DISTANCE: 3
22. [-1, 1, -1] DISTANCE: 3
23. [-1, 1, 1] DISTANCE: 3
24. [1, -1, -1] DISTANCE: 3
25. [1, -1, 1] DISTANCE: 3
26. [1, 1, -1] DISTANCE: 3
27. [1, 1, 1] DISTANCE: 3
对于L=4：
1. [0, 0, 0] DISTANCE: 0 33. [1, -1, -1] DISTANCE: 3
2. [-1, 0, 0] DISTANCE: 1 34. [1, -1, 1] DISTANCE: 3
3. [0, -1, 0] DISTANCE: 1 35. [1, 0, 2] DISTANCE: 3
4. [0, 0, -1] DISTANCE: 1 36. [1, 1, -1] DISTANCE: 3
5. [0, 0, 1] DISTANCE: 1 37. [1, 1, 1] DISTANCE: 3
6. [0, 1, 0] DISTANCE: 1 38. [1, 2, 0] DISTANCE: 3
7. [1, 0, 0] DISTANCE: 1 39. [2, -1, 0] DISTANCE: 3
8. [-1, -1, 0] DISTANCE: 2 40. [2, 0, -1] DISTANCE: 3
9. [-1, 0, -1] DISTANCE: 2 41. [2, 0, 1] DISTANCE: 3
10. [-1, 0, 1] DISTANCE: 2 42. [2, 1, 0] DISTANCE: 3
11. [-1, 1, 0] DISTANCE: 2 43. [-1, -1, 2] DISTANCE: 4
12. [0, -1, -1] DISTANCE: 2 44. [-1, 1, 2] DISTANCE: 4
13. [0, -1, 1] DISTANCE: 2 45. [-1, 2, -1] DISTANCE: 4
14. [0, 0, 2] DISTANCE: 2 46. [-1, 2, 1] DISTANCE: 4
15. [0, 1, -1] DISTANCE: 2 47. [0, 2, 2] DISTANCE: 4
16. [0, 1, 1] DISTANCE: 2 48. [1, -1, 2] DISTANCE: 4
17. [0, 2, 0] DISTANCE: 2 49. [1, 1, 2] DISTANCE: 4
18. [1, -1, 0] DISTANCE: 2 50. [1, 2, -1] DISTANCE: 4
19. [1, 0, -1] DISTANCE: 2 51. [1, 2, 1] DISTANCE: 4
20. [1, 0, 1] DISTANCE: 2 52. [2, -1, -1] DISTANCE: 4
21. [1, 1, 0] DISTANCE: 2 53. [2, -1, 1] DISTANCE: 4
23. [2, 0, 0] DISTANCE: 2 54. [2, 0, 2] DISTANCE: 4
23. [-1, -1, -1] DISTANCE: 3 55. [2, 1, -1] DISTANCE: 4
24. [-1, -1, 1] DISTANCE: 3 56. [2, 1, 1] DISTANCE: 4
25. [-1, 0, 2] DISTANCE: 3 57. [2, 2, 0] DISTANCE: 4
26. [-1, 1, -1] DISTANCE: 3 58. [-1, 2, 2] DISTANCE: 5
27. [-1, 1, 1] DISTANCE: 3 59. [1, 2, 2] DISTANCE: 5
28. [-1, 2, 0] DISTANCE: 3 60. [2, -1, 2] DISTANCE: 5
29. [0, -1, 2] DISTANCE: 3 61. [2, 1, 2] DISTANCE: 5
30. [0, 1, 2] DISTANCE: 3 62. [2, 2, -1] DISTANCE: 5
31. [0, 2, -1] DISTANCE: 3 63. [2, 2, 1] DISTANCE: 5
32. [0, 2, 1] DISTANCE: 3 64. [2, 2, 2] DISTANCE: 6
该解决方案的优点是不需要任何特殊的数据结构，甚至不需要数组。
另一种解决方案可能是，如果您可以使用队列（使用数组实现并不难），并且 3D 布尔（或 int）数组就像从中心开始的 BFS 一样。
首先，要定义什么是邻居，可以使用运动数组，例如：
如果两个单元格共享公共边（曼哈顿距离），则两个单元格是邻居：
Run Code Online (Sandbox Code Playgroud)DX = { 1, 0, 0, -1, 0, 0 } DY = { 0, 1, 0, 0, -1, 0 } DZ = { 0, 0, 1, 0, 0, -1 }如果两个单元格共享公共边，则它们是邻居：
Run Code Online (Sandbox Code Playgroud)DX = { 1, 0, 0, -1, 0, 0, 1, 1, 0, -1, -1, 0, 1, 1, 0, -1, -1, 0 } DY = { 0, 1, 0, 0, -1, 0, 1, 0, 1, 1, 0, -1, -1, 0, 1, -1, 0, -1 } DZ = { 0, 0, 1, 0, 0, -1, 0, 1, 1, 0, 1, 1, 0, -1, -1, 0, -1, -1 }如果两个单元共享一个公共角（切比雪夫距离），则两个单元是邻居：
Run Code Online (Sandbox Code Playgroud)DX = { 1, 0, 0, -1, 0, 0, 1, 1, 0, -1, -1, 0, 1, 1, 0, -1, -1, 0, 1, -1, 1, 1, -1, -1, 1, -1 } DY = { 0, 1, 0, 0, -1, 0, 1, 0, 1, 1, 0, -1, -1, 0, 1, -1, 0, -1, 1, 1, -1, 1, -1, 1, -1, -1 } DZ = { 0, 0, 1, 0, 0, -1, 0, 1, 1, 0, 1, 1, 0, -1, -1, 0, -1, -1, 1, 1, 1, -1, 1, -1, -1, -1 }
现在，使用队列，您可以从中心位置开始，然后添加邻居，然后添加邻居的邻居，依此类推。在每次迭代中，您都可以访问每个生成的位置。
像这样的东西：
DX = { 1, 0, 0, -1, 0, 0 }
DY = { 0, 1, 0, 0, -1, 0 }
DZ = { 0, 0, 1, 0, 0, -1 }
VISIT_COORDS_FOR_DIM(L):
LET N = L/2
IF (REM(L, 2) == 0)
N--
V: BOOLEAN[L, L, L]
Q: QUEUE<POINT3D>
V[N, N, N] = TRUE
ENQUEUE(Q, POINT3D(N, N, N))
WHILE COUNT(Q) > 0
P = DEQUEUE(Q)
VISIT(P.X - N, P.Y - N, P.Z - N) //To Transform coords to [-N, N] range.
FOR I = 0 TO LENGTH(DX) - 1
LET X = P.X + DX[I]
LET Y = P.Y + DY[I]
LET Z = P.Z + DZ[I]
IF IS_VALID_POS(L, X, Y, Z) && V[X, Y, Z] == FALSE
V[X, Y, Z] = TRUE
ENQUEUE(Q, POINT3D(X, Y, Z))
IS_VALID_POS(L, X, Y, Z)
RETURN X >= 0 && X < L &&
Y >= 0 && Y < L &&
Z >= 0 && Z < L
使用的功能：
REM(X, Y): Remainder after division of X by Y
ENQUEUE(Q, X): Enqueue element X in queue Q
DEQUEUE(Q): Dequeue first element from queue Q
COUNT(Q): Number of elements in queue Q
VISIT(X, Y, Z): Visit the generated coordinate (X, Y, Z)
该解决方案的优点是，您可以使用移动数组定义两个位置是否相邻。