python - Pygame, efficient collision handling for rpg game? -

i'm programming little snes-like rpg pygame.
on map have 4 layers :
0 : terrain, no collision (under char)
1 : on terrain no collision (under char)
2 : collision objects (under char)
3 : on char objects

i wanted create rect every tile in second layer prevent character go on these objects. there efficient way not check every rectangle each time character moves ? thanks.

pygame has bunch of optimized functions this, rect.collidelist:

collidelist()
test if 1 rectangle in list intersects

collidelist(list) -> index

test whether rectangle collides in sequence of rectangles. index of first collision found returned. if no collisions found index of -1 returned.

if still encounter performance problems, use quadtree.

here's implementation in python using pygame.

from pygame import rect  class quadtree(object):     """an implementation of quad-tree.      quadtree started life version of [1] found life of own     when realised wasn't doing needed. intended static     geometry, ie, items such landscape don't move.      implementation inserts items @ current level if overlap     4 sub-quadrants, otherwise inserts them recursively 1 or 2     sub-quadrants overlap.      items being stored in tree must pygame.rect or have have     .rect (pygame.rect) attribute pygame.rect         ...and must hashable.      acknowledgements:     [1] http://mu.arete.cc/pcr/syntax/quadtree/1/quadtree.py     """      def __init__(self, items, depth=8, bounding_rect=none):         """creates quad-tree.          @param items:             sequence of items store in quad-tree. note these             items must pygame.rect or have .rect attribute.          @param depth:             maximum recursion depth.          @param bounding_rect:             bounding rectangle of of items in quad-tree.             internal use only.         """          # sub-quadrants empty start with.         self.nw = self.ne = self.se = self.sw = none          # if we've reached maximum depth insert items         # quadrant.         depth -= 1         if depth == 0 or not items:             self.items = items             return          # find quadrant's centre.         if bounding_rect:             bounding_rect = rect( bounding_rect )         else:             # if there isn't bounding rect, calculate items.             bounding_rect = rect( items[0] )             item in items[1:]:                 bounding_rect.union_ip( item )         cx = self.cx = bounding_rect.centerx         cy = self.cy = bounding_rect.centery          self.items = []         nw_items = []         ne_items = []         se_items = []         sw_items = []          item in items:             # of sub-quadrants item overlap?             in_nw = item.rect.left <= cx , item.rect.top <= cy             in_sw = item.rect.left <= cx , item.rect.bottom >= cy             in_ne = item.rect.right >= cx , item.rect.top <= cy             in_se = item.rect.right >= cx , item.rect.bottom >= cy              # if overlaps 4 quadrants insert @ current             # depth, otherwise append list inserted under every             # quadrant overlaps.             if in_nw , in_ne , in_se , in_sw:                 self.items.append(item)             else:                 if in_nw: nw_items.append(item)                 if in_ne: ne_items.append(item)                 if in_se: se_items.append(item)                 if in_sw: sw_items.append(item)          # create sub-quadrants, recursively.         if nw_items:             self.nw = quadtree(nw_items, depth, (bounding_rect.left, bounding_rect.top, cx, cy))         if ne_items:             self.ne = quadtree(ne_items, depth, (cx, bounding_rect.top, bounding_rect.right, cy))         if se_items:             self.se = quadtree(se_items, depth, (cx, cy, bounding_rect.right, bounding_rect.bottom))         if sw_items:             self.sw = quadtree(sw_items, depth, (bounding_rect.left, cy, cx, bounding_rect.bottom))       def hit(self, rect):         """returns items overlap bounding rectangle.          returns set of items in quad-tree overlap         bounding rectangle.          @param rect:             bounding rectangle being tested against quad-tree.             must possess left, top, right , bottom attributes.         """          # find hits @ current level.         hits = set( [ self.items[n] n in rect.collidelistall( self.items ) ] )          # recursively check lower quadrants.         if self.nw , rect.left <= self.cx , rect.top <= self.cy:             hits |= self.nw.hit(rect)         if self.sw , rect.left <= self.cx , rect.bottom >= self.cy:             hits |= self.sw.hit(rect)         if self.ne , rect.right >= self.cx , rect.top <= self.cy:             hits |= self.ne.hit(rect)         if self.se , rect.right >= self.cx , rect.bottom >= self.cy:             hits |= self.se.hit(rect)          return hits 

this improve performance on checking each tile in simple loop.