StarWright 0.1.0 - Bounties & Blueprints!

At long last (more than a year and a half!) I finally have a brand-new version of StarWright available for you to download and (hopefully!) enjoy, and it's a doozy of an update: StarWright 0.1.0. I consider this the first "non-prototype" version of the game, since it now has some amount of actual challenge and progression.

The changelog lists most of the improvements since the last prototype version, but I'll outline here the biggest new features...

The first big feature is what I call Bounty Mode. Just start up the game and hit the New Game button. You'll start the game with a small ship just like this one:

You start the game with 5000 credits, which if you want you can immediately use to make some upgrades to your ship, though you won't be able to afford much more than a cannon and another couple crew.

In order to earn more credits, you'll need to fight and defeat enemy ships. They're listed under the BOUNTIES in the top-right along with the reward for defeating each ship, and there will also be an arrow pointing in the direction of any enemy ship off-screen. Many of the bounties you may see will be too difficult to defeat without upgrading your ship first.

Once you defeat an enemy ship (specifically, by destroying its Control Room and Reactor), you'll earn a substantial credit reward, which you should use to repair any damage to your ship and, if you have any credits left over, make further improvements to your ship such as adding more cannons, thrusters, and crew.

In order to make upgrades to your ship (or even repair it), you'll utilize the other big feature: Blueprints. Click on the "Blueprints" button in the bottom-left corner, and you'll be presented with a U.I. that looks something like this:

(This screenshot is from much later in the game after the playing has already upgraded their ship many times.)

When this U.I. is displayed, you're not actually modifying your ship itself; you're modifying its blueprints. The cool thing about blueprints is that you can edit and tweak them as much as you want at no cost, only paying the required credits once you're actually happy with your design and want to commit to it. And the other cool thing about blueprints is that, if your ship takes damage and has parts of it destroyed, the blueprints are unaffected, making it easy to restore your ship to its intended design.

When you're satisfied with your design and want to commit to it, simply press the MAKE IT SO button in the bottom right. As long as you have enough credits, your ship will be updated to match the blueprints, and the required funds will be deducted from your account.

Once you've upgraded your ship, you can fly off and attempt to defeat one of the enemy bounties:

Simply right-click on the enemy ship to attack it. Hold the alt key and right-click on a specific part of an enemy ship to concentrate fire on that specific part. (I recommend usually taking out the weapons and ammo supplies first, unless its Control Room or Reactor is especially vulnerable.)

The enemy ships will try their best to shoot you from their best side and will occasionally maneuver to hit you from another position. If you disarm them, then they'll try to run away, so you may want to consider taking out their engines or Control Room to prevent that.

And lastly, we have to say a sad goodbye to an old feature that I have decided to remove to make developing the rest of the game easier.... Goodbye, multiplayer. :(  I removed multiplayer because its presence was making the game's code far more complicated than it otherwise would be and was greatly slowing down the development of the primary singleplayer mode of play. It's possible that some sort of multiplayer "my ship versus your ship" mode will return in the future, but for now I've decided to remove multiplayer from StarWright.

Please feel free to download the game. I welcome all of your feedback!

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 build 2013.09.01

No major new StarWright news, other than that I have just posted a new build of the game that shows off the starship designer, ship combat, and multiplayer!

Download it from here: http://starwright.waltdestler.com/

StarWright - Power

Over the past couple of weeks I implemented one of the last remaining starship simulation mechanics that I had planned to create. This mechanic has to do with providing power to all the various ship systems.

The power mechanic works very similarly to the existing ammo mechanic. If you don't recall, the purpose of the ammo mechanic is to require the player to carefully balance weapons (which consume ammo) with ammo supplies. The closer the ammo supply is to a weapon, the faster the ammo can be delivered, and the faster the weapon can shoot, so the player has to think carefully about where they place weapons and ammo supplies relative to each other. While I've found that this mechanic is successful in giving greater depth to the design of small, localized areas of ships, it adds little depth to the overall design of larger ships since ammo rarely needs to be transported more than short distances.

The power mechanic is intended to complement the ammo mechanic by providing greater depth to the overall design of larger ships. Power works similarly to ammo in that many ship systems (currently thrusters, ammo supplies, and the cockpit) require power to operate. And just like ammo, power "batteries" (for lack of a better word) must be hand-delivered by the ship's crew to the systems that need power. But power is different from ammo in the distance that batteries travel, the rate at which batteries are consumed, and the cost of creating batteries. Ammo is consumed very quickly during combat, but ammo typically travels only short distances, since ammo supplies are cheap enough that any well-designed ship will have one for every few weapons. Producing batteries, on the other hand, is extremely expensive due to the very high dollar cost of the "reactor core", a new ship part that produces batteries. The reactor core is so expensive that most any medium-size ship will only have one. Thankfully, power-consuming systems need fresh batteries fairly infrequently, so the potentially longer distances between the power core and power-consuming systems is not as big a deal as it would be for ammo. However, the distance that power has to travel is still a major consideration when designing a ship, so choosing a relatively central and protected location for the reactor core and keeping traffic congestion low is very important.

Here's a screenshot showing a power core and glowing batteries being carried to some nearby systems:

As I mentioned above, the ammo supply now requires power to operate. You can see the new redesigned ammo supply and thruster artwork in the above screenshot, which clearly shows how many batteries the thrusters and ammo supplies have remaining. Since producing ammo now requires power, power is now the most important resource on any ship. Without it all your systems will eventually become non-functional.

Reactor cores are very expensive, but they can produce an unlimited amount of power. Sometimes when designing a ship, you may find it beneficial to have a closer source of batteries, but you don't want the huge added expensive of another reactor core. The compromise solution is a "battery storage" which can be seen in this screenshot:

A battery storage room does not itself produce batteries, but it can store up to 15 batteries in case of an urgent spike in local demand for power. When all 15 batteries are used up, then any additional batteries must come directly from the reactor core, or the battery storage must be re-filled from the reactor.

If you think it's weird that power must be carried by hand instead of over wires, then I admit you're right. This is a design decision where I have deliberately compromised realism for the sake of deeper ship design and a more transparent simulation. The ship design is deeper because batteries make large-scale ship design decisions and corridor layouts more meaningful. And the simulation is more transparent and understandable because, rather than having some abstracted representation or numbers for power levels, you can actually see how power travels throughout the ship as it is being carried around by the crew.

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 Logo

I made a logo for StarWright using the in-game ship editor, mostly just to show off how flexible the ship editor is.