What I have working so far:
I've setup a logic to calculate scores for each tile of a map, based on a number of factors, like TC trnWalkTerrain values, how good water bodies and their shores are in the map, trnWalkTerrain values of some arbitrary units, some arbitrary trnWalkTerrain values for determining how good a tile would be as a nearby tile to a TC (for building factories, primarily), whether a tile has destructible or indestructible orbstacles on it, etc., and got some probability maps working decently enough (at least for now).
For example, these are the probability maps I've got for the map Riverside (currently, tests are only being done with AoS maps, but will most likely be expanded later to other games too)
(closest to 10 means "most probable", and closest to 0 means "least probable")
The "bad" probability map is for tiles in which a TC can be placed in, but that have too bad 8 surrounding tiles, so would only be considered as a last resort (and since being on an edge or corner of the map means some of those surrounding tiles are inexistent, this makes those tiles the most likely to be "bad" tiles), if the "good" tiles aren't enough to properly generate all the TCs needed.
Now, the next step is where I'm having problems at. I thought about dividing the map into 25 regions (in a 5x5 grid), and deciding the starting region for each player based on the total score of each region and some symmetry and distance rules. Here's what the region scores would look like:
For 2 players, this was just a matter of distance and symmetry. The logic would be to gather all pairs of regions that obey these rules:
- Manhattan distance between Region 1 and Region 2 is bigger than 2 (in the region grid, not in the map itself) AND
- (Region 1's row = Region 2's row AND distance from Region 1's column to the center = distance from Region 2's column to the center) (in other words, symmetry relative to a vertical axis in the center) OR
- (Region 1's column = Region 2's column AND distance from Region 1's row to the center = distance from Region 2's row to the center) (in other words, symmetry relative to a horizontal axis in the center) OR
- (Region 1's row = Region 2's column AND Region 1's column = Region 2's row) (in other words, symmetry relative to the primary diagonal of the matrix) OR
- (Region 1's row = column count - Region 2's column AND Region 1's column = row count - Region 2's row) (in other words, symmetry relative to the secondary diagonal of the matrix) OR
- (Region 1's row = row count - Region 2's row AND Region 1's column = column count - Region 2's column) (in other words, radial symmetry relative to the center)
For 3 players, it started to get more complicated, because there would be no configuration (at least that I've found, I haven't proved it mathematically or anything near that) that would make all 3 players be equidistant from the center and from each other in a 5x5 grid using manhattan metric, so I started trying a different approach, which was drawing on a paper positions and try to analise how much territory each player would get in theory, assuming expansion occurred to all sides at the same rate, and stopped in regions shared by more than 1 player. The results I got were these:
So any valid combination would involve these positions or one of their rotations (with multiples of 90°, or PI/2 radians):
For 4 and 6 players, I went back to using radial symmetry, because I couldn't find any other configuration that would make the amount of territories for each player the same:
For 5 players it got tricky again, because radial symmetry didn't fit the grid, just like for 3 players, and a lot of combinations would leave some player between 2 others, so those were also discarded, ending up with:
The problems:
- These combinations wouldn't work for a lot of maps and, more importantly, for at least some player count in I'd say most maps.
- These combinations might not even be balanced in some extreme cases of terrain distributions.
- There are probably way better and simpler ways to solve this that I'm not aware of or didn't think to use.
- These combinations currently don't take into account player teams, which could allow for many more combinations by reducing the order of symmetry needed. (I have some ideas to solve this one, though)