less precise sorting in range manager

[chrstgtr]

2 hours ago, real_tabasco_sauce said:

Well, it is hard to say on performance: On one replay, I got a pretty sizeable improvement, but on a few others, it's been basically the same. @phosit had a significant detriment to performance on one replay. There are probably a few things that can still be done to optimize it.

Still sounds like little downside. Benefits just might be narrow. 

[Stan`]

It could also be a compiler difference @phosit is using GCC while @real_tabasco_sauce is using MSVC. Maybe gcc has a harder time optimizing that specific code (would be a first, since it's usually the converse but who knows)

The more logical explanation is the cause of the slowdown is not correctly identified, could be the sorting, could be the computation or something else.

[real_tabasco_sauce]

The current version works like this, where near by units are evaluated with precision, and P controls how fast the margin grows with respect to distance:

The values above are arbitrary, just to illustrate. For a value to be sorted over another, it must surpass the other length^2 on the red line, and for a value to be considered lesser, it must be less than the other length^2 on the blue line.

So this means the effect is more noticeable at larger ranges where a single unit is more likely to be considered the closest by many ranged units (or melee units).

[real_tabasco_sauce]

Still working on this, the new version (2, blue) is a bit better. It works without any division, and lets the P value equate to a percent error: 1 -> +/-10%, 2-> +/-20% 3 ->+/-30%

Edited July 29 by real_tabasco_sauce

[guerringuerrin]

my results

[real_tabasco_sauce]

@Effervescent's results:

[real_tabasco_sauce]

@Stan` @phosit would you say these graphs are better, worse, or about the same in terms of performance? My goal is that it can be pretty much the same for everyone.

[guerringuerrin]

New test. Same Specs:

Edited August 5 by guerringuerrin

[real_tabasco_sauce]

If another volunteer or two could profile this patch, I'd be super grateful!

[Stan`]

4 minutes ago, real_tabasco_sauce said:

If another volunteer or two could profile this patch, I'd be super grateful!

Hey, I haven't looked in details but if the goal is to improve performance this looks like a bad target to me. You've invested a lot of energy in this which is nice, but maybe you should shelve it for some time ? Given the current activity I do not want you to burn all your energy on this while you've been doing great for the rest.

If this is a major gameplay improvement that's another matter but maybe integrating some of autociv units and building hotkeys could be worthwile too

Anyway just a heads up

[real_tabasco_sauce]

6 minutes ago, Stan` said:

Hey, I haven't looked in details but if the goal is to improve performance this looks like a bad target to me. You've invested a lot of energy in this which is nice, but maybe you should shelve it for some time ? Given the current activity I do not want you to burn all your energy on this while you've been doing great for the rest.

If this is a major gameplay improvement that's another matter but maybe integrating some of autociv units and building hotkeys could be worthwile too

Anyway just a heads up

The target isn't performance, I just want to avoid making it worse. I think its a significant gameplay improvement, as it really helps with melee units not all pathing to try and hit the first unit when there are other targets nearby (see the video I posted on page 2). Also, it helps for ranged units to not all shoot the closest unit when there are others really close behind. So for ranged units, it elegantly avoids overkill.

I suppose it also looks more cool/realistic as @wowgetoffyourcellphone pointed out earlier.

The improvement will be the best for han crossbows which experience overkill when more than 3 xbows hit an enemy ranged unit, or more than 6 xbows hit an enemy melee unit.

That being said, its not a huge departure from the way fighting works, and it may not be noticeable to the casual player. There are also possible gameplay downsides to choosing too large a P for a unit, like spreading damage too much over units. However, if one unit should be targeted, the typical player will specifically attack that unit anyway. And, with the P values being determined in the templates, any undesirable behavior can be adjusted or removed on a per-unit basis.

[Stan`]

One thing you could try instead of hacking existing functions is to add new ones. Maybe the if switching depending on p has an impact

[real_tabasco_sauce]

35 minutes ago, Stan` said:

One thing you could try instead of hacking existing functions is to add new ones. Maybe the if switching depending on p has an impact

Hmm, well the rough sort is a new function. If no P value is used in the template, then the regular full-precision sorting is used.

[Stan`]

25 minutes ago, real_tabasco_sauce said:

Hmm, well the rough sort is a new function. If no P value is used in the template, then the regular full-precision sorting is used.

Yeah my point was calling that new function directly from js to remove the if test.

[real_tabasco_sauce]

17 minutes ago, Stan` said:

Yeah my point was calling that new function directly from js to remove the if test.

So you mean when a P exists, unitAI.js should call a separate query setup/activation function(s) in Rangemanager and use a separate EntityDistanceOrdering?

Or do you mean using the function to re-sort an existing set of targets within UnitAI.js?

[Stan`]

Quote

So you mean when a P exists, unitAI.js should call a separate query setup/activation function(s) in Rangemanager and use a separate EntityDistanceOrdering?

Dunno about should but might be worth checking

 

[real_tabasco_sauce]

yeah I think this would be really helpful for Han crossbows in particular. When 50+ crossbows all shoot 1 unit because its a tiny bit closer than the others, its effectively almost 4 seconds of no damage dealt by the crossbows.

I'm looking forward to porting it over to the gitea

[real_tabasco_sauce]

On 14/08/2024 at 12:35 PM, Stan` said:

Yeah my point was calling that new function directly from js to remove the if test.

Do you think the 'if' in EntityDistanceOrdering is wasteful (since it is done for each unit and each target)?

I could move it out to where the stable_sort()'s are called and make an EntityDistanceOrderingRough, but this would be a little bit redundant code wise.

[Stan`]

Maybe. But in these cases it's always better to know and test than to think. For instance my intuition would be that we should reuse all the queries results that happen on the same turn at almost the same location. Compute them once instead of 400 times and return slightly less accurate data. But it might be that this simplification could cost more than doing it 400 times.

[real_tabasco_sauce]

3 hours ago, Stan` said:

Maybe. But in these cases it's always better to know and test than to think.

Ok, I'll go ahead and try it. As long as some semi-redundant code is ok.

3 hours ago, Stan` said:

For instance my intuition would be that we should reuse all the queries results that happen on the same turn at almost the same location. Compute them once instead of 400 times and return slightly less accurate data. But it might be that this simplification could cost more than doing it 400 times.

But if a unit got another unit's target data, they would choose the same target no? I suppose its trading the task of finding nearby enemies for finding nearby units, but maybe it could be a future improvement.

[real_tabasco_sauce]

my goodness, it made computeShortPath suuuuper slow. Green is with the if moved to the functions that call entityDistanceOrdering.

Blue is the patch as is, with the check for P inside entity distance ordering.

Edited September 1 by real_tabasco_sauce

[real_tabasco_sauce]

 This is with a higher P value (P = 5, so +/-25% error) for demonstration purposes. To be honest I think its pretty close to ideal for xbows. I went with P = 4 in the PR: https://gitea.wildfiregames.com/0ad/0ad/pulls/6960 Edited Tuesday at 23:08 by real_tabasco_sauce