Build is green

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

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

Build is green

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

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

Build is green

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

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

DistanceBetweenEntities doesn't use distanceToSquared, but if that sqrt operation is neglible, we should definitely use that helper function

Not a performance optimization, but wolves should really not spawn right besides mines, so that the player can build a wall around them

From the gameplay and design point of view (I won't speak of code), I think there should be really more wolves and more powerfull ones but spamming them more or less randomly (and really big wolves hord roaming between players). But that's just a personal feeling.

The first thing I noticed was this line:

	for (let target of targets.sort((ent1, ent2) => getDistance(ent1) - getDistance(ent2)).slice(0, targetCount))

It sorts a huge vector but then only grabs the first few elements, which seems pretty wasteful. And it does that for every attacker.
I wrote a quick ugly thing to skip the sorting and it looks like it has an impact. Here's an a22 game:

And here's a game with D185 and Petras (since I didn't have any replays) where I tried to replicate the settings of the other game (3v3, medium, 200 pop, 30m). They never got their populations up to the same level, so the targets array wasn't as long and there wasn't as much savings:

The hashes were okay in both. Here's the quick ugly thing:

let good_targets = [];
let good_dists = [];
for (let target of targets)
{
	let dist = getDistance(target);
	let i = good_dists.findIndex(element => { return dist < element; });
	if (i != -1 || good_targets.length < targetCount)
	{
		if (i == -1)
			i = targetCount;
		good_targets.splice(i, 0, target);
		good_dists.splice(i, 0, dist);
		if (good_targets.length > targetCount)
		{
			good_targets.pop();
			good_dists.pop();
		}
	}
}

for (let target of good_targets)
	ProcessCommand(0, {
		etc.

Finding the closest targets for each attacker isn't possible without looking at each possible target, right?
So if I understand your patch correctly, it still looks at all entities but doesn't create a sorted array but instead just stores the closest N targets in an array? sounds good. Thanks for the hint.
Also element => { return dist < element; } can be written as element => dist < element.

(Perhaps we could also do a range query with a fourth of the mapsize and then do check the entire mapsize if that fails. Not sure if it's worth the code though.)

In D185#33613, @elexis wrote:

So if I understand your patch correctly, it still looks at all entities but doesn't create a sorted array but instead just stores the closest N targets in an array?

Yep.

(Perhaps we could also do a range query with a fourth of the mapsize and then do check the entire mapsize if that fails. Not sure if it's worth the code though.)

You mean adding a query for every attacker? My original thought is that that would slow things down too much since there's so many attackers, but I tested and it's faster than even my sorting fix.

In the NOTFASTER patch there was a huge typo, for (let target of targets.splice(targetCount)) instead of for (let target of targets.slice(0, targetCount)). Because splice returns the removed objects rather than the remaining ones, you were actually attacking every target except the first three! Of course the 10000m radius was a bit much, too.

Here I search for targets within a 200m radius (210m is a civic center in town phase). In my replay they didn't need more than that until turn 3259 = 163 on the graph, after the game was basically over (Edit: Not quite over, but it was 3v2 at that point, which is why there was an area where wolves weren't near to a player). (It was 3v3 on a medium map.) If the 200m radius failed I used all targets plus the sorting fix, so the hashes still match.

I didn't test any other radii, but maybe even a smaller value would be reasonable? Or letting wolves be idle if there's no targets nearby? But e.g. looking around 75 or 145, it seems maybe there's not really any more lag to eliminate; the remaining spikes are there because there's more units and more activity.

Here's the final version I used. I only tested it with the medium 3v3 Petra game.

In D185#33735, @temple wrote:

You mean adding a query for every attacker?

One query for each group of attackers (since a bunch of wolves are spawned at the same position).

huge typo

Oh dear, splice vs slice again.

If a player had been wiped out, the wolves spawned down there should be able to move to the other side of the map.
So doing a 200m radius search first and then a complete query would be ok.
The graphis look however like the range queries are negligible.
So that optimization is only useful if its like < 5 lines of code.
Oh I copied that already from some damage dealing component?
If you want to upload a patch combining all the performance optimizations we have figured out, you can commandeer the revision proposal as you can see that Im not too motivated to work on this patch :P

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://jenkins-master:8080/job/phabricator/1959/ for more details.

Thanks for the patch and review!