六边形网格(有时也叫蜂窝网络)在实际生活中有很多应用,例如无线基站定位,蜂窝(名字的由来),战棋游戏中人物的移动等.对于六边形网格的定位方法有很多,几何计算应该是最简单的.不过对于想要直观显示,计算的方式并不能说是最好的方法.曾经看到一个题目,对于一个从中心螺旋生长的蜂窝网格,求任意给定的2个cell的距离(看下图).此题如果是正方形网格,一个很简单的BFS(广度优先搜素)即可解决.但是对于蜂窝网格,如果不用几何的办法,最好是先定义网格cell,然后构造整个network,最后对于给定的cell按照广搜找到路径即可.
下面是python实现的六边形网格构造及寻路算法,可以给出任意指定的2个网格cell的最短距离与路径.
思路简单描述一下三个类(为了与python的list下标对应,所有的下标操作都从0开始):
cell类: 表示单个网格,nbs是它的邻居,从正上方开始顺时针分别是0-5
net类: 表示整个网络,按照给定的数字,可以生成包含该数字的最小网络(从中心向外一圈圈辐射).
layer是net类中比较重要的一个数据,保存了每一层的属性: [最小数字a,最大数字b,每边cell个数n].其中对照图可以发现,每一圈都可以看做是一个六边形,有六个顶点,六条边.
这个六边形的边上会有cell(从第2层开始),因此知道了层数L,该层的网格就是从a到b一共(b-a+1)=(n*6+6)=(L*6)个(第0层比较特殊,只有一个1).
边的编号与cell的邻居编号略有差别,从第0号顶点坐标开始编号,因此边与顶点的对应关系是:
e0: v5-v0; e1: v0-v1; ... e5: v4-v5
node类: 表示搜索路径时的节点,类似于单链表,用来从出口回溯到入口.每个节点都保存了父节点信息.
bfs函数: 就是最简单的广度优先搜素,如果某cell的邻居中有未访问过的cell,加入搜索队列,直到找到出口为止.由于net类初始化时使用了2个网格的最大下标,因此可以保证肯定能找到至少一条路径.
实现代码:
class cell(object):
# hexagon cell
def __init__(self,ind,neighbours=None):
self.ind = ind
if neighbours and len(neighbours)==6:
self.nbs = neighbours
else:
self.nbs = [None]*6
# start from top neighbour, clock wise direction
def setnb(self,n,nb):
self.nbs[n] = nb
def __repr__(self):
'''
0 1 0
6 * 2
5 * 3
0 4 0
'''
rpd = [x and (isinstance(x,cell) and x.ind or x) or 0 for x in self.nbs]
ind = [[0,rpd[0],0],
[rpd[5],self.ind,rpd[1]],
[rpd[4],self.ind,rpd[2]],
[0,rpd[3],0]]
ma = max([max(x) for x in ind]) # max number
return '\n[\n'+'\n'.join([' '.join([('{:'+str(len(str(ma)))+',d}').format(d) for d in x]) for x in ind])+'\n]\n'
class net(object):
# hexagon net start from centre
def __init__(self,num):
# each layer(like round circle): min_num,max_num,nums,edge_length
# if consider each layer a bigger hexagon, then the vertices are same
# as the cell definition. However, the edge is introduced for layers
# (the layer id starts from 0), means the cell between vertices.
# edge0: v5-v0 (up left); edge1: v0-v1 (up right)
# edge2: v1-v2 (right); edge3: v2-v3 (down right)
# edge4: v3-v4 (down left); edge5: v4-v5(left)
self.layer = [(1,1,1,0)]
# find the max number contains num
i = 0
self.max = 1
new_min, new_max, new_len, new_num = 0,0,0,0
while self.max<num:
i += 1
new_num = 6*i
self.max += new_num
new_min = self.layer[-1][1]+1
new_max = new_min+new_num-1
new_len = ((i-1)>0 and [i-1] or [0])[0]
self.layer.append((new_min,new_max,new_num,new_len))
# create the cells
self.cells = [cell(i+1) for i in range(self.max)]
self.setinfo()
def link(self,c1,c2,a,b):
# set neighbours of 2 cells
# c1's a-th neighbour is c2
# c2's b-th neighbour is c1
c1.setnb(a,c2)
c2.setnb(b,c1)
def setinfo(self):
# set up neighbours for all cell in the network layer by layer
# only set to the inner one using double link, start from the edge0
# layer id start from the second layer
for lid in range(1,len(self.layer)):
cur_ind = self.layer[lid][0] # start index
# edge e0, only set 3,2,1
for i in range(self.layer[lid][-1]): # loop number on the edge
if cur_ind==self.layer[lid][0]: # the start number
self.link(self.cells[cur_ind-1],self.cells[self.layer[lid-1][1]-1],3,0)
self.link(self.cells[cur_ind-1],self.cells[self.layer[lid-1][0]-1],2,5)
else: # the others
self.link(self.cells[cur_ind-1],self.cells[cur_ind-(lid-1)*6-1-1],3,0)
self.link(self.cells[cur_ind-1],self.cells[cur_ind-(lid-1)*6-1],2,5)
self.link(self.cells[cur_ind-1],self.cells[cur_ind+1-1],1,4)
cur_ind += 1
# vertex v0, only set 3,2
self.link(self.cells[cur_ind-1],self.cells[cur_ind-(lid-1)*6-1-1],3,0)
self.link(self.cells[cur_ind-1],self.cells[cur_ind+1-1],2,5)
cur_ind += 1
# edge e1, only set 4,3,2
for i in range(self.layer[lid][-1]):
self.link(self.cells[cur_ind-1],self.cells[cur_ind-(lid-1)*6-2-1],4,1)
self.link(self.cells[cur_ind-1],self.cells[cur_ind-(lid-1)*6-1-1],3,0)
self.link(self.cells[cur_ind-1],self.cells[cur_ind+1-1],2,5)
cur_ind += 1
# vertex v1, only set 4,3
self.link(self.cells[cur_ind-1],self.cells[cur_ind-(lid-1)*6-2-1],4,1)
self.link(self.cells[cur_ind-1],self.cells[cur_ind+1-1],3,0)
cur_ind += 1
# edge e2, only set 5,4,3
for i in range(self.layer[lid][-1]):
self.link(self.cells[cur_ind-1],self.cells[cur_ind-(lid-1)*6-3-1],5,2)
self.link(self.cells[cur_ind-1],self.cells[cur_ind-(lid-1)*6-2-1],4,1)
self.link(self.cells[cur_ind-1],self.cells[cur_ind+1-1],3,0)
cur_ind += 1
# vertex v2, only set 5,4
self.link(self.cells[cur_ind-1],self.cells[cur_ind-(lid-1)*6-3-1],5,2)
self.link(self.cells[cur_ind-1],self.cells[cur_ind+1-1],4,1)
cur_ind += 1
# edge e3, only set 0,5,4
for i in range(self.layer[lid][-1]):
self.link(self.cells[cur_ind-1],self.cells[cur_ind-(lid-1)*6-4-1],0,3)
self.link(self.cells[cur_ind-1],self.cells[cur_ind-(lid-1)*6-3-1],5,2)
self.link(self.cells[cur_ind-1],self.cells[cur_ind+1-1],4,1)
cur_ind += 1
# vertex v3, only set 0,5
self.link(self.cells[cur_ind-1],self.cells[cur_ind-(lid-1)*6-4-1],0,3)
self.link(self.cells[cur_ind-1],self.cells[cur_ind+1-1],5,2)
cur_ind += 1
# edge e4, only set 1,0,5
for i in range(self.layer[lid][-1]):
self.link(self.cells[cur_ind-1],self.cells[cur_ind-(lid-1)*6-5-1],1,4)
self.link(self.cells[cur_ind-1],self.cells[cur_ind-(lid-1)*6-4-1],0,3)
self.link(self.cells[cur_ind-1],self.cells[cur_ind+1-1],5,2)
cur_ind += 1
# vertex v4, only set 1,0
self.link(self.cells[cur_ind-1],self.cells[cur_ind-(lid-1)*6-5-1],1,4)
self.link(self.cells[cur_ind-1],self.cells[cur_ind+1-1],0,3)
cur_ind += 1
# edge e5, only set 2,1,0
for i in range(self.layer[lid][-1]):
self.link(self.cells[cur_ind-1],self.cells[cur_ind-(lid-1)*6-6-1],2,5)
self.link(self.cells[cur_ind-1],self.cells[cur_ind-(lid-1)*6-5-1],1,4)
self.link(self.cells[cur_ind-1],self.cells[cur_ind+1-1],0,3)
cur_ind += 1
# vertex v5, only set 2,1
self.link(self.cells[cur_ind-1],self.cells[cur_ind-(lid-1)*6-6-1],2,5)
self.link(self.cells[cur_ind-1],self.cells[self.layer[lid][0]-1],1,4)
cur_ind += 1
def get_cells(self):
return self.cells
def get_layer(self):
return self.layer
def __len__(self):
return len(self.cells)
class node(object):
# linked list to save search path
def __init__(self,c,prev):
self.p = prev
self.n = c
def __repr__(self):
return 'Node:'+str(self.n)+'Prev:'+str(self.p)
def bfs(net,a,b):
# breadth-first seach to find the shortedst path from one to another
cells = net.get_cells()
visited = []
path = [node(cells[a-1],None)]
cur = path.pop(0)
while cur.n.ind!=b:
visited.append(cur.n.ind)
path.extend([node(x,cur) for x in cur.n.nbs if x and x.ind not in visited])
cur = path.pop(0)
# back to start
num = 0
path = []
while cur.p:
path.append(str(cur.n.ind))
path.append('->')
num += 1
cur = cur.p
path.append(str(cur.n.ind))
print ' '.join(path[::-1]),'(',num,')'
return num
# test cell
##a = cell(1)
##print a
##c = cell(10)
##a.setnb(0,c)
##print a
##b = cell(1,[2,3,4,5,6,7])
##print b
##b.setnb(2,20)
##print b
# test net
##n = net(8)
##print len(n)
##print n.get_cells()
##print n.get_layer()
# test bfs function
##n = net(8)
##bfs(n,5,11)
def checkio(data):
a, b = data
n = net(max(a,b))
return bfs(n,a,b)
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
assert checkio([2, 9]) == 1, "First"
assert checkio([9, 2]) == 1, "Reverse First"
assert checkio([6, 19]) == 2, "Second, short way"
assert checkio([5, 11]) == 3, "Third"
assert checkio([13, 15]) == 2, "Fourth, One row"
assert checkio([11, 17]) == 4, "Fifth, One more test"
测试结果:
>>> ================================ RESTART ================================ >>> 2 -> 9 ( 1 ) 9 -> 2 ( 1 ) 6 -> 7 -> 19 ( 2 ) 5 -> 1 -> 3 -> 11 ( 3 ) 13 -> 14 -> 15 ( 2 ) 11 -> 3 -> 1 -> 6 -> 17 ( 4 ) >>>
No comments :
Post a Comment