Time’s starting to get tight around here due to a bunch of N+ related deadlines.. however we’re going to do our best to keep this delicious blog from getting too stale.
Let’s just backtrack a bit. This was almost exactly a year ago:
- we made all sorts of soft-collision/simple physics experiments (as mentioned previously)
- we banged out a geometry-based collision system which worked pretty well (mostly this was a proof-of-concept to convince us that such an approach would be much simpler in the long run than the tile-based system in N)
- we spent about a month getting rope collision working (an incredibly bitchy problem since finding the actual intersections involves swept-lines vs swept-points, and moreover required a pretty sophisticated event-based scheduler/simulation to properly handle all the wrapping/unwrapping that can occur between frames.. how the hell did they do it in Umihara?!)
- we came up with an initial concept for graphics/design, and did some mockups/prototypes of ideas
- we started learning C++/openGL, and got some of our graphics ideas working (as well as text rendering and some other misc junk)
..That may not seem too bad for 5 months or so, but at this point we were planning on having the game ready for September 2006 (aka “IGF entry deadline”). So, from that perspective we were a bit behind.
Then again, we couldn’t really be said to be working on the game, since what we were doing was more like R&D for when we eventually started work on the game proper. When we came to this shocking realization, we decided that — given the immense amount of work required to get this right (just getting up to speed with C++ is a big enough task!) — we should push things back a year.
Aside: Our initial business plan (yes, we actually have one) was to release one game a year, with target sales of 1000/year. This might seem incredibly low or high, depending on your perspective; our desire to sell things through our site (instead of via portals, which probably wouldn’t want our games anyway) and the fact that N was generating a decent amount of web traffic (~2k downloads/day) led us to this decision.
This plan as a whole might seem a bit untenable (yearly income of ~$20k?!), but the idea was that if we managed to avoid going bankrupt for the first couple years, we’d have a back-catalog of several games which would continue to sell. This has worked for others! We had about 6 months of savings, and a 1-month contract lined up for the fall, _and_ Microsoft had just contacted us about maybe doing N on XBLA (this is several blog posts in itself)
So, back to Robotology. Now that we had MORE THAN AN ENTIRE YEAR to work on stuff (instead of just a few months), we decided to do things right. And that meant writing a proper physics simulator!
The world would be 100% physics-based (all animation/etc. would be driven by motors), so that players could really screw with enemies. Of course, this requires a simulator that’s better than any existing simulator — free ones such as ODE can simulate a walking robot, but it takes a lot of tweaking, and in the end it’s neither super-stable nor fast. Commercial simulators such as Havok, aside from being way too expensive, are similar to ODE — they’re great for lots of loose tumbling bodies, but jointed/articulated motorized limbs are not their forte. Which brings us back to where we left off, last time on metablog:
“This lead us to start from scratch, building an entirely new and different ‘robot simulator’..”
The first thing we figured out was we really wanted to have proper rigid bodies to work with — all of our previous physics things were particle-based.
The first simulator took about a month, and was called “bondshop” (no idea why, aside from the fact that constraints between bodies were called “bonds”, and we like “shop”s): check it out (opens in a new window)
That demo is a pretty lame ragdoll — it looks particle-based. Rest assured that each limb is a rigid body (look at the torso — it’s rigidly connected to several things!), and check out the funky constraint regions: instead of just constraining a point on one body to a point on the other, we experimented with rectangular, circular, and arc-shaped regions.
Bondshop was based on solving constraints between rigid bodies geometrically: given two points (one on each body), it would figure out how to translate+rotate each body such that the points coincided. This was totally based on geometry instead of physics, but it worked pretty well: it was very stable and didn’t blow up. Like all of our solvers, it used “relaxation”: basically, instead of trying to solve everything at once, solve things one at a time and hope that all of the individual solutions add up to the correct global solution.
For the technically inclined, a paper we came across that presents a similar approach is A Procedural Approach To Solving Constraints of Articulated Bodies.
This approach was nice in that it was simple (no heavy calculus/linear algebra), fast (the demo isn’t exactly blazing, but it’s Flash, which is at least 100x slower than C++), and stable. But, bondshop was lacking in a couple important ways: we couldn’t figure out how to apply our method to angular constraints (very useful for simulating limbs — you need to be able to specify min and max bend-amounts), and we couldn’t figure out a simple way to implement motors, to get the limbs moving around on their own.
So, we reluctantly moved on to try other things; this involved hitting the books and learning some of that “math” stuff we did such a good job of avoiding at school.
Cool stuff, there. Heh, you thought it’d be done by September ’06? Well, glad you’ve taken time to make sure everything’s just right. Also, in that demo you say there’s no graphical representation of which limb you’ve chosen…but it seems to me like the a part becomes bolder when you’ve chosen it. Meh, anyway, good luck with the “math” stuff, hah.
Woo first comment, wait…I don’t know!
Good job, love the closing comment, hope all goes well!
You’re right soybean.. whoops 😉
We don’t usually bother to implement that sort of thing, I just assumed it was like that without checking! Thanks — it’s changed now.
also, PLEASE let’s not have any first-comment posts.
Whee. Now you’re speaking my language. 🙂
And you’re right, I really should go all technical nitty gritty bloggy and talk about my game.
Anyways, I really did mean to fire a mail to you about the Umihara rope thang, but apparently never got around to it.
So here we go. My thoughts on how they pulled that off on the SNES, AKA 2-3 MHZ tiled beast. To put things in more perspective, a CPU with 8bit register with no internal multiplication or division. However, I think I read somewhere that there was either a hardware multiplier or divider, essentially some hardware address you plug some numbers in to, and several cycles later you can read back a result. This compared to the GBA with it’s 32bit registers, and it’s “so very nice” multiplication opcode. 🙂
First off, I think the biggest thing they had to their advantage was the tile graphics hardware. All Nintendo hardware except the N64, GameCube, and Wii have tile map 2D graphics hardware. Memory for 8×8 tile graphics, and memory for a map to build from those tiles. So really, you’re either making a tiled game, or your not making a game on those systems.
So that means, as far as testing against collision, you’re only testing against easy aligned tiles (surfaces with normals (1,0), (0,1), and the negatives). Our rope, technically only needs to be concerned with things in units of tiles. A 64 pixel tall wall is merely 8 tiles, and only 8 “unit tests” as we interpolate across the line.
Also, a locked framerate. So long as we don’t travel more than 8 pixels in 1 frame, we should be able to stay completely stable. Lets also say each tile only finds nearest edges on it’s exposed sides (i.e. no tile adjacent to me, then it’s an exposed side).
And an optimization for rope segments, every 2 bends we can put the previous part to sleep. We just need enough memory set aside to support a dozen or so bends.
The final big thing is something I ran in to durring my adventures deeper in to physics and maths. Something in math nerd speak called the Manhattan Length or Distance (I forget it’s proper name, I just call it the Manhattan). The Manhattan is a length formula for a line, in much the same way as magnitude (or magnitude squared, how I love thee). The formula is the sum of all the absolute value parts of a vector. I.e. Manhattan = abs(x) + abs(y). No doubt you’ve played with this yourself, and scoffed it off because it’s not an accurate length. That is, except in one key case…
When it’s axis aligned! No square root required! (1,0) or (0,1) respectfully, the Manhattan or length is 1, and so would the magnitude. Why is this important?
Tile hardware is axis aligned! So as long as we wrap around axis aligned things, our rope segments are accurate. Even if not, so what? Worst case, our rope shrinks a bit going over a slope.
You’ve probably noticed how extra bouncy/elastic the rope in Umihara is. My best guess, is it’s because they live with the horrible innacuracies of the Manhattan Length. And truth be told, asuming that’s what it is, it still looks great. Eventually you’ll pendulum your self to a stop whilst hanging vertically.
So there you go, Mike’s “how they did Umihara Kawase”. 😀
I’m loving that bondshop thing, having a whole environment of interacting parts like this would allow a lot of experimentation and creativity with movements.
Although, I’m not sure how a character like that could be controlled. Simple arrow-key movement seems so restricted to control such a complicated character, and individual limb control sounds very tricky.
Yeah, I’m waiting for the part where they had to create some sort of simple AI to keep the body from falling over. 🙂
We added a link to a related paper if anyone’s interested.
@matt: we want this to feel like a normal platformer, so for the player we’ll be using a somewhat different approach.
But, direct control over a physics-based player could be pretty fun/funny — we immediately thought of making a game called “drunk man” where you just try to stay upright and walk home, after watching the biped videos here: http://www.dgp.toronto.edu/~jflaszlo/interactive-control.html
@PoV: we’re still working on balancing controllers.. we should get to that in a couple posts, when we finally catch up to the present! Van De Panne’s recent paper is great — simple and powerful: http://www.cs.ubc.ca/~van/papers/2007-siggraph-simbicon.pdf
@PoV: your Umihara theory overlooks some of the key mind-blowing features of that game:
-non-axis-aligned/arbitrary sloped surfaces, including acute corners! (which is something mario never had)
-conveyor belts: we’re still trying to figure out how to simulate these well — any of the arbitrarily-sloped edges of the world can be a “conveyor belt” which will move the grapple along itself, around corners, etc..
-both ends of the rope are simulated; when you’re attached to an enemy or a moving platform (in later levels there are platforms which you can pull up/down!) both ends of the rope “swing”
The rope is really short, so no matter how much work they need to do, there will be at most maybe 8 “bends” in the rope. Still, it is _amazing_ that they got that working so well — we haven’t found any collision/sim glitches yet. Whoever programmed that is a genius!
p.s – your blog post uses the past tense.. you’re not making the rope game anymore?! why not?!?!?! damn it!
> non-axis-aligned/arbitrary sloped surfaces
This is something, after thinking about it, I suspect isn’t a big deal. The so called “Manhattan Length” still works for horizontal/vertical, diagonal and in between lines, but it will report a longer distance than magnitude, so normalization ends up making the length just a little bit less than 1. If that turns out very rigid looking, give the rope some “give” to it, like using a .25 or less instead of .5 on each end to solve a spring. Eventually, you’ll make it to equilibrium, and everybody will think you’re a mastermind. 🙂
Hehe, I’m soooo very tempted right now to throw together a little prototype of this. :). I have a strange suspicion the entire rope, Umi-style, can be done with no roots and only 1 division. I doubt it’s something we don’t already know of, just aspects are handled by clever tricks you use on crap old. Reciprocal tables instead of division, shifts for cheap doubling/halfing, fixed point instead of floating point.
> conveyor belts
Ah yes. I forgot about those. Well, that just goes to show that either A. They don’t sleep the rope, or B. you sleep it in the middle. If you’re right about the 8 bends (another nicety of the tile map), then the need to sleep part of the rope is irrelevant. Perhaps it’s not so much sleeping, as it is just creating a list of bend points, and you only deal the bends on the outskirts (first and last). As a bend no longer bends, the next one (or previous respectfully) becomes the bend of note.
I’m also making the assumption that the rope is solved as a whole rope, at least given my less than satisfactory results with a segmented multi spring rope where each segment has an individually solved length. Individual segments are fine for a “rope ragdoll”, but not so good for a bent around edges rope.
> your blog post uses the past tense.. you’re not making the rope game anymore?!
Well, like you guys with N and N+, I have my little game PuffBOMB, while nowhere nearly as successful as N, it has proven itself. With my rope game, while I have control scheme I like, I lack a well developed universe/mythology or such. PuffBOMB as a concept has been stewing in the noggin’ and sketchbook for 4 years, since I made the original prototype game in 2003.
I started the rope game because I thought it suited a game pad better than PuffBOMB (a previously mouse driven game). It did, but I decided I could probably make PuffBOMB work. Why waste 3 years (at the time) of notes and ideas by not doing the remake. So I did that, and added a variant that works better on a pad. It wasn’t really a radical shift either. We simply started making PuffBOMB appropriate content using the tools.
And besides, there’s nothing stopping me from using ropes or ropey things in PuffBOMB. I love the idea of tethering things or the character to a bungee cable. Paddle ball with explosives. 🙂
And you bring up a good point, I don’t think I ever actually announced I was “back” on PuffBOMB via my blog. I just sort of invented new topics to confuse my 2-3 readers. 🙂
Anyways, the specifics we can take to e-mail (or try to), so long as I’ve not completely lost your interest as of the switch. 😉
> we’re still working on balancing controllers
Cool. I’ve tried to stay as conservative as I can in my designs, introducing something technically tricky incrementally each project, but it’s cool to see that you’ve gone all out with both ropes and going Frankenstein on a rag doll. ;). In retrospect though, I imagine ropes weren’t the hard part.
Thanks for the paper. Very much on the topic of things I’m investigating for a follow up game concept. An approach I’ve been thinking about was to simply lean forward (“try” to fall over) in the case of bipedals, or giving the center of the body forward momentum, with some sort of analysis code that intelligently calculates places/aims appendages to avoid falling over. Be it arms, legs, webbing, tentacles, tails, capes, wings, etc. All theory right now though.
*cough*, so I decided to try out what I was saying. A long analysis of what resulted you can read on my blog.
http://www.toonormal.com/2007/06/15/exploring-the-umi-rope/
After all, I may as well blog it. No reason to lose a good discussion in comments. 🙂
I’m sorry, I just realized you might not have *only* been talking about the rope aspects that make it cool. I guess I’m just so used to some things now in games I neglected to notice their significance, given the age of the game.
> non-axis-aligned/arbitrary sloped surfaces, including acute corners!
Ok, lets try this again. You mean the platformer part, not the rope? Actually, yeah, now that you mention it, maybe it does have 22.5 degree slopes too. Huh… I shouldg o back and pay more attention.
> conveyor belts
The rope attached to one of these doesn’t strike me as that tough of a problem. Locking the rope to it, and make your rope solving not move the attached point. Then incrementally move it along a path without velocity. If we’re talking a verlet solver, you’re setting both your current and last equal to the same value.
Of course, this only works because the hook doesn’t need to move except along the path. I ended up with a “I wish the code was cleaner” hacky system in a GBA game to do moving platforms by applying the platforms motion to the position and old. I can’t remember the specifics, but I know I wasn’t happy with the cleanlyness of the code.
I guess it wasn’t so much the rope simulation “per se”, but the collision detection/wrapping around all of those arbitrary tile shapes.
You’re right, the belt part in hindsight is simple: just move the hook!
Can I ask you if you have worked out the physics problem yet? If you have, can I ask you what method you have chosen to use? Have you considered using a constrained impulse-based method? It does multibody dynamics for rigid bodies extremely stably, robustly, and rapidly. It sounds like these impulse-based physics ideas might fit your needs well. You can find a lot of info on it at http://i31www.ira.uka.de/. Note that though the homepage is in German, the papers that can be found on this website are mostly in English.
thanks — we’ve tried a couple different impulse-based methods, including Jan Bender’s (http://www.impulse-based.de/) and Erin Catto’s (http://gphysics.com/).
future posts will probably touch on those.. both are practical and simple.
[…] Previously we mentioned the first of our physics tests; we also mentioned that it had shortcomings which pretty much ruled it out as a basis for physics-driven robots — it didn’t support friction, angular constraints, or motors. […]