Paths

Table of Contentst

Differential D118

Infinite loop in random map Ambush
ClosedPublic
Actions

Authored by elexis on Feb 2 2017, 12:54 AM.

Details

Reviewers

FeXoR

Commits

rP19203: Fix infinite loop detection when placing players randomly on the newer random…

Summary

The function placeRandom choses random coordinates for each player.
If the chosen position was too close to another player, it will try different coordinates repeatedly.
If the previous player positions already covered the entire map so that finding such a position can't work,
it will thus end up in an infinite loop.

_kali already identified this issue and added an infinite loop detection,
but messed it up as it resets the attempt counter to 0 with each new attempt.

Test Plan

Replay the commands.txt in the attached replay of #4485.
Without the patch the game will freeze endlessly.
With the patch it does retries and succeeds.

Also notice that placeStronghold is not affected as that uses a radial placement.
randomPlayerPlacementAt is it only choses from a set of given valid locations.

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.Feb 2 2017, 12:54 AM

Build is green

Updating workspaces.
Build (release)...
Build (debug)...
Running debug tests...
Running cxxtest tests (302 tests)..............................................................................................................................................................................................................................................................................................................OK!

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

Harbormaster completed remote builds in B436: Diff 431.Feb 2 2017, 1:38 AM

Though this will still end up in an infinite loop when the maps size is to small for a given map size and minimum distance between player AFAICS this change will reduce the chance.
Otherwise the minimum distance would need to be lowered with each "reset" which also would be possible to do in case "if (attempts > 100)".
I'd find the use of a while loop more appropriate than reducing the current player index "i" over and over again but OK.

Since this still is an improvement I accept this revision.

This revision is now accepted and ready to land.Feb 3 2017, 2:03 PM

Added comments explaining the different arguments in use.

Actually prevent infinite loops by abolishing the randomization approach after too many retries.

Thanks for the review!
It is a valid point that this can still end up in an infinite loop if we the RNG picks a bad choice every single time.
This is comparable to flipping a coin and getting heads everytime until the end of time.

Reducing the minimum distance between civic centers isn't an acceptable approach to me, as we want't to ensure that
civic centers don't end up inside of each other and
since we also want players to be able to do anything inside of their own territory without being shot at by the enemies civic center.

Notice the "small mapsize" argument is invalid, as the affected function works completely independent of the mapsize.
It will retry picking new locations until the distance between each pair of civic centers is at least a quarter of the mapsize,
so this is possible even on a mapsize of 1 tile (so the minimum distance here doesn't guarantee that CCs don't end up inside each other unless assuming our current tiny mapsize).

Since the purpose of the ticket and revision proposal is to prevent infinite loops, the patch should do that (even if highly unlikely).

fatherbushido added a subscriber: fatherbushido.Feb 6 2017, 9:05 AM

Build is green

Updating workspaces.
Build (release)...
Build (debug)...
Running debug tests...
Running cxxtest tests (302 tests)..............................................................................................................................................................................................................................................................................................................OK!

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

Harbormaster completed remote builds in B458: Diff 462.Feb 6 2017, 9:21 AM

Build is green

Updating workspaces.
Build (release)...
Build (debug)...
Running debug tests...
Running cxxtest tests (302 tests)..............................................................................................................................................................................................................................................................................................................OK!

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

Harbormaster completed remote builds in B459: Diff 463.Feb 6 2017, 10:24 AM

Oh, I didn't see that the minimum distance was relative, sorry.
That means that the probability that all attempts fail go against 0 for resets going against infinity.
So the last change returning Undefined is not needed. And it will break the map definitely if more than 10000 tries are needed.

So please reset that part returning Undefined.

The additional documentation looks good ;)

This revision now requires changes to proceed.Feb 6 2017, 2:53 PM

Accepting this patch since in case of returning Undefined the only function using it (addBases) takes care of valid start positions.
I don't think that return Undefined is needed but this patch solves the original issue of an infinite loop.

This revision is now accepted and ready to land.Feb 6 2017, 9:39 PM

Closed by commit rP19203: Fix infinite loop detection when placing players randomly on the newer random… (authored by elexis). · Explain WhyFeb 7 2017, 12:21 AM

This revision was automatically updated to reflect the committed changes.

Refs https://en.wikipedia.org/wiki/Almost_surely

Revision Contents
Changeset List

Path

Size

ps/

trunk/

binaries/

data/

mods/

public/

maps/

random/

rmgen2/

setup.js

30 lines

Diff 470

View Options

ps/trunk/binaries/data/mods/public/maps/random/rmgen2/setup.js

Infinite loop in random map AmbushClosedPublicActions

Details

Diff Detail

Event Timeline

Revision ContentsChangeset List

Diff 470

ps/trunk/binaries/data/mods/public/maps/random/rmgen2/setup.js

Infinite loop in random map Ambush
ClosedPublic
Actions

Revision Contents
Changeset List