Preload function Distance

[Antizombie]

I preloaded the Distance function, it should speed up the calculations a bit. (I couldn't measure if it got better/worse)

Also added a "simple" path cache so that when bots travel short distances or use the same path, they can use the already "cached" version. If there is no RAM limitation, you can increase the MAX_CACHE_SIZE to save more paths. I also took the GAMEMODE:GetWave() out of the loop in this function.

Why not use DistToSqr instead of Distance? With DistToSqr, calculations will definitely be much faster, I tested this. But I can't say exactly how well the bots will work with this replacement.

[Dadido3]

I preloaded the Distance function, it should speed up the calculations a bit. (I couldn't measure if it got better/worse)

The main problem with gmod vectors is that they are userdata objects, and every time methods on these are called lua is running code outside its runtime. Which means that the optimizer has to assume that every globally accessible variable could have been changed, and therefore can't do some optimizations.

So your optimization is propably helpful, as the compiler can't optimize the metatable lookup otherwise. But no idea without testing.

Also added a "simple" path cache so that when bots travel short distances or use the same path, they can use the already "cached" version.

This is really helpful, as it reduces a lot of unnecessary computations. But the cache entries need a maximum lifetime. I would add "valid until" timestamp when a new cache entry is created, so that after some time the cache entries are invalidated and can be deleted.

This is needed for maps which rely on nodes being unlocked/locked after some time or specific conditions. Because if a cached path contains a node/link with a condition the cache entry does not represent the best path anymore. In the worst case it even contains a now illegal path. Also, bots may want to choose a different path if the node/link costs change over time.

Another thing is live testing when navmeshing, as you now can end up with cached paths which definitely don't exist anymore.

So it would be best to add a "valid until" timestamp and then some logic to delete invalid cache entries. The easiest way would be to just check the timestamp inside of get_path.

(Also add a way to change these parameters (max cache entries, max lifetime) in the config file, so server owners can easily tweak the values to their liking)

Why not use DistToSqr instead of Distance?

While it is true that the sum of the distances of the individual parts of a path is equal to the total distance of the path, this is not true for the squared distance. So when you use the squared distance in the heuristic it gives wrong results. The difference may not be noticable on most maps, but it will definitely break some maps.

[Dadido3]

I just benchmarked the changes (With caching disabled, as it's hard to benchmark with cached paths in a way that produce real world values).

It's a ~13% reduction in time spent for my standard test case (calc path on zs_infected_square_v1 from node 32 to 866). And that's mostly by putting Distance into an upvalue, as no other code paths are used.

Looks really good so far.

[Antizombie]

This is needed for maps which rely on nodes being unlocked/locked after some time or specific conditions. Because if a cached path contains a node/link with a condition the cache entry does not represent the best path anymore. In the worst case it even contains a now illegal path. Also, bots may want to choose a different path if the node/link costs change over time.

Yes, I did not think about the ways that will change. It is possible for a quick "solution" to simply not cache such paths. A model like mine partially solves this problem. Since the "cache" is updated constantly. But yes, there is no precision in such ways. As for me, an excellent "cache", but yes, for "static" cards. For normal zs / zm . Time would be a great solution. As for me, I would generally change the principle of finding a path. But I don't have enough knowledge how to do it. So far there is only an idea.

[Dadido3]

It is possible for a quick "solution" to simply not cache such paths.

This prevents paths that can become illegal (node/link condition that may block the path in the future) from being cached. But it will not help the other way around, like when a better path becomes available after some time. Because then the worse path is in the cache, but the better and new path will not be used.

Another thing i haven't thought about yet is that when the cached paths are inconstistent with the rest of the navmesh it can cause bots to not arrive at their target at all. The reason is, bots will recalculate their path every now and then. What may happen is the following loop:

1. Bot uses cached path to get from A to B.
2. Bot walks along its path, after some time it wants to recalculate its path.
3. Bot finds a better path, which goes through A because the weight/cost or conditions of the navmesh changed.
4. Bot walks along its new path, after some time it wants to recalculate its path while being near A.
5. Bot finds the old cached path that is not the optimal path, and will send it into the opposite direction.
6. This will continue and loop with step 2.

It's unlikely that something like this happens all the time, but it can happen. Just knowing this, there will be people stumbling upon this bug, or there will be specific maps which are more likely to provoke this. This calls for future bug reports and annoyed players.

And sure, the maximum number of cache entries reduces this problem a bit, as new entries will flush old ones out of the cache. But this is not predictable enough in my opinion, and relies on the fact that bots will find more start-destination pairs than MAX_CACHE_SIZE. Which may not be the case with a lower number of bots.

I also think it's better to have a lot of short lived cache elements than just a few long lived ones. RAM usage is not a problem, not even with like 1000 cached paths (Haven't measured it, but it can't be that much).

If you don't have time/motivation to add lifetimes to the cache, i could try it myself in the next few days or so.

As for me, I would generally change the principle of finding a path.

I'm not that much into path search algorithms either, so i don't know if there are any modern algorithms that would beat A*.

But what could be done is to split the navmesh into groups/clusters. Then you can do something like a quick search from cluster to cluster, and then refine the path inside the start and end cluster. It's a lot less nodes/links to check and could easily speed up pathfinding many times. Problems are just:

• How do you efficiently cluster the maps? This would need some research and an implementation.
• With changing conditions and costs the clusters would need to be updated regularly.
• The way conditions work right now would need constant updates as conditions don't store their state inside the node/link but are reevaluated every time a path is searched. This can be changed more or less easily, but is another thing that has to be done.
• Possible paths also depend on bot abilities (like pouncing), so there need to be some mechanic that represents that. Also not impossible, but something that has to be considered.
• More stuff i probably forgot.

[Antizombie]

Then I think it's better to leave only "Preload Function Distance"

[Dadido3]

Ok, you can leave the caching code in there and just disable reading/writing from the cache. I may revisit this in the future and reenable it once i made sure it has no side effects.

The 13% speedup alone is already a really good improvement on its own.

[Antizombie]

and "I also took the GAMEMODE:GetWave() out of the loop in this function."

[Dadido3]

"I also took the GAMEMODE:GetWave() out of the loop in this function."

Yeah, it may not have such a big impact, but it's definitely an improvement.

[Antizombie]

I removed caching

[Antizombie]

I think if we don't change anything in terms of how the calculations are performed, we could just cache the distance. And make sure to reset this cache when someone modifies the NavMesh.

[Dadido3]

This could actually work really well, so if you wanna test it feel free to open a new pull request.

You could even store the distance in the link object, so there is no need to do a slow map lookup. The only "slow" part is to iterate over all links and remove the cached distances when a change is done to the navmesh. But this is limited to navmesh editing anyways, and doesn't normally happen ingame.

[Antizombie]

This is a great idea to save it in NavMesh files. But it will increase its size, and we will need to make sure that in "old" NavMeshes where this data doesn't exist, it should be computed/written (preferably). Of course, I don't think it's a big problem (especially considering that I have "sv_d3bot_db" and synchronization between my six servers happens via SQLServer). The latest version is not stored on GitHub, but you can take a look. I can update it if necessary. https://github.com/Antizombie/mesnik/blob/main/lua/autorun/server/sv_d3bot_db.lua

[Dadido3]

No, i didn't meant to store it in the navmesh files, but the distance cache should be stored in every link object (in RAM). Just so it doesn't require a map lookup.

Also the cache doesn't need to be fully rebuilt at once, it only needs to be invalidated/deleted when the navmesh changes. The rebuild of the cache can happen piece by piece inside of GetBestMeshPathOrNil.

That's at least how i would do it.

[Dadido3]

I just did a quick test, and i get about 11% speedup when caching the link distances:

local blockedForward = (linkParams.Direction == "Forward" and link.Nodes[2] == node)
local blockedBackward = (linkParams.Direction == "Backward" and link.Nodes[1] == node)

if able and not blocked and not blockedForward and not blockedBackward then
    local linkDist = link.CachedDist
    if not linkDist then
        linkDist = Distance(node.Pos, linkedNode.Pos)
        link.CachedDist = linkDist
    end
    local linkedNodePathCost = minimalPathCostByNode[node] + mathMax(linkDist + (linkedNodeParams.Cost or 0) + (linkParams.Cost or 0) + (pathCostFunction and pathCostFunction(node, linkedNode, link) or 0), 0) -- Prevent negative change of the link costs, otherwise it will get stuck decreasing forever.
    if linkedNodePathCost < (minimalPathCostByNode[linkedNode] or mathHuge) then
        entranceByNode[linkedNode] = node
        minimalPathCostByNode[linkedNode] = linkedNodePathCost
        local heuristic = (heuristicCostFunction and heuristicCostFunction(linkedNode) or 0)
        minimalTotalPathCostByNode[linkedNode] = linkedNodePathCost + heuristic + Distance(linkedNode.Pos, endNode.Pos) -- Negative costs are allowed here.
        evaluationNodeQueue:Enqueue(linkedNode)
    end
end

It's a bit less than i expected. And the code isn't ready to be put into master, as it is missing cache invalidation on navmesh changes.

57