Compile and Run

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.