Automatically Resolving Battles

Picture this – you’ve built up just about the toughest merc outfit this side of the sector. Your officers are all hardened veterans. Your ships are outfitted with the best weapons and hull mods. Your skill is legendary, your reputation for prevailing against incredible odds unrivaled. Then, you encounter a small enemy convoy – they pose no threat, but the resources they carry would be a welcome addition to your cargo holds. With hardly a second thought, you order an attack – but really, does such a minor fleet action demand your personal attention? “I’ll let my second-in-command handle it,” you decide as you press the button to auto-resolve the “battle” not worthy of the name – it’s target practice, really. But a nasty surprise awaits – you’ve lost a top-line ship, and two elite officers are dead!

… and that’s the scenario we all want to avoid. Auto-resolve has great potential to frustrate the player, because it can obliterate their progress (in the form of resources, ships, and officers) – but worse, it can do this unfairly. The unfairness comes from breaking the player’s expectations of how the game world works. In our example, the player knows their fleet can mop up that convoy – but auto-resolve plays by a different set of rules, one the player hasn’t been exposed to before, one that isn’t clear. Even worse, the rules are hard to learn because they’re hidden. In the situation above, the player might assume that luck plays a big role – but it may well be that the officer skills weren’t valued as much as they should be, or the weapons you’ve equipped the ships with, or any combination of those and other factors. The player might give up on auto-resolve entirely – there’s no clear way to get better at it, and it’s not apparent whether improvement is even possible – and the player is punished for experimenting.

It’s still necessary though, because the alternative is having to fight every piddling battle yourself. Besides, battles that don’t involve the player need to get worked out somehow. So how can we address these underlying problems? Because I like lists, let’s make a list of things that aren’t fair to do to the player:

  • ignoring any improvements they’ve made to their fleet – be it weapons, hull mods, officers, character skills, anything at all that has a bearing on combat
  • ignoring the overall rules of combat the player knows – carriers increasing the effectiveness of fighters, bombers being effective vs large ships, point-defense weapons countering fighters, etc
  • destroying any ships which would absolutely never, ever get a dent put in them if the actual battle was played out. A wing of Talon-class interceptors should have no chance to take out a wing of Wasps, for example.

To sum it up, the auto-resolve system has to roughly simulate the way combat plays out, take all relevant ship & fleet stats into account, and be very careful that “adding a degree of randomness” doesn’t become “anything can happen”.

One thing we can’t take into account is the actual player’s skill at piloting (not their character’s skill, which can be). That’s ok – a battle where the outcome hinges on the player’s personal skill shouldn’t get auto-resolved to victory, anyway. More importantly, I think the player wouldn’t expect auto-resolve to do as well as they do with themselves at the helm.

In the remainder of this post, I’ll talk about the approach I decided on and give some examples of it in action.

The Approach
A natural way to design the auto-resolver is to approach it like a turn-based game. A “simplified Heroes of Might and Magic battle simulator” is an apt comparison to how it turned out. If you haven’t played HoMM, it’s like King’s Bounty. If you haven’t played that either, it’s like the original King’s Bounty from the early 90s. If you haven’t played any of those, you’d probably enjoy them. For the HoMM series, I’d suggest the 3rd one… but I digress. Where was I? Oh, right – designing a turn based combat simulation based on the real-time combat of Starfarer. Yes.

The first step is to come up with the stats of our units, the ships. We have to do that with an eye towards accurately representing the real-time dynamics of the game in a turn-based environment, of course. The actual set of stats evolved as I kept fine-tuning the auto-resolver, but it didn’t get too far from the starting point. Here’s the final set of ship stats:

Hits, Shields
These reflect how tough a ship is to bring down – two sets of hitpoints, with damage getting through the shields causing the ship to be damaged after the battle. For simplicity, shields don’t regenerate during the battle, but the regeneration rate is included in computing the shield strength. Both stats also reflect how difficult a ship is to hit, with faster ships having increased hits/shields values.

Attack, Point Defense, Strike Attack
The goal of having these three is to reflect the most important counters present in real-time combat – PD vs fighters, and strike weapons (bombs & torpedoes) vs large ships. Notice that damage types are not reflected here – they could be, but it seems to work well without them. It’s an extra level of complexity, and would require a more detailed hits model – you couldn’t fold the ship’s maneuverability into its hitpoints anymore.

Movement, Maneuverability
These are used to modify the hitpoint values, and also affect the chances of a ship to escape/retreat.

Number of Flight Decks
Each flight deck can double the hitpoints of up to two fighter wings in the fleet.

The computations to come up with these values get a bit involved – suffice it to say, it took a couple of days to design the overall system, and at least double that time to fine-tune the calculations until the battles worked out right. Everything from hull mods to mounted weapons to officer personalities and the commander’s skill is taken into account.

The second step is creating a system that mimics how battles work when played out in real time.

First up is a “skirmish phase”, to reflect the jostling for objectives that happens at the start of most battles. The relative strengths of fast ships in each fleet are compared to determine which side got the advantage. No damage is dealt in this phase. The skirmish advantage that can be gained is reduced when small fleets are involved – can’t exactly split the enemy forces if all they have is one ship!

In the second phase, the ships fight it out. A ship is picked at random to attack – but the outcome of the skirmish makes it more likely for a winning side’s ship to be picked.

Then a target ship is picked from the enemy fleet. If a ship has good strike weapons, it’s more likely to go after a large ship, while interceptors are more likely to target enemy fighters. Higher commander skill improves the odds of getting a beneficial target pick.

Then the damage dealt to the target is calculated – a combination of attack, point defense, and strike attack, with coefficients based on the target type. For example, strike attack deals a lot more damage against cruisers and capital ships, and no damage at all against fighters and frigates. The target also gets to fight back, but only once per “turn” – the ability to fight back is reset when a ship is picked to be an attacker.

This process is repeated until all ships on one side are disabled, destroyed, or have retreated. When the number of remaining ships becomes small, the amount of damage they deal is reduced to mitigate the effect of luck.

Sample Battle Results
A good way to test this system is to have it run some battles that we’re already familiar with – and what better than some of the current missions?

Here are the results –  with the chance of the player’s side winning the battle. Each simulation was run 10,000 times – incidentally, taking around a second to do so. The performance isn’t so important for battles the player is involved in – even if it took a second, that’d still be acceptable – but battles happening on the other side of the sector should not cause any delay.

Fair warning – f you haven’t played the game, these aren’t going to make a lot of sense.

Turning the Tables: 75%
The very first mission. It’s an easy one, and 75% seems about right. It’s certainly possible to lose if the enemy bombers get a good strike in, or if the Lasher frigates fire off a well-timed missile salvo. Replacing the bombers with heavy fighters boosts the win percentage to 88 – they have a much harder time handling the heavier ships in the player’s fleet.

For the Greater Lud: 62%
A fairly easy mission. The enemy cruiser poses a big problem on paper, but the player’s fleet has a number of bomber wings to take it out. If it weren’t for those (if they’re replaced with heavy fighter wings), it’s not even close – the score drops to 33%.

Hornet’s Nest: 14%
A medium difficulty mission, with the player commanding a far outnumbered, high-tech fleet. It’s not too hard to do well in the early going, but eventually the enemy numbers start to wear you down. It’s obviously hard to say whether 14 percent is exactly right (whatever that even means), but it doesn’t seem unreasonable. After all, it takes a good amount of piloting skill to get a win. The enemy fleet only has a single small carrier – but removing it boosts the player win percentage all the way to 40, because of all the fighters in the enemy fleet.

Predator or Prey?: 0.1%
This one is tough. The player’s fleet is outgunned, outnumbered, and the enemy fleet is full of strike craft that counter the player’s flagship really well. It takes a decisive attack on the enemy carrier and a fair dose of luck to win. Replacing the enemy bombers with fighters  raises the win percentage to 2.5, but it’s really the combination of a quality carrier with a swarm of fighters – whatever the type – that makes the opponent so hard to handle.

Having played those missions to death myself, I’m pretty happy with those results. If one thing is certain, though, it’s that we’ll keep tweaking and refining this system as development goes on and issues crop up. One thing I wouldn’t rule out is cheating erring on the side of caution to benefit the player, should situations like the one outlined in the opening paragraph still arise from time to time.

Tags: , , , ,

This entry was posted on Wednesday, November 9th, 2011 at 5:52 pm and is filed under Development. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

15 Comments:

  1. Have you considered using the player’s past performance as an additional bonus? If the simulations are so cheap to run, then you can trivially compare the player’s performance in a given mission to the averaged result of a large number of trials of autoresolve. This allows you to compute the difference between the autoresolve outcome and actual outcome in surviving resources and fleet strength. By keeping a running average of the player’s score relative to “par” you can give high performing players an additional numerical boost in autoresolve to better reflect the expected outcome.

    My concern is the following scenario: suppose I normally perform about 5% better than autoresolve. That’s enough that I’ll probably let it play out the minor battles, but what happens when I’m facing a string of minor battles leading up to a major battle? By autoresolving the tedious preliminaries, I may enter the critical action with a fleet that’s been pared down by the algorithm to the point that I now have a significantly harder fight. It might convince me to reload a save and play out each of the battles for maximum efficiency, just to preserve my force, even though I’m not enjoying them much. I’ll take a small performance hit to avoid a tedious fight that doesn’t interest me, but the cumulative effect of such decisions may hurt my fun in the long run.

    On an unrelated note, do you have any plans to give players feedback as the expected outcome of an autoresolved battle? Even just a percentage chance of victory, generated in the same manner as the figures in this post, may help players avoid a nasty surprise. Then again, the ability to judge the relative strength of your fleet vs. an opponent’s fleet is a legitimate skill for the game to test, and I can see why you wouldn’t want to give players such a crutch.

    by Tom
  2. You bring up some really interesting points.

    I did consider keeping track of the player’s past performance, but that ends up giving a player incentive to not fight the battles themselves. Assuming they’ve convinced the autoresolver that they’re awesome, why risk its high opinion of them by actually playing out a battle? Besides, if it’ll do as well as the player, for less effort/time, players will use it, even if it’s less fun. Overall, it feels like making the player game a mechanic that they don’t have a lot of insight into, making the auto-resolve results more unpredictable because they can change, and actually discouraging them from playing out their battles.

    The scenario you describe is a valid concern, but I’d think that battles where you have a real chance of losing something important are interesting enough that you’d want to play them out. The way I see it is you’d either auto-resolve if you have overwhelming superiority, or if it’s a playstyle choice (say, a generally non-combat oriented character), and you’re willing to take your lumps. It’s not meant as an equal-effectiveness replacement for actually fighting the battles.

    However, I think there’s a good way to help the situation – giving your officers and crews bonus experience for battles that are auto-resolved. That way you may take some extra losses, but will also end up with a more experienced crew and staff. Best of all, that actually makes sense.

    As far as giving players some feedback, that’s an excellent idea. Maybe nothing as detailed as a specific percentage, but your second-in-command expressing his opinion of the likely outcome.

    by Alex
  3. Dear Alex,

    I’ve often wondered why other games simply don’t handle autoresolve as actual combat instead of reducing it to the basic numbers.

    You have your AI, why don’t you have the same AI routines take control of your units in the actual battle? Of course to turn it into an “autoresolve” you have to hide the graphics and speed up the battle a few magnitudes. You’d think CPU’s from these days would be able to handle Starfarer combat in hyperspeed mode?

    Please enlighten me :)
    -Jamie

    by Jamie
  4. Hi Jamie – you’ve hit on the answer in your question. CPUs would need to be a couple of orders of magnitude faster for that to be viable. And if they were, I’m sure we’d find ways to put the extra capacity to good use, instead of leaving it untapped just so we can speed the game up by an ungodly amount :)

    To put it in concrete terms, a small 5-minute battle *might* get resolved in about 15 seconds – assuming a decent computer and some optimization. That’s already much too long, and when you consider wanting to support a broad range of hardware, as well as larger battle sizes, it’s just nowhere near the right ballpark. It needs to be milliseconds at the most.

    by Alex
  5. I kinda agree with the first post.
    I also agree with Alex.
    But instead of making win percentages very high if you do well, why not have it increased to say, 5 percent at max? Also happy 11/11/11 (and veterans day) :)

    by misterjscape
  6. >>But instead of making win percentages very high if you do well, why not have it increased to say, 5 percent at max?

    If we do that, then why do it at all? It’s still as troublesome implementation-wise, and we’d be getting around its gameplay-mechanics-troublesomeness by making it insignificant :)

    by Alex
  7. Mount & Blade. Auto-resolve.
    Even if my warband consists of 25 master archers firing ten arrows per minute and 30 mounted knights in full body armour, those twelve bare-shirt forest bandits with clubs still manage to kill nine of my men and wound two.

    This will be fantastic if you make it work.

    by Sludge
  8. Or Auto battle Sword of the stars.
    While most of the battles seem to resolve logically, those including cloaked vessels are ridiculous.
    While using a fleet of cloacked cruisers I either get massacred by defending fleet en planet missiles, or suffer not a single dent in the armor and deal huge amounts of damage with auto resolve.
    While this is for a specific kind of ship, it is still something to be wary of falling in.
    I’m greatly interested in the game BTW, seems to me like a 2Dfied 4X-less X game, or a persistent world of Gratuitous Space Battles :)

    by Troll
  9. O ho ho, lots of work looks like it went into that. Immensely gratifying to see large features like that get a mention in Ye Blog. Get to see progress… Get to look forward to the game more… Love it. And you guys respond to comments! Also love it.

    Anyways, has there been testing done on how much a fleet needs to be better than the opposition by to have reliable, 99%+ win rates? Because, really, even 75% is waaay too much chance to lose for many players to risk their awesome, expensive fleet on what should be an easy encounter if they were piloting it. A player can reasonably expect to win Turning Tables 100% of the time with minimal losses. Esp. since it seems like Autoresolve is /intended/ to be used in situations where your expected win-rate is near or about 100 percent, to save you tedium. A 25% chance to just lose is… pretty catastrophic, actually, especially with the snowballing effect of ‘if you are losing, you keep losing,’ that may result in massive, or at least significant, damage/casualties in the few instances when you do lose (Though we didn’t see those numbers, maybe it’s not true)

    by Konstantin Vernikovskiy
  10. Thanks for the kind words!

    Well, with the current dev setup, I’ve been known to lose Turning the Tables every so often. Granted, I’m not trying my hardest, but I wouldn’t expect auto-resolve to reflect that kind of effort.

    The fleets for Turning the Tables are actually fairly evenly matched, and if you auto-resolve under those circumstances, you deserve what you get :) I think the important thing is to generate plausible losses (i.e., often none) in situations where the player’s fleet is truly overwhelming. To give a Mount & Blade example, you shouldn’t ever have to worry you’ll lose a Swadian Knight to Looters.

    Now, since it also needs to produce good results for NPC vs NPC battles, it gets a little more involved. If that wasn’t a consideration, something as simple as saying “no losses if the player fleet strength according to <some metric> exceeds the enemy fleet strength by a certain amount” would cover most of the cases. Of course, that metric by itself would have to be fairly involved to account for fighter/carrier interactions, weapon types, officers, etc – so in the end, it made sense to roll it all into the auto-resolve algorithm.

    by Alex
  11. For some reason the game Space Rangers didn`t got out of my mind when reading this post. =]

    by Vanguard
  12. I realize you guys must be hella busy developing the game and all, but one blog post per month just isn’t enough for us starving fans ! Please, please, please give us more updates !

    by Dimitar
  13. I’m aiming for around two posts per month, but sometimes it doesn’t quite work out that way. Any suggestions/requests for topics, btw? :)

    by Alex
  14. Yeah i’d love to read a blog post about ship lore and/or complete ship descriptions, like the ones that are missing from the game atm.

    I’d also like it if someone could tell me why none of the mods work for my game, i do everything like instructed and the mods dont show up on the activation list, help!

    by Dimitar
  15. Have you checked out this post? That’s got a good bit of ship lore in it.

    As far as mods, take a look at this thread. The short of it is that the Star Control mod is the only one that’s been updated to work with 0.35a.

    Also, new blog post is up :)

    by Alex