less precise sorting in range manager

[real_tabasco_sauce]

13 minutes ago, Stan` said:

So... It's worse than without the patch?

Yeah, i think slightly worse, but its hard to say. It would be great if @wraitii could profile it. I modified EntityDistanceOrdering, which is used by all the different range queries, so its possible this version could be used in less locations.

Also, I do whole division after finding the square root:

u32 r2 = isqrtEst64(d2,P)/(100000*P);

but it might be faster to find the sqrt after whole number division.

[Stan`]

In a non visual replay iirc isqrt takes about 1% of a match.

[real_tabasco_sauce]

Wow thats huge. I tried replacing the isqrt64() in FixedVector2D.Length() with my isqrtEst64() with P=1 and got teleporting units and a game crash.

In theory, the new sqrt with P=1 should be exactly the same as isqrt(), so maybe Ill need to compare the two to figure out what happened above.

Edited June 25 by real_tabasco_sauce

[Stan`]

32 minutes ago, real_tabasco_sauce said:

Wow thats huge. I tried replacing the isqrt64() in FixedVector2D.Length() with my isqrtEst64() with P=1 and got teleporting units and a game crash.

In theory, the new sqrt with P=1 should be exactly the same as isqrt(), so maybe Ill need to compare the two to figure out what happened above.

A good question one should ask is whether all the calls to that function are justified, whether they can be cached or batched.

[real_tabasco_sauce]

Ok, so I was checking the isqrtEst64 against isqrt(), and they are exactly the same when P = 0.

However, because I am using SLD2's "SDL_MostSignificantBitIndex32(n)" to get log2, large integers overflow.

u64 sqrt_lo(const u32 n) noexcept
{
	u32 log2floor = SDL_MostSignificantBitIndex32(n);
	return (n != 0) << (log2floor >> 1);
}

u32 isqrtEst64(u64 n, u8 P = 0)
{
	u32 est = sqrt_lo((u32)n);
	u32 b = (u32)n;
  ...

The nice thing is the larger values don't occur in fights, I guess they happen in map generation and pathing, probably a lot of other things. As far as I can tell, the patch is working, but I am sure there are more improvements possible.

So @Stan` I would need to come up with a 64 bit equivalent to SDL_MostSignificantBitIndex32(n) in order to see if this sqrt approach could be faster than the current isqrt().

Edited June 27 by real_tabasco_sauce

[Stan`]

int reverseMostSignificantBit(uint64_t n) {
    if (n == 0) return -1; // If n is 0, there is no significant bit set.
    
    int msb = 63; // Start with the highest bit position (63 for 64-bit numbers)
    uint64_t mask = 1ULL << 63; // Initialize the mask to check the highest bit
    
    while (mask > 0 && !(n & mask)) {
        msb--;
        mask >>= 1; // Move the mask to the next lower bit
    }
    
    return msb;
}

That's a naive way for that function. I must say I'm not yet convinced of your approach but we'll see.

Another simpler version depending on the number size, might make a speed difference.
 

int mostSignificantBit(uint64_t n) {
    if (n == 0) return -1; // If n is 0, there is no significant bit set.
    
    int msb = 0;
    while (n >>= 1) {
        msb++;
    }
    return msb;
}

 

[real_tabasco_sauce]

ok, I got a 64 big equivalent working, and I tested every isqrt() call against isqrtEst64(), and not once was there a difference. Do you think I should just wing it and replace the old isqrt()?

[Stan`]

Well is it faster ?

[real_tabasco_sauce]

35 minutes ago, Stan` said:

Well is it faster ?

After a couple of combat demo huges, it seemed a little faster, but that's just anecdotal. Also, i don't know if my build was making use of the builtins, so it may be better or worse than what I experienced for some players.

I uploaded the latest version (with the isqrt64() replacement). 

Edited June 28 by real_tabasco_sauce

[real_tabasco_sauce]

ok, well the patch is pretty much done and working: https://code.wildfiregames.com/D5282

if anyone can apply it (and build) to test on their system that would be great!

[guerringuerrin]

@real_tabasco_sauceI'd be happy to test it, but I'd need some guidance on how to apply the patch. 

[real_tabasco_sauce]

Ok so the way I do it is this:

1. in phabricator(https://code.wildfiregames.com/D5282), click "Download Raw Diff", this will open a plain text file in your browser.
2. Copy the contents of the file
3. navigate to your SVN directory
4. Paste the contents into a new file with the extension '.diff'
5. type 'svn patch ABC.diff'

now at this point, some files should print to console with 'U' for updated. bigger patches might have conflicts, but that shouldn't be the case here. Since this patch modifies the engine, you will need to also build the game: https://trac.wildfiregames.com/wiki/BuildInstructions

Edited June 30 by real_tabasco_sauce

[guerringuerrin]

 

@real_tabasco_sauceTy.

I've been busy these days and couldn't put my hand to work.

I've done what you told me. This is how the folder looks right now.

I've already patched the .diff and built the game (a27)

But I'm not sure how to start testing. I share you also a screenshot of the SVN results

 

Edited July 1 by guerringuerrin

[guerringuerrin]

I share here a video with an attempt to test it
https://drive.google.com/file/d/1qGB6c_KsmjwhgiB01P3bxbENO6prCQqI/view?usp=sharing

[real_tabasco_sauce]

Ok, in order to see what's going on you will need to turn on the developer overlay (alt+d) and then select range overlay. Ok, yeah looks like its working fine. I'll be on later today and we could do a 1v1 on the patch if u like. It would be nice to see how the differences impact things like rushing and raiding, as well as other kinds of fights.

Edited July 1 by real_tabasco_sauce

[guerringuerrin]

5 minutes ago, real_tabasco_sauce said:

Ok, in order to see what's going on you will need to turn on the developer overlay (alt+d) and then select range overlay.

Yeah, sorry. I've found the option. In my next post there is a video with range overlay activated

[guerringuerrin]

8 minutes ago, real_tabasco_sauce said:

I'll be on later today and we could do a 1v1 on the patch if u like. It would be nice to see how the differences impact things like rushing and raiding, as well as other kinds of fights.

Sure thing! I have an hour to test this whenever you are available. Just send me a PM i'll be checking my inbox

[real_tabasco_sauce]

Ok I had a thought: The same thing happens with LOS range queries. The closest unit is chosen as the target even if the target is just a tiny bit closer than many other targets.Take this as an example:

Spoiler

 

 

Now compare it to the behavior when we use P=3. Its a bit of an exaggeration to see the effect. I think it would work better at p = 2.

Spoiler

 

 

 

[alre]

On 24/06/2024 at 10:03 AM, Stan` said:

The game uses integers for its calculations, because floating point are note reliable on different machines, so we need to have the exact same values on each machines else the game will go out of sync pretty quickly. So I suppose what you are seeing are decimal values represented as int.

so all position data is integer values? does this mean that each turn units movement is rounded down according to isqrt? just curious.

[real_tabasco_sauce]

4 minutes ago, alre said:

so all position data is integer values? does this mean that each turn units movement is rounded down according to isqrt? just curious.

yes, but the integers are huge, so there is basically no issues with rounding. I can't tell if isqrt produces floor(sqrt(x)) or some other rounding.

[real_tabasco_sauce]

In sniping testing with @guerringuerrin, 11 40 vs 40 han xbow fights with P = 2 resulted in a mean victory of @real_tabasco_sauce +1.9 soldiers remaining (I was sniping, @guerringuerrin did attack move).

In our vanilla control, sniping won all 5 battles, with an average of 12 remaining soldiers.

So we have partially succeeded at least in the case of crossbows in making sniping less impactful.

[real_tabasco_sauce]

 

Vanilla^

Rough sort>

 

Edited July 8 by real_tabasco_sauce

[wowgetoffyourcellphone]

The 2nd video would create better looking battles and have less auto-focus fire.

[chrstgtr]

Is there any downside here? It seems like a slight performance upgrade and, at worst, even play mechanics. 

I'm skeptical on how much this will actually help fix the sniping meta. But I see no reason why this shouldn't be implemented. 

[real_tabasco_sauce]

1 hour ago, chrstgtr said:

Is there any downside here? It seems like a slight performance upgrade and, at worst, even play mechanics. 

I'm skeptical on how much this will actually help fix the sniping meta. But I see no reason why this shouldn't be implemented. 

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.