Saturday, March 11, 2023

7DRL 2023: Lurk, Leap, Loot

Once again, I've participated in the Seven-Day Roguelike Challenge. My entry's called Lurk, Leap, Loot. It iterates on the stealth gameplay I've developed over previous 7DRL entries.


In the lead-up to the game jam I had several different game ideas from my notebook that I was developing. I came very close to doing a version of Paradroid, an old C64 game. But I changed my mind at the last minute and decided to return to stealth mechanics. When I mentioned this on the roguelikedev subreddit, Damien Moore contacted me asking if I'd like to collaborate. We made this game together and it turned out much better than I would have been able to do on my own. Damien created a new tile set and did the entire audio end of things. The game has music, sound effects, and voiced dialogue! Evan Moore (Damien's son) recorded the guard voices; it adds a lot of character to the game.

More importantly, he proved an invaluable design partner. One of the things he pushed for was for guards to move on predictable patrols rather than wandering semi-randomly. It took me about a day and a half to come up with a patrol route generation system, but I think it worked out pretty well.

A game ideally gets the player into a state where they are absorbed in anticipating and predicting what will happen, and then correcting based on their observations of how things actually play out. Ideally not only on a moment-to-moment level but also on longer time-frames. Patrol paths serve this purpose; players can watch, plan, and then try to execute their plan. It doesn't always go as expected, which is what keeps it interesting.

The patrol path generator shuffles a list of all the room adjacency pairs, then adds each pair if each room has zero or one edges already connected to it. This produces long chains and sometimes loops, with the occasional room that gets left out. To improve on this, I first chop up long chains into pieces to get down to a target length, and then insert side trips to the left-out rooms. The end result is that every room is on a single patrol path. Here's an example; I've hand-drawn over the patrol routes:


The lower left route is a loop; the rest are lines that the guards go back and forth along. Longer routes mean a lower overall guard density; this is from an earlier level in the game so the routes are allowed to be long. At the endpoints, the algorithm looks for a point of interest in the room for the guard to stand by for a few turns. Highest priority is windows: if there are any windows, the guard will stand looking out of one. Next highest priority is sitting in a chair, then standing near loot. As a final resort the guard will attempt to stand two spaces in from the door, which gives the player the opportunity to sneak into the room from behind them. This is important for some of the tiny dead-end rooms.

The other big design challenge I set myself was to try to move from the eight-way movement of ThiefRL2 to four-way movement. Skyrogue was an inspiration. Guards are still allowed to move diagonally if the space is clear on either side of the move. The player, instead, has a leap move. In my case it moves two spaces instead of one, and can go over some obstacles. The eight-way movement had given the player a speed advantage by allowing diagonal movement even if the spaces on either side were solid. This is similar to how in Pac-Man the player character can get around corners slightly more quickly than the ghosts. The leap move gives the player the advantage when moving in a straight line, which is a contrast to the corner-cutting.

Lastly, I ported in torches that can be lit or doused, from the very first ThiefRL game. I'd left it out of ThiefRL2 in the interests of simplicity, but it gives players a mechanism with a few tradeoffs. First, guards really want all the torches to be lit, so they'll interrupt their patrols to do that. This can be used to slow them down a bit if you need to do something elsewhere on their route. Standing in a lit room allows you to be seen from much farther away, so having torches unlit is good from that perspective. On the other hand, torches allow you to see which floor boards are creaky, so there's a slight reason for having them lit.

This is my first game made in TypeScript. Last year's 7DRL entry was written in JavaScript. In the leadup to this year's jam I ported it to TypeScript and then ported a bunch of my ThiefRL2 code from the C++ and Rust versions. It mostly went smoothly. The one gigantic gotcha in TypeScript/JavaScript is that any data type beyond a boolean or number will be passed around by reference instead of by value. I used 2-dimensional coordinates extensively throughout, and more than one time accidentally ended up pointing at a coordinate stored in something when I intended to copy it. It's ironic that scripting languages like Python or JavaScript try to insulate programmers from pointers, but then hit you with this. Languages that are clearer (like Rust) or simpler (like Haskell) avoid the problem.

I also used Parcel.js to run a server that automatically rebuilds whenever you save a source file. It worked great about 95% of the time, but whenever we did something like merge code in Git, it would break down. The fix appears to be clearing its .parcel-cache directory, and I got into the habit of doing that regularly. Feels kind of junky; you don't ever quite trust that you're seeing the version of the program that you just edited. I would make trivial changes in a place where it'd be immediately obvious if the program had updated.

We used Howler.js to play audio, although Damien did all the work of setting that up and using it. One thing we discovered while testing on various platforms is that Safari does not have built-in support for playing Ogg files. They aren't new so it's kind of annoying.

Overall I did not get anywhere close to the amount done on the fundamental game design as I would have wished. It still feels very much like the previous games in its series. On the final day I did a little bit of work to try to give the game an ending and a score, but it's very basic.

However, I'm happy with how it turned out. It's fairly polished and fun. The sound effects for player actions add a ton of great feedback; it's very satisfying to collect loot, based on the sound alone. (It's a bunch of Australian 50-cent pieces in a sock.)

Saturday, March 12, 2022

7DRL 2022: Complete


 

I'm excited to share my entry for this year's Seven-day Roguelike Challenge: Amulet Raider. It uses Rogue's setting (dungeon, amulet, potions, etc.) and XQuest's gameplay (fast mouse-controlled action). Here's a video of it in action:


The game is written entirely in JavaScript using WebGL shaders. It's by far the largest JavaScript program I've ever written. The code quality is not great; I was putting things in at a furious pace. JavaScript is not too bad for small things. I found myself increasingly relying on VSCode's syntax highlighting, which tries to show unused variables and function signatures. A lot of the bugs I had were the dumb variety (misspellings, calling functions with the wrong parameters). These are the things that type systems were created to catch. Perhaps next time I will try TypeScript. The edit/test cycle was really fast for this though. It made the shader programming in particular really fun.

Wednesday, March 9, 2022

2022 7DRL: Midpoint

It's that time of year again! Time to wake up the blog for the annual Seven-day Roguelike Challenge. This year I tried to do some planning ahead of time but I haven't really gone with any of my plans, specifically.

My first idea was one I've had in my list for a long time, which is to try to do a Roguelike homage to the (recently Hugo-award-winning) Murderbot novella series by Martha Wells. Murderbot mostly does computer hacking in a fairly hand-wavy way, fighting in a slightly less hand-wavy way, and watching telenovelas in a completely hand-wavy way. So I thought it'd be interesting to try to come up with ways to see sections of the level through security cameras, alter what enemies see through those cameras, and other hackery things. Ideally I wanted the game to keep to the Roguelike ideal of slightly more than one keystroke per turn, though, and I've had trouble thinking of how that should work, exactly. Oh, and also there was a 7DRL entry last year based on Murderbot! I had a bit of fun playing it.

My second idea had been to do a riff on Meritous, a somewhat monotonous action Roguelike with a one-button combat mechanic. I like its stripped-down mechanics but I have only been able to complete a game a couple of times. The map has thousands of nearly-identical rooms and a handful of slightly more interesting bosses.

The third idea, which I ended up going with, is to mash up Rogue and XQuest. (XQuest itself is based on Crystal Quest, an old Macintosh game). {X/Crystal} Quest has a novel mouse-based movement system; moving the mouse changes the player character's velocity directly. Firing is in the direction the player is moving, as a multiple of the player's speed. It can be a bit squirrelly to learn but it has a high skill ceiling. I spent countless hours playing XQuest and XQuest2 back in the day. Here's some example video of it:


Work's been going OK. The in-development version can be played here and the source is on Github. I'll put the final version on Itch.io. You will need a good mouse; I'll add sensitivity options before I'm done but it's hard-coded for now. You will probably a decent video card to play; it uses WebGL but I'm  not pushing crazy amounts of data at it. Also, Firefox seems to be really slow as compared to Chrome, Edge, or Safari. I use Firefox for my day-to-day browsing but I must be doing something in my games that doesn't sit quite right with it.

I started from a very simple JavaScript game that I'd made to demonstrate the fast marching method. So far I have a rudimentary dungeon generator and some turret enemies. For the player character I have movement, shooting, and the beginnings of melee behavior. Today's work will be developing a melee enemy and hopefully getting the melee to a point that feels right.

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: