Pygame. Efficient detection of line collision with sprite

Question

QUESTION

I am currently writing a small rpg. I've managed to make a player shooting and destroy the projectile when it collides with a sprite. It works well because the player is "smart" enough to not shoot when there is a wall between him and the target.

I am currently thinking about how to move this method to my monsters. But the only way I can think of to avoid the monster shooting if there is an obstacle between the target and him is to draw a line between the two and check if the line intersects with any obstacles.

I haven't found a way of doing this efficiently. For the moment I am considering testing every single point along the line but I think that this will slow the game down significantly.

If you have any answers on how to efficiently check if a line collides with a rectangle I'd appreciate.

Thanks

ANSWER

Thanks to @DCA- 's comment was able to implement exactly what I was looking for. I got the Bresenhams's line algorithm pretty much strait from the box (cpoy/pasted it in my functions.py module). I then coded in:

'''the range_ argument represents the maximum shooting distance at which the shooter will start firing.  and obstacles is a list of obstacles, shooter and target are both pygame Sprites'''
def in_sight(shooter, target, range_, obstacles):
    line_of_sight = get_line(shooter.rect.center, target.rect.center)
    zone = shooter.rect.inflate(range_,range_)
    obstacles_list = [rectangle.rect for rectangle in obstacles] #to support indexing
    obstacles_in_sight = zone.collidelistall(obstacles_list)
    for x in range(1,len(line_of_sight),5):
        for obs_index in obstacles_in_sight:
            if obstacles_list[obs_index].collidepoint(line_of_sight[x]):
                return False
    return True

DCA- DCA- · Accepted Answer · 2016-06-06T14:43:04

I think what you're looking for is a line of sight algorithm.

Look into Bresenhams's line algorithm or other such resourses as a starting point.

This is a common algorithm used in 2d rogue-like's and rpg's.

I can't vouch for the efficiency of the algorithm or it's speed when implemented in python but hopefully this gives you a point in the right direction.

Another useful algorithm may be Raycasting. There are many python implementation around and won't be hard to find.

Hope this helps.

Pygame. Efficient detection of line collision with sprite

1 Answers