Monday, March 16, 2009

SpaceRL released

I knew ahead of time that it would be next to impossible for me to enter this year's Seven-Day Roguelike Challenge due to my work schedule. When the call for dates went out at the beginning of the year I decided to start immediately on something small in the hopes of having it ready to release to coincide with the Challenge deadline, since deadlines are good to have. The core idea was to try and approximate zero-gravity movement in a turn-based, square-based game, as I outlined in my previous post.

Starting with the engine for ThiefRL, my unreleased stealth-based Roguelike (eh; might as well release it now), I stripped out the sound propagation, guard speech, and various other things. I kept the line-of-sight code, the pathfinding, the map structure, and the basics of the monster type. I added in a random map generator from another experiment I'd done in villa creation, and I created the basic inertia-based movement scheme.

And that is pretty much where it is now.

I spent a huge amount of time thinking about how to do predictable rigid-body dynamics so that you could push collections of objects around (or be pushed by them). In the end I had to abandon all of that in order to get something done. Currently, only you and the monsters move, and the monsters don't obey the zero-gravity movement rules.

I also spent a huge amount of time on the dungeon (a.k.a. starship wreck) generator. I'm happy with the overall shape of the spaceships. Here are some examples (click to enlarge):

The generator starts with a target number of rooms and a horizontal or vertical symmetry axis. It accretes rooms next to existing rooms. Each placed room adds its four neighbor positions (if they're not already in use) to a set of candidate positions. The next position to use is drawn randomly from that set. Thus empty positions become more likely to be used as they acquire more used neighbor positions.

Once the core room layout is created, the walls are randomly offset by up to half a room in either direction. A fixup process ensures that rooms don't overlap by picking horizontal or vertical at each intersection and forcing the walls to align in that dimension at that intersection.

Next is the crazy part. Originally I allowed doors only between rooms that were adjacent in the original grid. However, the wall-shifting can create new adjacencies. At considerable pain I created a system to identify all adjacencies and form a graph of possible room connections (doors). Then I create a simply-connected graph by randomly adding edges between unconnected components until the entire spacecraft is connected. This ensures that you can always get everywhere. After that I add a random fraction of the remaining unused edges, as well as some doors to the outside.

I got partway through cleaning up the door placement. You may notice in the maps above that some doors are placed symmetrically and others aren't. I'd like to have the underlying door structure be symmetric, and then block or destroy doors to satisfy the level connectivity requirements, which would be determined by a system that would take into account locked doors and key placement; that sort of thing. You want to make the player work a bit to get through the level.

I also got partway into implementing air ducts: an alternate movement layer which only the monsters can use. The idea is that they can't open or close the doors, so if you close the doors they will backtrack to the nearest duct and get through to you that way. I think it shows promise but I just didn't get it done in time.

I've got loads of additional feature ideas which I'd like to put in when I get more time.

The ThiefRL game I linked to above is an entirely different experience. It features a single hand-authored map at the moment, which I have been using to test out gameplay features. You can't kill anything in that game, although you do play a threat to society. I'd estimate that it's got 30 minutes to a couple of hours of gameplay in it right now, and is quite a bit more fun (I think) than SpaceRL.

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.)