Navmesh / Pathfinding WIP

Author Topic: Navmesh / Pathfinding WIP  (Read 15477 times)

refactored node collapsing, new benchmarks
ATC fort: ~1300 milliseconds
Afghan DM: ~188 seconds (about 3 minutes)

Additionally - saving/loading generated graphs is working. The idea would be to generate the navmesh once and load it thereafter, Afghan DM's nodes save in ~400ms and load in ~1300ms. I'm not really a data guy though so that's probably pretty slow

will there be integration with other mods to add distinct node types?

ie if im making a slayer ctf or point capture could slayer/i add a special node for the flags/points?

Shouldn't be too difficult to pass nodes an attribute from the brick they generate on. There's already one type of special node - crouch nodes, to tell bots when they need to crouch under something. That's handled in the bot AI which will be extensible by mod authors


At the cost of extra node placements, we can determine which ledges can be jumped to




Wow mate, this is actually some impressive pathfinding navmesh you are developing right here.

So what pathfinding algorithm are you having intentions of working with for this navmesh you are currently designing;
Dajikstra, A* or some variant of these algorithms?

Either way, I can't wait to see what new comes up with this in your freetime. Keep it up!

So what pathfinding algorithm are you having intentions of working with for this navmesh you are currently designing;
Dajikstra, A* or some variant of these algorithms?
I believe Port already has an A* algorithm implemented in TorqueScript, I don't think it'd be too much work to get them to work together. If not I'll reference it to write my own A*. Theoretically any algorithm that uses linked nodes should work

You are doing god's work. Keep it up.

I believe Port already has an A* algorithm implemented in TorqueScript, I don't think it'd be too much work to get them to work together. If not I'll reference it to write my own A*. Theoretically any algorithm that uses linked nodes should work
for reference, that algorithm is generally pretty slow when it comes to lots of nodes. i know that carbon zypher experimented with depth first search and it ended up being way quicker, could find paths through thousands of nodes in a millisecond instead of just hundreds. might be worth looking into that
« Last Edit: August 04, 2020, 10:03:38 PM by Gytyyhgfffff »

it might also be a good idea to use multiple algorithms and switch between them based on how many nodes are on the map or the structure of the map, if you really want performance

Additionally - saving/loading generated graphs is working. The idea would be to generate the navmesh once and load it thereafter, Afghan DM's nodes save in ~400ms and load in ~1300ms. I'm not really a data guy though so that's probably pretty slow
that's pretty good

for reference, that algorithm is generally pretty slow when it comes to lots of nodes. i know that carbon zypher experimented with depth first search and it ended up being way quicker, could find paths through thousands of nodes in a millisecond instead of just hundreds. might be worth looking into that
Thanks for the tip, Afghan DM has many nodes even after collapse so I'll look up depth first. Is carbon zypher's code public?

it might also be a good idea to use multiple algorithms and switch between them based on how many nodes are on the map or the structure of the map, if you really want performance
Should actually be somewhat simple, I've been trying to keep everything relatively modular


Thanks for the tip, Afghan DM has many nodes even after collapse so I'll look up depth first. Is carbon zypher's code public?
it isn't but you could probably discord him if you want details. iirc, he used a long string using setWord, removeWord, etc to construct and iterate through the tree. he got pretty good speed from it

arrays might also be a great choice instead of script objects

for reference, that algorithm is generally pretty slow when it comes to lots of nodes. i know that carbon zypher experimented with depth first search and it ended up being way quicker, could find paths through thousands of nodes in a millisecond instead of just hundreds. might be worth looking into that
can you explain why a* is slow in bl? is it the heap? sounds like the issue is less a* and more no good heap implementation, but that seems like it could be easily fixed via a binary heap array implementation

the heuristic is meant to greatly reduce the spread + make the algo go in the right direction so i cant imagine why dfs would perform better, especially on big nodemaps where it’s likely for the dfs to go the wrong way for a long time. unless you aren’t searching for shortest path in which case i *guess* it would be faster than a* at the cost of making the bot possibly taking nonsensical paths
« Last Edit: August 04, 2020, 11:49:08 PM by Conan »