Pancake's Personal Website

说明：文章所示优化对某些地图有一定优化作用，运行速度可以提高2倍以上，但很大程度上会牺牲准确度，并且很多时候并不能用此方法加速运行，请在有一定A*算法代码基础上阅读。代码中piecemeal_matrix判断边界函数没有那么完美，只是提供一种参考，有兴趣的朋友可以和我一起改进。

A*算法在迷宫很复杂的情况下运行速度会很慢，甚至会和Dijkstra算法运行速度差不多，比如遇到如下这张复杂地图：

尽管只有约100*100像素，但是在我电脑上要运行10s左右时间才能计算出来（我电脑运行速度比较慢，不同电脑运行时间不同，文章测试环境均为同一台电脑）

遇到这种规则的方方正正的迷宫，我们可以运用（伪）图片缩小。不同于直接缩小图片，更可以说成对迷宫切片，防止图片缩小变糊。简单算法思路：把迷宫围墙边界作为转换后矩阵像素，类似于边缘检测，如下图x轴方向上的切片：

最终可以得到如下切片/缩小后图片：

最终结果对比：

优化前10s左右运行速度得出的图片：

优化后5s左右运行速度得出的图片：

切片优化python代码

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)

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代码

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)

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)

具体A*算法代码可见我的博客

Timus #1005

Timus #1296

GitHub 访问及下载加速方法

优化A* 算法运行时间python代码

切片优化python代码

优化前python代码

letax tips