2022 年 3 月 – Pancake's Personal Website

GitHub 访问及下载加速方法

自己电脑常用方式：
SteamCommunity302
及得勾上github
服务器常用镜像下载网站
https://ghproxy.com/

GIT CLONE：
git clone https://ghproxy.com/https://github.com/stilleshan/ServerStatus

WGET & CURL：
wget https://ghproxy.com/https://github.com/stilleshan/ServerStatus/archive/master.zip
wget https://ghproxy.com/https://raw.githubusercontent.com/stilleshan/ServerStatus/master/Dockerfile
curl -O https://ghproxy.com/https://github.com/stilleshan/ServerStatus/archive/master.zip
curl -O https://ghproxy.com/https://raw.githubusercontent.com/stilleshan/ServerStatus/master/Dockerfile

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

说明：文章所示优化对某些地图有一定优化作用，运行速度可以提高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*算法代码可见我的博客

letax tips

表格斜杠
参考链接
eg：

\usepackage{diagbox}
\diagbox {Year}{Deviation} & Residual Error & Class Ratio Dispersion\\

1 2	\usepackage{diagbox} \diagbox {Year}{Deviation} & Residual Error & Class Ratio Dispersion\\

表格跨页
参考链接
eg：

\usepackage{longtable}
\begin{center}
\begin{longtable}{clc} 
\caption{Symbol}
   \label{table:label}  \\
	\toprule 
 \textbf{Symbol} & \multicolumn{1}{c}{\centering \textbf{Definition}} & \textbf{Unit}\\
	\midrule
$CP$ & Critical Power & W \\[0.2cm]
	\bottomrule
\end{longtable}
\end{center}

\usepackage{longtable}

\begin{center}

\begin{longtable}{clc}

\caption{Symbol}

\label{table:label} \\

\toprule

\textbf{Symbol} & \multicolumn{1}{c}{\centering \textbf{Definition}} & \textbf{Unit}\\

\midrule

$CP$ & Critical Power & W \\[0.2cm]

\bottomrule

\end{longtable}

\end{center}

图片强制固定
参考链接

\usepackage{graphicx} 
\usepackage{float}
\begin{figure}[H] %加H是为了固定图片位置
\centering
\includegraphics[width=1.0\linewidth,height=0.2\textheight]{图片名称.png}
\caption*{图片标题}
\end{figure}

\usepackage{graphicx}

\usepackage{float}

\begin{figure}[H] %加H是为了固定图片位置

\centering

\includegraphics[width=1.0\linewidth,height=0.2\textheight]{图片名称.png}

\caption*{图片标题}

\end{figure}

子图
参考链接（和下列示例方法不一样）
示例代码为2*3即2行三列代码
\linewidth为一行的宽度，如下面代码所示，若要在一行放三张照片则每张照片需要<=1/3行宽，设置{0.3\linewidth}就需要根据你一行有多少照片而定。
\textwidth则无需特别修改。
若要换行图片则直接加一行空行就行。
eg:

\begin{figure}[H]
\centering
\begin{subfigure}[b]{0.3\linewidth}
\includegraphics[width=\textwidth]{power wind friction.png}
\caption{The influence of drag coefficient on power}\label{subfig:left}
\end{subfigure}
\begin{subfigure}[b]{0.3\linewidth}
\includegraphics[width=\textwidth]{v wind friction.png}
\caption{The influence of drag coefficient on velocity}\label{subfig:right}
\end{subfigure}
\begin{subfigure}[b]{0.3\linewidth}
\includegraphics[width=\textwidth]{time wind friction.png}
\caption{The influence of drag coefficient on time to finish racing}
\end{subfigure}

\begin{subfigure}[b]{0.3\linewidth}
\includegraphics[width=\textwidth]{power wind direction.png}
\caption{The influence of wind direction on power}\label{subfig:left}
\end{subfigure}
\begin{subfigure}[b]{0.3\linewidth}
\includegraphics[width=\textwidth]{v wind direction.png}
\caption{The influence of wind direction on velocity}\label{subfig:right}
\end{subfigure}
\begin{subfigure}[b]{0.3\linewidth}
\includegraphics[width=\textwidth]{time wind direction.png}
\caption{The influence of wind direction on time to finish racing}
\end{subfigure}
\caption{The influence of drag coefficient}\label{fig:subfigures}
\end{figure}

\begin{figure}[H]

\centering

\begin{subfigure}[b]{0.3\linewidth}

\includegraphics[width=\textwidth]{power wind friction.png}

\caption{The influence of drag coefficient on power}\label{subfig:left}

\end{subfigure}

\begin{subfigure}[b]{0.3\linewidth}

\includegraphics[width=\textwidth]{v wind friction.png}

\caption{The influence of drag coefficient on velocity}\label{subfig:right}

\end{subfigure}

\begin{subfigure}[b]{0.3\linewidth}

\includegraphics[width=\textwidth]{time wind friction.png}

\caption{The influence of drag coefficient on time to finish racing}

\end{subfigure}

\begin{subfigure}[b]{0.3\linewidth}

\includegraphics[width=\textwidth]{power wind direction.png}

\caption{The influence of wind direction on power}\label{subfig:left}

\end{subfigure}

\begin{subfigure}[b]{0.3\linewidth}

\includegraphics[width=\textwidth]{v wind direction.png}

\caption{The influence of wind direction on velocity}\label{subfig:right}

\end{subfigure}

\begin{subfigure}[b]{0.3\linewidth}

\includegraphics[width=\textwidth]{time wind direction.png}

\caption{The influence of wind direction on time to finish racing}

\end{subfigure}

\caption{The influence of drag coefficient}\label{fig:subfigures}

\end{figure}

wordpress 近期文章去除置顶文章

原作者链接（大量参考）

vim /usr/share/nginx/html/wordpress/wp-includes/widgets/class-wp-widget-recent-posts.php

找到如下代码删除并修改

<ul>
<?php
    $recentPosts =  new WP_Query(array('post__not_in' => get_option('sticky_posts'),'posts_per_page' => $number));
?>
<?php while ($recentPosts->have_posts()) : $recentPosts->the_post(); ?>
    <li> <a href="<?php the_permalink() ?>" rel="bookmark" class="title"><?php echo  get_the_title(); ?></a>
         <?php if ( $show_date ) : ?> 
             <?php  the_time('y/m/d'); ?>
         <?php endif; ?>  
    </li> 
<?php endwhile; wp_reset_query();?>
</ul>

<ul>

<?php

$recentPosts = new WP_Query(array('post__not_in' => get_option('sticky_posts'),'posts_per_page' => $number));

<?php while ($recentPosts->have_posts()) : $recentPosts->the_post(); ?>

<li> <a href="<?php the_permalink() ?>" rel="bookmark" class="title"><?php echo get_the_title(); ?></a>

<?php if ( $show_date ) : ?>

<?php the_time('y/m/d'); ?>

<?php endif; ?>

</li>

<?php endwhile; wp_reset_query();?>

</ul>

A* 算法 Python 代码

版本说明：
V1.0版本为只有固定上下左右四个方向进行规划路线。
V2.0版本对V1.0做出了提升，现在可以填入任意方向（至多8个方向）进行路线规划。
V3.0版本删除了sub和index的互相转换，减少了算法复杂度。优化了代码，增加可重复使用性。发现并改正了total_costs计算错误。

V3.0使用方法：
(1)
from 文件名 import A_star
a_star = A_star(matrix=[], step=1000, way=[“R”, “L”, “D”, “U”, “RU”, “RD”, “LU”, “LD”], wall=0)
road = a_star.run(start_point=[],end_point=[]) #可重复使用

或者直接
from 文件名 import A_star
road = A_star(matrix=[], step=1000, way=[“R”, “L”, “D”, “U”, “RU”, “RD”, “LU”, “LD”], wall=0).run(start_point=[],end_point=[])

输出为二位点坐标数组eg:[[10, 10], [9, 9], [8, 8], [7, 7], [6, 6], [5, 5], [4, 4], [3, 3], [2, 2], [1, 1], [0, 0]]

(2)参数说明：
start_point 为起始坐标.
end_point为终点坐标.
matrix为地图/迷宫地图，bool类型.
wall为matrix里True/False哪个为墙，False为墙写0，True为墙写1.
weight为权值（不用特别调整）.
Corner_amend为拐角优化，1开启，0关闭.
step表示运行一定循环后退出程序，防止因为地图过大无限运行。代码默认无限循环即step=float(“inf”)，推荐加入限制条件，减少特定程序时间.
way表示可以走的方向，eg：[“R”, “L”, “D”, “U”, “RU”, “RD”, “LU”, “LD”]。需要大写（因为没写upper操作）.

说明：
该代码为matlab改编成的python代码并经过我的相关优化，有一定参考性，在pycharm debug调试中你可以测试该算法逻辑，希望对你有帮助。

待更新：
无
如果代码有错误请和我联系，我会及时改正。

V3.0版本代码

import numpy as np
from math import sqrt


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
        # 当你知道你的 way 配置保证问题的时候下面三行可进行更改，虽然没有加快多少速度
        self.way = list(map(lambda x: x.upper(), way))
        if len(set(self.way + ["R", "L", "D", "U", "RU", "RD", "LU", "LD"])) != 8:
            exit("Error 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 += 1
            elif "R" in _temp:
                col2 -= 1
            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__":
    print(A_star(matrix=[[True for i in range(1000)] for j in range(1000)]).run(start_point=[0, 0], end_point=[999, 999]))

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

import numpy as np

from math import sqrt

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

# 当你知道你的 way 配置保证问题的时候下面三行可进行更改，虽然没有加快多少速度

self.way = list(map(lambda x: x.upper(), way))

if len(set(self.way + ["R", "L", "D", "U", "RU", "RD", "LU", "LD"])) != 8:

exit("Error 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 += 1

elif "R" in _temp:

col2 -= 1

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__":

print(A_star(matrix=[[True for i in range(1000)] for j in range(1000)]).run(start_point=[0, 0], end_point=[999, 999]))

A*算法可视化参考代码

from PIL import Image
import numpy as np
import os
import imageio

# 删除文件夹下原有图片
list_dir = os.listdir()
for i in range(len(list_dir)):
    if "visualization" in list_dir[i] and ".jpg" in list_dir[i]:
        os.remove(list_dir[i])


# 合成 picture 文件夹下图片成jpg， fps为帧率， between为多少张图片选一张（防止图片过多）
def output_gif(fps, between):
    image_path = os.listdir("./picture")
    gif_image = []
    i = 0
    while 1:
        if "picture{}.jpg".format(i) in image_path:
            gif_image.append(imageio.imread("./picture/picture{}.jpg".format(i)))
        else:
            break
        i += between
    imageio.mimsave("test.gif", gif_image, fps=fps)


# location 为原图片， road为A*算法找到的路，如果要输出A*算法每步的图片，建议把im = Image.open(location)设置成全局变量，加快运行速度
def visualize(location, road):
    filenames = os.listdir()
    count = 0
    if "visualization0.jpg" in filenames:
        for filename in filenames:
            if "visualization" in filename and ".jpg" in filename and "Edge" not in filename:
                now = int(filename.split(".")[-2][13:])
                count = count if count > now else now + 1
    name = "visualization{}.jpg".format(count)
    im = Image.open(location)
    for i in road:
        pos = (i[1], i[0])
        im.putpixel(pos, (255, 0, 0))
    im.save(name)

from PIL import Image

import numpy as np

import os

import imageio

# 删除文件夹下原有图片

list_dir = os.listdir()

for i in range(len(list_dir)):

if "visualization" in list_dir[i] and ".jpg" in list_dir[i]:

os.remove(list_dir[i])

# 合成 picture 文件夹下图片成jpg， fps为帧率， between为多少张图片选一张（防止图片过多）

def output_gif(fps, between):

image_path = os.listdir("./picture")

gif_image = []

i = 0

while 1:

if "picture{}.jpg".format(i) in image_path:

gif_image.append(imageio.imread("./picture/picture{}.jpg".format(i)))

else:

break

i += between

imageio.mimsave("test.gif", gif_image, fps=fps)

# location 为原图片， road为A*算法找到的路，如果要输出A*算法每步的图片，建议把im = Image.open(location)设置成全局变量，加快运行速度

def visualize(location, road):

filenames = os.listdir()

count = 0

if "visualization0.jpg" in filenames:

for filename in filenames:

if "visualization" in filename and ".jpg" in filename and "Edge" not in filename:

now = int(filename.split(".")[-2][13:])

count = count if count > now else now + 1

name = "visualization{}.jpg".format(count)

im = Image.open(location)

for i in road:

pos = (i[1], i[0])

im.putpixel(pos, (255, 0, 0))

im.save(name)

下面为历史版本代码：

V2.0使用方法：
(1)from 文件名 import A_star
A_star(各种参数).a_star()
(2)参数说明：
start_point 为起始坐标可以像matlab一样输入单个或二维索引
end_point为终点坐标可以像matlab一样输入单个或二维索引
matrix为地图/迷宫地图，bool类型，True为可走的路，False为不可走的墙
weight为权值（不用特别调整）
Corner_amend为拐角优化，1开启，0关闭
step表示运行一定循环后退出程序，防止因为地图过大无限运行，如果想要无限运行可以删除有关step代码
way表示可以走的方向，eg：[“R”, “L”, “D”, “U”, “RU”, “RD”, “LU”, “LD”]。需要大写（因为没写upper操作）

V2.0版本

import numpy as np
from math import sqrt


class A_star:
    def __init__(self, start_point=[0, 0], end_point=[10, 10], matrix=[[True for i in range(11)] for j in range(11)], weights=1.1, Corner_amend=1, step=1000,
                 way=["R", "L", "D", "U", "RU", "RD", "LU", "LD"]):
        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.start_point = self.sub2index(start_point) if type(start_point) != int else start_point
        self.end_point = self.sub2index(end_point) if type(end_point) != int else end_point
        self.startx, self.starty = self.index2sub(self.start_point)
        self.endx, self.endy = self.index2sub(self.end_point)
        self.step = step
        self.way = way
        if not (self.matrix[self.startx][self.starty] and self.matrix[self.endx][self.endy]):
            exit("start or end is wall")

    def a_star(self):
        field = self.chansform_field()
        fieldpointers = self.chansform_fieldpointers()
        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 = setopencosts + list(self.weights * np.array(setopenheuristics))
            temp = np.min(setopencosts)
            ii = total_costs.index(temp)
            if setopen[ii] != self.start_point and self.corner_amend == 1:
                new_ii = self.Path_optimization(temp, ii, fieldpointers, setopen, setopencosts, setopenheuristics)
                ii = new_ii
            [costs, heuristics, posinds] = self.findFValue(setopen[ii], setopencosts[ii], field, self.end_point)
            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:
                        [row, col] = self.index2sub(posinds[jj])
                        fieldpointers[row][col] = movementdirections[jj]
                        setopen = setopen + [posinds[jj]]
                        setopencosts = setopencosts + [costs[jj]]
                        setopenheuristics = setopenheuristics + [heuristics[jj]]
                    elif posinds[jj] in setopen:
                        I = setopen.index(posinds[jj])
                        if setopencosts[I] > costs[jj]:
                            [row, col] = self.index2sub(setopen[I])
                            setopencosts[I] = costs[jj]
                            setopenheuristics[I] = heuristics[jj]
                            fieldpointers[row][col] = movementdirections[jj]
                    else:
                        I = setclosed.index(posinds[jj])
                        if setclosedcosts[I] > costs[jj]:
                            [row, col] = self.index2sub(setclosed[I])
                            setclosedcosts[I] = costs[jj]
                            fieldpointers[row][col] = movementdirections[jj]
            if not setopen:
                exit("Can't")
        if self.end_point in setopen:
            rod = self.findWayBack(self.end_point, fieldpointers)
            return rod
        else:
            exit("Can't")

    def sub2index(self, array):
        return int(array[1] * self.matrix_width + array[0] + 1)

    def Path_optimization(self, temp, ii, fieldpointers, setOpen, setOpenCosts, setOpenHeuristics):
        [row, col] = self.index2sub(setOpen[ii])
        _temp = fieldpointers[row][col]
        Parent_node = setOpen[ii]
        if "L" in _temp:
            Parent_node -= self.matrix_width
        elif "R" in _temp:
            Parent_node += self.matrix_width
        if "U" in _temp:
            Parent_node -= 1
        elif "D" in _temp:
            Parent_node += 1
        if Parent_node == self.start_point:
            new_ii = ii
        else:
            [row, col] = self.index2sub(Parent_node)
            _temp = fieldpointers[row][col]
            Expected_note = Parent_node
            if "L" in _temp:
                Expected_note += self.matrix_width
            elif "R" in _temp:
                Expected_note -= self.matrix_width
            if "U" in _temp:
                Expected_note += 1
            elif "D" in _temp:
                Expected_note -= 1
            if Expected_note < 0 or Expected_note > self.matrix_width * self.matrix_length - 1:
                new_ii = ii
            else:
                [row, col] = self.index2sub(setOpen[ii])
                [row2, col2] = self.index2sub(Parent_node)
                if fieldpointers[row][col] == fieldpointers[row2][col2]:
                    new_ii = ii
                elif Expected_note in setOpen:
                    untext_ii = setOpen.index(Expected_note)
                    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, posind, costsofar, field, goalind):
        currentpos = self.index2sub(posind)
        goalpos = self.index2sub(goalind)
        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((goalpos[1] - y) ** 2 + (goalpos[0] - x) ** 2))
                cost.append(costsofar + field[x][y])
            else:
                posinds.append([0, 0])
                heuristic.append(float("inf"))
                cost.append(float("inf"))
        posinds = list(map(lambda x: self.sub2index(x), posinds))
        return [cost, heuristic, posinds]

    def chansform_field(self):
        field = np.ones((self.matrix_width, self.matrix_length))
        for i in range(self.matrix_width):
            for j in range(self.matrix_length):
                if not self.matrix[i][j]:
                    field[i][j] = float("inf")
        field[self.startx][self.starty] = 0
        field[self.endx][self.endy] = 0
        return field

    def chansform_fieldpointers(self):
        fieldpointers = []
        for i in range(self.matrix_width):
            temp = []
            for j in range(self.matrix_length):
                if self.matrix[i][j]:
                    temp.append(1)
                else:
                    temp.append("inf")
            fieldpointers.append(temp)
        fieldpointers[self.startx][self.starty] = "S"
        fieldpointers[self.endx][self.endy] = "G"
        return fieldpointers

    def findWayBack(self, goalposind, fieldpointers):
        posind = goalposind
        p = self.index2sub(posind)
        sum = [p]
        x = p[0]
        y = p[1]
        while fieldpointers[x][y] != "S":
            temp = 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
            if temp not in self.way:
                print("Error Find way back")
                exit()
            sum.append([x, y])
        return sum

    def index2sub(self, posind):
        row = (posind - 1) % self.matrix_width
        col = (posind - 1) // self.matrix_width
        return [int(row), int(col)]


if __name__ == "__main__":
    print(A_star().a_star())

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

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

import numpy as np

from math import sqrt

class A_star:

def __init__(self, start_point=[0, 0], end_point=[10, 10], matrix=[[True for i in range(11)] for j in range(11)], weights=1.1, Corner_amend=1, step=1000,

way=["R", "L", "D", "U", "RU", "RD", "LU", "LD"]):

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.start_point = self.sub2index(start_point) if type(start_point) != int else start_point

self.end_point = self.sub2index(end_point) if type(end_point) != int else end_point

self.startx, self.starty = self.index2sub(self.start_point)

self.endx, self.endy = self.index2sub(self.end_point)

self.step = step

self.way = way

if not (self.matrix[self.startx][self.starty] and self.matrix[self.endx][self.endy]):

exit("start or end is wall")

def a_star(self):

field = self.chansform_field()

fieldpointers = self.chansform_fieldpointers()

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 = setopencosts + list(self.weights * np.array(setopenheuristics))

temp = np.min(setopencosts)

ii = total_costs.index(temp)

if setopen[ii] != self.start_point and self.corner_amend == 1:

new_ii = self.Path_optimization(temp, ii, fieldpointers, setopen, setopencosts, setopenheuristics)

ii = new_ii

[costs, heuristics, posinds] = self.findFValue(setopen[ii], setopencosts[ii], field, self.end_point)

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:

[row, col] = self.index2sub(posinds[jj])

fieldpointers[row][col] = movementdirections[jj]

setopen = setopen + [posinds[jj]]

setopencosts = setopencosts + [costs[jj]]

setopenheuristics = setopenheuristics + [heuristics[jj]]

elif posinds[jj] in setopen:

I = setopen.index(posinds[jj])

if setopencosts[I] > costs[jj]:

[row, col] = self.index2sub(setopen[I])

setopencosts[I] = costs[jj]

setopenheuristics[I] = heuristics[jj]

fieldpointers[row][col] = movementdirections[jj]

else:

I = setclosed.index(posinds[jj])

if setclosedcosts[I] > costs[jj]:

[row, col] = self.index2sub(setclosed[I])

setclosedcosts[I] = costs[jj]

fieldpointers[row][col] = movementdirections[jj]

if not setopen:

exit("Can't")

if self.end_point in setopen:

rod = self.findWayBack(self.end_point, fieldpointers)

return rod

else:

exit("Can't")

def sub2index(self, array):

return int(array[1] * self.matrix_width + array[0] + 1)

def Path_optimization(self, temp, ii, fieldpointers, setOpen, setOpenCosts, setOpenHeuristics):

[row, col] = self.index2sub(setOpen[ii])

_temp = fieldpointers[row][col]

Parent_node = setOpen[ii]

if "L" in _temp:

Parent_node -= self.matrix_width

elif "R" in _temp:

Parent_node += self.matrix_width

if "U" in _temp:

Parent_node -= 1

elif "D" in _temp:

Parent_node += 1

if Parent_node == self.start_point:

new_ii = ii

else:

[row, col] = self.index2sub(Parent_node)

_temp = fieldpointers[row][col]

Expected_note = Parent_node

if "L" in _temp:

Expected_note += self.matrix_width

elif "R" in _temp:

Expected_note -= self.matrix_width

if "U" in _temp:

Expected_note += 1

elif "D" in _temp:

Expected_note -= 1

if Expected_note < 0 or Expected_note > self.matrix_width * self.matrix_length - 1:

new_ii = ii

else:

[row, col] = self.index2sub(setOpen[ii])

[row2, col2] = self.index2sub(Parent_node)

if fieldpointers[row][col] == fieldpointers[row2][col2]:

new_ii = ii

elif Expected_note in setOpen:

untext_ii = setOpen.index(Expected_note)

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, posind, costsofar, field, goalind):

currentpos = self.index2sub(posind)

goalpos = self.index2sub(goalind)

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((goalpos[1] - y) ** 2 + (goalpos[0] - x) ** 2))

cost.append(costsofar + field[x][y])

else:

posinds.append([0, 0])

heuristic.append(float("inf"))

cost.append(float("inf"))

posinds = list(map(lambda x: self.sub2index(x), posinds))

return [cost, heuristic, posinds]

def chansform_field(self):

field = np.ones((self.matrix_width, self.matrix_length))

for i in range(self.matrix_width):

for j in range(self.matrix_length):

if not self.matrix[i][j]:

field[i][j] = float("inf")

field[self.startx][self.starty] = 0

field[self.endx][self.endy] = 0

return field

def chansform_fieldpointers(self):

fieldpointers = []

for i in range(self.matrix_width):

temp = []

for j in range(self.matrix_length):

if self.matrix[i][j]:

temp.append(1)

else:

temp.append("inf")

fieldpointers.append(temp)

fieldpointers[self.startx][self.starty] = "S"

fieldpointers[self.endx][self.endy] = "G"

return fieldpointers

def findWayBack(self, goalposind, fieldpointers):

posind = goalposind

p = self.index2sub(posind)

sum = [p]

x = p[0]

y = p[1]

while fieldpointers[x][y] != "S":

temp = 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

if temp not in self.way:

print("Error Find way back")

exit()

sum.append([x, y])

return sum

def index2sub(self, posind):

row = (posind - 1) % self.matrix_width

col = (posind - 1) // self.matrix_width

return [int(row), int(col)]

if __name__ == "__main__":

print(A_star().a_star())

V1.0版本

import numpy as np
from math import sqrt


class A_star:
    def __init__(self, start_point=[0, 0], end_point=[2, 2], matrix=[[True for i in range(3)] for j in range(3)], weights=1.1, Corner_amend=1, step=10000):
        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.start_point = self.sub2index(start_point) if type(start_point) != int else start_point
        self.end_point = self.sub2index(end_point) if type(end_point) != int else end_point
        self.startx, self.starty = self.index2sub(self.start_point)
        self.endx, self.endy = self.index2sub(self.end_point)
        self.step = step
        if not (self.matrix[self.startx][self.starty] and self.matrix[self.endx][self.endy]):
            exit("start or end is wall")

    def a_star(self):
        field = self.chansform_field()
        fieldpointers = self.chansform_fieldpointers()

        setopen = [self.start_point]
        setopencosts = [0]
        setopenheuristics = [float("inf")]
        setclosed = []
        setclosedcosts = []
        movementdirections = ["R", "L", "D", "U"]

        while self.end_point not in setopen and self.step:
            self.step -= 1
            total_costs = setopencosts + list(self.weights * np.array(setopenheuristics))
            temp = np.min(setopencosts)
            ii = total_costs.index(temp)
            if setopen[ii] != self.start_point and self.corner_amend == 1:
                new_ii = self.Path_optimization(temp, ii, fieldpointers, setopen, setopencosts, setopenheuristics)
                ii = new_ii

            [costs, heuristics, posinds] = self.findFValue(setopen[ii], setopencosts[ii], field, self.end_point)

            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:
                        [row, col] = self.index2sub(posinds[jj])
                        fieldpointers[row][col] = movementdirections[jj]
                        setopen = setopen + [posinds[jj]]
                        setopencosts = setopencosts + [costs[jj]]
                        setopenheuristics = setopenheuristics + [heuristics[jj]]
                    elif posinds[jj] in setopen:
                        I = setopen.index(posinds[jj])
                        if setopencosts[I] > costs[jj]:
                            [row, col] = self.index2sub(setopen[I])
                            setopencosts[I] = costs[jj]
                            setopenheuristics[I] = heuristics[jj]
                            fieldpointers[row][col] = movementdirections[jj]
                    else:
                        I = setclosed.index(posinds[jj])
                        if setclosedcosts[I] > costs[jj]:
                            [row, col] = self.index2sub(setclosed[I])
                            setclosedcosts[I] = costs[jj]
                            fieldpointers[row][col] = movementdirections[jj]

            if not setopen:
                return None
        if self.end_point in setopen:
            rod = self.findWayBack(self.end_point, fieldpointers)
            return rod
        else:
            exit("Can't")

    def sub2index(self, array):
        return int(array[1] * self.matrix_width + array[0] + 1)

    def Path_optimization(self, temp, ii, fieldpointers, setOpen, setOpenCosts, setOpenHeuristics):
        [row, col] = self.index2sub(setOpen[ii])
        _temp = fieldpointers[row][col]
        if _temp == "L":
            Parent_node = setOpen[ii] - self.matrix_width
        elif _temp == "R":
            Parent_node = setOpen[ii] + self.matrix_width
        elif _temp == "U":
            Parent_node = setOpen[ii] - 1
        elif _temp == "D":
            Parent_node = setOpen[ii] + 1

        if Parent_node == self.start_point:
            new_ii = ii
        else:
            [row, col] = self.index2sub(Parent_node)
            _temp = fieldpointers[row][col]
            if _temp == "L":
                Expected_note = Parent_node + self.matrix_width
            elif _temp == "R":
                Expected_note = Parent_node - self.matrix_width
            elif _temp == "U":
                Expected_note = Parent_node + 1
            elif _temp == "D":
                Expected_note = Parent_node - 1

            if Expected_note < 0 or Expected_note > self.matrix_width * self.matrix_length - 1:
                new_ii = ii
            else:
                [row, col] = self.index2sub(setOpen[ii])
                [row2, col2] = self.index2sub(Parent_node)
                if fieldpointers[row][col] == fieldpointers[row2][col2]:
                    new_ii = ii
                elif Expected_note in setOpen:
                    untext_ii = setOpen.index(Expected_note)
                    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, posind, costsofar, field, goalind):
        currentpos = self.index2sub(posind)
        goalpos = self.index2sub(goalind)
        cost = [float("inf") for i in range(4)]
        heuristic = [float("inf") for i in range(4)]
        pos = np.ones(8).reshape(4, 2)

        x = currentpos[0]
        y = currentpos[1] - 1
        if y >= 0:
            pos[0, :] = [x, y]
            heuristic[0] = sqrt((goalpos[1] - y) ** 2 + (goalpos[0] - x) ** 2)
            cost[0] = costsofar + field[x][y]

        x = currentpos[0]
        y = currentpos[1] + 1
        if y <= self.matrix_length - 1:
            pos[1, :] = [x, y]
            heuristic[1] = sqrt((goalpos[1] - y) ** 2 + (goalpos[0] - x) ** 2)
            cost[1] = costsofar + field[x][y]

        x = currentpos[0] - 1
        y = currentpos[1]
        if x >= 0:
            pos[2, :] = [x, y]
            heuristic[2] = sqrt((goalpos[1] - y) ** 2 + (goalpos[0] - x) ** 2)
            cost[2] = costsofar + field[x][y]

        x = currentpos[0] + 1
        y = currentpos[1]
        if x <= self.matrix_width - 1:
            pos[3, :] = [x, y]
            heuristic[3] = sqrt((goalpos[1] - y) ** 2 + (goalpos[0] - x) ** 2)
            cost[3] = costsofar + field[x][y]

        temp = [[pos[i, 0], pos[i, 1]] for i in range(4)]
        posinds = [self.sub2index(i) for i in temp]
        return [cost, heuristic, posinds]

    def chansform_field(self):
        field = np.ones((self.matrix_width, self.matrix_length))
        for i in range(self.matrix_width):
            for j in range(self.matrix_length):
                if not self.matrix[i][j]:
                    field[i][j] = float("inf")
        field[self.startx][self.starty] = 0
        field[self.endx][self.endy] = 0
        return field

    def chansform_fieldpointers(self):
        fieldpointers = []
        for i in range(self.matrix_width):
            temp = []
            for j in range(self.matrix_length):
                if self.matrix[i][j]:
                    temp.append(1)
                else:
                    temp.append(float("inf"))
            fieldpointers.append(temp)
        fieldpointers[self.startx][self.starty] = "S"
        fieldpointers[self.endx][self.endy] = "G"
        return fieldpointers

    def findWayBack(self, goalposind, fieldpointers):
        posind = goalposind
        p = self.index2sub(posind)
        sum = [p]
        x = p[0]
        y = p[1]
        while fieldpointers[x][y] != "S":
            temp = fieldpointers[x][y]
            if temp == "L":
                y -= 1
            elif temp == "R":
                y += 1
            elif temp == "U":
                x -= 1
            elif temp == "D":
                x += 1
            else:
                print("Error Find way back")
                exit()
            sum.append([x, y])
        return sum

    def index2sub(self, posind):
        row = (posind - 1) % self.matrix_width
        col = (posind - 1) // self.matrix_width
        return [int(row), int(col)]


if __name__ == "__main__":
    A_star().a_star()

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

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

import numpy as np

from math import sqrt

class A_star:

def __init__(self, start_point=[0, 0], end_point=[2, 2], matrix=[[True for i in range(3)] for j in range(3)], weights=1.1, Corner_amend=1, step=10000):

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.start_point = self.sub2index(start_point) if type(start_point) != int else start_point

self.end_point = self.sub2index(end_point) if type(end_point) != int else end_point

self.startx, self.starty = self.index2sub(self.start_point)

self.endx, self.endy = self.index2sub(self.end_point)

self.step = step

if not (self.matrix[self.startx][self.starty] and self.matrix[self.endx][self.endy]):

exit("start or end is wall")

def a_star(self):

field = self.chansform_field()

fieldpointers = self.chansform_fieldpointers()

setopen = [self.start_point]

setopencosts = [0]

setopenheuristics = [float("inf")]

setclosed = []

setclosedcosts = []

movementdirections = ["R", "L", "D", "U"]

while self.end_point not in setopen and self.step:

self.step -= 1

total_costs = setopencosts + list(self.weights * np.array(setopenheuristics))

temp = np.min(setopencosts)

ii = total_costs.index(temp)

if setopen[ii] != self.start_point and self.corner_amend == 1:

new_ii = self.Path_optimization(temp, ii, fieldpointers, setopen, setopencosts, setopenheuristics)

ii = new_ii

[costs, heuristics, posinds] = self.findFValue(setopen[ii], setopencosts[ii], field, self.end_point)

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:

[row, col] = self.index2sub(posinds[jj])

fieldpointers[row][col] = movementdirections[jj]

setopen = setopen + [posinds[jj]]

setopencosts = setopencosts + [costs[jj]]

setopenheuristics = setopenheuristics + [heuristics[jj]]

elif posinds[jj] in setopen:

I = setopen.index(posinds[jj])

if setopencosts[I] > costs[jj]:

[row, col] = self.index2sub(setopen[I])

setopencosts[I] = costs[jj]

setopenheuristics[I] = heuristics[jj]

fieldpointers[row][col] = movementdirections[jj]

else:

I = setclosed.index(posinds[jj])

if setclosedcosts[I] > costs[jj]:

[row, col] = self.index2sub(setclosed[I])

setclosedcosts[I] = costs[jj]

fieldpointers[row][col] = movementdirections[jj]

if not setopen:

return None

if self.end_point in setopen:

rod = self.findWayBack(self.end_point, fieldpointers)

return rod

else:

exit("Can't")

def sub2index(self, array):

return int(array[1] * self.matrix_width + array[0] + 1)

def Path_optimization(self, temp, ii, fieldpointers, setOpen, setOpenCosts, setOpenHeuristics):

[row, col] = self.index2sub(setOpen[ii])

_temp = fieldpointers[row][col]

if _temp == "L":

Parent_node = setOpen[ii] - self.matrix_width

elif _temp == "R":

Parent_node = setOpen[ii] + self.matrix_width

elif _temp == "U":

Parent_node = setOpen[ii] - 1

elif _temp == "D":

Parent_node = setOpen[ii] + 1

if Parent_node == self.start_point:

new_ii = ii

else:

[row, col] = self.index2sub(Parent_node)

_temp = fieldpointers[row][col]

if _temp == "L":

Expected_note = Parent_node + self.matrix_width

elif _temp == "R":

Expected_note = Parent_node - self.matrix_width

elif _temp == "U":

Expected_note = Parent_node + 1

elif _temp == "D":

Expected_note = Parent_node - 1

if Expected_note < 0 or Expected_note > self.matrix_width * self.matrix_length - 1:

new_ii = ii

else:

[row, col] = self.index2sub(setOpen[ii])

[row2, col2] = self.index2sub(Parent_node)

if fieldpointers[row][col] == fieldpointers[row2][col2]:

new_ii = ii

elif Expected_note in setOpen:

untext_ii = setOpen.index(Expected_note)

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, posind, costsofar, field, goalind):

currentpos = self.index2sub(posind)

goalpos = self.index2sub(goalind)

cost = [float("inf") for i in range(4)]

heuristic = [float("inf") for i in range(4)]

pos = np.ones(8).reshape(4, 2)

x = currentpos[0]

y = currentpos[1] - 1

if y >= 0:

pos[0, :] = [x, y]

heuristic[0] = sqrt((goalpos[1] - y) ** 2 + (goalpos[0] - x) ** 2)

cost[0] = costsofar + field[x][y]

x = currentpos[0]

y = currentpos[1] + 1

if y <= self.matrix_length - 1:

pos[1, :] = [x, y]

heuristic[1] = sqrt((goalpos[1] - y) ** 2 + (goalpos[0] - x) ** 2)

cost[1] = costsofar + field[x][y]

x = currentpos[0] - 1

y = currentpos[1]

if x >= 0:

pos[2, :] = [x, y]

heuristic[2] = sqrt((goalpos[1] - y) ** 2 + (goalpos[0] - x) ** 2)

cost[2] = costsofar + field[x][y]

x = currentpos[0] + 1

y = currentpos[1]

if x <= self.matrix_width - 1:

pos[3, :] = [x, y]

heuristic[3] = sqrt((goalpos[1] - y) ** 2 + (goalpos[0] - x) ** 2)

cost[3] = costsofar + field[x][y]

temp = [[pos[i, 0], pos[i, 1]] for i in range(4)]

posinds = [self.sub2index(i) for i in temp]

return [cost, heuristic, posinds]

def chansform_field(self):

field = np.ones((self.matrix_width, self.matrix_length))

for i in range(self.matrix_width):

for j in range(self.matrix_length):

if not self.matrix[i][j]:

field[i][j] = float("inf")

field[self.startx][self.starty] = 0

field[self.endx][self.endy] = 0

return field

def chansform_fieldpointers(self):

fieldpointers = []

for i in range(self.matrix_width):

temp = []

for j in range(self.matrix_length):

if self.matrix[i][j]:

temp.append(1)

else:

temp.append(float("inf"))

fieldpointers.append(temp)

fieldpointers[self.startx][self.starty] = "S"

fieldpointers[self.endx][self.endy] = "G"

return fieldpointers

def findWayBack(self, goalposind, fieldpointers):

posind = goalposind

p = self.index2sub(posind)

sum = [p]

x = p[0]

y = p[1]

while fieldpointers[x][y] != "S":

temp = fieldpointers[x][y]

if temp == "L":

y -= 1

elif temp == "R":

y += 1

elif temp == "U":

x -= 1

elif temp == "D":

x += 1

else:

print("Error Find way back")

exit()

sum.append([x, y])

return sum

def index2sub(self, posind):

row = (posind - 1) % self.matrix_width

col = (posind - 1) // self.matrix_width

return [int(row), int(col)]

if __name__ == "__main__":

A_star().a_star()