2021 7DRL: Begin

I'm participating in this year's Seven-day Roguelike Challenge after a couple of years away. It always seems like a bad time in terms of whatever is going on in my life, but participating in previous years has been really rewarding for me personally.

This year I am starting from my 2016 7DRL entry, ThiefRL2. It was a simple game of stealth. My main goals are to make something playable on the web, and to try to implement a disguise mechanic along the lines of the Hitman games.

For starters I have ported ThiefRL2 to Rust+Javascript, using WebAssembly. The port is mostly complete and playable here. I'll probably be rearranging that website as I figure out what I'm doing. The source code is on Github.

The main gameplay feature that isn't yet implemented in this port is that the guards don't hear each other shouting. Other features that aren't yet implemented are viewport resizing and scaling.

Otherwise it seems to work pretty well! I had originally done the port to Rust using a library called Quicksilver, but performance was not good and the library's creator ended up dropping it. I asked around on the roguelikedev reddit and somebody mentioned Dose Response, a Roguelike that Tomas Sedovic had created and then ported to Webassembly. The blog post linked above was really helpful for me. He started from an ultra-simple example by Richard Anaya. I started from the same point and was able to bootstrap my way up to a working framework. Fortunately my needs were really simple.

I ended up using WebGL for the rendering, which I'd never used before. WebGL hews very closely to OpenGL, for better and worse; in my case since I was already familiar with OpenGL it made things pretty easy to put together. Dose Response was using a memory buffer exposed from the WebAssembly module for collecting the tiles to be rendered. That is probably a faster method than what I'm doing, which is to collect the geometry on the Javascript side. As a result there's one call from the WebAssembly to Javascript per rendered quad. In practice that seems to work fine.

The current interface between the Javascript and the Rust is very narrow. Javascript calls a function to start the game, passing in a 64-bit random seed. It then calls a function each time a key is pressed, and another function when it wants the canvas drawn. Rust, in turn, calls a function for rendering an untextured quad; another function for rendering a textured quad; and a function to request that the canvas be redrawn. That's it!

The Javascript loads up the textures ahead of launching the webassembly; the Rust code just refers to them by index. The WebAssembly interface only handles basic integral and floating-point types; I had some issues trying to get the fancier wasm-bindgen stuff to work so I skipped that.

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.