Jump to content

less precise sorting in range manager


Recommended Posts

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.

Link to comment
Share on other sites

Posted (edited)

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 by real_tabasco_sauce
Link to comment
Share on other sites

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. :)

Link to comment
Share on other sites

Posted (edited)

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 by real_tabasco_sauce
  • Like 1
Link to comment
Share on other sites

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;
}

 

  • Like 1
  • Thanks 1
Link to comment
Share on other sites

Posted (edited)
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 by real_tabasco_sauce
Link to comment
Share on other sites

Posted (edited)

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 by real_tabasco_sauce
  • Thanks 1
Link to comment
Share on other sites

 

@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
image.thumb.png.ad67e4b36b659442bf6020c0f9bfcb88.png

image.thumb.png.39396bea2cdc4daf8cc85495d38c367e.png

 

Edited by guerringuerrin
Link to comment
Share on other sites

Posted (edited)

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 by real_tabasco_sauce
Link to comment
Share on other sites

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

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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

 

  • Like 1
Link to comment
Share on other sites

On 24/06/2024 at 10:03 AM, Stan&#x60; 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.

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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.

  • Like 1
Link to comment
Share on other sites

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. 

  • Like 1
Link to comment
Share on other sites

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.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

 Share

×
×
  • Create New...