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!!
Loki’s Tattoo 1
Loki’s Tattoo 2
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.
Constraint Paths
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.
Rope+Belt Redux
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!!
Editor Screenshot
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!
Guys this sounds so incredible.
And amazing tatoo. I was going to get one before the wifey vetoed that decision. I was very sad, but it would have been awesome (although probably not as awesome as that one above)
Again, the game looks stellar so far, and the level designer in me is already drooling over the potential in this game.
Absolutely amazing. I’m particularly impressed with the piles of circles and capsules not intersecting at all — I had huge nightmares with collision resolution creating new problems with other geometry – I tried both the solutions you mentioned and got nowhere with both. I hope you go more in-depth with the “smaller steps” you took, sometime in the future.
The constraint paths are something I didn’t expect and I also like a great deal. When you mentioned modelling conveyor belts physically at first I interpreted that as having a sort of sagging segmented rope around two wheels (like the conveyor belts you can build in armadillo run), which usually cause strange glitches and because they’re segmented, have slightly unnatural properties. This exact solution is much better. I can imagine some really cool puzzles being created with pulling stuff along a path.
One thing I am slightly disappointed with is the rope physics though. In Umihara, and the very first demo you showed us, the rope was not made out of physical segments but seemed to have code independent of the physics engine to exactly wrap around things along their edges. I greatly prefer an exact solution, but I can see how it would be hard to extend your code to arcs (as I found out myself when I contemplated adding ropes to a game), and I can see how a more physical approach would allow the rope to bend and swing in the air for a more realistic effect. If you do end up using the segmented approach as it seems you have here, you should probably use smaller segmentations instead of drawing a curvy rope over the more approximate actual physical object. I don’t like it when the graphics don’t fully represent the underlying physics. No doubt you’ll go through rope physics further in a future post and explain the impossibility of my suggestions, but that’s my 2 cents.
Also, the editor. I wasn’t sold on the idea at first but now I can see how intuitive it could be in practice. As I understand it, you only control the skeleton joints, and the editor automatically creates the purple region. If this is the case I would like to see the additional ability to create exact point-by-point geometry for creating exact shapes for puzzles and such, because creating a shape that responds in a certain exact way could be difficult when you have such “clumped” control. Also I’m glad you’re making the move from tiny N levels to larger levels that you can “explore” and find secrets — to me this will make it feel more like a full game than the giant list of tiny levels that N presents you with (don’t get me wrong, I love N)
So yeah, have a long comment to go with your long post. I can’t wait to play it!
It sounds to me like you are still using frame by frame collision! Have’nt you heard of frame independant collision, much more accurate.
@maximo: Yeah, we were blown away when we got that pic.. 8D
@mattk210: The rope is still the same as it was before! We just changed the way collision was detected and dealt with, but the basic idea is the same — a line that splits into two lines when it collides the corner of a shape.
Reviewing the screenshots, there’s some stair-stepping with the drawn lines, but that’s just the non-anti-aliased debug renderer. Don’t worry, it’s still like in Umihara 🙂
@t3hpwn3r: By frame-independent do you mean swept tests? We tried those previously, but for various reasons they don’t really work all that well..
the purple line is the rope right? Around the ends of the capsules for example, the rope is square instead of curved and fails to wrap around the rest of the capsule exactly. I’m not talking about the aliasing.
I believe t3hpwn3r means using timed intervals as steps rather than iteration as fast as can be calculated. Kind of like frameskip compared to slowmo in IWBTG, or using enterFrame instead of setInterval in Flash. Although that definition doesn’t make much sense… I can’t see how t3h would infer you’re using one or the other so far
here’s a (very) hastily drawn picture:
http://offtype.net/image_1662622696296.gif.html
the one on the left is what it should look like (the green guy is hanging from the red grapple point by the way), and the one on the right is an approximation of the rope wrapping around the curve, made out of straight segments.
Aha!
Well actually the “capsules” are really rectangles as far as the rope knows — we’re going to be using polygons mostly for larger bodies, capsules are just a nice shape to test rope with because you can exaggerate penetration (i.e by making the rope collision shape a rectangle and using the capsule shape for rigid body collision, you get situations where the rope collision shapes overlap).
This sort of overlap will be very tiny when polygons collide, but it will still be there — using capsules just makes the error much larger so we can more easily test/see what’s going on and make sure the rope doesn’t “snag” on things.. it can get pretty messy when two shapes rub corners with each other!
Also, we’re definitely running at a fixed rate, I think 100hz.. this is a must, using variable-length steps is evil!
awww! Thanks for the early birthday present!
“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.”
Funny how that works out. It’s like using Riemann sums to approximate instead of solving the integral. With sums, you can be as accurate as you want with the cycles you have.
Are there plans to open source the physics engine? You mentioned Box2D–maybe it could benefit from your techniques.
Some of us wouldn’t mind if you did both at once and frequently did novel-length posts… As if you have that kind of time. xD
Anyway, that was neat to see / read about; it’s all very impressive.
does that mean we can’t use arcs in level design or else the rope will wrap strangely around them? Or did you treat the capsules as rectangles on purpose, and you actually do have some arc-wrapping code you haven’t shown us yet? If so, show us! I couldn’t figure that one out myself.
Why does loki not come on the forums? :(:(:(
Vezquex: We’re going to do some tutorials like we did with N which explains what’s going on, probably with source. Most of what we’re doing will likely not benefit Box2D, because (a) it uses a velocity-based solver, so the solver doesn’t move things in mid-frame, and (b) it already has a much more advanced collision system which uses conservative advancement to move objects to the time of first collision.
mattk210: Yes, sadly arcs are out as collision shapes ( http://www.metanetsoftware.com/?p=31 ) 🙁
They complicate editing and generally were more trouble than we wanted to deal with. Now that we’re no longer using sweep tests, it would probably be much easier to add arcs, but we already have enough to do as it is!
Awesome collection of experiment screenshots. 🙂
…Hey, I just saw a video of your “indie game maker rant” at GDC. I really enjoyed it, especially Raigan’s talk about “Cool stuff someone should be doing, but not us because we’re too busy/lazy”.
I feel the same way; if you simply must do 3D, at least do something interesting with it.
What if the rope were to collide with a small box, while you’re swinging on it – in a fashion that you would loop around the box and back (into/through) the rope. What would happen? Would you hit the rope and collide? Or would you simply pass through?
By what i can deduce from the current system, you would cause another… break? in the line, and… end up entrapped by the rope?
We don’t know yet! We’re planning on having the player not collide with the rope; this is also an issue for smaller enemies, it’s not clear whether it would be better to have everything collide or not. We’ll see..
If you make enemies colide with the rope you can do things where a piston that moves up and down can be used to life the player up by contacting the rope while it is between the player and the attach point of the rope.
If that made any sense.
I’m inclined to think it should always interact with the rope. But What do I know, i’m not looking at the simulation.
OOH, or an enemy that floats up and down could be used as a puly. That just sounds like too much fun to _not_ have in the game.
*Starting post-chant*
(speed up)
UP-DATE!
UP-DATE!
*clap* *clap* *clap*
UP-DATE!
UP-DATE!
*clap* *clap* *clap*
UP-DATE!
UP-DATE!
We’re working on it 🙂
hey well this is way off subject but well i have got no response anywhere else I was wondering if there is going to be a 4th map pack for n+ well if there is I have over 150 levels that I would be glad to show….yeah that’s my gamer tag
Sadly there won’t be any more map packs — because of how we’re saving data, we’re limited to a finite amount of space, and since we have to store the best time per level, this means that the number of levels we can handle is finite.
I think we may have mentioned this in a previous post, possibly not though. Sorry! 🙁
man, the internet has been so boring lately…
Sorry.. we’re working on it!
We just have a very specific feature we want to show, and getting it to work is taking longer than anticipated. Also Raigan was sick for a couple weeks 🙁
well under the circumstances you are 100% forgiven. As long as you guys aren’t just playing miner dig deep I’m happy. Take as much time as you need!
Is there a date when N 1.5 will release?
N 1.5 will not be released. You will have to live with the glitchy engine 1.4 produced forever.
I’m sorry.