First of all, we have a few new winners for Contesque #3, at long last. The first win goes out to Duncan, who sent us a whole bunch of drawings of N+ costumes. We chose the one we thought was the most fun 🙂
And next, we have to share what may be the most awesome thing we’ve ever seen. Previously, we thought we knew about hardcore fans — you know, the people who play N using the invisible ninja, or that complain that the 80s column is too easy. The people that can beat the most difficult N+ level pack in an hour, and dominate the leaderboards with their skill and panache.
It turns out we were only kidding ourselves, for the bar of hardcore-fandom has been raised — to the Nth degree, as it were — by Lokitrickmaster, and his AMAZING N+ TATTOO!!
It’s a really awesome feeling to see something you helped create resonate with gamers; thanks so much for sending this in Loki, you rock!
This officially concludes the third Contesque, for obvious reasons — we don’t want anyone to die trying to top that! Congrats to you two, and check your email. Thank you to everyone who sent in a submission, it was great to see so many creative and cool people with wonderful senses of humour 🙂 We hope you’ll come back for our future contesques!
And now, by special reader request, lets go through some screenshots from recent weeks and document what we’ve been working on. As the title suggests, these will not be very pretty and may not make a lot of sense…currently the “real” graphics system isn’t hooked up to the simulator so you’ll just be seeing debug graphics (showing the collision shapes, constraint points, etc).
Mostly we’ve been working on finishing v2 of the simulator, but we’ll throw in an editor pic just for fun. (Click the title of each section to pop the screenshot up in a new window.)
Constraint Solver Stress Test
Here we have a thousand or so rigid bodies linked into a long chain with point-to-point constraints (aka “pin” constraints, aka “revolute joints” for Box2D users); a few points along the line are pinned to the background.
There are no collision shapes on the bodies, so they’re just drawn as lines, but each line is a full rigid body. Of course, the bottleneck in most simulators is collision detection (at least, this has been our experience…might be we’re just bad at collision! ahaha.) but it’s still nice to know that the simulator can solve several thousand constraints per frame. Just like in Little Big Planet, we’re not relying on “sleeping”, i.e we’ll be simulating the entire world all the time, which seems much simpler in the long run when trying to nicely handle large user-made worlds.
Also we should point out that we’re using only 2 constraint-solving iterations per frame. We can actually get away with 1, everything is stable, but there can be artifacts due to constraint ordering (forces generated by constraints solved later in the frame aren’t “felt” by earlier constraints until next frame)… We’re still not sure what we’ll end up doing, possibly we’ll use different iteration counts depending on the type/priority of the constraints (i.e offscreen mechanisms use 1 iteration, onscreen mechanisms use 2, etc.)
The revised solver probably isn’t that much faster than the old solver (it may even be slightly slower since it’s quite generalized in comparison), but it is a LOT simpler and much easier to use. A huge plus!
Circle Collision Stress Test
Capsule Collision Stress Test
These two are just quick tests to make sure that we can handle many hundreds of collision shapes moving around. Again, it’s really nice to see good stability and lack of penetration with just 2 solver iterations, check out those circles!
The second version of our simulator required that we rewrite our collision detection system, since the old simulator supported only rigid polygons and the new simulator is more generic. We needed something that could support simple and cheap shapes (circles and capsules) as well as non-rigid shapes (such as simple telescoping/deforming shapes).
Also, the old version was pretty slow, at least in comparison — we were doing all sorts of sweep tests and complicated predicting, in the end we decided that a better (and simpler) solution is to use static non-swept collision tests and just take smaller steps to prevent objects from passing through each other.
Thankfully we didn’t need to actually rewrite everything, most of the low-level stuff like the grid system and whatnot was reusable and the rest just needed a bit of revision to work with the new simulator. The main collision loop is now only a couple dozen lines of code, super nice and simple 🙂
Collision detection is definitely still a bottleneck with this type of simulator: the constraint solver moves shapes around, which can cause collisions in mid-frame, which means you need to either (a) perform collision detection with each solver iteration, or (b) generate collision constraints between shapes that aren’t currently colliding but might collide during solving (i.e nearby shapes). The former results in lots of additional collision tests, while the latter results in lots of additional constraints to be solved, so either way there’s more work to be done than in a velocity-based solver.
We’re hoping once we finish the game and have time to write up some tutorials, other people will experiment with this sort of simulator and find some new solutions to this problem.
This picture shows a constraint “path” (a chain of line segments and circular arcs forming a closed loop or open strip of geometry) anchored to a rigid body (the capsule), with two particles connected via constraints to points on the path. If you pull one of the particles, it will stay connected to the path and will drag the other particle along the path with it.
This is a bit complicated to describe, but essentially “paths” are how we model moving platforms and conveyor belts and stuff like that. If you look closely on the left side, you’ll see a little square on the path, this is a “bead” which describes movement along the path, adding 1D degree-of-freedom to the system.
If you consider a 2D rigid body, it has three degrees of freedom: position along the x axis, position along the y axis, and orientation (“rotation about the z axis” if you’re picky).
Now imagine that the surface of the body isn’t fixed, but is like a loose belt or piece of string that’s wrapped around the body, and which can slide around the surface: this is what the bead models.
You can think of a constraint path as a rail or wire that the bead slides along. The name “bead” is meant to suggest a bead sliding along a wire; the position of the bead along the wire can be described by a single number (its position/distance along the wire from some fixed reference point on the wire), hence it adds one degree of freedom. You can constrain points along the wire, and as the bead moves those points will move too (and vice versa — pulling on a point will cause the bead to move). This lets us model conveyor belts, and also lets us move platforms along complicated routes, all by adding a motor which pushes the bead along the wire. Hooray!
Anyway, while the basic idea remained the same, we had to revise/rewrite all the constraint path code from the old simulator…so far we’ve tried two or three different ways of describing both path geometry and bead position/movement!
The really nice thing about this revised version is that the constraints don’t know or care if they’re working on points embedded rigidly in a body, or points embedded somewhere along a path which is itself embedded rigidly in a body!
The old simulator wasn’t so nice: to interact with belts, you had to create a proxy particle which was attached to the path via a special “point on path” constraint. External constraints could then pull on the particle, and the particle would in turn pull on the path via the PoP constraint. This was a bit hacky: you didn’t want the particle to be too heavy, or else you would notice mass being added to the system when you started interacting with belts, but if the particle was too light the solver wouldn’t converge well. It’s much nicer to just embed a point in the path’s degree-of-freedom and let constraints work on that directly. Yay!
Conveyor Belt Test
This shows a capsule with a bead/path wrapped around it, acting as a “tank tread” to drive the capsule up a hill; there’s an object pinned to the conveyor belt — perhaps a robot whose grappling hook is attached to the tread? 😉
We’re not sure how much we’ll use conveyor belts like this (i.e to model tank-type entities rather than the regular use of “moving floor” that you see in Umihara), but it’s nice to know that it’s possible and happens automatically without special-case code. Who knows, maybe that moving floor you run across will later turn out to be the bottom of a large robot’s foot? 🙂
Rope Simulation Test
Along with collision, rope was something that needed to be totally rewritten, and it was pretty fundamental. The old version was failing to deal nicely with situations involving small penetration which can happen when objects pile together.
This post is getting way too long, so in the interest of brevity we’ll just say that we’ve tried two or three completely different ways to model rope, and we’ll be documenting them whenever we get a chance to write some tutorials! This new rope is a lot of fun though, here you can see it wrapped around a bunch of boxes.
This was just a quick test to make sure all the different systems interacted nicely; you can see a rope which has one end embedded in a path, so that pulling on the rope will pull the bead along the path.
While it took only a couple weeks to rewrite the basic core of the constraint solver, revising all the other bits which interacted with the solver (collision, belts/paths, rope) took a lot longer than we had anticipated. Now that it’s finally over, we get to work on stuff like controllers and motors and moving things around in the world using constraints. Getting closer to the fun stuff, finally!!
Finally, a pic of the “inflated skeleton” editor. You can see the purple area, which is a “secret region”: it will appear to be solid until one of the link-points (the circle-with-plus-shapes) moves, disconnecting the chain of geometry that defines the secret area and opening it.
This is pretty hard to describe, and it was definitely tricky to implement! We may not have mentioned this before, but we want exploring and discovering secret areas to be part of the game (we really enjoyed it in Gish and Loco Roco), and this dynamic-hidden-area system will allow levels which are layered like an onion.. previously solid shapes in a level may turn out to really be hollow spaces with an entire new level inside! Mmm, delicious onions.
Anyway, this concludes our review of the past couple months of work. We’re going to start really trying to post more frequently, so that each time we do post it’s a smaller, easily-digestible read and not a gigantic endless novel of a post.
Onward to pithyness!