shooflenet/articles/mindjail-engine.article.html

<article>
	<h1 class="title">Mindjail Engine!</h1>
	<p>This is doubtlessly my most ambitious project. It's a little 2D game engine in python that I've been working on for a while now. It's got some basic physics (not accurate, but they feel right, and that's what counts) and it can zip along pretty respectably! I first started this project in my second year of college, but I soon abandoned it because (surprise of surprises!) I had a lot of classes to work on. When I finally picked it back up towards the start of 2013, I had grown a lot as a programmer and a human being, and there were changes to make. I still love this project, but the primary goal I had here was to never set a deadline for myself. The idea was that I should never say when this project will be done - because it's always in progress. I'm never fully committing myself to a flawed approach, and, although there's a bunch of ugly code here, I'm never afraid to go back and change how I did something.</p>
	<h3>Tell me all about collision detection, it is my favorite subject!</h3>
	<p>I was good at my data structures and algorithms class, and they're concepts I'm deeply familiar with. It's interesting, though, that nothing ever gave me such a good sense for how algorithmic complexities compare until I was doing real-time collision detection. It doesn't help that my chosen language was python - a decision that helped many things in this project, but not speed. <span class="sidenote">People will happily claim that python is too slow to ever make a real game with, but it's just not true. Computers are fast. I'm convinced that python is perfectly capable.</span> There've been a lot of data structures I used for this, and the source is somewhere - <span class="todo">I'm going to put those online at some point.</span></p>
	<ul>
		<li>When I started out, of course, I did the brute force N^2 test, because I just wanted to get objects moving around on the screen. This rapidly bottomed out once I got more than probably 30 objects on the screen. I don't remember, it was a long time ago! I knew from the start that I was going to have to do something better, so I did.</li>
		<li>The next step was to roll something more advanced of my own. It had problems, but I'm still proud of how well it worked - I called it a sorted search list. The idea was that the list of objects in the world would be simultaneously kept sorted by each object's maximum and minimum extents on the x- or y-axes. When you're searching for a collision, then, you can cut down how many checks you do by searching upwards and downwards through the list until you find an object which is too far away to intersect - at which point no further objects could possibly be touching you. <span class="todo">I should make a picture.</span> Anyway, this system worked alright - if I remember correctly, I got up to around 50 objects on screen before it started slowing down a lot. I kept this around as a supporting data structure, but I didn't realize the massive flaws in it - in order to be certain about objects Foo and Bar not colliding, you need to run the check for Foo against Bar as well as Bar against Foo. Anyway.</li>
		<li>
			<p>After that I finally decided to ask the great oracle Google for help. Why didn't I use the knowledge of others before that? Well, they never really covered collision detection-specific data structures in my classes... I found out about a thing called a quadtree, and I was hooked. The idea is to recursively divide space into quadrants - objects northeast of center, northwest of center, and so on. This is the structure I spent the most time on, because I was dead-set on making it work. It was just so <em>cool!</em></p>
			<p>Well. That was silly of me. There are a lot of problems. Suppose Foo is in the northwest corner, but Bar overlaps between northwest and northeast! There's no simple solution, and mine was to have a secondary data structure, which stored objects which couldn't fit into any of the corners.</p>
			<p>At this point, I realized a structure-agnostic speedup I could use: Be mindful of whether objects move or not. If two objects never move, you never need to see if they collide. With this, the system got up to probably 80 objects on screen, with most of them stationary. Point being, it was a lot faster. I needed more, though! There was a huge problem:</p>
			<p>The quadtree wasn't balancing. Balancing a regular tree data structure is one thing, but quadtrees have two dimensions to balance at once, which makes it infinitely more difficult... And I couldn't find a tutorial on it, nor figure it out on my own. All the tutorials either dealt with worlds that had a size limit for objects, or discrete-position finite-world grid systems. I didn't want to do either of those! So I started panicking.</p>
		</li>
		<li>The next solution was to try variations on quadtrees. I tried a bunch - changing what supporting data structure I used, switching from a strict quadtree - at each level dividing in quadrants - to a <a href="http://wikipedia.org/wiki/K-d_tree">k-D tree</a>: At each level, it divides the world in half, and switches the lines along which it divides the world each level. They're a little more flexible in a few ways, and in theory easier to balance (because you don't need to balance two dimensions at the same time so much). Unfortunately, there's a dearth of information about using them for collision detection, because everyone uses them for graphics and not much else. <span class="sidenote">At this point, I was running out of steam for recursive data structures, but I briefly considered extending my k-D tree to be the most general kind of <a href="https://en.wikipedia.org/wiki/Binary_space_partitioning">binary space partitioning tree</a>, wherein you don't just cycle your dividing axis through a set of options, but rather you divide along a completely new axis - not necessarily perpendicular! - at each level. This is used for raytracing a lot, but implementing it for these purposes would have been a pain. It would have just meant more balancing and trying to make the trees smart, which I didn't want to get too heavily into.</span> I gave up on this soon after, partly because...</li>
		<li>I realized that my secondary data structure didn't work right. You needed to double-check every collision in order to be sure you had gotten all of them, and besides, sorting along one axis had little effect when you were frequently checking collisions which are grouped along the axis it doesn't sort on. I was basically back to square one. That's when I finally gave up on the tree - I would have needed to make it too smart in filling itself, I would have needed to balance it, I would have needed to have a good secondary data structure, and... It wasn't worth it. But then I found the light.</li>
		<li>
			<p>Spatial Hashing was something I'd heard of before, but mostly in the context of grid-based systems, finite worlds, and size-limited systems. I didn't want <em>any</em> of that. The typical spatial hashing scheme goes like this: You have a 2D array of lists. Each list corresponds to one grid space in your world, and so you only need to check against objects in adjacent squares. Here was my problem: Static arrays means you need to have a set size for your world, I don't like strict gridding, and I wanted to account for the fact that I might have large objects! But there's a solution, and, as it <em>always</em> seems to be in the world of data structures for practical everyday purposes, it's hash tables.</p>
			<p>Here's how my system works: The Spatial Hash Grid is a dict. The keys are (x,y) tuples which index into the infinite space of grid squares. The items are a secondary collision-detection data structure, which contain the objects. To find the key for an object, you just have to integer divide its coordinates. Since it just uses python's built-in dicts, it's hashing the tuples - so you never need to pre-specify the size of your world! The thorniest thing to get around was storing large objects. I tried throwing items into all the grid squares they touch, but it was too slow. The solution I ended up using is to make multiple tiers.</p>
			<p>When you put an object in the grid, it checks its size (by looking at the min/max x/y coordinates, which shape objects contain). If it's small enough to fit in this grid - that it will only ever occupy one square and its neighbors - then it goes in the dict we're looking at. Otherwise, the grid makes a new grid - with twice the grid size! Larger objects get shoved up the ladder, and when you're checking for collisions, you traverse up the ladder until you hit the end. This is reasonably fast so long as you don't have unreasonably many objects on different size scales.</p>
			<p>And it works! I haven't done extensive testing, but it goes up to 150 - 40 moving around, and the rest stationary - with 60FPS. I've gotten some slowdown after that (only from adding more moving objects) but it's certainly fast enough for my purposes - and some of the speed loss is from unoptimized rendering - and it should be the case that a sparsely populated world will have nearly no slowdown from additional objects being chucked in.</p>
		</li>
	</ul>
	<p>So I'm using Spatial Hashing, and there're ways for it to be sped up, but collision detection works pretty well for now - certainly well enough to focus on other things.</p>
	<h3>Yes, but what about... anything else?</h3>
	<p>Well, this project is about the engine, so I'm not prepared to go into the actual game I want to make with it, but there's certainly graphics and windowing to talk about. The graphics are, for the moment, all coded up with vertex lists that it generates when it runs, and they're far from optimized or anything. This is good because I learned a lot about OpenGL. This is bad because pretty much all of what I learned is now obsolete, since the computer I've been developing for doesn't... have support... for shaders. Whoops. I want to get more experience with shaders, but I don't have a computer that's good for it right now. Also, that will be more meaningful when I have a better model-&lt;engine pipeline for actually putting content into the engine.</p>
	<p>Windowing is, for the moment, done through pyglet, which is a lightweight framework for windowing and opengl bindings. I like it okay, but it's not capable of doing much - I'd have to write my own GUI, which would be suboptimal (although not too hard) given that I could just get a framework to do it for me. What I'm trying to do now is switch to using PyQt, having tried wxPython briefly and found it very hard to work with. I'm still working through reimplementing secondary things that pyglet was doing for me, such as keyboard and mouse handling and clock/fps management. That's what the gui branch is for, on github.</p>
	<h3>I guess links would be nice?</h3>
	<p>Oh, yes! Right. <a href="http://github.com/shoofle/mindjailengine/">The repository</a> is up on github, and it should work for you if you fork it. You'll need to pip install pyglet, or fork their latest dev version if you're on a mac - there's some kind of unresolved problem with OSX or something. That's one of the reasons I want to switch to a different framework - better portability.</p>
</article>