Efficient way to find the closest position from a list

Hello,

first thanks for this tool, I’m having great fun using it so far.
I ran into an issue and the solution I found worry me as it may really impact the game performance.

In my game I have “builder” unit that can be ordered to build blocks in a grid.
I want them to always work on the closer block to build.

So far I’ve done this using StartMultiTargetPath with the list of blocks to build in parameters, but from what I understand the method is asynchronous for performance reason. Also if no path is found the current movement is stopped.

So in order to make it fit in my code I used BlockUntilCalculated method and that’s where I’m afraid of consequences.

Is there any more appropriate way to get the closest block? Note that I may have to use similar method in lots of places in my game.
Should I completely rework my ai system in order to retrieve this info asynchronousely? Or should I just stick to traditional Vector3 distance calculation even if result may be innacurate sometimes?

Thanks in advance for any advice you could give me

Hi

Have you profiled this and found it to be an issue?

That method is the best one to find the closest node of a list of multiple options. I do have some improvements planned for it which should give it a speed boost in some cases though.

Thanks for your answer!

No at the moment this is just theoritical. I’m not very familiar with the plugin yet and just wanted to ensure there were no better way to handle this specific case.

I’m just afraid that BlockUntilCalculated lead to freezes as I’ve to do this many times per second (9 right now) for multiple builder units, to ensure they’ll always target the right block. Because blocks to builds are set by user inputs and it can change frequently.

Ok. Yeah it can definitely be a problem, but it’s very hard to say without some testing. Try to configure a simple test and check the performance of it.

Okay, so after some testing here’s what I can see:

I’ve created a test scene with 20 builders that will have to build 128 blocks

With pathfinding activated:

var l_multiPath = m_seeker.StartMultiTargetPath(transform.position, l_blockPositions, false);

l_multiPath.BlockUntilCalculated();

if (!l_multiPath.error)
{

//If we found one
var l_path = l_multiPath as MultiTargetPath;
if (l_path != null && l_path.path != null && l_path.targetNodes[l_path.chosenTarget] != null)
{

//Retrieve the block in map using its position
TargetBlock = GetNearestTargetableBlock(l_path.targetPoints[l_path.chosenTarget]);

}

}

min fps 19 / max fps 45 / avg 31

With no pathfinding:

TargetBlock = GetNearestTargetableBlock(l_blockPositions[0]);

min fps 27 / max fps 60 / avg 47

So it is quite heavy, any advice?

Hi

Okay.
Is your pathfinding graph static or changes very rarely? I would guess no because you have builders, but I suppose I can always ask.

Do you run the code to search for the closest block every frame for every worker or do they only do that search when they are finished with a block?

First thanks again for your time, I know how time consuming this can be so I really appreciate your support.

The graph is a grid graph that I will locally update each time a block is builded (or destroyed)

I do not run it ever frame but I have to do it quite often, my current sweet spot is every 0,11 seconds.
It has to be so often because if the player deselect a block or reselect it, I must always ensure that the builder has a valid target and look reactive enough.

But more importantly in the case where a builder destroy a block, I have to make sure it will be able to target any new accessible block that were behind it after the grid was updated.

Here are 2 gif to better illustrate the issue:
With 1 sec refresh period

With 0.11 sec refresh period

Okay. Wouldn’t it be best for reaction time to make sure you update it immediately after a block has been destroyed (and possibly when a player selects/deselects a block)?

As for block selection it may be possible this way indeed, I’ll check.

Now you made me realize that I’ve previously added a delay to the graph update after destroying a block.
Because my mesh was not updated immediately but during next LateUpdate.

Anyway you put me on the right tracks, I’ll clean up my mess and try to come up with a more efficient way to deal with this, thanks again!

1 Like

Okay. In case you need to in the future, there are a few more tricks that can be used to improve performance. But it’s probably best to focus on what matters: the game, before digging too deep into optimizations that may not be necessary.

indeed, just wanted to make sure I was using the right tool for the task