Practical application effect
A-star algorithm principle
There are many articles on the Internet that explain the principles, so I won’t go into them here
Code implementation:
First add two generic classes, Array2D and Point:
class Array2D:
The constructor takes two parameters, namely the width and height of the two-dimensional array 2. Member variables w and h are the width and height of a two-dimensional array. 3. Use: 'object [x][y]' to directly take the corresponding value 4. The default array is 0 """
def __init__(self,w,h) :
self.w=w
self.h=h
self.data=[]
self.data=[[0 for y in range(h)] for x in range(w)]
def showArray2D(self) :
for y in range(self.h):
for x in range(self.w):
print(self.data[x][y],end=' ')
print("")
def __getitem__(self, item) :
return self.data[item]
class Point:
"""
表示一个点
"""
def __init__(self,x,y) :self.x=x; self.y=ydef __eq__(self, other) :
if self.x==other.x and self.y==other.y:
return True
return False
def __str__(self) :
return "x:"+str(self.x)+",y:"+str(self.y)
Copy the codeArray2D is designed to simplify the creation of two-dimensional arrays,Point is designed to represent a Point, and the equal operator is overloaded to determine whether two Point coordinates are equal.
AStar class:
class AStar:
""" PYTHon3.x implementation of AStar algorithm """ "
class Node: # Describe node data in AStar algorithm
def __init__(self, point, endPoint, g=0) :
self.point = point # own coordinates
self.father = None # the parent node
self.g = g # g value, the g value will be recalculated when used
self.h = (abs(endPoint.x - point.x) + abs(endPoint.y - point.y)) * 10 # Calculate h value
def __init__(self, map2d, startPoint, endPoint, passTag=0) :
""" """ """ """ """ """ """ """ """ """ Point or binary pathfinding ends: Param passTag: Int walkable markers (if map data! =passTag = barrier) """
# open table
self.openList = []
# close table
self.closeList = []
# Pathfinding map
self.map2d = map2d
# Start and end
if isinstance(startPoint, Point) and isinstance(endPoint, Point):
self.startPoint = startPoint
self.endPoint = endPoint
else:
self.startPoint = Point(*startPoint)
self.endPoint = Point(*endPoint)
# Moveable mark
self.passTag = passTag
def getMinNode(self) :
""" return: Node """
currentNode = self.openList[0]
for node in self.openList:
if node.g + node.h < currentNode.g + currentNode.h:
currentNode = node
return currentNode
def pointInCloseList(self, point) :
for node in self.closeList:
if node.point == point:
return True
return False
def pointInOpenList(self, point) :
for node in self.openList:
if node.point == point:
return node
return None
def endPointInCloseList(self) :
for node in self.openList:
if node.point == self.endPoint:
return node
return None
def searchNear(self, minF, offsetX, offsetY) :
Param offsetX: offset :param offsetY: :return: """
Out of bounds detection
if minF.point.x + offsetX < 0 or minF.point.x + offsetX > self.map2d.w - 1 or minF.point.y + offsetY < 0 or minF.point.y + offsetY > self.map2d.h - 1:
return
If it's an obstacle, ignore it
ifself.map2d[minF.point.x + offsetX][minF.point.y + offsetY] ! = self.passTag:return
If in the closed table, ignore
currentPoint = Point(minF.point.x + offsetX, minF.point.y + offsetY)
if self.pointInCloseList(currentPoint):
return
Set unit cost
if offsetX == 0 or offsetY == 0:
step = 10
else:
step = 14
If it is not in openList, add it to openList
currentNode = self.pointInOpenList(currentPoint)
if not currentNode:
currentNode = AStar.Node(currentPoint, self.endPoint, g=minF.g + step)
currentNode.father = minF
self.openList.append(currentNode)
return
If in openList, determine if G from minF to the current point is smaller
if minF.g + step < currentNode.g: If it is smaller, then recalculate the value of g and change father
currentNode.g = minF.g + step
currentNode.father = minF
def start(self) :
""" Start pathfinding :return: None or Point list (path) """
Determine if the pathfinding end is an obstacle
ifself.map2d[self.endPoint.x][self.endPoint.y] ! = self.passTag:return None
# 1. Put the starting point in the open list
startNode = AStar.Node(self.startPoint, self.endPoint)
self.openList.append(startNode)
# 2. Main loop logic
while True:
# Find the point with the lowest F value
minF = self.getMinNode()
Add this point to the closeList and remove it from the openList
self.closeList.append(minF)
self.openList.remove(minF)
# Determine the top, bottom, and left nodes of this node
self.searchNear(minF, 0, -1)
self.searchNear(minF, 0.1)
self.searchNear(minF, -1.0)
self.searchNear(minF, 1.0)
# Determine whether to terminate
point = self.endPointInCloseList()
if point: If the endpoint is in the close table, return the result
# print(" close table ")
cPoint = point
pathList = []
while True:
if cPoint.father:
pathList.append(cPoint.point)
cPoint = cPoint.father
else:
# print(pathList)
# print(list(reversed(pathList)))
# print(pathList.reverse())
return list(reversed(pathList))
if len(self.openList) == 0:
return None
Copy the codeFinally, test the code:
if __name__ == '__main__':
Create a 10*10 map
map2d=Array2D(10.10)
# Create obstacles
map2d[4] [0] =1
map2d[4] [1] = 1
map2d[4] [2] = 1
map2d[4] [3] = 1
map2d[4] [4] = 1
map2d[4] [5] = 1
map2d[4] [6] = 1
# Display the current map
map2d.showArray2D()
Create an AStar object and set the starting point to 0,0 and the end point to 9,0
aStar=AStar(map2d,Point(0.0),Point(9.0))
# Start finding your way
pathList=aStar.start()
# Traversal waypoint, displayed as '8' on map2D
for point in pathList:
map2d[point.x][point.y]=8
# print(point)
print("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --")
# Display the map again
map2d.showArray2D()
Copy the code