そしてセットを調べて迷路とAStarアルゴリズムを生成して自動的に経路を探します
7399 ワード
ソース:https://github.com/tzous/mazeastar
またはhttps://download.csdn.net/download/zhoury/11929633
ラビリンスリファレンスを生成するhttps://blog.csdn.net/qq_40693171/article/details/100716766
一、前半は迷宮生成
二、A*アルゴリズムは経路を探す
またはhttps://download.csdn.net/download/zhoury/11929633
ラビリンスリファレンスを生成するhttps://blog.csdn.net/qq_40693171/article/details/100716766
一、前半は迷宮生成
import random
#
aa = 5
tree = [] #
isling = [] #
for i in range(0, aa):
ta = []
for j in range(0, aa):
ta.append(-1) # -1
tree.append(ta)
for i in range(0, aa * aa):
tb = []
for j in range(0, aa * aa):
tb.append(-1) # -1
isling.append(tb)
def getnei(a): # ， random
x = int(a / aa) #
y = a % aa
mynei = [] #
if x - 1 >= 0:
mynei.append((x - 1) * aa + y) #
if x + 1 < aa:
mynei.append((x + 1) * aa + y) #
if y - 1 >= 0:
mynei.append(x * aa + y - 1) #
if y + 1 < aa:
mynei.append(x * aa + y + 1) #
ran = random.randint(0, len(mynei) - 1)
return (mynei[ran])
def search(a): #
if tree[int(a / aa)][a % aa] > 0: #
return search(tree[int(a / aa)][a % aa])
else:
return a
def union(a, b): #
a1 = search(a) # a
b1 = search(b) # b
if a1 != b1:
if tree[int(a1 / aa)][a1 % aa] < tree[int(b1 / aa)][b1 % aa]: # ()
tree[int(a1 / aa)][a1 % aa] += tree[int(b1 / aa)][b1 % aa] #
tree[int(b1 / aa)][b1 % aa] = a1 # b a ，b b1 a， >0
else:
tree[int(b1 / aa)][b1 % aa] += tree[int(a1 / aa)][a1 % aa]
tree[int(a1 / aa)][a1 % aa] = b1 # a b ， >0
while search(0) != search(aa * aa - 1): #
num = int(random.randint(0, aa * aa - 1)) # aa*aa-1
neihbour = getnei(num) #
if search(num) == search(neihbour): #
continue
else: #
isling[num][neihbour] = 1 # num neihbour
isling[neihbour][num] = 1
union(num, neihbour)
#
#
s = "+"
for j in range(0, aa):
s = s + "-+"
print(s)
# aa-1
for i in range(0, aa):
s = "|"
for k in range(0, aa - 1): #
s = s + " "
if isling[i * aa + k][i * aa + k + 1] == 1:
s = s + " "
else:
s = s + "|"
s = s + " |" #
print(s)
# ，
s = "+"
for k in range(0, aa):
if i < aa - 1: #
if isling[i * aa + k][(i + 1) * aa + k] == 1:
s = s + " "
else:
s = s + "-"
s = s + "+"
else: #
s = s + "-+"
print(s)
二、A*アルゴリズムは経路を探す
# AStar
#
class Node: #
def __init__(self, x, y):
self.x = x #
self.y = y
self.g = 0 #
self.h = 0 #
self.px = -1 # x
self.py = -1 # y
class AStar: #
def __init__(self, w, h, isling):
self.W = w #
self.H = h #
self.Isling = isling #
self.OpenSet = [] #
self.CloseSet = [] #
def findPath(self, startNode, endNode): #
curNode = startNode #
bFound = False
while (not bFound):
self.CloseSet.append(curNode) #
cura = curNode.x * self.W + curNode.y #
arrs = []
if curNode.x - 1 >= 0:
arrs.append([curNode.x - 1, curNode.y]) #
if curNode.x + 1 < self.W:
arrs.append([curNode.x + 1, curNode.y]) #
if curNode.y - 1 >= 0:
arrs.append([curNode.x, curNode.y - 1]) #
if curNode.y + 1 < self.H:
arrs.append([curNode.x, curNode.y + 1]) #
for arr in arrs:
a = arr[0] * self.W + arr[1] #
if self.Isling[cura][a] != 1: # ，
continue
found = 0
for cnode in self.CloseSet: # CloseSet
if cnode.x == arr[0] and cnode.y == arr[1]: # OpenSet
found = 1
break
if found == 1: # Closet ，
continue
node = Node(arr[0], arr[1])
node.g = curNode.g + 1 #
node.h = abs(node.x - endNode.x) + abs(node.y - endNode.y) #
node.px = curNode.x #
node.py = curNode.y
if node.x == endNode.x and node.y == endNode.y: # ， ，
self.CloseSet.append(node)
bFound = True
return node
found = 0
i = -1
for onode in self.OpenSet: # OpenSet
i = i + 1
if onode.x == node.x and onode.y == node.y: # OpenSet
if node.g < onode.g: # g ，
self.OpenSet[i].g = node.g
self.OpenSet[i].h = node.h
self.OpenSet[i].px = node.px
self.OpenSet[i].py = node.py
found = 1
break
if found == 0: # OpenSet ， OpenSet
self.OpenSet.append(node)
# OpenSet f=g+h ，
f = 99999
i = -1
j = -1
for onode in self.OpenSet:
i = i + 1
if f > onode.g + onode.h:
f = onode.g + onode.h
j = i
if j < 0: # OpenSet ，
return None
else:
curNode = self.OpenSet[j]
del self.OpenSet[j]
astar = AStar(aa, aa, isling)
startNode = Node(0, 0)
endNode = Node(aa - 1, aa - 1)
node = astar.findPath(startNode, endNode)
if node == None:
print(" ")
exit
astar.CloseSet.reverse()
for cnode in astar.CloseSet:
if cnode.x == node.x and cnode.y == node.y:
tree[node.x][node.y] = aa*aa
node.x = cnode.px
node.y = cnode.py
#
#
s = "+"
for j in range(0, aa):
s = s + "-+"
print(s)
# aa-1
for i in range(0, aa):
s = "|"
for k in range(0, aa - 1): #
if tree[i][k] == aa*aa:
s = s + "@"
else:
s = s + " "
if isling[i * aa + k][i * aa + k + 1] == 1:
s = s + " "
else:
s = s + "|"
if tree[i][aa-1] == aa*aa: #
s = s + "@"
else:
s = s + " "
s = s + "|"
print(s)
# ，
s = "+"
for k in range(0, aa):
if i < aa - 1: #
if isling[i * aa + k][(i + 1) * aa + k] == 1:
s = s + " "
else:
s = s + "-"
s = s + "+"
else: #
s = s + "-+"
print(s)