Interior-point constrained nonlinear optimization

Here's a boring-looking plot of something I've finally made some progress on after years of trying to learn it:



This is constrained nonlinear optimization on a very tiny problem. It's a trajectory (in one spatial dimension) composed of two cubic segments (colored yellow and blue). The top plot is displacement over time, and the bottom plot is acceleration over time.

The objective is to minimize the total time of the trajectory. In these animated plots the total time is decreasing as the animation proceeds, but the plot is scaled to keep the same width so it's a bit misleading.

The cubics have fixed endpoint positions; the position at the boundary between the two cubic segments is also fixed. In this example it is closer to the left end of the curve, so the yellow cubic has a smaller displacement than the blue cubic. The velocity at the start and the end is fixed at zero, while the velocity at the boundary between the cubics is a free variable. The time durations of the two segments are the other two free variables.

The problem is constrained by limiting the maximum/minimum allowed acceleration, which is represented by the top and bottom extents of the bottom plot. Because cubics have their most extreme acceleration at their endpoints the constraints are applied there. There are eight potential acceleration constraints, because each cubic has two endpoints, and each endpoint has a lower bound and an upper bound on its acceleration.

If the midpoint between the segments is equidistant from the endpoints (as in the animated image below), then the optimum trajectory is to accelerate at maximum for the duration of the yellow segment, and then decelerate at maximum for an equal duration in the blue segment. This is a trajectory made of two parabolas, due to the constant accelerations:



Because the first plot has an offset midpoint, only the shorter-duration segment can be at maximum acceleration; the blue segment needs to have a varying deceleration so it can hit the target position and velocity simultaneously. Note that if we were to break up the trajectory into more segments we could get shorter overall travel time. Here's another animation of the problem being solved, with the midpoint displacement shifted the opposite direction:



Solving constrained problems like this can be done in a couple of broad ways, both of which involve taking a guess at a solution and iteratively making it better via a series of steps. In all of the examples shown my initial guess is to have the midpoint velocity be zero and the segment durations be long enough that the accelerations are within limits.

Active-set methods try to keep track of which constraints are active and move in a way that improves the objective score without violating the active constraints. As the solution is iteratively improved, the set of active constraints may change. You could think of it as sliding downward in the objective direction along the boundary of the constrained area, bumping along from surface to surface of the different constraints.

Interior-point methods, in contrast, keep all of the constraints active all the time, and instead adjust their strengths until the solution gets very close to the constraint boundary. They are kind of like landing a rocket on the surface; the solutions start out in the middle and settle down toward the constraint surface. The advantage of interior-point methods is that the structure of the problem stays the same as the solution is improved.

The animated solutions here are interior-point movement. There is a “slack” variable that controls how far from the constraint surface we're aiming to be (roughly). In the animations shown I'm controlling it by hand. I do a few iterations at a given level and when the solution looks like it's converging I reduce the slack by a factor of ten.

Both of these methods make use of first and second derivatives of the constraints and objective to come up with a likely direction to move. It involves building and solving a system of linear equations; the size corresponds to the number of variables and constraints in the problem. (It's called the Karush-Kuhn-Tucker system; there are lots of names in this area.) This gives a movement direction and expected ideal distance, which then needs to be trimmed down (backtracking) to avoid violating constraints or making things worse in any other ways.

References:

• An Introduction to Trajectory Optimization: How to Do Your Own Direct Collocation, by Matthew Kelly, is a good introduction to trajectory optimization.
• Practical Methods for Optimal Control and Estimation Using Nonlinear Programming, by John Betts, covers active-set methods.
• Convex Optimization, by Stephen Boyd and Lieven Vandenberghe, covers interior-point methods (in its last chapter).
• Numerical Optimization, by Jorge Nocedal and Stephen Wright, covers interior-point methods in its last chapter as well.

Pico-8 Thrust-alike WIP

This is what a mid-life crisis looks like for a game developer in my age bracket:



Most men in their 40s buy something they were into in their teens. I tell my wife she's lucky I wasn't into cars or airplanes or anything like that. The Pico-8 fantasy console costs $15 or so. I've been adapting my rocket lander game to it.



The controls are changed up quite a bit to make the game play faster. It still has a braking line, though.

Dijkstra fill in Python

There was a thread on the Roguelike development Reddit with some quite alarming versions of Dijkstra's algorithm for computing graph distances, so I threw one together to contribute.

Here it is.

Pico-8 Orrery

Super-simple solar system, implemented on the Pico-8 retro fantasy console. Left/right to adjust time, up/down to adjust zoom.

Here's the "cartridge" which is a PNG with the whole program embedded inside it:

The Pico-8 has 16.16 fixed-point arithmetic, which makes working on things that span a wide range of scales challenging.

2018 7DRL: Sword Horde

The game's up for download now over at Itch.io: https://mcneja.itch.io/sword-horde

I marked it as an Incomplete in the 7DRL challenge because it is very short and doesn't feel much like a Roguelike. The closest thing to it is probably Unexplored, an action Roguelike with a similar top-down view. Unexplored has some nice dungeon generation techniques. I felt like its combat was underwhelming, though.

Sword Horde was an attempt to work on group movement and formations. I didn't get very far on that because I needed a core combat mechanic, which is something I'd been putting off for a while. It was good to spend some focused time on developing the core though. With some tuning I feel like this could be a workable base for a bigger game.

I had talked with a friend about Dynasty Warriors since that is the main franchise I can think of that handles a hero versus an army. I have played a little bit of Dynasty Warriors over the years but probably not more than a couple of hours. Consequently I was working mainly from my own imagination and from previous combat prototypes that I've made.

---

Some of the ideas that were on the list and didn't make it in:

Enemy types. The obvious things: a boss who's bigger, slower, hits harder, has more hit points. A guy with a shield on one side. Projectile launching guys.

Formations. I was thinking the guys would be in groups of three or four, with a marked leader. Any group with a leader would attack in a pattern. If you kill the leader the guys attack in a less coordinated fashion until they can hook up with another leader. Whether patterned or chaotic attacks would be harder to handle is unclear; ideally the former though.

Combos. This is the core of Dynasty Warriors and I did not get this in at all. It would have been relatively easy to do a combo meter and have some area-of-effect attacks that you can discharge when the meter fills to certain points.

---

One of the things that has bothered me about these kinds of games is that the player has free run of the whole battlefield. There's very little feeling of enemies denying access to spaces. My initial experiments were aimed at trying to produce a well-defined territorial boundary that would move as you fought the battle. In the end I scrapped it and let the allies run around on the battlefield with you.

I suppose one of the problems with having a well-defined front is that it reduces the dimensionality of the encounter space. In a 2D-surface-based game you have a line where the action is occurring. With ranged weapons that might be a little less of a hard line, but it's still a smaller space for action, and at any given time you're not using the whole space. I think the idea of a battle front is still useful, though, to try to guide the player toward the action.

Figuring out how to make armies look like they're fighting but still keep the player as the driver of the action is an interesting challenge. In the little bit of Dynasty Warriors I've played it felt like they were lazy on this front. Guys are mostly just standing around when I come upon them.

Combat targeting is a hard problem to solve. I have some ideas of improvements that could be made but it's hard to know what will work until you try it. The characters kind of flip themselves 180 degrees if they think it will help them swing at a better target.

Combat flow is hard, too. Sword Horde makes use of Gabriel graph structure to decide who is eligible to do a running-charge attack at the player. Only people who have an unobstructed sphere of space between them and the player are allowed to attack. Once they have started charging they keep charging, which can mean they are trying to find their way through crowds to get to you. But the initial decision is based on clearance.

The biggest problem, I feel, is that it's hard to predictably avoid getting hit accidentally while swinging at someone. I did a lot of tuning—adjusting elasticity and friction, mass and moments, sword lengths, attack timings, attack steering directions, stun durations—to try to come up with something that would reliably separate the characters after a hit. It's not really there yet. It seems like maybe it's close. All of the afore-mentioned parameters interact with each other, though. I spent a ton of time instrumenting and testing the charge attack.



You can see some of the thinking in the debug display above: the orange guy is moving toward the pink disc which is offset to the left side of the yellow player (because orange is planning to make a counter-clockwise swing). The player's not moving, so its predicted position (the tiny pink disc) is centered in the yellow disc. The orange guy is predicting that based on where he wants to be and how fast the distance is currently closing, he should launch his attack when the gray disc touches the yellow player disc. If the player were to lunge toward the orange guy the gray disc would expand accordingly, triggering the attack earlier.

2018 7DRL: Day 7

Tidying things up for release. Today's work so far:

• Give the player a bit bigger of a sword than the rest
• Tune combat flow
• Ditch the territory and let allies run around as a pack and “help” you
• Add a very simple level progression and a screen fade between levels

I think it will probably be called Sword Horde.

2018 7DRL: Day 6

It ain't looking great. I've got the thirty seconds of fun (as Jaime Griesemer said once about Halo) but that's about it. There is still a fair amount of tuning to do on that thirty seconds, too.

Today's work:

• Link statically to the C runtime library, so I don't need to have people install the DLL
• Fool around with an enemy territory mechanic, with friendly soldiers and enemy soldiers marshaling on either sides of the front
• Simplify the debris system
• Add a player health meter
• Tune the runnning-charge enemy attack

As part of doing the health meter I ended up learning about OpenGL scissoring, so I could ensure that if the window was resized you wouldn't be able to see outside the play area. I'm using the area outside to spawn in enemies now so I want them to move in across the edge.

There is still a lot of tuning and bug fixing on the core combat feel, without going into new features like a boss or combo attacks. The game really needs things like the latter to give the player interesting things over a longer time scale. I also don't have any text rendering (or texturing) capabilities right now. So the game's very bare-bones.

The territory was kind of a waste of time. I'd thought perhaps it could help serve as a place for the player to retreat to for a breather, or could give a medium-term goal of pushing the battle front to the right. But it doesn't really add anything in its current form.

I'll put the game up on Itch.io at the end of the day tomorrow for anyone who wants to try it out. I'm not sure if I'll enter it in the Roguelike challenge for judging; it really isn't a Roguelike in any meaningful sense. At least I've gotten a chance to work on some things I've wanted to flesh out for a while, and it forms a good basis for further experiments.

2018 7DRL: Day 5

Getting some basic combat in, finally. This is my daughter playing the game. It still needs tuning and so forth.

The green zone is friendly territory but it's not doing anything in this video.

2018 7DRL: Day4

It's looking increasingly unlikely that I'll have anything even remotely resembling a Roguelike by the end of this week. On the plus side I've got some cool crowd motion.

This morning was spent working on the enemy steering behavior so they would behave better in groups. It's all a bunch of damped spring type things that generate forces on the enemies. There is a force toward/away from the target; a much smaller lateral force to bring orbiting to a halt; and forces to repel enemies from each other. The neighbor repulsion force never has any component pointing toward the target, though. This keeps large groups from compressing in on the target, and reflects how people avoid each other; they mostly only pay attention to the people in front of them. Finally, the desired separation distance between neighbors is a function of distance from the target. This lets groups move close together to approach the target and then spread out when they reach combat range.

The afternoon was spent trying to improve the player control scheme, with only minor success. I tried a couple of schemes. One involved “dragging” the sword like a water-skier behind a boat. Another went for simple dual-stick control: one stick to move and another to swing the sword. I've always thought about trying this, so I'm glad I did, but it really doesn't work. It takes too long to move the right stick for the speed of gameplay I'm targeting, especially if you have to swing it through an arc.

In the end I settled on a couple of refinements to the prior scheme, which involves auto-targeting the nearest enemy and then swinging the sword into a forehand or backhand stance relative to that target. I've got some adjustments to help minimize rotation when switching targets; it will switch from a forehand stance to a backhand and vice versa.

Tomorrow I will work on enemy windups and attacks. With luck I'll have a simple combat game by the end. Maybe with a boss enemy who is bigger, more dangerous, etc.

7DRL 2018: Day 3

I ended up pushing through and keeping the Chipmunk physics engine in place. I'm glad I did. Once I'd managed to get back to where I had been in terms of the movement feel I was able to quickly get the sword contact working, which would have been quite a bit more work to do myself.

It took a couple of tries to figure out the best way to handle movement. The Chipmunk forums suggest tying the main physics body to a kinematic body via constraints, and then setting target velocities on the kinematic body. I found it was much easier to just use forces and torques. The things I'm doing aren't stiff enough to require anything more complicated. I ended up sub-stepping the physics sim anyway, to enable better sword collisions. It's running at 240 Hz right now. We'll see whether that holds up as I add more people.

I'm still behind where I wanted to be. It's not technically a game yet because you can't fail. It's starting to be a bit of a fun toy, though.

Tomorrow I'm going to turn this into a real game. The enemies will try to fight back. There will be more than one, which means I have to revisit the player control scheme. Right now the player character orients toward the closest enemy. Pressing the button swings the sword between forehand and backhand stances, but with the re-orientation to face new enemies that can do some weird things. It also doesn't really say what to do when there are no enemies around.

7DRL 2018: Day 2

It's been a dispiriting day.

My goal has been to start with basic movement and one-on-one combat and expand outward from there. By the end of Sunday I had a decent-feeling movement and sword-swinging action. I didn't have any collision between swords and people yet, though. The thought of doing that myself was somewhat daunting so I decided to bite the bullet and switch over to a 2D physics engine. I've used Chipmunk in the past so I went with that.

What followed was the usual wrestling with Git to get the project set up. Eventually I did, and converted things over. But I haven't been able to recreate the feel of what I had. In particular, the AI movement is really loose now.

I think it may be quicker ultimately to go back to doing things myself, implementing sword collision myself. I'm weighing it. I need to get on to group movement patterns and challenge gameplay.

7DRL 2018: Begin

Tap, tap. Is this thing on?

It's time to reanimate the blog for the annual Seven-day Roguelike Challenge. I've participated the last three years; you can find those games on Itch.io.

The 7DRL is always a high point of the year for me. I'm a professional big-budget game developer, and those types of games can take a long time to make. The last one I shipped came out in August 2014. It's refreshing to push a game all the way through to release on a regular basis. In addition I've helped out a bit with 7DRL judging, and it's really energizing to see the creativity everyone puts into their games.

This year I'm intending to make a game along the lines of Dynasty Warriors, albeit with very crude 2D graphics. Also I am not a Dynasty Warriors player, so I'm working mainly from second-hand descriptions. It should be great! If you're unfamiliar with the franchise, it's about a super-hero with a sword going up against vast armies of soldiers. The main franchise is set in the Three Kingdoms era of Chinese history; they've done spin-offs into European history, Gundam, Zelda, Dragon Warrior, other anime, etc. etc. It's a prolific line of games.

So far I have a simple framework set up on top of GLFW; it looks something like this:



The yellow circle is the player and the pinkish circles are enemies. You can move around with a game controller and the enemies move toward you.

Today's goal is to work out an acceptable one-on-one combat mechanic.

Large-Tile ThiefRL2

I'm starting the 2018 7DRL but I had a little bit of time before my official start so I added a feature request to ThiefRL 2. Pressing the number keys 1-4 will adjust the zoom level for the main tile display. This may help when playing the game on very large monitors.

Slight update to ThiefRL2

I had a little bit of time over the holidays so I fixed a couple of bugs in ThiefRL 2 that show up in rare circumstances.

When a guard was moving to the player's last known position, if the player moved into their path they'd move on top of the player. This has been fixed.

When there were windows adjacent to both sides of the corner of a room, the corner would not be visible from that room. I kind of hacked in the one-way visibility for the windows and it had some unintended side effects. I completely overhauled the visibility portal system which was incredibly boring but it now supports one-way portals, making the hacks unnecessary.

Guards now turn to face noises, which makes noises more risky than they were. Previously you pretty much had to just not make two noises in a row and you were fine.

Finally, I experimented with having guys face in the direction of their intended next move, instead of facing the direction of their last move. It looked weird though so I left it out.