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

I'm working on navmesh again for Blockland. Thanks to the local torque wizards at BCC, I have made great strides since my last attempt and I can now actually link nodes together in a reasonable amount of time on meshes that have variable node sizes.



Will post updates in this thread. Or dump code if I abandon it. To be honest I'm really just trying to pressure the guys that have already made this and are keeping it to themselves into releasing it.



There's a lot of optimization to be done but the fact that my computer isn't exploding right now is a huge step in the right direction probably

because pathfinding only needs at least one node for each object's line of sight, its better to focus less on generating nodemaps and rather letting people build them manually. it's still cool though but it's always going to be very inefficient when compared to hand-placed node mapping.

ex: bottom right roof has at least 50 nodes on it and almost the same amount of paths that need to be traversed every iteration. it could be refactored into just one node in the middle of the roof and then you can let the ai follow based on direct line of sight, which will always be fastest. if you need extra ai capabilities like more complex movement and avoiding cliffs, you can just code that directly into the ai itself rather than let the pathfinding bear the brunt of the iterations. alternatively, you could use a second layer of nodes that the ai will use under certain conditions, ie in combat, put nodes behind boxes so that bots can take cover, or nodes for crouching under objects, etc. that would require using weights and heuristics, and on a generated node map like that, would basically slow everything down really quickly
« Last Edit: August 01, 2020, 10:51:03 PM by PhantOS »

also looking at the photos gave me this wild idea for a mod that loads and refactors a map using the largest bricks available, to reduce brickcount. idk if this exists already but it should. call it 'superpack'
« Last Edit: August 01, 2020, 10:43:54 PM by PhantOS »

because pathfinding only needs at least one node for each object's line of sight, its better to focus less on generating nodemaps and rather letting people build them manually. it's still cool though but it's always going to be very inefficient when compared to hand-placed node mapping.

This is still being worked on btw. I agree that it's probably the best solution. It's in a pretty good place right right now, I have successfully saved and loaded nodegraphs I made by hand with a tool



My complaint; it's extremely time consuming mapping out even a map as small as Afghan by hand. I suppose Afghan has a lot of nooks and crannies though, and the flow will be improved in the future. The new shapelines library will help with this. When complete, you should be able to generate a nodegraph and then edit it by hand to reduce the amount of garbage nodes.

On that note: I haven't done any work in combining nodes. I'm avoiding it because it's scary

yea doing it by hand is super tedious but its part of good level design. you could also just skip nodes entirely and use planes and triangulation to build paths. ideally it would supplement the iteration for recursive geometry math and because the planes are larger than nodes, you can divvy them up into zones so that the pathfinder can avoid searching over parts of the map that are guaranteed to not connect. with nodes the pathfinder can just accidentally search through an entirely different tree of paths that don't lead anywhere important and waste processing time, since each algorithm has its own pros and cons dependent on the nodemap's design

« Last Edit: August 01, 2020, 11:08:34 PM by PhantOS »

you could also just skip nodes entirely and use planes and triangulation to build paths.
Could you elaborate on this?

posted pics. in theory the navmesh triangulation makes it so you can control how accurate it should be and you can approximate either stuffty paths quickly or great paths slowly.



this is a non-ideal generation. the parts that aren't triangulated will be inaccurate but you can see for like the corridors it's not necessary to even triangulate in the first place. also its possible to have paths that intersect through parts of the map like where the red squares are. that requires some extra work to solve, but since its all geometry based it's pretty straightforward. also no raycasts/collision checks required, you can check overlaps/OOB paths purely with intersection math. there may be some surface approximation involved

it [may] be easier to generate from a bls save too than with nodes but I have no proof of that
« Last Edit: August 01, 2020, 11:15:49 PM by PhantOS »

Had success in node collapsing today








3.5 seconds to generate linked navmesh on ATC Fort

holy stuff. incredible

im collapsing at how good this is wtf

The node collapsing algorithm leaves much to be desired: There's many instances where nodes can be collapsed further and it's probably more time complex than it needs to be. However, it's certainly worth it. Generating node links on Afghan was a process that used to take around 47 minutes, it now takes less than 20 seconds.





If those green lines look like nonsense don't worry, they are, they only show which nodes shared a boundary, they're not the final paths bots will take




For real though, this is some advanced stuff i didn't think Blockland (or Torque for that matter) would be capable of

This is a very neat project!
 
[img height=300 ]https://3.bp.blogspot.com/-EOowSVy8V-8/VS1t0OHHyHI/AAAAAAAAB7Y/CHpaXqjtXkE/s1600/Untitled.jpg[/img]
For real though, this is some advanced stuff i didn't think Blockland (or Torque for that matter) would be capable of
It's possible for sure, but efficiency is our issue. I see people shift bit numbers around, or use local/global variables. Methods matter! Of course.. DLLs are an option to process calculations faster.
When I was hosting Tower Defense a few months ago I ran into issues, mainly because script object path finding and using more script objects for node locations. This inspires me to fix the pathfinding I had.

I wanted to eventually make a boundary node system where what you plant is where it goes but cannot pass itself, lets say you make a ring and an inner ring so the bots cant use the middle or vise versa