Paths

Table of Contentst

Group players on alpha 20 and alpha 21 maps
ClosedPublic
Actions

Authored by elexis on Jun 20 2017, 7:23 PM.

Details

Reviewers

bb
fatherbushido

Commits

rP19840: Group starting positions of players by team on the new random map sripts in…

Summary

Maps that use randomStartingPositionPattern(i.e. Ambush and Frontier by _kali in Alpha 20) use completely random starting positions by 50% chance.
This works well often enough, but sometimes the map is too imbalanced (f.e. one player being surrounded by 3 enemies, which shifts the game into a 3v4 from the start).

Maps that use randomPlayerPlacementAt (i.e. Amazon, Mediterranean, Red Sea, ...) come with a set of hardcoded starting locations which are picked at random.
The problem of imbalanced maps is much greater here, because these maps have a large portion of water and impassable terrain, i.e. are ring- or U-shaped.

Grouping players would solve that issue and make these maps much more popular.
Furthermore the probability to get a stronghold placement was reduced to 33% on these maps (as often only a fraction of the map will be used by players until the game is over).

Test Plan

Generate a bunch of testmaps. That 1/3 number can be set to 0 to see random placement each time on the newer maps with every mapgen.

The code uses Heap's algorithm to generate all permutations (of possible starting locations) and then picks the permutation where the distance between allies is minimal.
It weighs the distance with the teamsize, so that it is more important to keep a small team close by.

Trivia: The recursive variant of Heap's algorithm is 10 times slower.

Diff Detail

Repository

rP 0 A.D. Public Repository

Lint

Automatic diff as part of commit; lint not applicable.

Unit

Automatic diff as part of commit; unit tests not applicable.

Event Timeline

elexis created this revision.Jun 20 2017, 7:23 PM

Add missing if (teamSize) and simplify one loop with .some()

In case someone wants to compare the loop version with the recursive one (10x slower):

/**
 * Generates each permutation of the given array and runs the callback function on it.
 * Creating arrays with all permutations of the given array has a bad memory footprint.
 * Algorithm by B. R. Heap. Changes the input array.
 */
function heapsPermuteRecursive(array, callback, len = undefined)
{
	len = len || array.length;

	if (len == 1)
	{
		callback(clone(array));
		return;
	}

	for (let i = 0; i < len; ++i)
	{
		heapsPermute(array, callback, len - 1);

		let pos1 = len % 2 ? 0 : i;
		let pos2 = len - 1;

		let tmp = clone(array[pos1]);
		array[pos1] = array[pos2];
		array[pos2] = tmp;
	}
}


var t = Date.now();
heapsPermute([1, 0, 2, 3, 4, 5, 6, 8, 7, 9], function(permutation) { });
warn(Date.now() - t);

t = Date.now();
heapsPermuteRecursive([1, 0, 2, 3, 4, 5, 6, 8, 7, 9], function(permutation) {  });
warn(Date.now() - t);

Build is green

Updating workspaces.
Build (release)...
Build (debug)...
Running release tests...
Running cxxtest tests (306 tests)..................................................................................................................................................................................................................................................................................................................OK!
Running debug tests...
Running cxxtest tests (306 tests)..................................................................................................................................................................................................................................................................................................................OK!
Checking XML files...

http://jw:8080/job/phabricator/1592/ for more details.

Executing section Default...
Executing section Source...
Executing section JS...

binaries/data/mods/public/globalscripts/utility.js
|  47| »   callback(clone(array))
|    | [NORMAL] JSHintBear:
|    | Missing semicolon.

binaries/data/mods/public/maps/random/rmgen2/setup.js
| 396| function·placeRandom(playerIDs)
|    | [NORMAL] ESLintBear (consistent-return):
|    | Expected to return a value at the end of function 'placeRandom'.
Executing section XML GUI...
Executing section Python...
Executing section Perl...

http://jw:8080/job/phabricator_lint/216/ for more details.

Harbormaster completed remote builds in B2351: Diff 2631.Jun 20 2017, 9:27 PM

Build is green

Updating workspaces.
Build (release)...
Build (debug)...
Running release tests...
Running cxxtest tests (306 tests)..................................................................................................................................................................................................................................................................................................................OK!
Running debug tests...
Running cxxtest tests (306 tests)..................................................................................................................................................................................................................................................................................................................OK!
Checking XML files...

http://jw:8080/job/phabricator/1593/ for more details.

Executing section Default...
Executing section Source...
Executing section JS...

binaries/data/mods/public/globalscripts/utility.js
|  47| »   callback(clone(array))
|    | [NORMAL] JSHintBear:
|    | Missing semicolon.

binaries/data/mods/public/maps/random/rmgen2/setup.js
| 396| function·placeRandom(playerIDs)
|    | [NORMAL] ESLintBear (consistent-return):
|    | Expected to return a value at the end of function 'placeRandom'.

binaries/data/mods/public/maps/random/rmgen2/setup.js
| 413| »   »   if·(locations.some(loc·=>·getDistance(x,·z,·loc.x,·loc.z)·<·0.25))
|    | [NORMAL] JSHintBear:
|    | Don't make functions within a loop.
Executing section XML GUI...
Executing section Python...
Executing section Perl...

http://jw:8080/job/phabricator_lint/217/ for more details.

Harbormaster completed remote builds in B2353: Diff 2632.Jun 20 2017, 11:11 PM

About the globalscript:
let array = [1, "a", ["b", 2], {"k":1, "j":2}]; heapsPermute(array, x => warn(uneval(x)));
gives the good 24 permutations

Ambush map, all of a sudden frontier cc's, maybe more maps do so. (I guess now all locations are filled instead of just 8)

binaries/data/mods/public/globalscripts/utility.js
47 ↗	(On Diff #2632)	semicolomn
binaries/data/mods/public/maps/random/rmgen2/setup.js
314 ↗	(On Diff #2632)	commentin (after testing is done)
396 ↗	(On Diff #2632)	placeRandom is expected to return something (L152), some make it do again
446 ↗	(On Diff #2632)	periods Also list type of param
448 ↗	(On Diff #2632)	This will work when the map is fairly open, but will fail at U shaped maps, then most like one team (on 4v4) ends up 2 and 2 (or worse a 3and1), I guess map designer should simply take this into account when designing the map, so it won't happen. Most likely this will also happen on amps like English canal or other split up maps. (and I even recorded a 3v2v1v1v1, where the 3 team is split up, seed 4331 medium and 11102204 teams)
448 ↗	(On Diff #2632)	Do notice that this algo is not the most efficient in this case, since we are not interested in where which member of the same team is placed, just the places given to each team. But the maximum number of permutations is 40320 (8 players) so not really a problem now (when enlarging this limit though it will rise quickly since the number of permutations is n!). Also I don't see an easy way to change the algo to take into account the teams. (Would be an interesting topic though for a thesis... (I guess one should do a Heap on a Heap or something, perhaps when I get bored in the summer))
456 ↗	(On Diff #2632)	-and +ted
463 ↗	(On Diff #2632)	Rather important here that the ids are ordered per team, but the teamSizes could already be stored before the Heaps call, same for players per team. Perhaps this helps on performance a bit.
465 ↗	(On Diff #2632)	I guess gaia not included so correct
470 ↗	(On Diff #2632)	have been wondering about Manhattan distances, but who really cares about performance in mapgen... Also were thinking about the adding up the squared distances and than deviding by the square of the teamsize, but same argument
470 ↗	(On Diff #2632)	We only look here to the distance between two players following on each other, perhaps it is better to calculate the all distances between all allies (so adding per new player all distances to the previous set team members, when doing also adapt the weights).
473 ↗	(On Diff #2632)	This weight is not really making small teams go together over large teams, it only makes it about level (it would be exactly level when dividing by teamSize-1), one should divide by teamSize^2.
479 ↗	(On Diff #2632)	Wasn't clear at ones that this is done for the last team, perhaps worth a comment (after some consideration it is obvious though, not entirely sure if comment is really needed)

elexis added inline comments.Jun 22 2017, 1:49 PM

binaries/data/mods/public/maps/random/rmgen2/setup.js
448 ↗	(On Diff #2632)	It definitely should be improved upon when considering larger player numbers, even 10 seems too slow already. Passability is indeed not considered by the algorithm, so if it's a U shaped map and allies are grouped but yet split by impassable terrain, that's broken by design. Taking terrain into account sounds like costing a lot of performance. At least we don't have such a map yet (Howe Sound is U-Shaped, but not so much that players at opposite ends of the passability map are closer). If such a map would be added, this algorithm probably still performs better than completely random placement I would assume.
465 ↗	(On Diff #2632)	The loop starts at 1 because it checks for connections between players
473 ↗	(On Diff #2632)	Yes, leveling out is what I had in mind. Didn't want to go for the -1 to keep that equation small and not having to add a ternary or Math.min(0, ...)

Has been a while since I got a proper bb review, thanks so far :-)

binaries/data/mods/public/maps/random/rmgen2/setup.js
463 ↗	(On Diff #2632)	would prefer to keep it as simple as possible. As you mentioned for more than 8 players the algorithm should be overhauled completely Indeed we don't have to consider the order of players within a team, but in the worst case (teams of the size 2) it will only help 50%. If we invent a different algorithm, it should be at least an order of magnitude faster (i.e. 10x) (which gives us only +1 playerslot).
470 ↗	(On Diff #2632)	Manhattan distance is a good thought, but we would lose accuracy and that is the most important part. Adding the squared distances and then doing the squareroot only once per team is also faster but technically wrong and when testing it, it failed to achieve its goal drastically
470 ↗	(On Diff #2632)	Yes, minimizing the area that a team uses is also an option, but that's not really important (and would cost performance), because having players in a line-shape still allows every ally helping every other ally and being able to trade from A to D.

Fix style issues. Also might move that function when committing, so that the placer functions remain grouped.

Suggested reading about permutations by fatherbushido:
http://www.cs.princeton.edu/~rs/talks/perms.pdf
https://arxiv.org/vc/cs/papers/0306/0306025v1.pdf

Build is green

Updating workspaces.
Build (release)...
Build (debug)...
Running release tests...
Running cxxtest tests (306 tests)..................................................................................................................................................................................................................................................................................................................OK!
Running debug tests...
Running cxxtest tests (306 tests)..................................................................................................................................................................................................................................................................................................................OK!
Checking XML files...

http://jw:8080/job/phabricator/1609/ for more details.

Executing section Default...
Executing section Source...
Executing section JS...

binaries/data/mods/public/maps/random/rmgen2/setup.js
| 413| »   »   if·(locations.some(loc·=>·getDistance(x,·z,·loc.x,·loc.z)·<·0.25))
|    | [NORMAL] JSHintBear:
|    | Don't make functions within a loop.
Executing section XML GUI...
Executing section Python...
Executing section Perl...

http://jw:8080/job/phabricator_lint/227/ for more details.

Harbormaster completed remote builds in B2377: Diff 2661.Jun 22 2017, 4:11 PM

Thanks fatherbushido, bb, Vladislav and causative for all the proposals.

Agree with bb that we should do the optimization to skip team numbers one day (i.e. if there are two permutations where each location is occupied by the same teams, then we only need to check one permutation), which will speed up the computation by an order of magnitude,
thus will also work for 16 players once we get there.

Unfortunately there is no algorithm that will work faster than exponential time (NP-complete problem) as long as we want to group players this way.

Agree with causative that we should also maximize the distance between starting positions, so that for 1v1s, the two players won't be squeezed into a corner of the map. However this is logically separate, as it only affects the chosen starting locations before doing any playerID checks.

I think this is an important bugfix to have for the upcoming release, because many players will never play these Alpha 21 maps because of the almost certain isolation of a team member and consequent defeat of a team. So I hope you see why I will commit this patch, even if it will be too slow for more than 8 players.

elexis added reviewers: bb, fatherbushido.Jun 28 2017, 7:08 PM

Closed by commit rP19840: Group starting positions of players by team on the new random map sripts in… (authored by elexis). · Explain WhyJun 28 2017, 7:09 PM

This revision was automatically updated to reflect the committed changes.

Here a partial untested patch causative proposed on 2017-06-29-QuakeNet-#0ad-dev.log which might work for up to 12 players:

something.patch1 KBDownload