Sunday, November 11, 2018

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:

Wednesday, April 25, 2018

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.

Thursday, April 12, 2018

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.

Tuesday, April 3, 2018

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.

Saturday, March 10, 2018

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.

Friday, March 9, 2018

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.