I am currently writing a top down man vs robot shooter. The game works now, but if I have a decent sized level it runs slowly when you are being chased by robots. While just roaming around it can go at full 60 fps, but with the robots on your tail it slows down immensely.
I have traced the source of the problem to the part of the code where the robots decide whether or not their sight of the player is obstructed by a wall. This code works by seeing if the line segment formed by the center of the robot and the center of the player intersects a wall.
I have written this algorithm to see if a line segment goes through a rect:
for wall in wall_rects:
#is wall between the robot and player:
if man.rect.centerx < wall.rect.centerx < self.rect.centerx or\
man.rect.centerx > wall.rect.centerx > self.rect.centerx or\
man.rect.centery < wall.rect.centery < self.rect.centery or\
man.rect.centery > wall.rect.centery > self.rect.centery:
r = [] #are the corners above or below the line between the man and robot
r.append((self.rect.centerx-man.rect.centerx)*(wall.rect.top-man.rect.centery)\
- (self.rect.centery-man.rect.centery)*(wall.rect.left-man.rect.centerx))
r.append((self.rect.centerx-man.rect.centerx)*(wall.rect.top-man.rect.centery)\
- (self.rect.centery-man.rect.centery)*(wall.rect.right-man.rect.centerx))
r.append((self.rect.centerx-man.rect.centerx)*(wall.rect.bottom-man.rect.centery)\
- (self.rect.centery-man.rect.centery)*(wall.rect.left-man.rect.centerx))
r.append((self.rect.centerx-man.rect.centerx)*(wall.rect.bottom-man.rect.centery)\
- (self.rect.centery-man.rect.centery)*(wall.rect.right-man.rect.centerx))
if not(max(r) < 0 or min(r) > 0):
#if all of the corners are not on the same
#side then the line does go through the wall
break
else: #IT SEES YOU! >:D
however it is not near fast enough to check all 450 some walls there are in my test level. My difficulty is either making it faster or having it find out which walls are worth checking for sight-line blockage. I tried checking the distance between the wall and robot to see if it is closer to the robot than the man, which slowed it down more.
Any suggestions?
EDIT:
I forgot to mention that in this game, while the walls are placed on a grid with 25X25 pixel squares, you are free to move any distance in any direction, and so are the robots, but it looks like the suggestions below will still likely help.