Feasible landing trajectory

Life's a series of trade-offs. Today instead of cleaning the bathrooms I continued to work on optimal rocket trajectory planning. This version represents a switch from Haskell to C++, which is where I'll need it to be ultimately anyway.

New things I'm trying:

• Eigen linear algebra library. It's the greatest! It has plugged in very smoothly and just works, at least so far as I have used it. There are lots of constructor and operator options, so the resulting code is pretty close to the Haskell in conciseness.
• GLFW is also pretty great. I've used GLUT for years as my test application framework. GLFW fills much the same space but is actively developed, and can be statically linked (I hate dangling DLLs). I was able to trivially get input from my 360 controller, which was exciting.
• Learn OpenGL tutorial web page. I've used OpenGL 2.0, more or less, for years; this represents my initial forays into modern OpenGL. The planet is a flat piece of geometry that computes its lighting and anti-aliasing in the pixel shader, for instance. The lighting is in linear space; the crisp terminator on the planet is the give-away. Fun stuff, apart from the runtime compilation of text source code, which seems half-baked to me.

I've had a hard time figuring out how to do this. The math explodes if you look at it wrong; I've been gradually learning the various places in which things can go awry.

The current approach is to build an initial guess trajectory out of two equal-duration parabolic arcs. I chose two as being the minimum that could work. As it turns out, the nonlinear nature of the gravity field means that two segments do not work very well in some cases; the resulting trajectory does not bear a close resemblance to the trajectory you'd get with more segments. The process of ensuring feasibility tends to make it slew across the gravity field a bunch to get a usable average gravity vector.

The state vector includes the segment duration, the thrust vector for each arc, and the position and velocity after each arc. There is a set of 11-13 constraints. Each segment has four constraints asserting that the position and velocity variables integrate correctly across that interval with respect to each other and the acceleration. There are end-condition constraints, in this case specifying that the rocket is at ground height with zero velocity. Finally there are constraints that the acceleration vectors are less than the maximum rocket thrust. These are inequality constraints so they may or may not be present depending on whether the rocket is thrusting at maximum.

The initial guess is not feasible, in my case; I haven't made all the variables agree such that the constraints are all satisfied. So the first thing to do is to try to get to feasibility. This is done by measuring the error of all the constraints; getting the first derivatives of the constraint functions with respect to all the state variables; and then solving a linear system to find multipliers for the constraint gradient vectors that, when applied to them and summed up, will equal the constraint error vector. The sum-of-scaled-gradient-vectors is the step to restore feasibility. Of course this is a linear approximation, and the constraints are non-linear, so we won't actually be feasible. Rinse and repeat and hope for the best.

What works pretty well is to do a few iterations to get a close-to-feasible trajectory, and then subdivide it into four segments and iterate some more, then subdivide into eight segments and iterate some more. This gets to a nicely feasible trajectory in only a few iterations. The screenshot shows an example result from doing this.

I think next I may try switching to cubic arcs instead of parabolic arcs. Gravity and rocket thrust would be evaluated at the segment endpoints where I have position and velocity defined, which should be a bit simpler. In my parabolic arcs the rocket thrust is assumed to be constant over a segment, and gravity has to be assumed to be constant as well. I'm evaluating gravity at the midpoint between the two end positions, and then using that.

To get optimal trajectories I will need second derivatives of the constraints, and matrices with roughly double the dimensions; the fabled KKT system. I've gotten that working for a simpler problem over in Haskell; just have to get it over here with my planetary gravity field and so forth. More derivatives means more ways for things to explode, though.

ThiefRL2 Post-7DRL release

I released a small game in this year's Seven-Day Roguelike Challenge, which was in March. I'm finally getting around to putting out a post-challenge release, which has a couple of bug fixes and adds guard facing, so you can see which way guards are looking.

Here's the Zip file containing the Windows executable. (The previous, challenge version is here.)

Release notes:

• Show guard orientation. Guards can now only see in the direction they are facing, even when stationary.
• Guards do not move on top of each other.
• Player can hear guards from six squares away instead of five.
• Adjust house exterior to improve ability to evade guards and re-enter.
• Fix bug with guards pathing through trees sometimes when there was a non-tree route.

7DRL 2016: Day 5

Today was devoted to progression and polish. I tweaked the level generator so it could generate levels of increasing size and difficulty and strung them together in sequence. Then I added a help menu and tidied up some of the presentation to try and make it clearer what is going on. In the screenshot below the player is getting smacked around by the guard.

I cut a bunch of stuff but the resulting game should be good for a few minutes of fun. We have a giant wind storm and power is spotty in the neighborhood so I'm going to call it good.

Here's a link to the zip file containing the game. It runs on Windows. Enjoy!

7DRL 2016: Day 4

The game looks pretty much the same today as yesterday, but it's actually somewhat entertaining to play now.

The guard patrols work more-or-less as expected. There are a couple of pathfinding bugs (guards occasionally move on top of each other, or double back unexpectedly) but they're relatively minor.

The other big gameplay change was to streamline and have the player implicitly open and close doors, instead of doing it explicitly. This keeps the flow going better and requires less fiddly stuff.

Not much to see in the screenshot. There is a bit of furniture you can hide under inside the house now.

Tomorrow is the wrap-up. I still need to put in a help screen, level win conditions, and a level progression. If I have time I'd like to get in a collectible key that grants access to the upper blue-floored parts of the levels, and there are a couple of other functionality changes on the list.

7DRL 2016: Day 3

I've got more-or-less passable courtyard mansion levels going.

There are still room decorations to place and some bugs to fix with the existing room decorations. I'm trying to represent the hierarchy of the space by having the upper quarter or so of the rooms be a “master suite.” Eventually there will be more of the treasure here, and I've experimented with having locks separating it from the rest of the house.

Getting guards to patrol in a reasonable fashion is proving difficult. There are many more chokepoints in these levels than in my previous test levels, so guards tend to get stuck trying to go through doorways in opposing directions.

For a bit more thinking-on-your-feet, I decided to switch from fixed patrol routes to a system where guards wander from room to room, exiting a different way than they came in. I'm still in the middle of implementing that, though. My hope is that if two guards happen to bump into each other in a room they can exchange a couple of lines of dialogue and then head their separate ways.

The one-way windows work pretty well. I want to restrict visibility to be one-way through them as well, but I don't know if I'll get to that. At the moment the player can see through them but the guards can't.

7DRL 2016: Day 2

It's the end of my second day of work on this year's Seven-Day Roguelike entry.

The first day was devoted to fixing bugs and finishing some refactoring I'd begun a long time ago. I wanted to render objects like tables and chairs on top of the floor, with alpha, instead of having the table or chair tile completely replace the underlying floor. It is mostly aesthetic, but it is a pain to get right.

One of my main goals for this round, as I said in the last entry, is to make a random level generator that works for stealth gameplay. Darren Gray warns not to mess around with level generation in a 7DRL, but I've got gameplay that basically works and I had never managed to come up with a random level generator for it.

I grabbed the starship generator from my old SpaceRL project and have been cleaning it up and turning it into something that can generate courtyard houses.

The little wedge-shaped things in the walls are supposed to be one-way windows. The idea is that they're up higher, or latched from inside, or something like that so you can jump through them one way but not the other. This is to give the player quick escapes from inner areas toward outer areas. I don't know yet if it'll work as intended; I haven't got guard patrols into the generator yet. That'll be the first thing for tomorrow.

Hopefully the last day or two I can work on the graphics so they're not quite as hard to look at. My main priorities, though, are to get a random level generator that produces fun levels, and to try to tell a bit of story.

7DRL 2016: Late Start

I'll be getting a late start this year due to a travel conflict; probably on Tuesday the 8th.

Because of the short time frame I'm going with some existing game mechanics. A few years back I made a prototype that attempted to adapt Thief (one of my all-time favorite games) to a turn-based game. You can play that version here.

This year's 7DRL goals are to add a random level generator and a narrative. For levels I've been buying books and reading up about Chinese courtyard houses. Here are some layouts I did by hand to try to get a feel for the things I want to generate:

For a plot I'm probably going to crib something from Barry Hughart's Bridge of Birds, so expect supernatural crime. I don't know that I can match his delirious prose style and I know almost nothing about ancient China apart from courtyard houses so it'll probably be a travesty.