有效的避开敌人，减少敌人的步数

Question

我目前正在使用Python开发2D自上而下的无赖类游戏。该地图是一个地下城，其中包含许多开放的矩形房间(image)，每个房间内约有2-4个敌人。我目前正在寻找一种探路系统，敌人会四处走动，并试图使玩家蜂拥而至。

到目前为止，我已经实现了A *算法，该算法确实允许敌人以这种方式导航和聚集玩家。但是，我的方法导致帧率非常低：通常约为15 FPS，但是当敌人没有通往玩家的路径时，帧率将低于1 FPS。我觉得效率很低，因为正在为每个帧上的每个敌人进行寻路。当前，其他敌人被视为A *算法的障碍，唯一的优化是，如果没有障碍，则敌人将直接向玩家移动。这是代码：

import heapq
#...
FLOOR = 1
#...

class Game:
    def __init__(self):
        #...
        self.pathfindingGranularity = 5

    # Slope and line intersection functions are based on: https://www.codeproject.com/Tips/864704/Python-Line-Intersection-for-Pygame
    def lineInRect(self, start, end, r):
        if start in r and end in r: return True

        if self.segmentIntersect(start, end, r.origin, Point(r.x + r.width, r.y)) is not None: return True
        if self.segmentIntersect(start, end, Point(r.x, r.y + r.height), Point(r.x + r.width, r.y + r.height)) is not None: return True
        if self.segmentIntersect(start, end, r.origin, Point(r.x, r.y + r.height)) is not None: return True
        if self.segmentIntersect(start, end, Point(r.x + r.width, r.y), Point(r.x + r.width, r.y + r.height)) is not None: return True

        return False

    def slope(self, p1, p2):
        if p2.x - p1.x == 0: return 1e10
        return (p2.y - p1.y) / (p2.x - p1.x)

    def yIntercept(self, slope, p1):
        return p1.y - slope * p1.x

    def lineIntersect(self, start1, end1, start2, end2):
        min_allowed = 1e-5
        big_value = 1e10
        m1 = self.slope(start1, end1)
        b1 = self.yIntercept(m1, start1)
        m2 = self.slope(start2, end2)
        b2 = self.yIntercept(m2, start2)
        if abs(m1 - m2) < min_allowed: x = big_value if (b2 - b1 >= 0) else -big_value
        else: x = (b2 - b1) / (m1 - m2)
        y = m1 * x + b1
        return Point(x, y)

    def segmentIntersect(self, start1, end1, start2, end2):
        intersection = self.lineIntersect(start1, end1, start2, end2)

        def approx(f):
            return round(f * 10000) / 10000

        if not approx(start1.x) <= approx(intersection.x) <= approx(end1.x):
            if not approx(end1.x) <= approx(intersection.x) <= approx(start1.x):
                return None

        if not approx(start2.x) <= approx(intersection.x) <= approx(end2.x):
            if not approx(end2.x) <= approx(intersection.x) <= approx(start2.x):
                return None

        if not approx(start1.y) <= approx(intersection.y) <= approx(end1.y):
            if not approx(end1.y) <= approx(intersection.y) <= approx(start1.y):
                return None

        if not approx(start2.y) <= approx(intersection.y) <= approx(end2.y):
            if not approx(end2.y) <= approx(intersection.y) <= approx(start2.y):
                return None

        return intersection

class Enemy (Entity):
    def update(self, game):
        #...

        if not self.getRect().intersects(game.player.getRect()) and self.canMove():
            self.generatePath(game)

            if self.path:
                # Move towards player

        elif self.canMove():
            # Hurt the player

    #...

    def generatePath(self, game):
        if not self.lineOccupied(Point(self.x, self.y), game.player.getCenterpoint(), game):
            self.path = [game.player.getCenterpoint()]
            return

        frontier = PriorityQueue()
        start = Point(self.x, self.y)
        frontier.put(start, 0)
        came_from = {}
        came_from[start] = None

        done = False
        while not frontier.empty():
            current = frontier.get()

            if Rect(current.x + self.hitbox.x, current.y + self.hitbox.y, self.hitbox.w, self.hitbox.h).intersects(game.player.getRect()):
                done = True
                break

            for next in self.findAdjacents(current, game):
                if self.lineOccupied(current, next, game): continue
                if next not in came_from:
                    priority = self.heuristic(next, game)
                    frontier.put(next, priority)
                    came_from[next] = current

        if not done:
            self.path.clear()
        else:
            p = [current]
            while came_from[p[-1]] is not None:
                p.append(came_from[p[-1]])

            self.path = p[::-1][1:]

            i = 0

    def findAdjacents(self, currentPoint, game):
        d = 1 / game.pathfindingGranularity
        for x in (currentPoint.x - d, currentPoint.x, currentPoint.x + d):
            for y in (currentPoint.y - d, currentPoint.y, currentPoint.y + d):
                if x == currentPoint.x and y == currentPoint.y: continue
                elif self.canWalkAtCoords(x, y, game):
                    yield Point(x, y)

    def canWalkAtCoords(self, x, y, game):
        for nx in (x, x + self.hitbox.w):
            for ny in (y, y + self.hitbox.h):
                if game.blockAt(nx, ny) != FLOOR:
                    return False
        return True

    def lineOccupied(self, start, end, game):
        for e in self.room.enemies:
            if e is self:
                continue
            for xo in (self.hitbox.x, self.hitbox.x + self.hitbox.w):
                for yo in (self.hitbox.y, self.hitbox.y + self.hitbox.h):
                    if game.lineInRect(start + Point(xo, yo), end + Point(xo, yo), e.getRect()):
                        return True

        return False

我觉得应该有一个更有效的解决方案，尤其是因为房间是矩形的，敌人没有需要四处移动的墙壁或障碍物，但是到目前为止，我寻找解决方案的努力已经来临空手。我可以做一些优化来提高程序的性能吗？否则，是否应该寻找更好的寻路方法？任何帮助将不胜感激！

Answer 1

您应该尝试从角色开始寻找路径，并使用广度优先搜索（对坡度进行一些调整）将其散开。每次遇到敌人时，您都可以计算出其通往玩家的最佳路径。

这样，您只可以在整个棋盘上进行一次传球，而不是对每个敌人进行一次传球。

让我知道是否需要更多详细信息。