I am currently working on a 2D top down rogue-like game using Python. The map is a dungeon containing many open rectangular rooms (image), each with around 2-4 enemies inside. I am currently looking to implement a path-finding system where the enemies will move around each other and attempt to swarm the player.
So far, I have implemented an A* algorithm that does allow the enemies to navigate and swarm the player in this way. However, my approach is causing very low frame rates: generally around 15 FPS but it will go as low as under 1 FPS when an enemy has no path to the player. I feel it is very inefficient, since path-finding is being done for every enemy on each frame. Currently, other enemies are seen as obstacles for the A* algorithm, and the only optimization is that an enemy will move directly towards the player if there are no obstacles in its way. Here's the code:
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
I feel like there should be a much more efficient solution to this, especially seeing as the room is rectangular and there are no extra walls or obstacles that the enemies need to move around, but so far my searches for a solution have come up empty-handed. Are there some optimizations I could make to increase the performance of the program? Or if not, is there a better pathfinding method I should look into? Any help would be greatly appreciated!
You should try to have you path finding start from your character and fan out using a breadth-first-search (with some adjustment for slopes). Every time you come across an enemy, you can compute its optimal path toward the player.
That way you only do one pass across the whole board rather than one for each enemy.
Let me know if you want more details.