Navmesh / Pathfinding WIP

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

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
if i were to take a guess it would for sure be that heap implementation. i didn't really brown townyze the algorithm all too much, i just measured its runtime over a few hundred nodes. calculations involving more than like 100 nodes would take about 1 ms to compute on my laptop iirc, which for me was too slow to use it in-game. i imagine that if you take some hints from how carbon zypher implemented his tree stuff, you could probably re-implement the heap to be way more performant. then, you'd be able to use the heuristic which would be super nice since you could do stuff like factor in the crouch/jump nodes into your distance calculations and pick the truly fastest route from point a to b

my solution in comparison to carbon's was to implement a* in python and then have that asynchronously calculate and then communicate the path using sockets. but, for a pure TS solution that would be problematic obviously lol


while (%enqCurrent > 0)
{
      %enqParent = (%enqCurrent - 1) >> 1;

      if (%frontierPriority[%enqCurrent] > %frontierPriority[%enqParent])
            break;

      // There's about half a million variable assignments going
      // on here. How can this be improved?
      %enqTempItem = %frontierItem[%enqParent];
      %enqTempPriority = %frontierPriority[%enqParent];
      %frontierItem[%enqParent] = %frontierItem[%enqCurrent];
      %frontierPriority[%enqParent] = %frontierPriority[%enqCurrent];
      %frontierItem[%enqCurrent] = %enqTempItem;
      %frontierPriority[%enqCurrent] = %enqTempPriority;

      %enqCurrent = %enqParent;
}

looks like a heap deletion operation in port's spatial a*. doesn't look too fast for me, lol. obviously some work would have to go into finding out the best way to do something like this. TS is weird when it comes to variable assignment/access speed lol. globals might be faster here, but idk. i've long since forgotten the quirks of torque
« Last Edit: August 05, 2020, 11:12:13 AM by Gytyyhgfffff »

im still surprised you didn't settle for 1ms because that's incredibly good for torquescript imo. with caching and a few minutes of playtime you could probably just eliminate the search altogether at the cost of memory

im still surprised you didn't settle for 1ms because that's incredibly good for torquescript imo. with caching and a few minutes of playtime you could probably just eliminate the search altogether at the cost of memory
eh from experience doing that for a large amount of bots is trouble. if 30 bots need to path that's one tick of server time entirely used up (which happens more often than you might think). plus caching in my situation might not have given too many performance benefits, since you were constantly opening up new areas of the map that weren't cached yet

since you were constantly opening up new areas of the map that weren't cached yet
oops lol i told you to uninstall the delete launcher man

idk if this is feasible but couldn't you calculate beforehand certain nodes' pathing and store that? i mean you could generalize whole areas to 1 or 2 optimal pathways between other areas

imma make an example tomorrow morning when i get to my pc

idk if this is feasible but couldn't you calculate beforehand certain nodes' pathing and store that? i mean you could generalize whole areas to 1 or 2 optimal pathways between other areas
Paths are cached yeah, not sure about the second part, sounds like a manual job if I'm understanding

communicate the path using sockets
Could you elaborate on this if it's not too much trouble? I still plan to develop a working TS solution but sending data from TS to an external program is something I'd like to look into

nah forget that i just dowloaded a stuffty mobile ms paint equivalent



basically if you want to go from node in top to node in bottom you don't have to calculate any nodes in between red, and if you have an area full of nodes that all have to go to one node to travel to another area you can just store that node's paths to other "fast travel" nodes


Implemented port's A*





Weirdness in the lines is just me being lazy while writing the line function, shouldn't be difficult to get right edges

Could you elaborate on this if it's not too much trouble? I still plan to develop a working TS solution but sending data from TS to an external program is something I'd like to look into
https://github.com/bansheerubber/Server_MiniDungeons/tree/master/pathfinding
https://github.com/bansheerubber/Server_MiniDungeons/blob/master/ai/pathfinding.cs
i create a server in python and send over all node/neighbor data to the server which it then stores itself. whenever i need to path between one position and another, i send a request to that server which then runs the A* path itself async to blockland. means no server lag at all since all the tough calculations are happening async and most likely even on a different cpu core. i didn't implement any common A* optimizations at all and its still really quick for thousands of nodes since its not torquescript

should also be noted that one of the things you can abstract to a program like this is find closest node logic (which i haven't done yet), although i suspect that won't be too hard to do in TS, especially using the quad-tree stuff you already got going

beware, its sort of half-assed and doesn't really handle common errors very well, for sure still needs work
« Last Edit: August 06, 2020, 01:09:08 PM by Gytyyhgfffff »

i create a server in python and send over all node/neighbor data to the server which it then stores itself. whenever i need to path between one position and another, i send a request to that server which then runs the A* path itself async to blockland. means no server lag at all since all the tough calculations are happening async and most likely even on a different cpu core. i didn't implement any common A* optimizations at all and its still really quick for thousands of nodes since its not torquescript
imagine doing genius stuff like this just to get around some simple game engine limitations

does this mean that bots wont be half handicapped when it comes to everything they do
also Node graph out of date. Rebuilding...

https://github.com/bansheerubber/Server_MiniDungeons/tree/master/pathfinding
https://github.com/bansheerubber/Server_MiniDungeons/blob/master/ai/pathfinding.cs

Really excellent reference, thank you for this. Just finished setting up a small C# server and sent and received data from Blockland, I might be able to move a bunch of slow navmesh functions over to it. I'll continue working on the TS solution until it's feature complete but I don't see much more progress being made in efficiency in TS lol

does this mean that bots wont be half handicapped when it comes to everything they do
Just quarter handicapped
« Last Edit: August 07, 2020, 12:18:37 PM by Crook »

Got storing nodes in C#, sending nodes to Blockland from C#, and collapsing nodes in C# figured out today.

Tomorrow I want to tackle sending brick bounding information over to C#, so I can do all the node calculations there. To replicate containerBoxEmpty I guess I'm just going to store all the bricks in memory by their bounding box and check to make sure none of them intersect with the container box.

This will end up as a nested loop though when generating nodes for every brick though, how could this be improved?

can you add bsmod executions to blockland