somewhere to talk about random ideas and projects like everyone else

stuff

#optimization

Pinball 19 June 2012

Last year, for Computer Science 1, I built a pinball game in Java. Yes, Java, as in sans-script. I wrote it in Eclipse and it was pretty functional. Of course, the biggest part of the game was the collision detection, collision detection which, mind you, I built with only the slightest knowledge of how it’s actually done. So yeah, I made up a scheme. It sucks, but at least it sort of works. I was actually fairly proud of it since it was basically the only thing which was mildly interesting and non teacher directed (that is, it took more than one hundred ninety two seconds to write after the teacher gave a cue to attempt the task). I thought it was so cool in fact, that I decided to port it over to both Javascript and Coffeescript, the latter being a language which was uber-hip and awesome (I believe these events transpired approximately at the time of Coffeescript’s big one-oh release).

In essence, the collision detection scheme I devised was pretty simple. The ball experienced gravity in the form of a constant downward acceleration. It would move up and down. That was maintained by a variable (actually an array to mimic a vector), named position, and another one named velocity, where the y-coordinate for the latter was incremented by some term every time a frame was rendered. The collision detection system deals with the intersection between lines. First it takes the current position of the ball, and envisions that the current velocity is a line extending infinitely in that direction. All the other attributes of the environment are also lines, and the algorithm treats them all as unbounded (rather than segments). It quite trivially computes the intersection between the lines and calculates (with euclidean distance) how far that intersection is from the ball’s current point. If it detects a collision (the distance is less than the specified radius of the ball), then the ball’s direction is altered based on its current position and the tangent of the line it intersected with.

Fast forward a few months, and it’s July of 2011. Since then, I’ve basically forgotten about the pinball game, because it really isn’t cool enough to be worth revisiting. But I was in Virginia’s Summer Residential Governor’s School for Science/Math/Technology (hardly wholly unexpected). It was some dark night and I was in the back row of a white shuttle bus en route to an observatory where artificial light is verboten. Well, it started raining and the trip was cancelled and we were going back and I was bored. So I pulled out my iPad, which I had for some reason, and decided to look at what I had on my Dropbox which I could play around with offline. Lo and behold, there’s a pretty crappy Javascript pinball implementation (which notably, never having been finished is just a ball bouncing between a few lines). I changed the parameters and made weird shapes the ball hopelessly bouncing around in awkward trajectories, and I thought it was cool.

A friend, sitting next to me noticed that the balls were speeding up. He inquired whether or not I was using the euler method, and I didn’t know what that was. Either way, inadvertently, I was in fact using that. But the point was that here he was, making a fuss about the fact that my simulation in two dimensions blatantly ignores the conservation of momentum. And as such, I was compelled to finding a solution. I studied the code for a bit longer, trying to expose the nasty snippet which might have made it evade the laws of physics, albeit to no avail. In the midst of my struggle, he noticed at some point that since the trajectory paths are simple parabolas, it should be possible to find a closed form solution to the collision problem (rather than my iterative approach. In the end, I nobly gave up on my epic quest to fix the universe, and worked on some other crap.

A week ago, I finished my first formal (that is, in school) calculus class, where I learned what euler’s method was and how I inadvertently implemented it. But I still had to take the class final, which the teacher rather kindly decided to make extremely easy. And since I also had a huge math portfolio (which I decided to typeset with LaTeX, as I have for nearly every paper this year, for no real reason whatsoever) due that day, he made it take home, with the only caveat that we aren’t to collaborate on the final in his presence (eg. after school in his room), a subtle nod of assent to all other forms of aid. Well, at home, I thought that I should probably make use of all the tools I have at my disposal. I thought of that copy of Mathematica which hopefully wasn’t collecting dust on my hard drive platter because that might lead to a head crash, but alas was figuratively gathering dust.

I decided to start playing around with the awesomeness that is a computer algebra system, named after a guy whose last name is that otherwise inexplicable W on the periodic table (purely coincidental, unless Stephen Wolfram is actually a british iron manganese tungstate mineral). In what felt to be no time (at least it seemed interesting and productive enough that I in no way thought to discern the real time which elapsed), I had completed my final exam in a somewhat minimalistically formatted Mathematica notebook. I had, figuratively, fallen in love.

Soon afterwards, as I was working on some other completely unrelated project (creating a intraframe-only WebM encoder), I needed something somewhat cool to generate a series of frames to be encoded into video. Digging through my (newly reorganized) Dropbox project folder, I found that old incomplete pinball game. And I remembered that story and that brief suggestion and decided to use my newfound Mathematica prowess (that is, my ability to use Solve[] with some degree of it not puking) to find that solution to the collision between a parabola and a line. To my dismay, Mathematica returned an ungodly mess of an equation. And it also didn’t work for vertical lines.

But eventually, I did manage to get it to work. And thankfully now it obeys the laws of physics, at least to about 10x10^-13. And I also realized that that demo isn’t actually that cool but I used the older version anyway for my video encoder demo. So that’s the happy ending, everything lived happily ever after despite the fact the algorithm is still totally buggy and breaks when things are either too fast (velocity > 4000px/second) or too slow (velocity < 1px/second). And with corners, it occasionally fails. But I’m long since past the threshold of caring. At least now, you can speed it up a lot because the path prediction and the collision detection are completely separate from the render cycle (which also lets the speed become independent of processor speed). It uses requestAnimationFrame and other stuff, and if you want to try it, here.


New Features coming in Ajax Animator 0.15 (aka 1.5, read to find out why) 02 December 2007

Okay, so one day i felt crazy and changed everything by 1 decimal place because i don’t want this to seem misleadingly good. I mean, if it hits a 1.0 release, then some people would think it’s almost as good as Flash 1 (futuresplash animator) which it it isn’t even near yet.

So it should be 1.5 but now it’s 0.15 :D

Read more to find out the whole list, a summary of it would be axml2, UI polishing, save space, nicer code (but still hideous), css, users, tweening, finish partially completed ideas etc.

What’s done so far

  • Redesigned Register UI
  • Save Lots of code
  • New Save/Open file format (around 5x faster, and 10 times smaller)
  • Relocating stuff
  • interactive tutorials
  • Backwards Compat Mode
  • for the first time it’s gonna be a legitimate GPLv2 project (I’m gonna include the gpl.txt file for once)
  • replaced wz_tooltips with native ext.js ones
  • Change save file to computer architecture
  • change organization of Save/Open buttons in file menu (submenus)
  • optimized stuff
  • fixed bugs
  • No more save/open window (now, single-purpose dialog alerts, much better)
  • Progress bars
  • User friendly upload error message (yay!)
  • relocate css
  • delete lot’s of stuff from user-management
  • REAL SUPPORT FOR LINES/ELLIPSES, lines didn’t work for tweening, ellipses didn’t work for tweening or flash, and ALL suffered from a programming error causing line-widths to be messed up.
  • FastMode …and more to come