说明：文章所示优化对某些地图有一定优化作用，运行速度可以提高2倍以上，但很大程度上会牺牲准确度，并且很多时候并不能用此方法加速运行，请在有一定A*算法代码基础上阅读。代码中piecemeal_matrix判断边界函数没有那么完美，只是提供一种参考，有兴趣的朋友可以和我一起改进。
A*算法在迷宫很复杂的情况下运行速度会很慢，甚至会和Dijkstra算法运行速度差不多，比如遇到如下这张复杂地图：
尽管只有约100*100像素，但是在我电脑上要运行10s左右时间才能计算出来（我电脑运行速度比较慢，不同电脑运行时间不同，文章测试环境均为同一台电脑）
遇到这种规则的方方正正的迷宫，我们可以运用（伪）图片缩小。不同于直接缩小图片，更可以说成对迷宫切片，防止图片缩小变糊。简单算法思路：把迷宫围墙边界作为转换后矩阵像素，类似于边缘检测，如下图x轴方向上的切片：
最终可以得到如下切片/缩小后图片：
最终结果对比：
优化前10s左右运行速度得出的图片：
优化后5s左右运行速度得出的图片：
切片优化python代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
import numpy import numpy as np from numba import jit from A_star import A_star from PIL import Image import time # 把大矩阵切分成小矩阵 # jit 修饰可要可不要，jit只是为了加快程序运行速度，最好加上 @jit def piecemeal_matrix(matrix): length = [0, len(matrix[0]) - 1] width = [0, len(matrix) - 1] for i in range(1, len(matrix) - 1): for j in range(1, len(matrix[i]) - 1): if not matrix[i][j] and not matrix[i + 1][j] and matrix[i - 1][j] or not matrix[i][j] and not matrix[i - 1][j] and matrix[i + 1][j]: if i not in width: width.append(i) if not matrix[i][j] and not matrix[i][j + 1] and matrix[i][j - 1] or not matrix[i][j] and not matrix[i][j - 1] and matrix[i][j + 1]: if j not in length: length.append(j) length.sort() width.sort() return [length, width] # 找到转换过后的 values def find_values(matrix, x, y, start_point, end_point): changed_matrix = [] for i in range(len(x[:-1])): temp_bool = [] for j in range(len(y[:-1])): ii = (x[i] + x[i + 1]) // 2 jj = (y[j] + y[j + 1]) // 2 temp_bool.append(matrix[ii][jj]) changed_matrix.append(temp_bool) changed_start_point = [0, 0] for i in range(len(x) - 1): if x[i] <= start_point[0] < x[i + 1]: changed_start_point[0] = i break for i in range(len(y) - 1): if y[i] <= start_point[1] < y[i + 1]: changed_start_point[1] = i break changed_end_point = [0, 0] for i in range(len(x) - 1): if x[i] <= end_point[0] < x[i + 1]: changed_end_point[0] = i break for i in range(len(y) - 1): if y[i] <= end_point[1] < y[i + 1]: changed_end_point[1] = i break return [changed_matrix, changed_start_point, changed_end_point] # 转换成实际线路 def find_road(road, x, y, start_point, end_point): for i in range(len(road)): road[i][0] = (x[road[i][0]] + x[road[i][0] + 1]) // 2 road[i][1] = (y[road[i][1]] + y[road[i][1] + 1]) // 2 road.insert(0, end_point) road.append(start_point) road = supply_road(road) return road # 把 road 点补充成线 def supply_road(road): length = len(road) for i in range(length - 1): k = road[i + 1][0] - road[i][0] for j in range(0, k + 1 if k > 0 else k - 1, 1 if k > 0 else -1): road.append([road[i][0] + j, road[i][1]]) k = road[i + 1][1] - road[i][1] for j in range(0, k + 1 if k > 0 else k - 1, 1 if k > 0 else -1): road.append([road[i + 1][0], road[i][1] + j]) return road def piecemeal_A_star(file_location): image = Image.open(file_location) # 如果本来就是黑白图片可以省去下列这条代码 matrix = np.array(image.convert("1")) start_point = [3, 3] end_point = [110, 110] [y, x] = piecemeal_matrix(matrix) [changed_matrix, changed_start_point, changed_end_point] = find_values(matrix, x, y, start_point, end_point) # Image.fromarray(numpy.array(changed_matrix)).save("maze_changed.png") Road = A_star(matrix=changed_matrix).run(start_point=changed_start_point, end_point=changed_end_point) Road = find_road(Road, x, y, start_point, end_point) if Road else [] _matrix = np.ones(len(matrix[0]) * len(matrix) * 3).reshape(len(matrix), len(matrix[0]), 3) for x in range(len(matrix)): for y in range(len(matrix[x])): if [x, y] in Road: _matrix[x][y] = [255, 0, 0] elif not matrix[x][y]: _matrix[x][y] = [0, 0, 0] else: _matrix[x][y] = [255, 255, 255] # Image.fromarray(np.uint8(_matrix)).save("maze_road.png") if __name__ == "__main__": begin_time = time.time() piecemeal_A_star("blackwhite.bmp") print(time.time()-begin_time) |
优化前python代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 |
import numpy as np from math import sqrt from PIL import Image import time class A_star: def __init__(self, matrix, weights=1, corner_amend=1, step=float("inf"), way=["R", "L", "D", "U", "RU", "RD", "LU", "LD"], wall=0): self.matrix = matrix self.weights = weights self.corner_amend = corner_amend self.matrix_length = len(self.matrix[0]) self.matrix_width = len(self.matrix) self.step = step self.way = way self.wall = wall self.field = np.array(np.copy(self.matrix), dtype=float) for i in range(self.matrix_width): for j in range(self.matrix_length): if self.field[i][j] == self.wall: self.field[i][j] = float("inf") def run(self, start_point, end_point): self.fieldpointers = np.array(np.copy(self.matrix), dtype=str) self.start_point = start_point self.end_point = end_point if int(self.matrix[self.start_point[0]][self.start_point[1]]) == self.wall or int(self.matrix[self.end_point[0]][self.end_point[1]] == self.wall): exit("start or end is wall") self.fieldpointers[self.start_point[0]][self.start_point[1]] = "S" self.fieldpointers[self.end_point[0]][self.end_point[1]] = "G" return self.a_star() def a_star(self): setopen = [self.start_point] setopencosts = [0] setopenheuristics = [float("inf")] setclosed = [] setclosedcosts = [] movementdirections = self.way while self.end_point not in setopen and self.step: self.step -= 1 total_costs = list(np.array(setopencosts) + self.weights * np.array(setopenheuristics)) temp = np.min(total_costs) ii = total_costs.index(temp) if setopen[ii] != self.start_point and self.corner_amend == 1: new_ii = self.Path_optimization(temp, ii, setopen, setopencosts, setopenheuristics) ii = new_ii [costs, heuristics, posinds] = self.findFValue(setopen[ii], setopencosts[ii]) setclosed = setclosed + [setopen[ii]] setclosedcosts = setclosedcosts + [setopencosts[ii]] setopen.pop(ii) setopencosts.pop(ii) setopenheuristics.pop(ii) for jj in range(len(posinds)): if float("Inf") != costs[jj]: if not posinds[jj] in setclosed + setopen: self.fieldpointers[posinds[jj][0]][posinds[jj][1]] = movementdirections[jj] setopen = setopen + [posinds[jj]] setopencosts = setopencosts + [costs[jj]] setopenheuristics = setopenheuristics + [heuristics[jj]] elif posinds[jj] in setopen: position = setopen.index(posinds[jj]) if setopencosts[position] > costs[jj]: setopencosts[position] = costs[jj] setopenheuristics[position] = heuristics[jj] self.fieldpointers[setopen[position][0]][setopen[position][1]] = movementdirections[jj] else: position = setclosed.index(posinds[jj]) if setclosedcosts[position] > costs[jj]: setclosedcosts[position] = costs[jj] self.fieldpointers[setclosed[position][0]][setclosed[position][1]] = movementdirections[jj] if not setopen: exit("Can't") if self.end_point in setopen: rod = self.findWayBack(self.end_point) return rod else: exit("Can't") def Path_optimization(self, temp, ii, setOpen, setOpenCosts, setOpenHeuristics): [row, col] = setOpen[ii] _temp = self.fieldpointers[row][col] if "L" in _temp: col -= 1 elif "R" in _temp: col += 1 if "U" in _temp: row -= 1 elif "D" in _temp: row += 1 if [row, col] == self.start_point: new_ii = ii else: _temp = self.fieldpointers[row][col] [row2, col2] = [row, col] if "L" in _temp: col2 += self.matrix_width elif "R" in _temp: col2 -= self.matrix_width if "U" in _temp: row2 += 1 elif "D" in _temp: row2 -= 1 if 0 <= row2 <= self.matrix_width and 0 <= col2 <= self.matrix_length: new_ii = ii else: if self.fieldpointers[setOpen[ii][0]][setOpen[ii][1]] == self.fieldpointers[row][col]: new_ii = ii elif [row2, col2] in setOpen: untext_ii = setOpen.index([row2, col2]) now_cost = setOpenCosts[untext_ii] + self.weights * setOpenHeuristics[untext_ii] if temp == now_cost: new_ii = untext_ii else: new_ii = ii else: new_ii = ii return new_ii def findFValue(self, currentpos, costsofar): cost = [] heuristic = [] posinds = [] for way in self.way: if "D" in way: x = currentpos[0] - 1 elif "U" in way: x = currentpos[0] + 1 else: x = currentpos[0] if "R" in way: y = currentpos[1] - 1 elif "L" in way: y = currentpos[1] + 1 else: y = currentpos[1] if 0 <= y <= self.matrix_length - 1 and 0 <= x <= self.matrix_width - 1: posinds.append([x, y]) heuristic.append(sqrt((self.end_point[1] - y) ** 2 + (self.end_point[0] - x) ** 2)) cost.append(costsofar + self.field[x][y]) else: posinds.append([0, 0]) heuristic.append(float("inf")) cost.append(float("inf")) return [cost, heuristic, posinds] def findWayBack(self, goal): road = [goal] [x, y] = goal while self.fieldpointers[x][y] != "S": temp = self.fieldpointers[x][y] if "L" in temp: y -= 1 if "R" in temp: y += 1 if "U" in temp: x -= 1 if "D" in temp: x += 1 road.append([x, y]) return road if __name__ == "__main__": begintime = time.time() image = Image.open("blackwhite.bmp") # 如果本来就是黑白图片可以省去下列这条代码 matrix = np.array(image.convert("1")) start_point = [3, 3] end_point = [110, 110] Road = A_star(matrix=matrix).run(start_point, end_point) # for i in Road: # image.putpixel((i[1], i[0]), (255, 0, 0)) # image.save("maze_reference.png") print(time.time()-begintime) |
浙公网安备 33010902002953号