Saturday, March 13, 2021

2021 7DRL: Finished

 Here is the 7DRL submission on Itch.io. Here is the latest version on Github.io.

Long ago I spent a miserable year in graduate school. The research assistant job I had before I dropped out was in the cancer wing of the university's hospital. The radiation treatment facilities were adjacent and I'd gotten a tour of them when I started my job. It was a row of rooms with twisty entrance passages to break the lines of fire.

My parents came to visit me shortly after I had dropped out. I took them to see where I had been working. It was a Sunday and the radiation wing was largely deserted. Eventually, though, we were confronted by a woman who said "I don't think you should be in here!" and threatened to summon security. I hustled on out of there, chagrined. It really drove home that I no longer belonged at the school.

This feeling of being accosted where you don't belong was what I had in mind for this year's 7DRL challenge. I played the HITMAN reboot games recently and enjoyed the disguise mechanics. My primary goals for this year were:

  1. Produce a web-playable game
  2. Experiment with disguises in the framework of my existing thief roguelike game

Getting a web-playable game took about half the time. I was using languages, platforms, etc. that I haven't really worked with before. Working on the disguise mechanics took the other half. I don't know that I've succeeded in making a really fun disguise system yet, but there is a fair amount that went into it.

All the new tech:

Rust is not bad. I'm not sure yet if it's where I want to write all my code going forward, but it isn't bad. The compiler gives good error messages, and the game seemed to perform adequately. I didn't do any profiling. I did run into one crazy problem with the compiler; it doesn't properly handle excluding library features on a per-platform basis. I asked on a forum and the nightly build has a fix for it. In the end I just targeted WebAssembly alone; I haven't got a native target. My framework is simple enough that I expect I could write a Win32 version of it fairly easily in Rust.

WebAssembly still feels half-baked. I had trouble with wasm-bindgen versioning, so I ended up just wiring up the imports and exports myself. I stuck to simple integral data types in the function parameters and didn't try to do any memory sharing.

Javascript is also not bad. It always seems to work pretty much the way I expect it to. I only wrote around 450 lines of Javascript for this project.

WebGL is very similar to OpenGL. It works okay. I'm not a huge fan of the OpenGL way of doing things, but I am familiar with it so that helped.

Github.io was new to me. It turns out to be a really great way to set up a static website. Just point a Git repo at it and away you go. I'm told you can set up Github actions to automatically build the site when a repo over on Github changes. I'll probably try to set that up; I ended up manually doing that step and it was getting annoying.

The new game design elements:

Since the player's thief can look like the enemies I added a little overhead caret to mark him. I added bump-to-interact functionality (for changing clothes) which wasn't in the previous game. (It was in the first ThiefRL so I referred back to that.)

I created two different colors of guards, in order to have two different disguises (plus your default outfit). I set it up so one class of people is not allowed in the private rooms of the house; if the private-wing denizens see that outfit they'll attack. The public area is patrolled by both the public and the private guards. I'm not thrilled with how this turned out; bifurcating these already-small levels results in more un-patrolled space, since guards try not to go into a room where they will have to go back out via the same door. I have thought about changing the patrolling behavior to allow for going into dead ends; maybe they would stop and stand for a bit. Haven't gotten to that yet though.

Guard awareness got some adjustments. Since you are in disguise they can't just attack you, which means you can be doing things in their view like picking up loot or climbing on tables and that looks weird. When the player does anything "suspicious" it sets a flag for the next guard update. If they see the player, and the player is being "suspicious" then they escalate. In the old thief game if you got spotted you could duck into a bush or under a table in full view of the guard and hide successfully. This is no longer possible. I felt like I needed to nerf hiding somewhat to make the disguises serve more of a purpose.

Once I hit on the idea that disguises would effectively cut guards' maximum distance they can see you at down to one or two squares it was pretty fun to try to maneuver around them in the rooms to avoid being too close. Right at the end I realized that the inner-room disguise was strictly better than the outer-room disguise, which was not very fun. I ended up making it so that people who match the disguise are not as suspicious as people who don't. It doesn't make a lot of sense logically, but it means you want to be wearing the outfit that matches the area you're in (and the people who are in it) which gives a reason to switch back and forth. It's still not much of a reason.

I experimented with having special "boss" guards who could see through disguises from a distance. This was an idea borrowed from Hitman. It complicated things too much, I felt, so I removed it.

For a while I disallowed hiding in bushes or under tables (or underwater) while in disguise. This is potentially interesting; it gives much more of a mode shift between running around in the thief outfit and wearing a disguise. It means the thief outfit has its own perks and isn't strictly inferior to the disguises. I took it out because I felt like it was complicating the rules. It also made for some really difficult maneuvering sometimes in the current levels. It's worth further consideration though.

I made the one-way windows so the player can see through them both ways. I'd tried this out on the original thief game and rejected it because I didn't want players to feel like they had to run around the house to peek in all the windows and uncover as much of the map as possible before going in. However I think this is a really positive change. One of my big design tenets is that you should have areas you can see but not get to easily and this serves that goal handily. Often you'll go past a window and see a disguise in the room on the other side and it gives you a goal to work toward.

Placing the disguises so it will be satisfying to find them is something I haven't really fully worked out. Right now they're placed toward the back of their respective zones, so you will have to move through at least some of the zone without the benefit of its disguise. I really would like there to be more of a sense of accomplishing something when you get to a disguise, though.

Overall it was not my strongest game but it should hopefully be at least somewhat fun. Disguises make things easier, and they give you more detailed interactions with guards. Both of these present challenges to keeping the game fun. I think there are lots more things that could be done with disguises though. A couple ideas I wanted to try:

  • Identify a particular guard who is a secret ally. To do this you need to see the faces of guards from close range; they'll get marked off as they're identified as either your ally or not.
  • Confront a particular person when none of the other guards are nearby.
  • Disguises that provide environmental protection (from cold, or dust storms, say)
  • Ways to influence the patrolling behaviors of guards. Could be by activating "activity stations" that will occupy a guard for a time (cleaning up a mess or something). Or it could be by opening and closing doors, and guards would assume that closed rooms (that aren't on the main path) don't have to be checked but open rooms should be checked.
  • Add stationary guards; "bouncers" to make it much harder to get into parts of a level without the right disguise.

Thursday, March 11, 2021

2021 7DRL: Continued

The work-in-progress is playable here. It is basically the thief game with a disguise added. (The port of the old game, for comparison, is playable from here.)

If you find the outfit (generally in a dead-end room in the tiled part of the house) you can swap clothes. Guards don't see through the disguise unless you are very close. If they are suspicious you can move away and keep things from escalating.

I tried having one guard who was specially marked and could see through the disguise but that was not adding much. I'm trying making it so when wearing the disguise you can't hide under tables or in bushes. That seems promising. I'll probably also make it so you can't steal things while seen without raising suspicion.

I've also managed to fix a few bugs along the way. The most long-standing one, dating back to the original game, was that guards who couldn't move would spin in place. This was just due to how it updated their facing when the movement vector was zero.

I'm currently working on having three different sets of people, with distinct disguises that work for each. It will be interesting to see if this adds. The people will occupy different (possibly overlapping) parts of the house and will only see through the disguise that matches their own outfit. This might be too easy; I don't know.

Tuesday, March 9, 2021

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.

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.