StarWright 0.5.0 - Sounds!

I'm a bit ashamed to say this, but until today no version of StarWright has ever had even a single sound effect. Well it took me a lot longer than I anticipated, but sounds are finally here! (Or should I say hear?) I just released StarWright 0.5.0 which you can download, play, and hear right now!

I had told myself for the longest time that sounds were a lower priority than getting in core gameplay features. I guess that might be true to an extent, but now that I'm playing the game with sounds, I'm really regretting not adding audio months ago, because the game feels much better with sound effects. (And also some accompanying screen-shake effects, which really help to give the sounds some added punch.)

Sound Design

Sounds in StarWright can be grouped broadly into two categories: User interface sounds and gameplay sounds. User interface sounds are easy because they never vary in volume or pitch and always get played whenever the user interacts with the interface. Gameplay sounds on the other hand are much trickier to design and implement because whether they're played, their volume, and sometimes even their pitch depend on what's happening in the gameplay.

Designing gameplay sounds for any game is hard, but StarWright has proven to be by far the hardest sound design challenge I've yet tackled. There are two primary reasons for this challenge:

First, unlike most games where the area that the player can see is relatively constant, in StarWright the scale of the player's view can change dramatically as the player zooms in and out; the player's view can scale from a dozen meters across to a kilometer across or more in a second. What the player hears when zoomed in at 10 meters (the loading of ammo and beeps of controls and charging of lasers) is not what the player should hear at 100 meters (the muted, distant reverb of cannons and thrusters) nor what the player should hear at 1000 meters (the almost-empty yet strangely-beautiful resonance of space).

Many of the more-detailed gameplay sounds (such as beeping controls, loading ammo, and charging weapons) are only audible when zoomed-in near the 10-meter scale; they quickly fade out as the player zooms away. But the louder sounds (such as firing cannons, projectile impacts, and explosions) can be hard at the 100-meter scale as well. However, I wanted these louder sounds to sound more muted and distant when the player is zoomed out, and so each of these sounds is actually authored as two separate sounds; one containing higher-frequency elements that fade out quickly as the player zooms out, and one containing lower-frequency elements that fade out much more slowly. Eventually though, near the 1000-meter scale, no gameplay sounds are audible and the only sound left is the eerie sound of space itself. (Yes, I know space IRL has no sound, but in StarWright it does!)

Sounds don't just fade out as the player zooms out; they also fade out as their point-of-origin moves farther away from the center of the player's view. This works like most games in that more distant sounds are quieter (an enemy shooting you from ten meters away is a lot louder than one shooting at you from a hundred), with the added wrinkle that the distance that a sound can travel increases as the player zooms out the camera. This may seem unnatural, but if the distance didn't scale then the player would either (when zoomed in) be able to hear loudly a lot of sounds from objects they can't see or (when zoomed out) not hear sounds from objects that they can see.

The effect of fading sounds as the player zooms out while simultaneously increasing their audible distance leads to a nice "level of detail" -- that is, when zoomed in, the player hears a relatively small number of higher-pitched, high-details sounds; whereas when zoomed out, the player hears a large number of more muted, less-detailed sounds.

The other big challenge to designing sounds for StarWright is the sheer number of objects that can make sounds. While a typical side-scroller or action game might have a few dozen sound-emitting objects (on screen or near the player) at once, StarWright can have hundreds or even thousands since every weapon, thruster, projectile, explosion, and crew member could be making a sound. And the problem with so many sounds at once (aside from being computationally expensive) is that when they all combine together, too many sounds will start to be like gray noise and the individual details will get lost in the chaos; that's neither pleasant to listen to nor useful information for the player.

My solution is conceptually simple enough: limit the number of gameplay sounds of any single type that can be played at once; the theory being that there should be enough simultaneous sounds that the player won't notice when some don't play while also not having so many sounds that they just create unrecognizable noise.

Gameplay sounds in StarWright can be subdivided into two general groups: One-shot sounds and continuous sounds. One-shot sounds are those that are tied to a particular event happening in the game (such as a cannon firing or a battery being delivered) and are over within a few seconds. Continuous sounds loop indefinitely for as long as some state is true (such as while the control room is powered). The ways in which each of these two groups of sounds is limited differs significantly:

For one-shot sounds, there is a simple limit to the number of sounds of any particular type (such as the sound of the regular cannon firing) that can be played simultaneously. (Usually around 3-5 simultaneous sounds, which seems to be about the point at which players will stop noticing when some don't play.) When a one-shot sound is about to be played, the game checks how many other sounds of the same type are playing, and if the maximum number is already reached, it simply doesn't play the sound.

Continuous sounds are a bit more complicated. Any particular type of continuous sound is typically limited to only 1 playing at once. But unlike one-shot sounds, once the limit is reached, any additional continuous sounds will increase the volume of the currently-playing sound. For example, two thruster rumble sounds playing at 0.5 volume will get combined into one thruster rumble sound playing at 1.0 volume.

Sound Implementation

One of the biggest reasons that it took me so long to release 0.5.0 is that I almost completely rewrote my audio-playing code.

StarWright is based on the same codebase that I originally created for my game Tanky-Tank almost a decade ago. At the time, the best API for playing sounds on Windows was DirectSound. However, in the many years since, DirectSound has been obsoleted by the much-more-modern and well-maintained XAudio2 (and on newer systems, DirectSound is actually emulated on top of XAudio2).

When I started working on sounds for StarWright, I started with my old DirectSound-based code, but I quickly ran into some nasty race conditions that would cause crashes in the above-discussed sound-limiting code. These race conditions were going to be very difficult if not impossible to work around, and so I chose to spend a few days rewriting all of my audio code to use XAudio2 instead of DirectSound.

This rewrite went relatively smoothly, except that I found a few bugs in SharpDX, the C#-language DirectX wrapper I use. I spent at least a day tracking down and then fixing those bugs in SharpDX. (But on the bright side, I had my first-ever GitHub pull request accepted to fix those bugs!)

Screen Shake!

The greatest lesson I've learned in my years as a game developer is that every game is made better by adding screen shake!

While this may be a bit of an exaggeration, it's true enough for StarWright.

You may notice while playing that a lot of explosions and firing sounds are accompanied by a subtle (or not-so-subtle) screen shake effect. They started as kind of a silly experiment but they really added a great sense of weight and power to the louder, more explosion-y sounds. When you get hit by a Large Cannon, it feels quite impactful, and a lot of that has to do with the accompanying screen shake.

Screen shakes work a lot like sounds in the sense that they get weaker as the player zooms out or as the origin gets farther from the center of the screen. (And yes, that distance-to-center is scaled by the zoom, just like sounds.) But unlike sounds, there is only one type of screen shake, and so the magnitudes of all the currently-in-effect screen shakes get added together to determine the final amount by which the screen is actually shaking.

Procedurally Generated Starships in StarWright

I've been working on the main singleplayer (& co-op) "explorable universe" mode for StarWright. This mode is still a ways off, but in the meantime I'd like to share something with you that I think is pretty neat: the "random starship generator" that the singleplayer mode will use to generate an unlimited variety of enemy starships for you to fight. (You can play with these procedurally-generated starships in the "sandbox" mode of the latest version of StarWright.)

Here's a screenshot of just one of the practically-unlimited number of starships that the game can generate:

This is a fully-functional and heavily-armed starship, complete with thrusters, weapons, a cockpit, a reactor, ammo storage, power storage, and crew's quarters.

On the left you can see (click on the screenshot to get a bigger view) a user interface that gives a great amount of power and control over the underlying algorithm that generates the starships. I've included it in these screenshots to help you understand the underlying algorithm.

At a high level, the algorithm works by creating a starship in "stages", which you can see listed on the left with names like "Shape", "Fill Gaps", and "Cockpit". The algorithm starts at the top of the list and processes each stage in sequence. Each stage adds to what was generated by the previous stages, except for of course the first stage which starts from scratch.

Let's walk through each stage in sequence so we can see how the ship gets created stage-by-stage:

Stage 1: "Shape"

In the above screenshot, I've turned off all of the stages except for the very first: the "Shape" stage. On the right you see what the ship looks like (in this case a rough outline of a ship composed entirely of empty "corridor" tiles), and on the left you can see that I've expanded the user interface for this "Shape" stage to give a better view of the inner-workings of this stage.

The sole purpose of this stage is to give a rough outline to the general shape of the ship. Most subsequent stages will obey the shape given by this stage and only place additional parts ("part" being my technical term for discrete rooms, systems, and corridor/armor tiles) within this outline.

The "Shape" stage is actually unlike all the later stages in that it itself is comprised of some number of "shape modules". You can almost think of a shape module as a "brush" from a paint program such as Photoshop in that it defines a "shape" of 1x1 corridor tiles to add to the ship. The two shape modules you can see here are "CircleModule" (which places a blocky circle-like shape of tiles) and "RectangleModule" (which places a rectangular area of tiles).

The "Shape" stage adds somewhere between "MinModules" and "MaxModules" number of random modules (in this case it's always 8 modules), where the chance of any given module being added is determined by its "RandomWeight". Once the modules are chosen, the stage then joins them together in a random configuration and "paints" the resulting shape as corridor tiles.

Stage 2: "Fill Gaps"

Notice that the result of the first stage left some small gaps and rough edges in the ship. The purpose of this second stage is to fill in those gaps and "even out" the rough edges to give the ship a more solid appearance. While the desire to have ships appear more solid is largely an aesthetic preference (it's perfectly legal to have a ship with holes in it), it does make it easier for the later stages to place new rooms and systems inside the ship. For other styles of ships I may choose to leave out this stage entirely, or even replace it with a stage that carves away bits of the ship in order to make it appear more "stick-like".

The actual logic behind this stage is pretty simple: It simply looks at each empty tile, checks to see if it's surrounded on 2 or more sides by tiles no more than "ScanRange" units away, and if so, fills that empty tile in with another corridor tile. Then it repeats itself (up to "Iterations" number of times) to fill in any more tiles that are newly-eligible to be filled.

Stages 3 & 4: "Cockpit" and "Reactor"

The two most important rooms/systems on any starship are the cockpit and the reactor, so we add those before we add any others. While both the cockpit and the reactor have their own stages, the actual logic of the stages are very similar, so I'll talk about them both at once.

Each of these stages works by iterating through every possible location for the cockpit or reactor and picking the single "best" location for it.

The only difference between the Cockpit and the Reactor stages are in how they define "best". You can see in the user interface that each stage defines a "PlacementStrategy" that is used to determine the best location.

The cockpit uses a "Protected" placement strategy, which simply means that the "best" location for the cockpit is the one that is farthest from the perimeter of the ship. This makes sense since the actual location of the cockpit doesn't affect how well the ship functions, and so we just want to place it in the most difficult-to-destroy location possible.

The reactor uses a "Centralized" placement strategy, which simply means that the reactor will be placed as close to the ship's center of mass as possible. This makes sense since the reactor is most effective when it's in a relatively central and accessible location.

As you can see here, the "best" locations for the cockpit and reactor are often very close or even overlapping. In that case, the cockpit's location preference gets priority simply by virtue of being before the reactor in the list of stages. This explains why the reactor in the above screenshot is somewhat offset from the ship's actual center of mass -- the reactor couldn't be placed in the ideal location because the cockpit was already there, and so it picked the next-best location.

Stages 5 & 6: "Cockpit Armor" and "Reactor Armor":

Since the cockpit and reactor are so important, its usually a good idea to surround them with added protection in the form of armor tiles. These two stages do just that by each finding a part of a specific type and then surrounding that part with one or more layers of armor tiles.

But as you can see in the above screenshot, these stages will usually leave gaps and paths around the parts that they are protecting so that access by the crew to any room or section of the ship isn't cut off. The logic that handles this is crucial to how this and almost every other stage works, so let's talk about...

Path Contiguity Checking

Before any stage picks a location for a new part, it first does what I call a "path contiguity check", which essentially asks the question, "If I place a part here, will I be forcing crew to go too far out of their way to get around me?"

To perform this check, the stage picks any open tile adjacent to the proposed location, and does a quick Dijkstra search to each of the other adjacent tiles. As long as the search finds a path to each other tile no longer than, for example, 5 tiles, then the path contiguity check it considered a success and the part is allowed to be placed there. But if the path fails, then adding a new part to that location would either force the crew to go too far out of their way or would cut off a path entirely, and so the stage will exclude that possible location when deciding where a new part should go.

We can see the practical implications of this check in the above screenshot for stages 5 & 6. Look at, for example, the gap in the armor directly underneath the cockpit where the cockpit's door is located. The "Cockpit Armor" stage didn't place an armor tile there because doing so would have cut off access from the surrounding corridor tiles to the cockpit itself. And the corridor running between the cockpit and the reactor exists because adding an armor tile there would have forced crew to walk all the way around both the cockpit and the reactor to get to the other side.

Stage 7: "Thrusters"

After the Cockpit and Reactor are placed, along with their surrounding armor, the thrusters are placed. There are three sizes of thrusters (small, medium, and big), and this stage is responsible for placing all three.

If you take a look at the U.I. for this stage above, you can see that each size of thruster has a different "score" (1 for small, 2 for medium, and 4 for large), and the stage as a whole can place between 35-45 points worth of thrusters. In addition each size of thruster has a different random "weight", meaning that about 1/6 of the thrusters will be small, 2/6 will be medium, and 3/6 will be large.

The directions of the thrusters are also weighted randomly, so that 5/8 are placed pointing backwards and 1/8 are pointing in each of the other three directions.

Aside from those random weights, there is currently no additional logic (besides randomness) to determine where the thrusters are placed. Even so, randomly-generated ships usually have reasonably well-balanced thruster placements simply by virtue of random probabilities.

Stage 8: "Weapons"

The placement of weapons works almost identically to the placement of thrusters, but with different sizes, scores, and random distributions. (In this case, there are only two sizes of weapons, and their rotations are distributed more evenly around the ship while still favoring weapons that face forward.)

The one algorithmic difference between thrusters and weapons is that, when choosing a location for a weapon, the algorithm will choose the location that is farthest away from the center of the ship in the direction that the weapon is facing.

Stage 9: "Exterior Armor"

Once all the exterior systems (weapons and armor) are placed, a single layer of armor is placed around the perimeter of the ship on any tiles that are already occupied by a weapon or thruster, so long as placing an armor tile there will not block and crew paths according to the above "Path Contiguity Checking" algorithm.

Stages 10 & 11: "Ammo Supplies" and "Power Storage"

Next, Ammo Supply and Power Storage parts are placed. In this case, between 2-3 ammo supplies and 1-2 power supplies are added to the ship.

The algorithm that places these parts attempts to place them in locations that are nearby as many ammo-consuming or power-consuming parts as possible. In the case of ammo supplies, the algorithm will attempt to place them near as many weapons as possible, so long as those weapons aren't already near other ammo supplies. And in the case of power supplies, it places them near thrusters and ammo supplies (which use power to create ammo), so long as those thrusters and ammo supplies aren't near other power supplies or the reactor.

Stage 12: "Crew"

Finally, crew's quarters and bunk rooms are placed in the remaining empty areas. Their placement is completely random, except that the algorithm tries to line up the edges of the rooms if possible, which tends to cause crew's quarters and bunks to be placed adjacent to each other.

Stage 13: "Fill With Armor"

Once all of the crucial rooms and systems have been placed, the almost-final step is to fill any remaining space with armor tiles, because having armor throughout a ship makes it generally harder to destroy.

In order accomplish this, every single empty tile is scanned using the above "Path Contiguity Checking" algorithm to determine whether placing armor there will block any crew paths. If no crew paths will be blocked, then an armor tile is placed.

The neat side-effect of placing armor in this way is that corridors, like the ones you see above, are naturally "created" as a simple by-product not placing armor in locations that would block crew paths!

Stage 14: "Add Extra Doors"

The one final-final step is to place any extra doors in locations that would make crew access significantly more convenient. This is accomplished by scanning every wall location where a door could be placed (but isn't already there) and doing a path search from one side of the wall to the other. If the resulting path is over a certain distance (in this case 10 tiles), then a door is placed to make the path shorter.

In the above screenshot, I can only spot one additional door that was added -- in this case, on the right side of the medium-sized thruster on the bottom of the ship.

Threesus!

A couple months back I wrote an "A.I" computer program that knows how to play the brilliant iOS/Android game Threes -- and play it much better than most humans can! While I was happy with the quality of the A.I., the problem was that it used a text-based interface in which a human had to type in the state of the board, wait for a couple seconds for the A.I. to think, and then swipe in the direction that the A.I. tells the human to swipe. Repeat hundreds of times, and the process of playing even a single game can take several hours. It was incredibly tedious, and I myself only had the patience to play a couple of games with the A.I., getting a high score of 178,926.

Then, yesterday, Matthew Wegner debuted live on twitch a real, working robot that plays Threes on a real iPad. In no way has the actual game of Threes on the iPad been hacked, and the A.I. has no information that a human doesn't have or couldn't keep track of. Already, this robot, dubbed Threesus by the Twitch chat room, has achieved a whopping high score of 248,403 -- and I'm confident that it can score much, much higher than that!

The underlying A.I. logic code of Matthew's robot is based on my original A.I. code. This morning, in an effort to encourage collaboration and to create the best Threes-playing robot possible, I released the source code for the A.I. logic on Github. If you're interested in improving Threesus, then please check it out!

The rest of this post will talk about how the A.I. actually "thinks" and chooses what move to make next. I'll try to keep it high-level so that non-coders can understand, but if you're a programmer then I encourage you to take a look at the actual source code.

First of all, you should understand how Threes works under the hood -- specifically, how the game chooses what cards to add to the board and where. The best description I know of (and the one I used while writing Threesus) is this writeup on the Touch Arcade forum. Knowing how the game works under the hood isn't just useful for understanding the A.I. -- it will make you a better player too!

Fundamentally, Threesus works by looking 6 moves ahead into the future and then evaluating the potential future game board to determine its "quality". (I'll get to what "quality" means in a bit.) It does this look-ahead for every possible move in addition to many of the possible locations and new values of cards that might be added to the game board. Multiply all of these possibilities together, and Threesus will often examine millions of possible game states to decide just a single swipe. Once Threesus has calculated the quality of all of those game states, it simply swipes in the direction that is most likely to produce the highest-quality game state. (For you game-theory types, this is basically the expectimax algorithm.)

In addition to examining every possible move, Threesus also "counts cards" to determine the probabilities of what value a new card might be, just like how a blackjack player can count cards to beat a casino. Threesus knows that the game starts with a deck of 12 cards (4 ones, 4 twos, and 4 threes) and draws cards from the deck until the deck is empty, at which point the deck is re-created and re-shuffled with another 12 cards. So as the number of cards in the deck decreases, Threesus can better predict, often with very high accuracy, what new cards will be well into the future. This is why sometimes Threesus seems to know the future!

So how is the "quality" of a future game state calculated? Well, the naive way to evaluate the quality of the board is to simply count up the number of points on the board and try to maximize that. This works okay (in my tests it can score a little over 30,000 points on average), but it's actually far from the best way to evaluate a potential board. The problem with evaluating a board using only its score is that then Threesus will always be optimizing the game assuming that it will end in 6 turns, which is usually not the case!

A much better way to evaluate the quality of a future game board is to calculate a quality number that represents how much longevity a board has -- that is, for how much longer Threesus is likely to be able to play the game (after the six-move look-ahead) before finally losing.

Currently, Threesus attempts to calculate the longevity of a board using a fairly simple scoring calculation. The scoring calculation used in yesterday's live streams worked like this:

• Every empty space is worth 2 points.
• Every matching pair of adjacent cards is worth 2 points.
• A card next to another card twice its value is worth 1 point.
• A card trapped between two other cards of higher value, or between a wall and a card of higher value, is penalized 1 point.

That's it! This simple calculation was able to achieve a high score of 248,403, without ever actually trying to directly increase its score! And so if there's a single lesson to be learned from Threesus that you can apply yourself as you play Threes, it's this: Be patient. Don't play to increase your score; play to keep playing.

Running Threesus for 100 simulated games, here are the results it achieved:

100 games completed!
Total time: 02:13:08.2477053
Low Score: 10041
Median Score: 88653
High Score: 774996
% of games with at least a 384: 100%
% of games with at least a 768: 98%
% of games with at least a 1536: 92%
% of games with at least a 3072: 27%
% of games with at least a 6144: 3%

Since yesterday, Matthew has been working on tweaking the above scoring calculation, and already he's made significant improvements. Besides tweaking some of the point scores (including increasing the trapped penalty to 5), he also added bonus points if the highest-numbered card is on an edge or in a corner. With these improvements, Threesus is even better:

100 games completed!
Total time: 03:03:22.0262799
Low Score: 30126
Median Score: 89436
High Score: 717960
% of games with at least a 384: 100%
% of games with at least a 768: 100%
% of games with at least a 1536: 94%
% of games with at least a 3072: 41%
% of games with at least a 6144: 1%

(Don't read too much into the decrease in % of 6144. The difference between 1 game and 3 games is statistically insignificant.)

So in a nutshell, that's how Threesus works! But there's still a lot of room for improvement. Some ideas that come to mind are or have been suggested to me are:

• More refinements and testing of the board evaluator.
• Better handling of the end-game -- right now Threesus doesn't realize when he's almost certainly going to lose, and so he doesn't do anything to maximize score.
• Rewrite code in C or C++. The C# code that exists right now is very well optimized for C# code, but I think C or C++ could potentially be an order of magnitude faster, which should allow Threesus to look at least one more move ahead into the future in the same amount of time.
• Using a Monte Carlo algorithm to look ahead further without exploding computation times.
• Using a traditional reinforcement-learning method such as Q-Learning.

So please, if you think you can make Threesus even better, download the source code now!

StarWright - Doors, Doors, Doors

Recently I finished an artistic revamp to StarWright's visuals. One of the most important improvements is the addition of a separate layer of walls that is rendered above the crew on the ship. This gave the feeling of actually viewing a cross-sectional floor plan of the ship, which was sorely missing in earlier versions. But the one big oddity with that revamp was that the crew could still walk between the walls, which was definitely weird.

Now, finally, ships in StarWright have walls that crew can't move through, and of course by necessity, doors in the walls!

The player may place those white double-sliding doors in any legal wall locations (some are blocked). Once a wall has a door in it, crew may freely move through the wall. As in a lot of space fiction (Star Trek in particular), when a crew member walks up to a door, the door will automatically slide open to let them through.

From a technical standpoint, implementing doors and walls was much trickier than you might initially suspect, for a handful of reasons:

• The pathfinding system was previously unaware of the presence of walls between rooms, and making it "wall-aware" required a significant retrofit.
• The pathfinding system previously assumed that the entire ship was contiguous -- that is, it assumed that it was possible to get from any location of the ship to any other location of the ship. Additional fixes were required to remove this assumption.
• I didn't want to have to update every wall sprite with every possible door location, because that would have added many times as many wall sprites. Instead, I had to devise a way for the doors to "replace" the particular section of wall that they occupy, but no other parts of the wall. To do this, I render a rectangle representing the door sprites to a special off-screen "stencil" buffer. Then when I render the walls themselves, ever pixel of the wall gets checked against that stencil buffer to make sure there's no door at that pixel.
• Every door sprite has animations to open and close as crew walk through. Unfortunately, doing potentially hundreds of simultaneous sprite animations on the CPU can be slow, so instead I devised a special vertex shader to handle the sprite animation on the GPU. When an animation is triggered, such as the door is opened or closed, the CPU sends the vertex shader the information it needs to render the door animation, and then the CPU never has to worry about the animation again until a new animation is triggered.

Garbage Collection

Programmers who are opposed to garbage collection because manual memory management is easy completely miss the point of GC.

Regardless of whether manual memory management is easy (if you're experienced then it's mostly routine), the greatest strength of GC is not that it makes memory management a bit easier (true in most cases, but non-deterministic deallocation can occasionally complicate things), or even that it's safer and more secure (almost always true), but that it eliminates the need to track which object is responsible for deallocating another object, thus greatly simplifying program structure, increasing brevity of code, and enabling a handful of language features like closures, asynchronous methods, LINQ (C#), etc... that would be much more awkward if not impossible to use.

In short, GC enables programming languages to be more expressive and concise, and the code written in them to be cleaner and simpler, thus greatly improving flexibility, understandability, and maintainability of code. Whether that's worth the tradeoff of reduced performance and occasional added complexity is a matter of application domain and personal preference.

StarWright - Multiplayer! (and saved games too!)

WOW, it has been a very long time since I last posted about StarWright! To a great extent my new job has been keeping me quite busy, but also I've been working on the biggest new feature yet...

Multiplayer.

Adding multiplayer play to StarWright has been a huge task, as anyone who has ever added multiplayer networking to a previously-singleplayer game can tell you. Every core mechanic of the game, from damage and destruction to crew pathfinding to command and control, had to be overhauled to be multiplayer-capable. Add to this the creation of a custom UDP communications protocol and a programming library for "remote procedure call", both of which are critical to the multiplayer capabilities of StarWright.

To make matters even more difficult, my belief is that ever single mode of play in StarWright should be multiplayer-capable. That even includes the sandbox mode, which is the only real way to play the game right now. Making the sandbox multiplayer-capable as well meant that all the systems related to designing ships, such as adding and removing ships, adding and removing parts, and undo/redo, had to work over the network as well.

Oh yeah, I also want other players to be able to drop in and out of the game whenever they want. No pre-game lobbies, except for certain kinds of competitive matches. The host just starts a game, checks a box allowing other players to join, and then other players can hop right in. This means that the host computer must be able to send the entire current state of the game whenever a new player joins, which is its own big system unto itself.

On the bright side, sending the state of the game to another player essentially amounts to creating a save file of the game and sending it to the other player. So even though drop-in-anytime was a big feature to implement, I basically got a save-game feature almost for free. The code that handles networked state sending is about 95% shared with the code that handles game saving, even though networked state sending and game saving write the data to different formats (networked state sending uses a compact binary format to reduce bandwidth usage, while game saving uses a custom text format which is more tolerant of game version changes). This is thanks to a robust multi-format serialization library that I developed for my game engine, Halfling.

The Conservative<->Liberal Programming Spectrum

Well-known programming blogger Steve Yegge just posted a long but interesting article about the spectrum of programming philosophies ranging from "conservative" to "liberal". Conservative programmers are typically risk/change-averse (often for good reason) and very performance-conscious, while liberal programmers typically favor flexible systems, concise/elegant expressions, and rapid iteration.

I'm definitely a "liberal" programmer (I don't think anyone would ever call me a risk-averse programmer), but I do favor some traditionally-conservative programming practices, though for decidedly liberal reasons. For example:

• I strongly favor static typing over dynamic typing, but I don't believe that static typing is really any "safer" than dynamic typing. The unquestionable advantage of static typing (which the article admits) is that the programming tools are far, far better. And great tools make me a faster programmer.
• I like compile-time checking and static analysis not so much because it makes my code safer (it probably doesn't), but because the more problems (or potential problems) that can be brought to my attention before even running my program, the more time I save.
• I like strong encapsulation, again not because it makes code safer, but because strong encapsulation *usually* simplifies mental models of programs, meaning its easier and quicker to think about the program as a whole. Plus breaking down problems into small, discrete, self-encapsulated parts is just a good problem-solving technique.

StarWright - CPU Profiling

When programming video games, it's very important to understand how much time your computer's processor is spending in various parts of the game's code. In order to better understand StarWright's code, I added a CPU profiler to my game engine to display graphically how much time is being spent in each section of code.

Here's what that profiler looks like: (Click to see full-size version.)

Each row of text represents a single section of code that is being measured. A section of code may also have a number of "sub-sections", which are indented in the above picture.

The colored bars indicate the "slices" of the game frame that are spent in each code section. You can think of the left edge of the profiler as representing the beginning of the frame, the right edge as representing the end of the frame, and the colored bars as representing the time within the frame that is spent on a specific task.

StarWright - Steganography

Probably only programmers will appreciate this, but I did something I think is pretty neat today...

For StarWright, my super-awesome spaceship building game I'm making, I added more awesome to how spaceship designs are saved to files. Take a look at this PNG image:



If you download the file to your computer -- and of course have the latest version of StarWright -- you can simply load that PNG straight into the game and it will be fully playable and customizable. I'm hoping this will make ships easier and more fun to share, and it has the added bonus that I don't need to generate an in-game preview of the ship.

There's no fancy image-analysis going on. I'm simply embedding the ship data into the least significant bit of each of the red, green, and blue color channels of each pixel in the PNG (which is 32bpp ARGB). That's 3 bits per pixel, which means a 512x512 image can store about 98KB of data, which is more than enough for the largest ship I currently allow. Since only 1 very-insignificant bit is used per color channel, it's very difficult to see any visual difference. This is a kind of "Steganography" (hiding one message inside another), and Spore and the upcoming game Monaco use the same technique for creatures and custom levels.

The basic process in StarWright works like this:

1. Save the ship layout to a JSON-like proprietary text format. Text is better than binary because it's far more tolerant of changes. This is as far as the old version went.
2. Compress the text using GZIP. Since the text is highly repetitive, I get about a 20:1 compression ratio.
3. Take a 512x512 screenshot of the ship at 32bpp.
4. Embed the compressed data into the least significant red, green, and blue bit of each pixel in the screenshot. I could use the alpha channel as well but that'd probably be more visually noticeable.
5. Save as PNG! Done!

There are some drawbacks to this method, but nothing really major:

• Save files are much larger than plain compressed text files. But the largest ship I have is still only 116KB on disk.
• Any alterations to the PNG file will almost certainly corrupt the embedded data.
• Theoretically the ship data may not fit in the image, but I can always increase the image size or use more bits per pixel. At first I was using 1024x1024 at 6bpp which was way more than I needed.
• Supposedly embedding already-compressed data inside a PNG will reduce the PNG compression, but I've seen virtually no file size increase vs screenshots without embedded data.

Okay, I'm done nerding out now. ;-)

Texture Packing

Today I wrote a texture-packing tool for my game engine. It takes a lot of small image files and "packs" them into one really big image file.

Just for kicks I ran it on every single .png file in Tanky-Tank. This image is the result:

This image has been shrunk down, even after you click on it to see the larger version. The actual size is 4096x2655.

Particle Editor

I spent the past couple days re-writing the particle system and editor for my game engine. Here's a screenshot:

The user interface on the right s totally auto-generated based on whatever code variables are modifiable in the particle system.

Starship Builder - Crew Congestion & More

It's been a couple weeks since I last posted about Starship Builder, mostly because my progress since then has been lots of little improvements and not many big new features. But all those new improvements have added up, and I also have working on a significant new mechanic that I'd like to talk about, especially with regard to how it's programmed.

Here's a rough list of what's changed since the last post:

• Added crew congestion mechanic. (See below.)
• Replaced that ugly purple grid with a much nicer space background. A simple grid is overlayed on top of the background.
• Bullets fired from cannons now inherit the ship's velocity. (This is more physically realistic.)
• Tons of bug fixes and performance improvements.

Feel free to download the latest PC and Mac builds.

The significant new mechanic I mentioned above is "crew congestion". Essentially how it works is that, whenever two people are passing through each other in opposite directions, they will slow each other down. This is to emulate tight corridors where two people have to squeeze past each other to get by. But the people are smart, and they will try to avoid other people going in the opposite direction by taking a different route if they can. The result is that creating double-wide corridors or alternative paths can significantly increase the efficiency of your crew.

In the previous version of Starship Builder, a single person wanting to travel from point A to point B used a basic A* pathfinding algorithm to determine the shortest path from A to B, taking into account only the distance between points and travel speed (the rate at which the person can move through different parts of the ship, such as corridors vs thrusters).

In this new version, the A* algorithm is still used for pathfinding, but it also takes into account an estimated "congestion level" for each grid location. A grid location's congestion level is used to reduce the assumed speed at which the person can travel through that location. If the assumed speed is low enough, then the A* algorithm will naturally attempt to route around that location.

The way that congestion is estimated for grid locations is inspired by the way that ant colonies lay down scents to mark paths leading to food. After an ant finds a source of food, the ant will return to the colony, laying down a weak pheromone trail on its way back to the colony. This trail is a small suggestion for other ants to follow. Most ants won't follow, since the trail is very weak, but a few will, and when they find the food, they'll return, laying down more pheromone over top of the trail. As more and more pheromone is laid down, more and more ants will follow it to the food.

Congestion estimation in Starship Builder is inspired by these ant colonies, but it works in almost the exact opposite way. Whenever a person plans a path from point A to point B, a "virtual pheromone" is instantly applied to the entire path, but instead of persuading fellow crew to follow the path, it actually dissuades fellow crew from following the same path. The more virtual pheromone there is on any given grid location, the slower the "assumed speed" will be when the A* pathfinding algorithm runs. So the more people that travel along any given path, the more likely it will be for others to try to take a different path.

Starship Builder - Idea & Thruster Algorithm

I have an idea for a game that I've been wanting to make ever since I was a kid. I've actually tried to make it several times as a pen & paper tabletop game, but it's just too complex of an idea for pen & paper. It's only recently that I've become a good enough programmer to tackle the idea as a computer game, and so I've been thinking more about it lately.

The core idea of the game is that the player designs and builds a space ship on a 2D grid. Think SimCity, but instead of placing buildings and roads onto a grid, you're placing corridors, weapons, engines, crew's quarters, and other ship systems onto the grid. Unlike many games, which only let you place systems onto pre-assigned "hardpoints" of the ship's hull, my game will allow the player to completely customize the ship's size, shape, and the location of internal systems.

Where you place engines, weapons, and other systems on your ship will really matter. Engine physics will be accurate, so that you have to actually think about exactly where the best place to put that thruster will be. Weapon damage will be localized, so that weapon fire from an enemy ship will strike a particular part of a ship and damage whatever systems are there. You'll have to think about what systems you want to put near the outside of your ship, and what systems you'll want to protect deeper inside.

Inside the ship will be dozens, possibly hundreds of crew members scurrying about from one system to another, keeping everything operational. You'll have to think about the corridor layout inside your ship so that your crew can easily travel from one system to another.

The key to this idea is that the player has complete flexibility and customization when designing ships. The only game I know of that even barely resembles this is Captain Forever. But Captain Forever is a fairly simple arcade game, whereas my game, if I ever make it, will be much more of a tactical strategy and simulation game.

I actually just threw together a very rough prototype to prove to myself that I could solve what I think will be the hardest programming problem to solve: that is, how to make a ship realistically fly to a desired location no matter where the player places the ship's engines and no matter how many and what size they are. Future Walt laughs at his past-self's naiveté. This was far from the hardest problem to solve. You can try out this prototype right here.

The algorithm I came up with actually seems to work pretty well. Sure, it could use a lot of tweaking and some higher-level intelligence, but basically I think it proves that I can make it work within a larger game.

The basic algorithm works like this, assuming you have a number of thrusters that each can be "activated" from between 0.0 and 1.0:

1. Calculate a desired force to exert on the ship (X, Y, Rotational) based on the desired location and/or velocity.
2. Build a list of all the thrusters on the ship and sort it by how much more closely a change in the thruster's activation can bring the ship's current force to its desired force.
3. Iterate through each thruster in that sorted list, setting its activation to the value that brings the ship's current force as close as possible to the desired force.
4. Repeat steps 2-3 at least a few times so that the thrusters can "approach" and eventually "settle in" to a near-optimal set of activation levels.

This whole algorithm is run once every frame to constantly adjust the thruster's activation levels.