# Detecting if line crosses rectangle in python. Need speed boost

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.

You can reduce the number of walls you have to check by using a spatial hash (or spatial partition). It's a data structure that answers the question, “what objects are in this region?” In your case the objects are walls. You'll only have to check the regions that the line goes through instead of all walls. A grid is one form of spatial hash but there are others too.

This article has at the end a section on intersecting a line with a spatial hash. As nihohit mentions, you can use a line drawing algorithm.

However, the next question is, are you doing this for each robot? If you are, you're going through all the walls multiple times. Since the player's location is the same each time you can use a smarter algorithm. Instead of looking at each enemy and asking whether the player is visible, ask once, which enemies are visible from the player.

The roguelike community has collected some resources about the field of view problem.

• Spatial partition is what I would definitely use for this case, simple and effective. – DogDog Apr 19 '12 at 15:45
• Yes I am doing this individually for each robot right now because eventually I want the robots to have different sight regions, but good idea. I already have a grid which the robots use to avoid crashing into walls, and I think I will use to it speed up checking like you mentioned above. Great idea. Very good to know. – Sudo Bash Apr 19 '12 at 16:20

it seems you have some kind of 2d grid going there - maybe Bresenham's line algorithm will solve the problem, when run on the grid.

• Just a note: Bresenham draws 8-connected lines, thus "skips" valid grid cells; a line of sight would be a 4-connected line. – sam hocevar Apr 19 '12 at 9:05
• What is the difference between 8-connected and 4-connected? – Sudo Bash Apr 19 '12 at 16:13
• Oh, nevermind. I found a 4-connected line algorithm here link – Sudo Bash Apr 19 '12 at 20:15