Practical application effect

This is what I actually apply to the game

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 code

Array2D 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 code

Finally, 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

Operation effect: