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

Crook · November 04, 2020, 10:09:56 AM

Quote from: Badspot on November 04, 2020, 03:26:33 AM

I love Wrathfinder and Rallypack. I am officially endorsing these addons because they are awesome

Thank you good sir

I have been working on the manual node gun again. Blue nodes/links are for crouching, orange links are jump or fall links, purple links are jump + crouch links. It allows you to 'invert' node and link placement so you can force jump and crouch links when needed
https://streamable.com/hv13em
https://streamable.com/iksntp

Re-implemented Port's A* as well as saving/loading
https://streamable.com/7ctah8

Ad Bot · Advertisement

Crook · November 04, 2020, 05:47:39 PM

Bot navigating a path
https://streamable.com/02w94y

PhantOS · November 04, 2020, 07:48:02 PM

good loving stuff

RockyDoctor65 · November 04, 2020, 07:53:04 PM

Now that's quality.

Gautier00 · November 04, 2020, 11:27:32 PM

Not that I have an issue with doing it manually but I'm just curious, is this made so you have to do it yourself? Or is this just improving their intelligence? I've already noticed you have the tools to make it yourself but I'm just curious how it fully functions.

Crook · November 04, 2020, 11:38:08 PM

Nodes can be automatically generated - it's the main goal of this project and also the biggest bulk of the work, however, automatically generated navmesh is always going to be inferior to manually created nodemaps. The AI will work on navmesh but will require a little more effort (navmesh nodes are of variable size and are linked via overlapping bounds, when directing a bot between two nodes we have to direct it to it's shared edge first)

For example the generator may be able to detect nodes that can be jumped to or dropped down to in exchange for an increase in processing time but almost certainly will not be able to detect things like jumping horizontal across gaps. In the end I hope for a hybrid system in which you can generate a bulk of the mesh and then add finer details with the node gun

Crook · November 06, 2020, 12:44:25 AM

^ following up with this, here is a bot navigating a path that crosses over both generated and manually mapped node maps. both systems are now working with each other pretty well
https://streamable.com/z5pz7n

Conan · November 06, 2020, 03:01:31 AM

kind of insane how much mileage you�re getting out of shapelines

pales in comparison with this stuff. looking forward to a beta release.

Crook · November 06, 2020, 10:07:06 PM

aye... yuh

Crook · November 07, 2020, 01:11:36 PM

Made a recursive generator that gives the user a heads up display about what the generator is doing so they know it's working and hasn't just crashed their blockland on meshes that take a couple minutes to create. you'll still be able to access the normal one though, which is faster.

here's an example of how the generator works in general
https://streamable.com/s33ck2

You can probably tell the algorithm for collapsing nodes isn't where it needs to be for good pathfinding. I would say it's very functional because it reduces the link generation time from 30 minutes to 12 seconds so it will likely remain this way for a while but I will revisit it after finishing other features.

I'm not really sure where to go from here. I think I'm going to make a zombie bot and maybe do a manual nodemap for afghan to ship with and then I'll probably release a beta

Crook · November 07, 2020, 01:57:07 PM

Quote from: Conan on November 06, 2020, 03:01:31 AM

kind of insane how much mileage you�re getting out of shapelines

Just wanted to say: Shapelines 2 is awesome, being able to reference a line after creation is pretty much the only reason I decided to pick up the manual node gun again

jackrobbman · November 07, 2020, 10:50:57 PM

Once this gets released, making maps with bots in mind is never going to be the same. Never again will I have to event over a hundred bricks just to account for variance and unpredictability in a bots path on a complex map. I can just make the freakin' map and go ham with nodes. You're doing good work sir!

Actually, I think I remember some guy messing around with pathfinding seven years ago. Dude was trying to create Xcom in Blockland and was only using the pathfinding to make bots go places with a click. I think he ran into a lot of the long load time problems you did, but he got busy and had to drop the project.

Oh! This reminds me of some questions! Let's say I have a straight line path set for a bot. When it sees an enemy, will it forget all about the path nodes and never remember them after it starts chasing a target? (I think it's hard coded for them to forget any evented behaviors once they spot an enemy) Also, will they pick the fastest path to their target? If I event a bot to go to a brick on the other side of a complex map like Afghan, will it use the nodes to get there? Or are you literally trying to make the Nodegun from Gmod that has goal nodes and all that? If so, would that have events like, onBotReachNode and stuff? I'm no coder, but all that seems like it'd be difficult to figure out.

PhantOS · November 07, 2020, 10:59:31 PM

a good (imo) model for deciding bot behavior is a separate class like 'NavBrain' (working title) that hooks into the nodemap and is a property on bots. then users could code (or select a premade) navbrain that decides the decision-making process for specific bots or the threshold of a node's score required for the bot to attack (wouldnt want a shotgun bot trying to snipe you just cuz he has line of sight!)

examples of deterministic navbrains:
soldier navbrain that places heavier decision weights on cover & only shoots when target is nearby or the cover score is high enough
zombie navbrain that weighs all the nodes closest to their target & other zombies as better destinations (hordes!)
squad navbrain that weighs destinations based on other squad bots and their angles to the target to execute flanking maneuvers

+ the ability to combine navbrains and score them together might add some really unique and complex bot behavior right out the box (2*sniper+1*melee navbrain = long range bot that will melee you if you get too close, multipliers to decide which navbrains are more important :))

even just one function like WeighDestination(Node n) that can be hooked and called by the bot's setdestination bs so anyone can insert the custom logic for deciding where the bot should move best at that given time. would work well if you could also assign tagged weights to nodes manually so if i wanted a top of a building to be a great sniper spot i could just designate all the nodes on the building as like sniperbrain+20 so any bot with a sniperbrain will prioritize positioning themselves on top of the building to shoot at players

the downside to this is that on big maps you'd have to arbitrarily decide if you want to weigh every destination or some but with a selective tag system it'd be pretty simple to just identify which nodes can be scored and which can't. so hallways for example might just be unweighted if the host wants it since bots wont really do much in hallways in the first place besides just pass through them. another solution is only scoring the destinations that are within radius of the bot and not the target and letting said bot just fumble its way to the target on its own decision-making logic

Crook · November 08, 2020, 03:06:24 PM

Did a bunch of work with the node gun today for better workflow, and a lot of attributes for links, including things like one way links, jump only links, weighted links for things like bots prioritizing a path or a road over other links
https://streamable.com/5axpck

Quote from: jackrobbman on November 07, 2020, 10:50:57 PM

Let's say I have a straight line path set for a bot. When it sees an enemy, will it forget all about the path nodes and never remember them after it starts chasing a target? (I think it's hard coded for them to forget any evented behaviors once they spot an enemy)

This is mostly up to the bot AI... for something like a zombie you'd probably want it to just break off the path once LOS is established and go attack the player and only use the pathing to get to the player. The idea here is to just make utilities for making nodemaps and the ability to pathfind through them, what bots do with it is entirely up to the end-user, though I will include a basic zombie AI bot and probably some events

Quote from: jackrobbman on November 07, 2020, 10:50:57 PM

Also, will they pick the fastest path to their target? If I event a bot to go to a brick on the other side of a complex map like Afghan, will it use the nodes to get there?

Yeah the pathfinder will always try to get the shortest path but it doesn't always get it right, sometimes paths are longer than they need to be, but it shouldn't be too big of an issue. As for sending the bot to another brick, we will most likely have to find the node closest to that brick, so it's recommended to put a node on that brick and link it to the rest of the map. Then it should work fine.

Quote from: PhantOS on November 07, 2020, 10:59:31 PM

even just one function like WeighDestination(Node n) that can be hooked and called by the bot's setdestination bs so anyone can insert the custom logic for deciding where the bot should move best at that given time. would work well if you could also assign tagged weights to nodes manually so if i wanted a top of a building to be a great sniper spot i could just designate all the nodes on the building as like sniperbrain+20 so any bot with a sniperbrain will prioritize positioning themselves on top of the building to shoot at players

Very interesting read, great ideas. it probably wouldn't be that hard to implement a system for adding attributes like these to nodes, but it will def be out of the scope of server-side controls. I'll make a client for the nodegun eventually

PhantOS · November 08, 2020, 07:07:09 PM

Quote from: Crook on November 08, 2020, 03:06:24 PM

Very interesting read, great ideas. it probably wouldn't be that hard to implement a system for adding attributes like these to nodes, but it will def be out of the scope of server-side controls. I'll make a client for the nodegun eventually

thank you, its all just speculation though theres definitely a better way to go around and hopefully you'll find it. and imo a node tagger tool might be a feasible way to assign string tags to placed nodes so that bot ai can feed them into their equations. if you're planning on doing client sided eventually then its redundant and useless but until then it might be a helpful tool to make in tandem with the nodegun itself