The 3.2.x map generation system

Map layout

Algorithm

I have written in Ruby a MapLayout class, which gives a SC 3.2.x non-mirror map layout when instanciated. This class is used by genmaplayout, which generates one or several layouts when given the # of players and the # of systems, and maplayout2html, which turns them into fully compliant HTML. For instance, generating 1 layout with 4 players and 5 systems per player gives this, then turning it into HTML gives this.

How does it work ?

Each time an empire joins a game, a chain of systems is generated and linked to a random existing system. This very popular approach (hello Lugdunum !) unfortunately poses several problems, both in grudges (2 players) and in multiplayer (3+ players) games.

First, it encourages homeworld shopping, which means creating then quitting a game several times to ensure an optimal number of links around one's HW. In most series, it's sensible to go for 3 or even 4 links around one's HW, because that means a better choice of systems to colonize at the beginning. Moreover, unless she goes for 4 links around her HW, the first joiner can sometimes get information about where some of the following joiners are, since a chain of systems is created and linked to one or several existing systems each time a player joins. What if it is linked to an explored system (including HW) ? Indeed, one or several links pop up on the first joiner's map.

You could argue that the first player, especially in grudges, should just be honest and not look at the map before the second player joins. But then she would have a small disadvantage. That's because the other player(s) gets an hint of the position of one system in the first joiner's chain. Let's call N the actual number of systems per player times the maximal number of players. Then that system has both coordinates between 2N and 3N (though usually not the same). It's much better than in 2.8.5-, where that system had (N, N) coordinates, but it's still not perfect...

Multiplayer games

In grudges, each player only has to fight against one empire: his opponent. Whereas in multiplayer games, it is very common than some player's chains are only linked to an opponent whereas some others are linked to several opponents, which is more annoying, especially when there are several fronts. In other words, in many of those games (well, at least when alliances are not allowed), some players have already lost before the first update occurs. This example is probably one of the most obvious but many larger layouts are not very good either.

Here is one with seven players and seven systems per player. The best layout obviously belong to player #6, because the dispersion of her systems is pretty good and she has only one neighbor (player #2) and one front (98,99). In spite of their bad (maximal) dispersion, players #5 then #7 have a very good layout as well, since they only have one neighbor (respectively players #3 and #4) and one or two adjacent fronts. Players #2, and especially #3 and #4 are definitely in trouble, because they all have several neighbors and several fronts, and they are linked to one of the players above, who have nothing else to do but attack them. Look at another example: here player #1 is basically a corpse against player #7.

I think we shouldn't have to spend our valuable time playing hopeless layouts just to be polite to the other players. Instead, they should be detected as much as possible and shamelessly eliminated. Which layouts should we keep, then ? Well, those following these conditions:

• each opponent has at least two real neighbors (real means without using an engineer)
• each opponent has at least two real fronts

Players not following these conditions are labelled "lucky". I've extended MapLayout and written another script to display a list of lucky players (in joining order, starting from 0) from layouts. For instance, the result for this layout (in HTML) is 3 (i.e. only the fourth joiner is lucky). Layouts where no players are lucky are labelled "good". I've generated several layouts of both types so that you can check by yourself how "good" layouts are better than "bad" (i.e. with "lucky" players) layouts:

Problem is, with our algorithm, what is the proportion of "good" layouts ? For this purpose, I've generated 1000 layouts for 80 different configurations, ranging from 3x3 to 12x12 then printed the list of lucky players for each layout (files are here). The following table shows how many layouts out of 1000 are actually "good" (on first column: number of players, on first row: number of systems). As you can see, the frequency of "good" layouts is definitely low, especially when there are many players and/or few systems per player:

I hear you say, who cares, providing everyone has about the same probability to be "lucky" when joining a game ? Unfortunately, with our algorithm, a chain of systems is generated and linked each time an empire joins a game. The obvious problem is that, in multiplayer games, the first empires joining are likely to be in the middle whereas the last empires joining are probably in the outskirts. Guess which category of joiners win high profile bloods (i.e. without idlers or newbies) more often ? Let's see how often players are "lucky" for several configurations in function of their joining order:

To emphasize how preferable it is to join a high profile blood last instead of first or second, the following table shows the ("lucky" when joining last) / ("lucky" when joining first or second) ratio for many configurations:

Map setup

Algorithm

I have written in Ruby a MapSetup class, which gives a SC 3.2.x map setup when instanciated. This class is used by genmapsetup, which generates one or several setups when given the HW resources [100] and the average system resources [30], from layouts generated by genmaplayout. It is also used by mapsetup2html, which turns them into fully compliant HTML. For instance, generating 1 setup with 4 players and 5 systems per player from this layout gives this, then turning it into HTML gives this.

How does it work ?

In 3.2.x, for each player, after his chain's layout has been generated, one of the systems gets HW status (providing it isn't adjacent to someone else's HW) and the other systems get random resources [Ag, Min and Fuel]. Well, not exactly random, because the current algorithm ensures each chain gets the same total of resources, that is: <HW resources> + (<# of systems per player> - 1) * <average system resources>. This information can be useful sometimes to know how many systems per player there is, or whether it's worth to explore your last (far) system.

Statistics

What can be useful is to compute the access to resources for each player. For instance, for this setup, 53,45, 53,46, 54,44, 54,45 and 54,46' resources are for player #1; 50,45, 50,46, 51,45 and 52,45 are for player #2; 51,47, 52,46, 52,47, 52,48 and 53,47 are for player #3; and 47,45 to 49,47 are for player #4. 50,47 is shared between player #2, #3 and #4. The following table shows the access to resources for this example. But computing this by hand is tedious, that's why I've extended MapSetup and written this script.

Evaluation

With the statistics computed above, we'll see how we can rank map setups, at least for grudges and three players' "good" layouts. That's because in these cases, the very important number of neighbors is the same for all players (respectively 1 and 2), so it's one less variable to take into account. Our hypothesis is that the more balanced the resource accesses are, the fairer the map setup is. To quantify this, we substract the worse resource access to the best (in the example above: 704.0 - 569.3 = 134.7, i.e. 1.50 systems with average resources) and the lower that gap is, the better.

Here we have generated 1000 setups from 2x10 layouts and computed how much resource access differ (in number of systems with average resources: between 0 and 18). The following graph shows the results: quite a lot of setups appear very unfair indeed. We have also computed the average and the median in number of systems (with average resources) for several layout configurations (grudges and three players' "good" layouts with various numbers of systems).

An improved map generation system

Map layout

Overview

For grudges, there is nothing to do so far, just use genmaplayout. For multiplayer games, we have shown earlier that we need to generate "good" layouts, so that noone has to fight in the middle against a "lucky" player. We could generate as many layouts as needed till we get a "good" one, but this brute force approach doesn't scale well as the number of players increases... For instance, a random 5x6 layout is "good" around 5 % of the time, but a random 10x6 layout is only "good" around 1 % of the time... We need something else.

I've thought of three different methods, and I've only implemented the latter, so far. Don't hesitate to tell me if you can think of others. Don't forget all these methods (but maybe the first) assumes you generate the whole map once, which is usually the right thing to do, be it for grudges or for multiplayer games.

1. Dull setups

An easy solution which scales well is, for each player, to regenerate each chain from the third till the temporary layout is good. Unfortunately, it avoids many potential layouts this way (for instance, ringed setups). So I don't like it.

2. Hellish to program

Another idea would be to generate "bubbles" [of at least 3 players, preferably more] with one lucky player [maybe two sometimes], then link them with the lucky players to make bigger bubbles, and so on. This algorithm should scale well. But it's probably very tough to program as well if we want it to handle all cases without giving too stereotyped layouts for any number of players... So don't count on me !

3. Fast enough

The best solution I have found is to generate a random layout, then remove the obvious lucky (only one real neighbor) chains and generate them again till the layout is "good". This should be faster than brute force and still ensures the layouts are various enough.

But there can be [lucky] chains with one front but several neighbors left, because they can't be removed then regenerated as easily as other chains, as connectivity could be lost in special cases. That's why I remove the remaining part of these chains and regenerate them till they get another front.

I have been very pleased to observe that this algorithm works and scales very well, if you're careful not to switch to worse layouts in the first part (that is, whose # of lucky chains exceeds the previous generation). The resulting GoodMapLayout class, derived from the MapLayout class, is used by gengoodmaplayout, which generates one or several "good" layouts when given the # of players and the # of systems. For instance, generating 2 layouts with 6 players and 6 systems per player gives this, then turning it into HTML gives this.

Map setup

For grudges and three players' "good" layouts, it's easy: basically, you generate several setups from your layout, you compute the evaluation function (how much resource access differ), and keep the most balanced setup. I've modified genmapsetup for this purpose: there is now an optional third argument giving the number of tries (1 by default). Here we have generated 1000 setups from 2x10 layouts and computed how much resource access differ. The following graph shows the results for 3 tries and 5 tries: compare them to the graph above (one try). We have also computed the average and the median in number of systems (with average resources) for 4 tries. Again, compare the results to the table above.

Conclusion

Right now...

Here is what you should do to generate a nice map:

• for grudges, generate one layout, then generate several setups from it and keep the best.
• for three player games, generate one "good" layout, then generate several setups from it and keep the best.
• for larger games, generate one "good" layout then one setup from it.

Future work (layouts)

Right now, we don't rate map layouts at all. We only generate one layout, "good" (3+ players) or not (grudges). But we could also generate several of them and keep the best. How ? The rating function would have to balance two factors: fun and fairness. Fun could be measured by, say, counting the number of (real, virtual?) links between the two chains, and/or the diameter of the layout (i.e. the max. distance between two random systems). The higher the number of links, the lower the diameter of the layout, the better. Fairness could be measured by comparing the dispersion (measured, for instance, by the diameter of each chain) of all players, like we compared the resource access for setups. We could also take into account the dispersion of the front systems for each player (to take forks into account). As you can see, the problem is not to define new stats, but how to combine them into a single meaningful figure.

Maybe we can also improve the layout generation algorithm itself. One idea I had would be to generate a few extra chains then removing the same number at the end of the algorithm, providing the layout remains "good". For instance, we could remove chains being completely surrounded (ex: the first chain on that second layout), or chains with all fronts pretty close to each other (low dispersion of front systems), like the first and (especially) the sixth chains on that second layout. Another completely different idea would be to link the most lucky chains by wormholes ;)

Future work (setups)

I do believe that the resource access balance is the single most important factor. But we could also take into account the fairness function computed for the underlying layout. For instance, have a look at this setup. Resource access could hardly be fairer, but the second player's dispersion is significally worse than the first player's.

Other work

Ah has some interesting ideas (and code) on map generation. He introduces twisted maps (mirror map variation for grudges and team games) and balanced maps (for grudges). You can even test them on his SC server, Ahmageddon !

Tell me (replace localhost by agt-the-walker.net) if you have comments / suggestions / etc. about this page, since feedback is always appreciated !
Last Update: 2006/01/18 23:31:29