Sunday, March 1, 2009

Square-based, turn-based rigid-body dynamics

The day job's been very busy lately. I'm finishing up a game (Infamous) which I've been working on for something like three and a half years. I've always wanted to be on a game project from start to finish, and I'm almost there. It's sobering to think of my life in chunks of this length, though. I have two daughters I didn't at the start. How many more of these do I have left in my career? etc. It's night and I'm maudlin.

At home I've been thinking, fairly fruitlessly, about how to put simple rigid-body dynamics into a Roguelike framework. This was the inspiration:

In this scene from Tobias Buckell's Caribbean-flavored space opera, the heroes propel themselves across the zero-gravity core of a space colony by pumping lead into their pursuers with a giant Gatling gun.

The other inspiration would be Space Hulk, I suppose, although I've never played it.

First, I repurposed an earlier attempt to randomly generate villas to create derelict starcraft:

I did some work on opening and closing doors using bumping alone and finally came up with something I like. Bumping a door head-on opens it; the problem was always to come up with a reasonable interface for closing the door again. What I have now is that if the door is open and you stand in front of it and diagonally bump the door frame on either side it will close again.

My other current Roguelike-in-progress uses a Ctrl-dir key chord to close doors. In this game I'm devoting the Ctrl-dir key chords to shooting; the idea is that when you're shooting you keep moving in whatever direction you were moving the turn before (floating in zero gravity). Also, you cannot change your movement direction unless you're adjacent to a wall or other mass.

I mocked up movement for the player character and it went pretty well. I threw in some really basic monsters, and as soon as I gave them enough hit points that they took several turns to kill it got interesting. You'd want to lead them to a straight corridor, kick off, and glide backward while shooting.

The “physics” seems like it has potential for some interesting gameplay. For instance there might be a monster that can't be killed, only stunned. Permanently neutralizing it would involve pushing it to the nearest hatch and committing it to the void. Or you could have crate-stacking, but IN SPACE...

I thought it ought not to be too hard to adapt a rigid-body physics system to a turn-based, square-based regime but so far it has stymied me.

The important thing, I think, is for it to be predictable to the player. Positions are constrained to squares, obviously, and I want to prohibit multiple objects in the same square. I've decided to constrain velocities to be integral in each component as well. Furthermore I'm trying to constrain velocities to be -1, 0, or 1 in each dimension. Velocities of 2 or more might be okay for some things, but experimentation is necessary.

I've tried out solving collisions and contacts using a fairly standard impulse-based solver, in floating-point, and then rounding velocities back to integers. It doesn't yield good predictability though and falls down on some fairly simple cases, like a line of crates hitting another line of crates. With the right numbers of crates you can get it so that the momentum hasn't been totally propagated throughout the stack and some crates round to zero velocity and others not, which means they move on top of each other.

Contact is a tricky concept in the grid-based environment too. Objects that are diagonally adjacent are contacting if they're moving toward each other, but not if they are moving past each other. A conventional “relative velocity dotted with contact normal” approach can't distinguish these.

You can also have objects that will move into the same square on the next turn if left alone but which aren't actually adjacent at the start of the time interval. What ought to happen in these situations?

I'm now working out some problems on paper in terms of generating sets of contact constraints and solving them as a system of linear equations. I think it might be possible to do that with rational arithmetic so that everything comes out perfectly. There are some cases I'm not sure about though.

If you have any good ideas about doing “physics” in a turn-based, square-based game, I'd love to hear them. I feel like I'm spinning my wheels on this right now.

(An academic paper on this might be titled Rigid-body dynamics with large-scale time and space discretization.)


Snut said...

Have you investigated the lattice Boltzmann method? Admittedly it usually deals with continuous distributions over discrete space and time, but it might provide an interesting direction to check out.

I've been messing with it (as a more conventional use as a fluid simulator) as a method to model magical flow in a turn based game and on a hexagonal grid.

Fun stuff anyway, good luck!

James McNeill said...

Yeah! Thinking about the problem in terms of the grid (the Eulerian approach) might be more profitable than dealing directly with the bodies (the Lagrangian approach). I will read up about LBM to see if it is adaptable to this.

Mark Sachs said...

Aw man, no 360 version for Infamous? :)

I've had basic rigid-body physics working in my own game for some time, but as it's vector, not grid-based, that's of limited help to you.

I could picture an underlying simulation that maintains a more detailed view of everything's location and then renders it all on a fixed grid, which is the actual field the player interacts with. So it's a "real" physics sim under the hood, but the player can only apply impulses to it on a discrete grid. That said I have no idea how that would actually feel in practice.

Mark Sachs said...

Yeah, and I just re-read the article and you already thought of that. I need more sleep!

Andrew Doull said...

I don't think you need to worry about simultaneous actions. You're unlikely to be using a discrete time model anyway for a turn based system, so just process your entities in some order, and whomever gets processed first enters the grid.

You may want to have a look at my academic piece on a similar concept: A Method of Implementing Player-Crewed Sailing Vessels in ASCII Roguelikes

Eino said...

Judging by SpaceRL, you solved these problems. The game is a delight to play!

The zero-gravity concept is inspiring - I am already thinking that a top-down realtime shooter with wasd+mouse controls (and weapon recoil) would be cool.

Not to say that the turn-based approach wasn't fun. I'm not sure if there's much to this game after I figured out the strategy to move and shoot the monsters, but it certainly reaches the 5-10 minutes of fun goal.

I also liked the idea of identifying remains as an objective. The way you get a name of a dead person as a milestone-type reward, and how it's displayed as temporarily overwriting your HUD elements is somehow poignant and sombre.