SC2Mapster

SC2 Map Analyzer extracts a ton of data from an SC2 melee map; does that excite you as much as it does me?! The manual explains how to generate output and fiddle with some of the analysis parameters.

What the analysis reads in

If you just want to read about what the analyzer computes, skip to the "What the analysis computes" section. If you want to know where the tool gets its input data and what the caveats are, it's right here. Some future improvements will certainly concentrate on the input data.

The awesome community here at SC2Mapster discovered a lot of information about the internal file formats for SC2 maps. SC2 Map Analyzer reads some of these files to do its computations:

MapInfo

From MapInfo it gets the map name, map size, and boundaries of the playable area. This isn't too bad, although there is a section of the MapInfo where the first two character strings appear (in SC2Mapster's documentation they're named 'theme' and 'planet' probably for the tileset) and I've found that the rules for parsing these strings are hard to deduce, such as an unknown number of zero-bytes padding the end of the string. Future format revisions by Blizzard may very well break the map analyzer (it will tell you where it failed), so don't hesitate to start a ticket if that happens!

t3HeightMap

The tool gets the major cliff-level info from t3HeightMap. This is straightforward, no problems, easy to ignore all the cosmetic ripples and bumps that make a map look nice. You end up with terrain data in the analyzer that is rendered underneath all of the other images:

t3CellFlags

Now we've got an issue when it comes to pathing data. What you'd like is a nice, cell-fine matrix saying "ground units can/cannot walk here" and "cliff-jumpers can/cannot jump over here," but that doesn't appear to be available-even though in the editor you can actually view those two types of pathing directly, so it's possible, somehow. But what about t3SyncPathingInfo? Yes, that has cell-fine ground pathing info, and you could get a good approximation of cliff-jumping from guessing how the cliff-jumping algorithm works, but: t3SyncPathingInfo is just not included in every map. It makes me cry. If you open a bunch of Blizzard's maps you'll find it sometimes, sometimes not, and no melee map I've ever made appears to have it. My guess is they changed the overall internal map format so this file is no longer required, maybe it's calculated when you load in the game engine. In any case, I want the map analyzer to produce consistent results and therefore I approximate pathing by using t3CellFlags.

t3CellFlags is included in every map I've opened, and I posted some info about it on SC2Mapster's wiki. Basically, each cell has a bit vector of flags, and right now it appears only two flags are being used: one is for auto-generated foliage and the other is for a cell where the major cliff-level is changing. So I take this second bit and use it to make unpathable cells for ground units. How bad is the approximation? Well the cell flags are four-cell clumps so the pathing data is a little conservative, meaning that distances measured by this tool are probably a little longer than if units can hug cliffs in the game engine. Here's a close up of the pathing near the bottom starting position on Steppes of War. Notice how tight the main ramp is in terms of pathing:

I think the approximation is fine in the end, and I have some data in the shortest paths section to back that up.

Cliff-walk pathing I just allow between any two cells that aren't the lowest elevation, so there may be some cliffs a cliff-walker can't jump in the engine that my tool will let them jump. So far I haven't seen an example of this that breaks the results, but I think it is possible with a very long stretch of squiggly cliff.

Objects

The Objects file is XML that places start locations, resources, destructible rocks and other doodads/units/points on the map. This file is really easy to deal with, but only when you know what to grab out of it. Start locations and resources are easy because there is a very small number of variations to grab (like the space platform geysers are like normal vespene geysers). But what about destructible rocks? There are a lot of shapes and variations, and the XML doesn't give you the object's footprint, so anything you want to integrate with the map data has to be manually encoded. I laboriously placed every destructible on a map and figured out the footprints, then added the known footprints to the map analyzer. As of now, I'm ignoring the vast majority of normal doodads, some of which block paths! Unless someone comes up with a way to automatically discover the object footprints, I'll just have to add them as they are needed. For the Blizzard ladder maps so far there has been no problem because doodads generally don't form long, important barriers on the maps.

What the analysis calculates

The goal of SC2 Map Analyzer is to compute information about a melee map that is useful for a competitive player or a map designer. For instance, you know that the distance between start locations on Desert Oasis is long, but how long? How much longer is it than the farthest spawns on Kulas Ravine? Have you ever tried to measure the chokes around a map? What if we just calculate the "openness" of the entire map so it is very easy to see how the chokes and open spaces compare? Let's find out the answers to these questions and more!

Simple Facts

We can grab all kinds of simple facts about a map that are 1) useful by themselves and 2) useful for computing more interesting information. SC2 Map Analyzer finds facts like what is the playable area of the map? What percentage of the cells are pathable? How many bases are there, and how many resources are at each one? This stuff is pretty easy for a human to do, it just takes a little effort, but its nice to have it all tabulated. The analysis also does some extra legwork to classify bases as mains, naturals, thirds, islands or semi-islands.

Shortest Paths

The original motivation for creating SC2 Map Analyzer was to calculate shortest paths between locations. This is useful for comparing the relative distance between start locations and/or naturals in the various spawn configurations of a map, or to compare the distances between maps. Also, the shortest paths by ground, cliff-walkers and by air are used later to calculate the influence of a start location on a base versus another start location.

In order to simplify the shortest path algorithm I only consider a few connections between map cells, rather than allow a unit to stand anywhere, or walk at any angle. A cell connects to the cells it shares a side with, the diagonal neighbors, and cells that are a knight's jump away.

Another caveat is that the pathing approximation, as explained in the t3CellFlags section above, affects the shortest path calculations. Unless we use the exact pathing map as the game engine, and for that matter, the exact movement algorithm from the game engine, we will never be able to compute the true "game distance" between locations.

However, I think the tool does a fine approximation of computing game distances by comparing the analysis results with an experiment I did within the game itself. This spreadsheet shows the comparison of the analysis to the experimental values. The in-game experiment measures game seconds for an SCV to move from one start location to another. SC2 Map Analyzer computes the distance in cells between two start locations. The experiment values and the analysis values should be directly proportional (in other words, a distance divided by time should be the speed of the SCV) and the comparison shows this. There are a few anomalous data points but everything is within 5% so I'm pretty confident the analysis distances are useful.

Openness

Openness is a term I'm defining as "the distance (in cells) from a cell to the nearest unpathable cell." It measures how "open" the cell is, and if you plot the openness values along a color scale you get nice images that really give a feel for the space in a map.

We can do a lot of cool stuff with openness. Clearly you can judge the positional balance of slightly asymmetrical maps by checking the openness. You can also get the average openness across an entire map, or compare how tight or open a map is compared to other maps. SC2 Map Analyzer samples the openness values in a radius around bases to get a rough idea of whether the bases are balanced. More or less openness isn't necessarily better or worse, but we can compare the values to decide when they are different, how different are they?

Influence/Positional Balance

Now for the grand finale: can we use the data extracted to compute positional balance? Notice I did not say racial balance, which if Brood War taught us anything it's that the relative style/strength/advantage of races due to terrain is a hard thing to predict or measure. But positional balance we might be able to do something about.

Consider a perfectly symmetrical map with respect to pathing, start locations, and bases. This map has perfect positional balance because no matter which start locations players spawn in, they are faced with exactly the same situation. Okay, but perfectly symmetrical maps are boring both to look at and to play on. So let's see if we can't measure positional balance to judge whether an asymmetrical map is still fair for competitive play.

SC2 Map Analyzer attacks this problem in two phases. The first phase calculates influence, which is the percent influence that one start location exerts on a base versus another start location. The start locations are considered in pairs because the influence calculation is meant to reflect which player has greater potential influence in a 1v1 game.

Consider a base, B. What is the influence of Start Location 1 versus Start Location 2? First measure the shortest distances from B to 1 by ground, cliff-walk and air. These distances are weighted: ground 55%, cliff-walk 10% and air 35%. Then compute the same weighted distances from B to 2. The influence of 1 on B versus 2 is inversely proportional to the percentage of 1's weighted distance over the total with 2's. If that's just mumbo jumbo, here's an example:

Consider a base that is exactly the same distance between two start locations by ground, cliff-walk and air. These start locations will exert exactly 50% influence on the base versus each other, because players in those spawns have an equal potential, by distances, to control that area of the map.

Another example:

A base near start location 1 (like the natural) has a SHORT distance by ground, cliff-jump and air. The distance from start location 2 to the natural of 1 is LONG by all accounts. The influence of 1 on B versus 2 is inversely proportional, so SHORT becomes a HIGH influence (for a natural it's usually something like 75%).

Images show influence more intuitively, so:

Here you can see the start locations exert almost 100% influence over the main base. The naturals are roughly 75%. Notice the island in between the mains and the gold expo at the far end; these bases are supposed to be along the axis of reflection so they are perfectly contested between the players. But the analysis tells us start location 2 o'clock is a hair closer to the island (no problem) and the gold expo is bit closer to the 12 o'clock base. Scrap Station has asymmetry and in the grand scheme of things these fluctuations in influence are reasonably close.

So we calculated influence. Great. What does that tell us about positional balance? Not the whole story yet. What if you have 75% influence over your natural and I have 75% over mine, but my natural only has one mineral patch?! Ah! This is where phase two comes in: using influence and attributes of bases together to compute positional balance.

Positional Balance by Resources

We can add up the total resources for bases, then calculate the difference in influence percentage over the bases for start location 1 versus 2, then compute what percentage of resources start location 1 has more influence over than start location 2! Awesome! So if a base is 50%/50% contested it won't factor into the balance at all, and a base 75%/25% (like a natural) will contribute 75-25=50% of its resource value to the balance of the dominant start location.

Positional Balance by Openness

Let's consider a map that has perfect positional balance by resources, but my natural has a protective moat to make it harder to attack (without changing the shortest paths from the start locations, of course!). Clearly the positional balance should reflect that as well. SC2 Map Analyzer does a separate positional balance calculation by taking the same influence percentages for each base and applying them to the average openness of each base. This calculation (unlike the resource calc) doesn't say whether openness is good or bad; it is just one way to measure how different two positions are.

The map's overall positional balance can be thought of as the lowest positional balance computed by any separate method out of all the possible start location pairs.