I’ve been programming Lago for a while now and got decently far. Since python isn’t really known for its speed, I decided to implement a QuadTree in it, used for drawing and colliding with static objects in the world. In the future I may decide to make it compatible with moving objects, but for now it’s not necessary.
#Ion's Superific QuadTree! Static for now.
LEAF_MAX = 1
class Rect:
def __init__( self, x, y, width, height):
self.x = x
self.y = y
self.width = width
self.height = height
self.right = self.x + self.width
self.bottom = self.y + self.height
self.centerx = self.x + (self.width/2)
self.centery = self.y + (self.height/2)
def testIntersect( self, other ):
self.right = self.x + self.width
self.bottom = self.y + self.height
if self.right < other.x: return False if self.x > other.right: return False
if self.y > other.bottom: return False
if self.bottom < other.y: return False return True def testContains( self, other ): self.right = self.x + self.width self.bottom = self.y + self.height if other.right > self.right: return False
if other.x < self.x: return False
if other.y < self.y: return False if other.bottom > self.bottom: return False
return True
def colliderect( self, rect ): #pygame compatibility
return self.testIntersect( rect )
def contains( self, rect ): #pygame compatibility
return self.testContains( rect )
def getTuple( self ):
return (self.x, self.y, self.width, self.height)
class QuadTree:
def __init__( self, x, y, width, height ):
self.rect = Rect( x, y, width, height )
self.oblist = []
self.subnode = []
def addObject( self, ob ):
self.oblist.append( ob )
if len( self.oblist ) > LEAF_MAX:
halfwidth = self.rect.width/2
halfheight = self.rect.height/2
if len( self.subnode ) == 0:
self.subnode.append( QuadTree( self.rect.x , self.rect.y, halfwidth, halfheight) ) # upper left
self.subnode.append( QuadTree( self.rect.x + halfwidth, self.rect.y, halfwidth, halfheight) ) #upper right
self.subnode.append( QuadTree( self.rect.x , self.rect.y + halfheight, halfwidth, halfheight) ) # lower left
self.subnode.append( QuadTree( self.rect.x + halfwidth, self.rect.y + halfheight, halfwidth, halfheight) ) #lower right
kill = []
for ob in self.oblist:
for sub in self.subnode:
if sub.rect.contains( ob.rect ): #object is contained in that node
sub.addObject( ob )
kill.append( ob )
break
for ob in kill:
self.oblist.remove( ob )
def getInBounds( self, rect ):
total = []
for ob in self.oblist:
total.append( ob )
for sub in self.subnode:
if rect.colliderect( sub.rect ):
total += sub.getInBounds( rect )
return total
def getAll( self ):
total = []
for ob in self.oblist:
total.append( ob )
for sub in self.subnode:
total += sub.getAll( )
return total
It’s compatible with PyGame’s rect class if you want to use that. Simply make a quadtree and give it a size, then call addObject() on objects that have a rect attribute. It provides some optimization at least. Then you call getInBounds( ) to get all of the objects that are mostly in the rectangle you give it (more than what’s in the bounds, but never less).
Now I’m going to learn you some basic AABB collision. AABB stands for Axis Aligned Bounding Box, which is the simplest collision you can ask for. So think 2D rectangles. The first thing you need to is detect the collision between two rectangles. Perhaps surprisingly, its easier try and detect whether they’re not colliding. For example, if the right side of the first rectangle is less than the left side of the second rectangle, then they must not be colliding. The same with the other 3 sides.
So once you see if they’re colliding, you have to see how deep the rectangle is in the other rectangle. This depends on the first rectangles velocity. If its moving right, then you have to consider how deep the rectangle is in from its right side. And then the same with the other 3 sides.
Finally, you move the object along the smaller of the two depths (not both). But the thing is, if that depth is bigger than the velocity on that axis, then you want to move it along the other depth. Anyways the code probably explains it better than I can.
class CollisionMan:
def __init__( self ):
self.bodylist = []
def addBody( self, body ):
self.bodylist.append( body )
def collideBody( self, a ):
#simple collision detection
a.rect.x += a.velx
a.rect.y += a.vely
for b in self.bodylist:
if a != b:
if a.rect.colliderect(b.rect):
dx = 0
dy = 0
#find the intersection depth for each axis x and y
if a.velx > 0: #moving right
dx = -( a.rect.right - b.rect.left )
elif a.velx < 0: # moving left
dx = ( b.rect.right - a.rect.left )
if a.vely > 0: #moving down
dy = -( a.rect.bottom - b.rect.top )
elif a.vely < 0: #moving up
dy = ( b.rect.bottom - a.rect.top )
# I'm a genius! Kinda. The basic algorithm here is to use to find the smallest
# intersection depth, but with a twist: you never want to move the object passed its original position,
# that is, the interesection depth must be less than (or equal to) the velocity on that axis.
# So, at worst, an object can end up back in its original position, before the velocity shifted it.
if dy == 0:
a.rect.x += dx
elif dx == 0:
a.rect.y += dy
elif abs(dx) < abs( dy ):
if abs( dx ) <= abs( a.velx ):
a.rect.x += dx
else:
a.rect.y += dy
else:
if abs( dy ) <= abs( a.vely ):
a.rect.y += dy
else:
a.rect.x += dx
That’ll do. Add objects with a rect attribute via addObject, then call collideBody on an object in order to move it out of collision for every object in it. It’ll probably need to be modified for moving objects, but seems to work well for now. Hope this helps somebody.
