Tuesday, July 26, 2011

An Autoplace & Route Tool for Civilization Style Tech Trees

A particular statement in this piece by Derek "Kael" Paxton about technology in Stardock's Elemental: War of Magic stood out:
5. Autolayout- The tech tree draws itself and its lines automatically.  This was needed because the tech tree will be different every time, so it must be able to lay itself out programmatically.  The good news for modders is that they can add techs to their hearts content and they will be automatically added to the tree right where they belong.
I thought that was really cool, and decided to look into how to do such things.

After some literature research, I found this paper out of AT&T Bell Labs By Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, and Kiem-Phong Vo.

The algorithm looked fairly straightforward so I decided to see if I could implement it first in Excel 2007 (VBA) and then in Civilization IV (Python or C++ depending upon which level I ran the algorithm).

Here is how the tool works:

  1. Reads in the Technology Data from a spreadsheet
  2. Processes the Technology Data to add missing Parent-Children links (Data originally contains only Children-Parent links)
  3. Does a DFS search from every root node and calculates an affinity between each root based on how many nodes they share.
  4. Orders the Root nodes based on their affinities, so that roots which share many nodes are placed together
  5. Runs most of the Vertex Ordering part of Gansner's Algorithm (Heuristic Based)
  6. Determines X and Y coordinates for each technology based on its rank and vertex order.
  • I have not yet finished generalizing the code.  I think that if you try it right now on a tree that is deeper than 9 ranks, you'll get an out of bounds error.
  • It's not as fast as it could be, there are some inefficiencies I already have in my mind to target.  For now it takes about 2 seconds to generate and draw the placement.
  • It requires Excel 2007 and Macros enabled, you trust me right?
The Final Result

Download AutoPlace and Route Tool

A Cvilization IV Combat Calculator

Update (8/10/12): There was a bug in the calculator when calculating battles not at 100% health for both sides.  I've fixed it now.

Download Combat Calculator

In one of my PBEM Civilization games I needed to destroy one particular unit, but none of my units had good odds on it.  Since I outnumbered it 7:1, I decided to go ahead and attempt to mob it to death.  I had no idea what my odds were, but before combat began any one of my units did not get (in game calculator's) odds over 0.01%.  I ended up winning after 4 battles.

I was curious then, what my actual, group, odds were.

Looking online, there were no good current CIV IV combat calculators available, so I decided to build my own.  Working with some of the other fellows at Realms Beyond to understand how the combat system actually worked, I ended up with a decent calculator.

This calculator can be used to find the precise odds for 1:1 unit combats, or X:1 combats with many attackers and a single defender.  It is built on Excel 2007 and requires macros to be enabled.  You trust me don't you?


  • Does not properly calculate retreat Chances
  • Does not calculate defensive strikes (A Mechanic from FfH)
Multiple Attacker, Single Defender Tab

Single Attacker, Single Defender Tab

Saturday, July 16, 2011

Technology and Inventions Overview

Let's talk about technology systems in 4x games and how particular design decisions impact the overall game experience.  I'll be presenting examples from Civilization IV, Victoria II, and Master of Orion II.

The Examples:

Most 4x strategy games have some sort of system to represent technological progress during the game's play period.  These systems are made up of component parts, which are often referred to as technologies.  Each technology has inventions. These names can vary based on the game's setting.

The relationship between technologies and inventions is not fixed between game systems.

For example, in Civilization IV, if a player possesses a particular technology, they have access to every possible invention unlocked by that technology.  Below is a screenshot of the Machinery technology page. A player who owns Machinery will have access to all the units, abilities, and buildings unlocked by that technology from the moment they acquire it.

A technology page from Civilization IV
Under a Civilization model of technologies and inventions, technologies are the player's primary focus. Players plan around which technologies they will acquire and when.  Since inventions can skew the battlefield in the player's favor, their associated technologies become more valuable.  Beating your competitors to a particular technology by a handful of turns matters a great deal.

The designers of Victoria II took a different approach.  Instead of a technology granting all of its inventions upon discovery, the technology gives some immediate boost and a chance over time to unlock a series of other inventions.

Below, you can see that Advanced Metallurgy gives an immediate boost to Sulphur production, and a chance over time at Steel Alloys and Electric Rolling Techniques.  The list of possible inventions shows inventions that the player (me in this case) has not yet discovered and the percentage chance to discover each month.

Technology Screen from Victoria II
The Victoria model is very similar to the Civilization model.  A technology will eventually grant all of the inventions associated with it, given sufficient time.  Players can still plan around the immediate benefits of a technology, but they now need to include lead time in their plans when accounting for inventions.

I found in my own gameplay that this model encouraged a beeline to a particular technology (to start rolling for its inventions as soon as possible) and then back-filling other technologies which gave important benefits, but had no inventions associated with them.

Under the Victoria model then, beating your opponents to a key technology whose benefits are tied to inventions is less important than for a Civilization style model.  The player's primary focus, however, is still on the technologies themselves, rather than their associated inventions.

In Master of Orion II, each technology level has several inventions associated with it, but most races in the game will only be able to choose one invention to develop from each level.  Missing inventions could be traded for, or stolen from, other races.

MoO II Technology Screen
In the MoO II system a player plans to gain particular inventions, rather than technologies.  This style of system adds another layer to a player's technology decisions.  Instead of choosing between which technologies to prioritize, the player must also choose between the inventions.  They might be able to back-fill inventions later with diplomacy and espionage, but there's no guarantee that they'll ever be able to acquire an invention that they pass over.

Bringing it All Together

Technologies and invention play an important role in all three of these games, though how much of the player's focus they take up varies.

The Civilization model is best for games which want to encourage precise player planning.  Players can easily grasp the direct relationships between the technologies they acquire and the units and buildings they can make use of in the rest of the game.

The Master of Orion model has similar strengths to the Civilization model, but puts an additional emphasis on the choices a player makes when they acquire technologies.  It encourages the player to put more focus on their inventions, what they have and what they're missing, and leaves additional design space for espionage and diplomacy systems.

A Victoria style model encourages players to budget in slack time into their plans, to allow for the acquisition of inventions over time.  I think that it de-emphasizes precision technology planning and encourages the player to spend less focus on the technology portion of the game and more focus in other fields.  Additionally, when balancing technologies in a Victoria system, a technology with no inventions associated with it becomes a prime candidate for back-fill or back-burner status.

Back up and Running

It's been a year since I "launched" the blog. It sure hasn't gone very far has it?

I've jumped into a number of games over at Realms Beyond, and have updated the blog to reflect that.  I've also begun looking into a number of side projects which deserve their own space somewhere, rather than buried in some obscure thread on a forum.

My own education in multiplayer strategy games continues, and I'd like to think I've learned something over the past year.  I'm theoretically working on a thesis project for my MS this year.  That may take up more of my time, but the goal is to do a blogpost every other day or so.