How to make a good random maps for Medieval 2 Total War

Some news about Medieval 2 random scenario generator I wrote about yesterday.

Today I fixed most of the known bugs in scenario builder (except AI passivity, which would require playing an actual campaign to figure out), and I was looking at JRuby options for a simple GUI so everybody can enjoy scenario builder, and customize their Concentrated Vanilla experience any way they want - including simply turning all options off and playing vanilla with bugfixes and random scenarios if that's your thing.

Sadly making GUIs looks like a lot more work than expected. I got so used to the happy universe of HTML5 and jQuery on frontend with Ruby on Rails on backend that my first contact with Java GUI libraries was like hitting a wall. I'll figure something out eventually - in the worst case I'll just make the script start web browser and present you the mod customization form in browser window.

Anyway, scenario builder.

How to make good random maps

Assigning settlements completely at random means a few fun campaigns, but it confuses AI too much, and doesn't really lead to much strategic gameplay since whoever you just attacked probably can't respond since all their other settlements are in completely different part of the map.

So my next idea was % cluster / % random allocation, but there are many things I don't like about it. Here are some ways how cluster algorithm fails them, while random allocation worked reasonably:

• 5 settlements have no neighbours and 6 have only one. Cluster allocator assigns most of them to rebels.
• There are some false neighbours like Dongola / Benghazi, Tripoli / Timbuktu, Arguin / Marrakesh - they are next to each other on a map but you'd need to move through unpassable desert.
• Since factions were allocated in order, factions late on the list were most likely to get scattered settlements.
• Very often huge areas are all rebel, while there are no rebels in other places. On 67% cluster map there are no rebels in Spain, France, and Germany, but there's a massive 11-region rebel cluster in Anatolia and Balkans, and second 7-region cluster on South/East Baltic Sea coast. This is not due to algorithm since rebels just got whatever was left. Random chance will lead to some clusters, but rebel clustering is far too strong.

So I tried many things like:

• Allocating settlements to different factions in random order, one at a time.
• Allocating settlements to rebels first rather than last (without clustering), or one at a time as if they were normal faction (except without clustering) 
• Making rebels not take settlements with 0/1 regions if possible, so factions would get them instead.
• Using XY distance between cities instead of map neighbourhood, or some combination of both.

Eventually after looking at countless maps for far too long, the following algorithm seems to work best:

• Fully at random, allocate one settlement to each faction, and all rebel settlements.,
• Then allocate other settlements in random order. Some % will be neighbours of existing settlements, the rest will be random.
• If there are no neighbours available since all have been allocated to other factions, try neighbours-of-neighbours instead.
• If neighbours-of-neighbours still doesn't work, just do random allocation. (because of this % in this post are much higher than in previous post - you actually get significant random allocation because no other is possible)
• Neighbours of a settlement are 5 geographically closest settlements. Then we add arrows back, but only if they are geographically connected. This seems to work best. 

And now the maps. Muslim/Orthodox factions get 3+d6 regions, Catholics get 1+d6 regions, rebels get whatever's left.

Each with 10 different random seeds - for ton of maps.

100% clustering (only random when forced)

80% clustering

70% clustering

Next steps

So much map porn for today. The next step is making some kind of interface so people can run this without going into command line and/or editing code.

Testers very much welcome. If you want to play some random map soon, and don't mind possible technical difficulties, contact me ahead.

Also, if anybody knows how to run a mod on Steam version of Medieval 2 without going through massive pain (the way it works on retail and pirate versions), definitely tell me. I've heard rumors there is a way, but I've never seen anything reasonable.

By the way since maps will be mostly clustered, I'll probably move distance to capital penalty somewhat higher than it was on fully random map.

I've also been asked about hotseat mode. As far as I understand, this would require switching from Medieval 2 engine to Kingdoms engine with retrofit mod as base. I'll probably do that some day, but for the time being the mod will most likely stay a single player only thing.