Page MenuHomeWildfire Games

DiskPlacer: avoid scanning whole map
Needs ReviewPublic

Authored by badosu on Apr 26 2020, 5:48 AM.
This revision needs review, but there are no reviewers specified.

Details

Reviewers
None
Summary

Refactor DiskPlacer to scan only square containing disk instead of whole map

Test Plan
  • Verify a random generated map that uses DiskPlacer behaves the same, e.g. gear, wild_lake, jebel_barkal
  • Verify the tests passed with no error messages (javascript errors do not fail build)

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes

Successful build - Chance fights ever on the side of the prudent.

Link to build: https://jenkins.wildfiregames.com/job/docker-differential/2034/display/redirect

Successful build - Chance fights ever on the side of the prudent.

Link to build: https://jenkins.wildfiregames.com/job/docker-differential/2035/display/redirect

The test supports only running all tests at once, which is fast enough.

let it = new Vector2D();
for (it.x = Math.max(0, this.centerPosition.x - this.radius); it.x < Math.min(this.centerPosition.x + this.radius, g_Map.getMapSize()); ++it.x)
...

(<= mapsize? I guess it returns tiles, not vertices, so should be indeed < then)

I don't know about the addition of this map bounds check.
The plan was to trim operations down as far as possible, get all maps to generate in 1 second or something (and thus being able to generate more complex maps without having to wait a minute for it to load too).
So from the perf side it may be better to avoid it.
From the correctness side I suppose its also incorrect to add the check, since it should be possible to generate an area that is outside of the passable map circle but inside the tilegrid.
Outside of these circle MapBounds only terrain modifications and actors should appear, to ensure all entities are reachable. Actors and terrain changes are useful outside of those constraints, for example Ardennes Forest.

As mentioned that loop happens in more than one place, so it can be useful to avoid the repetition and move it to a helper something. In my second most recent discontinued branch I had something like

binaries/data/mods/public/maps/random/rmgen/Iterate.js
+function forEachVertexOnTile(point, iterator, func)
+function forEachVertexInArea(area, iterator, func)
+function forEachVertexOnMap(iterator, func)
+function forEachPointInBoundingBox(min, max, iterator, func)
+function forEachPointOnDisk(center, radius, gridSize, iterator, func)
+function forEachAdjacentPoint(point, iterator, func)

(Maybe it should become an Iterator class or something else)

The ChainPlacer uses disk iteration too, I wouldnt be surprised if there are more places with the purpose of looping over a disk.

binaries/data/mods/public/maps/random/rmgen/placer/centered/DiskPlacer.js
7

(perhaps its cleaner to make radiusSquared a local, so that one couldnt externally modify only one of the two members. Then again it saves performance in case place was called multiple times on a different center, which thus seems preferable (performance benefit over fault protection, so ok)

badosu updated this revision to Diff 11734.Apr 28 2020, 3:59 AM

Add tests for DiskPlacer, refactor iterator

Build failure - The Moirai have given mortals hearts that can endure.

Link to build: https://jenkins.wildfiregames.com/job/docker-differential/2037/display/redirect

I am not sure I'd like to add the iterator helper to the scope of this changeset, I refactored the code to be similar to what you shared though.

binaries/data/mods/public/maps/random/rmgen/placer/centered/DiskPlacer.js
7

I'd prefer to keep radiusSquared as it is to keep this part of original implementation at the moment even though I'm sure the performance benefits are negligible. I have no strong feelings either way however.

34

@elexis Pertaining your comment on checking map boundaries, it seems it's necessary due to Area cache requiring the point to be present on the map, see: https://github.com/0ad/0ad/blob/master/binaries/data/mods/public/maps/random/rmgen/Area.js#L11-L13

badosu updated this revision to Diff 11735.Apr 28 2020, 4:10 AM

Constrain point iterator inside map boundaries

Build failure - The Moirai have given mortals hearts that can endure.

Link to build: https://jenkins.wildfiregames.com/job/docker-differential/2038/display/redirect

badosu updated this revision to Diff 11736.Apr 28 2020, 4:13 AM

Style changes to DiskPlacer tests

Build failure - The Moirai have given mortals hearts that can endure.

Link to build: https://jenkins.wildfiregames.com/job/docker-differential/2039/display/redirect

I am not sure why the build has failed, it says there was a segmentation fault in the compiler?

As an additional remark, I suspect RandomMap.inMapBounds needs to be refactored to exclude points outside map disk range when map is circular.

badosu updated this revision to Diff 11737.Apr 28 2020, 4:48 AM

Removed the map boundaries condition, this is in effect already for the actual map grid boundaries. For circular maps we allow points outside the map range but inside the map grid boundaries

Build failure - The Moirai have given mortals hearts that can endure.

Link to build: https://jenkins.wildfiregames.com/job/docker-differential/2040/display/redirect

badosu added inline comments.Apr 28 2020, 4:50 AM
binaries/data/mods/public/maps/random/rmgen/placer/centered/DiskPlacer.js
34

A actually allow now points outside the map disk range, the boundary checking is irrelevant for square maps (due to the iterator) and for circular maps we can expect the map designer to be explicit on the constraints, especially since we are not changing the expected behavior compared to the current implementation.

Stan added a subscriber: Stan.Apr 28 2020, 9:56 AM

Some small comments.

binaries/data/mods/public/maps/random/rmgen/placer/centered/DiskPlacer.js
33
binaries/data/mods/public/maps/random/tests/test_DiskPlacer.js
11

Small nitpick, comments should start with capitals.

12

maybe use the center variable?

32

Maybe you can omit 0,0

From binaries/data/mods/public/globalscripts/vector.js

function Vector2D(x = 0, y = 0)
{
	this.set(x, y);
}
48

Comments on top rather than at the end of the lines.

Just for the record this.radiusSquared will be slower to evaluate than radiusSquared (multiplied by bbox area), but thats probably negligible (same for x vs it.x, then again using it.x avoids the set call).

When working with performance critical code it is good to do a final performance test between different suspected optimal solutions, perhaps not for this diff but at least in diffs where the impact may be greater. I didn't test well enough last time I changed the library functions.

There is the function Engine.GetMicroseconds and one can use the RandomMap.log function thing to print performance.
It's printed to terminal output and to mainlog.html.

Setting biome generic/temperate.
Generating Gear of size 256 and 2 players.
Determining number of rivers between players... 0.000008s.
Creating big circular lake... 0.357396s.
Creating rivers between players... 0.693647s.
Create path from the island to the center... 0.497051s.
Creating ring of land connecting players... 0.186742s.
Creating inner ring of water... 0.097884s.
Creating central island... 0.134736s.
Creating hill on the central island... 0.277358s.
Creating playerbases... 0.076830s.
Creating hills... 0.126952s.
Creating forests... 0.585886s.
Creating dirt patches... 0.215489s.
Creating grass patches... 0.188707s.
Creating stone mines... 0.004525s.
Creating metal mines... 0.001396s.
Creating fish... 0.241710s.
Creating decoration... 0.053136s.
Creating food... 0.005935s.
Creating food... 0.001746s.
Creating straggler trees... 0.081700s.
Total map generation time: 3.861981s.
Total entities: 1946, Terrain entities: 840, Textures: 13.

Gear seems to be a map where the DiskPlacer is used most often and often in comparison to the other code of the same map (jebel uses disk placer too but does so many more things that the DiskPlacer is a very subordinate aspect)

So if one wanted to, one could copypaste your optimized DiskPlacer to DiskPlacer2 and change the few things where one is uncertain about performance and measure the impact.
(Again perhaps useless for DiskPlacer but necessary for other classes)
(Also I made the experience that one has to run the test multiple times in the program consecutively, like 10x test1, 10 test2, 10x test1, 10x test2 yielding different results than test2, test1, test1, test2 etc.)
(Another option is to print the bytecode to see which implementation yields least statements, but we don't have that technology currently)

(At last there are different rasterization algorithms for disks, but they dont seem to be worth the effort if there is so little use of the DiskPlacer, or if the DiskPlacer placement method doesn't consume more than some 100ms or so per map.
https://en.wikipedia.org/wiki/Midpoint_circle_algorithm)

The unit test is nice.

(I don't have an svn repository currently, perhaps it might change in the future. From static analysis I agree with the patch, thanks for the patch.)

binaries/data/mods/public/maps/random/rmgen/placer/centered/DiskPlacer.js
33

(Wrong programming language, 0ads clone() is in ScriptInterface.cpp, and Vector2D.clone in Vector2D)

badosu added inline comments.Apr 29 2020, 2:55 AM
binaries/data/mods/public/maps/random/tests/test_DiskPlacer.js
32

I prefer to have it explicit for the tests

badosu updated this revision to Diff 11743.Apr 29 2020, 2:57 AM

Style fixes

Ok, I performed the style fixes, I'll make some profiling and testing and we should be good to land.

Build failure - The Moirai have given mortals hearts that can endure.

Link to build: https://jenkins.wildfiregames.com/job/docker-differential/2043/display/redirect

badosu updated this revision to Diff 11744.Apr 29 2020, 3:36 AM

Handle floating radius properly for DiskPlacer

Build failure - The Moirai have given mortals hearts that can endure.

Link to build: https://jenkins.wildfiregames.com/job/docker-differential/2044/display/redirect

I performed some tests on gear normal for 8 players, times are in seconds and retrieved from the map logger:

New (current implementation): 2.57 2.43 2.55 2.40 2.53
New (avoid acessing iterator properties): 2.55 2.65 2.52 2.59 2.54
Old: 2.95 3.12 2.96 2.88 3.26

So the implementation on this diff cuts time by 25% on total map generation for this map and one interesting fact is that avoiding property access on each iteration (use local x instead of it.x) does not have any significant impact.

Keep in mind I didn't use fixed seeds or biomes, this is just a small validation check. Also I tried to test other maps (especially ones that generate many small disks) but I found out that gear is the only with relevant discrepancy amongst the ones I tried.

binaries/data/mods/public/maps/random/rmgen/placer/centered/DiskPlacer.js
23–30

Extend rectangle containing disk by 1 tile on each dimension when radius is floating point

binaries/data/mods/public/maps/random/tests/test_DiskPlacer.js
53

Regression test for floating point radius, I am reproducing the exact issue I found testing gear

badosu updated this revision to Diff 11745.Apr 29 2020, 5:22 AM

Properly handle map edge

Build failure - The Moirai have given mortals hearts that can endure.

Link to build: https://jenkins.wildfiregames.com/job/docker-differential/2045/display/redirect

badosu added inline comments.Apr 29 2020, 5:24 AM
binaries/data/mods/public/maps/random/rmgen/placer/centered/DiskPlacer.js
25

Map size edge is not present on Area due to 0-indexing: g_Map.getSize() - 1 avoids that

badosu added inline comments.Apr 29 2020, 6:23 AM
binaries/data/mods/public/maps/random/tests/test_DiskPlacer.js
63

Another regression test to avoid cache access on map size index

badosu updated this revision to Diff 11746.Apr 29 2020, 6:24 AM

Remove redundant initializer

One important remark, I noticed the build does not fail if there was a javascript error (as it happens when there's an invalid cache access on Area). Is there a way I can assert there were no javascript errors?

Build failure - The Moirai have given mortals hearts that can endure.

Link to build: https://jenkins.wildfiregames.com/job/docker-differential/2046/display/redirect

badosu edited the test plan for this revision. (Show Details)Apr 29 2020, 6:29 AM
Stan added a comment.Apr 29 2020, 8:14 AM

Well I guess best way to test there are no errors is to add unit tests for those cases and fix the code :)

badosu added a comment.EditedApr 29 2020, 9:16 AM

Well I guess best way to test there are no errors is to add unit tests for those cases and fix the code :)

I am not sure I understand the procedure.

I could for sure test that the placer does not create points that could (or not) raise errors when passed to an Area, but I'd prefer to test the integration of these two components, which is a more probable and often used scenario.

Stan added a comment.Apr 29 2020, 9:23 AM

I guess the question you should be asking yourself is whose responsibility is it to ensure that the values are correct. Is it the placer's or the area's?

If it's the former then you should make sure it functions properly. If it's the latter's then you must make sure it either fixes or throws a tantrum if the value's incorrect.

I performed some tests on gear normal for 8 players, times are in seconds and retrieved from the map logger:

New (current implementation): 2.57 2.43 2.55 2.40 2.53
New (avoid acessing iterator properties): 2.55 2.65 2.52 2.59 2.54
Old: 2.95 3.12 2.96 2.88 3.26

So the implementation on this diff cuts time by 25% on total map generation for this map and one interesting fact is that avoiding property access on each iteration (use local x instead of it.x) does not have any significant impact.

Keep in mind I didn't use fixed seeds or biomes, this is just a small validation check. Also I tried to test other maps (especially ones that generate many small disks) but I found out that gear is the only with relevant discrepancy amongst the ones I tried.

Sorry for having taken it for granted, better performance testing is done by using the same map generation, which can be done by running the same replay.
This way one doesnt compare apples and oranges (for example tropic biome will have many more trees than savanna).
One can run the replay from commandline, which makes it a bit faster, check the readme file.
Those 5 measurements are 5 (new) games started in a row?
The number 25% is probably specific for Gear, if there was a map that has 1 circle that is as large as the map, the performance difference will be nothing I guess (same code), if there are 1 million circles of size 1 it will be many orders of magnitude faster.

The precision measured here was 10 milliseconds, and there were 5 Disks?
If one really wanted to measure the difference between using this.radiusSquared and a function local radiusSquared, one could run the DiskPlacer 10k times in a row.
It could be done in a custom test too.
If the objective was to reach 1 second for every map and if one considers complex maps like jebel, then milliseconds can be relevant (milliseconds can become seconds if there is a 1000 fold loop around it, and those loops can occur quickly if one has retry loops in placement).
(Still probably negligible, just wanted to point it out for the future since its easy to innocently assume that making a statement here or there is negligible and then one ends up making some map 30 seconds slower like I did before)

One important remark, I noticed the build does not fail if there was a javascript error (as it happens when there's an invalid cache access on Area). Is there a way I can assert there were no javascript errors?

Does build refer to the Jenkins bot who runs the unit tests or do you mean the map gen process? If I recall correctly if there is a JS error mapgen is abandoned in the loading screen.

Map size edge is not present on Area due to 0-indexing: g_Map.getSize() - 1 avoids that

Is that correct? The map has |mapSize| tiles which makes |mapSize+1| vertices on the heightgrid.
The values returned by a Placer should be locations of tiles I think and then if a Painter like the HeightPainters operate on vertices of tiles, its their responsibility to work on all four vertices of the given tile.
So actually seems correct then to go from 0 to N-1 making up for N tiles.

Either way patch still seems correct from static analysis (which is all I can offer at the time of writing this for multiple reasons).

binaries/data/mods/public/maps/random/tests/test_DiskPlacer.js
63

(One could also split the tests into separate scopes, so it becomes a bit more clear where one test ends and the next one starts, which locals they use. Also scopes imply deletion of previous values which can, in general, make the test safer or more explicit since it rules out that some values carry over unintentionally)

badosu marked 7 inline comments as done.May 1 2020, 12:11 AM

Is that correct? The map has |mapSize| tiles which makes |mapSize+1| vertices on the heightgrid.
The values returned by a Placer should be locations of tiles I think and then if a Painter like the HeightPainters operate on vertices of tiles, its their responsibility to work on all four vertices of the given tile.
So actually seems correct then to go from 0 to N-1 making up for N tiles.

I think I didn't formulate it too clear, I mean if the map has size 255 the placer shouldn't return a vertex with x or y 255 (as it was with the previous implementation), it was failing on that case and I fixed it.

One important remark, I noticed the build does not fail if there was a javascript error (as it happens when there's an invalid cache access on Area). Is there a way I can assert there were no javascript errors?

With build we usually refer to the process of compiling the binary and the CI, you mean that JS errors do not trigger a test failure in the program code, I could reproduce, and I could reproduce with my working copy from january that simulation tests do not pass if there is a JS error. So one can look at rP23455 and perhaps rP22970. In test_scripts.h we see TSM_ASSERT(L"Running script "+pathname.string(), scriptInterface.LoadScript(pathname, content));, there or somewhere down the line there should be a propagation of error instead of silent catching of the error, that's out of scope, there should probably be a concern raised unless we find the solution before then, and unless one wants to write a trac ticket and forget about it.

badosu added a comment.May 1 2020, 4:19 AM

With https://code.wildfiregames.com/D2715 sent I am confident that we can catch any regression tested by the tests introduced in this change. I am confident on the state of this patch. cc @elexis

badosu marked an inline comment as done.May 1 2020, 4:29 AM
badosu updated this revision to Diff 11756.May 1 2020, 4:30 AM
badosu edited the test plan for this revision. (Show Details)

Style fixes for tests

badosu updated this revision to Diff 11757.May 1 2020, 4:31 AM

Style fixes for tests

badosu updated this revision to Diff 11758.May 1 2020, 4:39 AM
Style fixes for tests
Vulcan added a comment.May 1 2020, 5:25 AM

Successful build - Chance fights ever on the side of the prudent.

Linter detected issues:
Executing section Source...
Executing section JS...
|    | [NORMAL] ESLintBear (indent):
|    | Expected indentation of 1 tab but found 2 spaces.
|----|    | /zpool0/trunk/binaries/data/mods/public/maps/random/tests/test_DiskPlacer.js
|    |++++| /zpool0/trunk/binaries/data/mods/public/maps/random/tests/test_DiskPlacer.js
|   1|   1| Engine.LoadLibrary("rmgen");
|   2|   2| 
|   3|   3| {
|   4|    |-  var g_MapSettings = { "Size": 512 };
|    |   4|+	var g_MapSettings = { "Size": 512 };
|   5|   5|   var g_Map = new RandomMap(0, 0, "blackness");
|   6|   6| 	let center = new Vector2D(10, 10);
|   7|   7| 	let area = createArea(new DiskPlacer(3, center));
|    | [NORMAL] ESLintBear (indent):
|    | Expected indentation of 1 tab but found 2 spaces.
|----|    | /zpool0/trunk/binaries/data/mods/public/maps/random/tests/test_DiskPlacer.js
|    |++++| /zpool0/trunk/binaries/data/mods/public/maps/random/tests/test_DiskPlacer.js
|   2|   2| 
|   3|   3| {
|   4|   4|   var g_MapSettings = { "Size": 512 };
|   5|    |-  var g_Map = new RandomMap(0, 0, "blackness");
|    |   5|+	var g_Map = new RandomMap(0, 0, "blackness");
|   6|   6| 	let center = new Vector2D(10, 10);
|   7|   7| 	let area = createArea(new DiskPlacer(3, center));
|   8|   8| 
Executing section cli...

Link to build: https://jenkins.wildfiregames.com/job/docker-differential/2052/display/redirect

Vulcan added a comment.May 1 2020, 5:29 AM

Successful build - Chance fights ever on the side of the prudent.

Linter detected issues:
Executing section Source...
Executing section JS...
|    | [NORMAL] ESLintBear (indent):
|    | Expected indentation of 1 tab but found 2 spaces.
|----|    | /zpool0/trunk/binaries/data/mods/public/maps/random/tests/test_DiskPlacer.js
|    |++++| /zpool0/trunk/binaries/data/mods/public/maps/random/tests/test_DiskPlacer.js
|   1|   1| Engine.LoadLibrary("rmgen");
|   2|   2| 
|   3|   3| {
|   4|    |-  var g_MapSettings = { "Size": 512 };
|    |   4|+	var g_MapSettings = { "Size": 512 };
|   5|   5|   var g_Map = new RandomMap(0, 0, "blackness");
|   6|   6| 	let center = new Vector2D(10, 10);
|   7|   7| 	let area = createArea(new DiskPlacer(3, center));
|    | [NORMAL] ESLintBear (indent):
|    | Expected indentation of 1 tab but found 2 spaces.
|----|    | /zpool0/trunk/binaries/data/mods/public/maps/random/tests/test_DiskPlacer.js
|    |++++| /zpool0/trunk/binaries/data/mods/public/maps/random/tests/test_DiskPlacer.js
|   2|   2| 
|   3|   3| {
|   4|   4|   var g_MapSettings = { "Size": 512 };
|   5|    |-  var g_Map = new RandomMap(0, 0, "blackness");
|    |   5|+	var g_Map = new RandomMap(0, 0, "blackness");
|   6|   6| 	let center = new Vector2D(10, 10);
|   7|   7| 	let area = createArea(new DiskPlacer(3, center));
|   8|   8| 
Executing section cli...

Link to build: https://jenkins.wildfiregames.com/job/docker-differential/2053/display/redirect

Vulcan added a comment.May 1 2020, 5:33 AM

Successful build - Chance fights ever on the side of the prudent.

Link to build: https://jenkins.wildfiregames.com/job/docker-differential/2054/display/redirect

Stan added a comment.May 1 2020, 10:51 AM

I wonder if you should use let for g_* in those scope. Var can be used out of the scope it's defined in

for(var i = 0; i < 50; ++i)
{
}
warn(i) // 50 while it should be out of scope of the loop.
In D2710#114523, @Stan wrote:

I wonder if you should use let for g_* in those scope. Var can be used out of the scope it's defined in

g_Map and g_MapSettings are (still) required to be globals by a number of rmgen library components, see #4964.

One could do a var g_Map; outside of the scope and then g_Map = ...; inside of the scope to avoid the var keyword in scopes or leave as is.

			+ 	TS_ASSERT(area.contains(new Vector2D(438, 438)));
			+ 	TS_ASSERT(area.contains(new Vector2D(437, 436)));
			+ 	TS_ASSERT(area.contains(new Vector2D(436, 437)));
			+ 	TS_ASSERT(area.contains(new Vector2D(435, 435)));

So speaking about creating lots of vectors causing perf impact, those could also become the same temporary vector and use the set method to change the coordinates. I guess 5 vectors dont consume much time and there are other operatings dwarfing that performance, for example the RandomMap constructor.
How the performance and safety aspect of the test should be weighed against each other is not obvious, the performance impact of rmgen tests would probably only show after having thousands of unit tests.
One could measure if one really wanted to find out, but I would/do accept the diff as is after I ran it successfully.

badosu added a comment.EditedMay 1 2020, 8:06 PM

So speaking about creating lots of vectors causing perf impact, those could also become the same temporary vector and use the set method to change the coordinates.

I always prefer to create new instances on tests, performance is secondary to correctness. E.g. even though this is a minor case we avoid coupling with Vector2D.set.

If it was inside a hot loop it could be a different story.

@elexis @Stan Any additional feedback?

(Whenever seeing this patch I can't stop to ask myself if sqrt(x) for 2*r times or computing x * x for pi/4 * r² times is faster for r < 5, respectively 5 <= r < 25. As in it seeming to be inviting to compute circle / line intersections and only iterating the points on the disk, but I dont know how many points on the wasted effort scale that yields.)

nani awarded a token.Jun 7 2020, 6:14 AM