Cosmoteer 0.13.0 - Multiplayer!!!

Given the lack of updates for the past couple of months, you'd be forgiven for thinking that I had stopped working on Cosmoteer. Thankfully, you could not be more mistaken!

I've actually been working on one of the biggest new features in the history of Cosmoteer: Multiplayer!

Those of you who have been following Cosmoteer for a really long time probably know that the original prototype versions had support for multiplayer in which players could design ships and battle them with their friends. But I realized that having to support multiplayer was dramatically slowing down the development of Cosmoteer, including development of singleplayer-only features. And so I removed multiplayer support from the game's code, hoping (but not expecting) that one day I would be able to bring it back.

Well, that day has arrived! I am incredibly proud and excited to announce that multiplayer is returning to Cosmoteer!

In this first version, multiplayer is a simple team-versus-team battle of up to 8 players spread across two teams. Each team has a certain amount of money (configured by the host) to spend on a fleet of up to 5 ships per player (or fewer, as configured by the host). Then the game starts and the players control their own ships, attempting to destroy the other team's fleet. The game ends and one team is declared the winner when either the other team's fleet is sufficiently destroyed or the timer runs out.

You can play with anyone on the same LAN (Local Area Network) as you, and you can also play with a friend anywhere else in the world by typing in the host computer's I.P. address. (There is not yet a public online list of games, but I hope to add that soon.)

This is just the beginning! This first version lays the coding foundation for more improvements to come. In the long term, I may add entirely different game modes, such as multiplayer co-op and creative modes. In the near future, I plan to add:

• A.I. players in multiplayer battles
• Observers (for streaming tournaments)
• More than two teams & free-for-all battles
• Some sort of boundary around the playing area to prevent people from being able to run away indefinitely
• Limit price per-ship and not just total price per fleet

There's lots more details and plenty of other fixes and improvements in the full changelog.

Technical Implementation

You may be wondering why I've chosen to bring back multiplayer given the fact that I originally removed it because it was slowing down development too much. Wouldn't bringing back multiplayer cause all future development to become a lot slower?

Thankfully, the answer to that is mostly "no", and the reason for that is that I've taken an entirely different approach to implementing the multiplayer code.

The original implementation of the multiplayer code required that every single change in the state of the game (such as a ship firing a weapon, a ship moving a millimeter, a crew person walking a foot, or a bullet hitting an enemy) be synchronized among all players by sending packets over the internet. This was a huge problem for two very important reasons:

1. In a game as complex as Cosmoteer with potentially dozens of ships and thousands of crew, that's a potentially huge amount data that needs to be transferred over the internet between all the players. We're talking megabytes per second of data for a large battle, which made the game really only playable on LAN or very-high-speed internet connections.
2. The code for anything that could affect gameplay even in the slightest became way more complicated due to the need to send those aforementioned internet packets. For example, if I wanted a bullet to inflict 1000 damage on an enemy ship, I couldn't just call the TakeDamage(1000) function; I first had to construct a network packet with all the needed information and send it to all other players. This made working on gameplay code far more time-consuming that it would've been without having to send all those packets.

The new multiplayer code uses an entirely different approach that's called "deterministic lockstep". Essentially, this approach requires that two computers running the same version of the game with the same initial battle setup and same player inputs will simulate the game in exactly the same way. (Not even off by a millimeter, or else the butterfly effect will cause bigger and bigger errors until the game desyncs.) There are two big advantages to using deterministic lockstep:

1. Only player inputs (commands issued to the ship) need to be turned into packets and sent over the internet. Everything else (physics, weapons, damage, etc...) will happen exactly the same way on every computer by virtue of them running completely deterministic game simulations. This saves massively on bandwidth, so much so that Cosmoteer now only uses a few KB of bandwidth per second.
2. Code that affects gameplay no longer needs to be synchronized using packets sent over the internet, so long as the gameplay code can be written to be 100% deterministic. Writing deterministic gameplay code isn't very hard as long as you know what kinds of things to avoid (primarily code whose outcome could change based on framerate).

There are, however, some important disadvantages to using deterministic lockstep:

1. The gameplay really does have to be 100% deterministic. 99% deterministic is not good enough. And non-determinism bugs can be very tricky to track down. I have written myself some pretty nice tools for debugging determinism issues, but it still took me several weeks to comb through the whole Cosmoteer codebase and convert everything to be deterministic.
2. Games that use deterministic lockstep typically have more latency than other types of games. You may notice that when playing multiplayer Cosmoteer (and most RTS games) that there's a small delay after assigning a ship an order and before you see it actually respond. That's because it has to wait for the other computers to receive the order before it can process it. In action games like first-person-shooters, this would be a huge problem, but in slower games like Cosmoteer, it's not a big issue.
3. Differences in how different CPUs compute floating-point (fractional) numbers can cause an otherwise 100% deterministic simulation to become only 99% deterministic, which due to the butterfly effect will ultimately lead to desyncs. In practice, this means that players running on 64-bit operating systems can't play with players on 32-bit operating systems. (Although there is a mode to force the game into 32-bits so that friends on different operating systems can play with each other.)

While these downsides are significant, none of them are deal-breaking, and are certainly preferable than the problems caused by the original way I implemented the multiplayer code.

All in all, getting multiplayer working again was a pretty huge undertaking -- one that I wasn't even sure I could pull off -- but in the end I think it has proven to be well worth it. And I'm looking forward to playing a ton of Cosmoteer multiplayer as a result!

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.

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.

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.

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 proprietary data format.
2. Compress the data using GZIP. Since the data 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. ;-)

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.