Feature #690313

Try to pick subset of scenario start positions that are uniformly distributed

Added by Jacob Nevins about 2 years ago. Updated about 1 year ago.

Target version:
Start date:
Due date:
% Done:


Estimated time:


Rhue's comments in feature #688280 and the associated forum thread make me wonder if we can improve start position selection: specifically, in the case where a scenario has a non-uniform set of start positions (such as Earth maps) and is started with many fewer players, can we try to pick a subset of start positions that are more uniformly distributed (rather than concentrating players in e.g. Europe); the idea being that scenario authors don't have to take as much care to produce a balanced set of start positions.

This wouldn't apply to any games where start positions are generated at runtime (in map_fractal_generate()), as this process generates exactly as many start positions as are required, using arguably more relevant criteria (players per island, etc). (Plus, start position generation is fragile enough as it is.)

First we'd need an algorithm to pick a good subset of start positions. This thread might be a good place to start, although we'd benefit from an algorithm where some of the points can optionally be pre-placed. I would expect to maximise simple map distance, rather than any more complicated metric.
  • This has implications on fairness, but if you are letting some players pick nations which imply start positions, then you have probably lost fairness already (or at least put it in the hands of the scenario designer). It's probably most useful for single-player games, where the human gets to pick their start position and a suitable set of AIs is solipsistically generated. It does mean we might have to explicitly disable any of this machinery when startpos_count()==player_count(), to avoid nation-selection exploits in common cases.
The places we can influence this are:
  1. generate_players(), which picks nations to match existing start positions (but doesn't actually assign start positions currently). In the common case where a start position is for a single nation, this determines the eventual distribution.
  2. init_new_game(), which later actually assigns start positions to players. This starts by matching start positions to assigned nations. (Perhaps ordering targeted_list would be good enough?)

I'm not sure if this would need to be controlled by a server setting; the ability for players to select nations might give sufficient control over it.

Related issues

Related to Freeciv - Task #705946: Europe 200x100 with lots more positions (~200)In Progress


#1 Updated by Marko Lindqvist about 2 years ago

Does current code actually prefer using nations from the same continent even in case of scenarios, because they belong to the same nation group? When solving this, there's likely to be some clash between the code that prioritizes nations of the same group and the code that tries to distribute starting positions uniformly.

#2 Updated by Jacob Nevins over 1 year ago

  • Related to Task #705946: Europe 200x100 with lots more positions (~200) added

#3 Updated by Nate Martin (vodot) about 1 year ago

way to link to an awesome computational science problem, how am I supposed to get work done today?

#4 Updated by Nate Martin (vodot) about 1 year ago

So in the UI for Scenarios would have something like:

Start Position behavior:
1. Use the Scenario-specified, Civ-Specific starting positions ONLY (each Civ has only ONE possible start position). Randomly selected AI civs could lead to wildly uneven distributions!
2. Option 1, but have Freeciv select AI civilizations based on which will provide the widest starting distribution, (maximize map distance between each civ)
2. Option 2, then randomize which civ get which start position
3. Let Freeciv analyze the map and attempt to create a fair random distribution of civilizations, attempting to place each civilization as close as possible to its scenario-specified starting position
4. Let Freeciv analyze the map for a fair, random distribution of civilizations without regard to the scenario-specified starting positions.

#5 Updated by Jacob Nevins about 1 year ago

I think that's overambitious. Bear in mind that start position selection is already balancing a number of constraints (such as nation affinity) and doing an imperfect job of it; increasing the number of combinations is just going to make it more flakey.

I think we should focus on finding the algorithm to choose among predefined start positions. Then we'd have option 1 (except that scenarios can assign several nations to one startpos) and option 3. (I think with scenario maps, fairness is already out the window, so I think 4/5 are non-starters.)

#6 Updated by Nate Martin (vodot) about 1 year ago

Alright- so from the perspective of finding the eligible Nation pool, we have the total number of players in the game = Pn. Then we have pool of all available nations in the selected set = N. We have, optionally, the player pre-selected nations = Ns and the nations that conflict with Ns (Nc). So, we get N - Ns - Nc = Nr or the remaining, eligible pool of nations that the algorithm can consider, and it will need to pick a non-conflicting combination of them with quantity Pn - Ns members.

From the perspective of starting locations, ignoring cases where the player has selected nations that have conflicting starting locations (what happens in that case?), to get the pool of starting positions we start with the whole scenario-programmed pool of them (H), subtract the starting locations for the pre-selected nations Hs and subtract any starting locations that can only be populated by Nc. So, the set of eligible remaining starting positions (Hr) that the algorithm will need to consider is given by H - Hs - Hc = Hr.

Given that doing so is part and parcel of every new Freeciv game, I assume that algorithms already exist for selecting valid Nr combinations, so hopefully they can be leveraged to select valid Hr combinations as well. That leaves only the even distribution bit; Our algorithm will need to pick one combination of Hr, with quantity Pn - Ns members, such that the map_distance between each starting position (including all Hs) most closely approaches some ideal value (which would, I guess, be the distance between points in a maximally spaced grid that is contained within a rectangle of map_x by map_y size, taking WRAPX and WRAPY into consideration).

If I'm not mistaken, WRAPX and WRAPY essentially cut the size of the virtual rectangle in half on either axis, respectively. Luckily all rectangles behave alike, so we can hardcode idealized map_dist values for different numbers of players in a rectangle by finding those distances for idealized grids of Np points, then just scale those values them for the actual map dimensions (taking WRAP into account). Going to try to work on that, next.

Another, much simpler option would be to simply have the engine pick 100 random combinations of eligible starting points, then just select the combination that has the highest minimum map distance between any two starting points.

Also available in: Atom PDF