Author Topic: WIP inefficient pathfinding algorithm  (Read 296 times)

Sorry to disappoint if you were one of the people in BCC following along with this but I don't think I have the capacity to finish this project. Pathfinding algorithms are over my head and I just haven't had the time to do the research, and with the future of Blockland becoming more and more uncertain I haven't had much motivation to work on it either. That may change, but nonetheless it feels wrong to just sit on it indefinitely so here you go.

I did my best to write comments to kinda explain what's going on in here. You are free to use this code however you want.
https://cdn.discordapp.com/attachments/609001398087974943/621229227395645451/System_WRathfinder.zip

Basic usage:
- Type wrath_generateNodeMap(); in console. This will create nodes for your entire build. If your build is too big it might explode and crash your game.
- Type wrath_newPath("start coordinates", "end coordinates"); in console. The system will now increment through nodes to try and 'find' the goal node from the start node and will dump a bunch of information into your console during the process. The example wrathfinder_newPath("-54.75 -56.25 0.5", "73.75 91.25 13.3"); will look between one corner of Afghan DM to a roof of a building at the opposite corner.

This wont produce any useful information, the shortest path isn't actually cached, it just stops once it finds its way through the nodes. The framework is there though. I think what I'd try to do would be to add a heuristic to every node visited in the path based on what time/order it was visited, and then increment through the path again, but always going to the neighbor with the highest heuristic. That should give you the shortest path through the visited nodes but not necessarily the actually shortest path.

Also features a tool that can place and delete nodes, the intent was to try and make it so you could create your own, way more efficient node graphs manually. You can equip it with /nodeGun. It seems to do a pretty stuffty job of finding nodes when deleting/linking though so careful if you intend to use it with generated maps with thousands of nodes.

This is pretty cool.  I can't get it to generate a nodemap without it hanging forever.  But the node Gun looks useful for things.

how is it different from port's node gun

how is it different from port's node gun

Can you post a link? Haven't heard of this before

For some reason I can't find it on their github, mb. But this exists https://github.com/qoh/ts-pathing-new/blob/master/lib.cs

Damn I had no idea this existed. Thanks

although the nodemap generator is an interesting and new pet project, its wildly inefficient and impractical. all map designers for professional game firms node maps by hand in order to optimize and cover all the movement space required and no amount of generation can get that accurate. the node tool design is definitely smart and although i remember having one in the past i also remember that it sucked richard and required a lot of tweaking before it could be used with any pathfinding. so its good that you made a tool

i feel like you burned yourself out on this one with the whole generation thing by trying to do all the work that the client can do themselves better (and to their liking). but providing a framework for nodemapping in general is still good, though its kinda sad that something like this is now only being made public in 2019

It was definitely interesting but you're right, it seems the automatic generation was too expensive and not feasible. I'd like to think that it could be made practical if I could reliably find neighboring nodes at variable distances/positions. Maybe using scriptobjects to store nodes was the wrong play. Looks like Port's code uses global variables to store node information instead.

ideally you should use like a node scriptobject with a list of neighbors, a number of neighbors, and a position. let players connect it themselves with a node tool, and from then on its just a regular a* which is kinda complex on its own but once you understand it fully you can translate it to torquescript. also caching the shortest path on the start node and using it until the nodemap is updated is usually a good idea too.

i wouldn't suggest heuristic because it can slow down the entire thing. you should rely on players themselves to design the nodemap sparsely so that every part of the map is in view of a node and nothing extra is added
« Last Edit: September 12, 2019, 01:04:23 AM by PhantOS »

one idea to generate a nodemap could have the nodemap maker turn on a script, and walk/jump/crouch through the build a lot. then you can build a sort of basic framework which they can then augment/connect... but then again thats not much different than just making the nodes manually i suppose.

one idea to generate a nodemap could have the nodemap maker turn on a script, and walk/jump/crouch through the build a lot. then you can build a sort of basic framework which they can then augment/connect... but then again thats not much different than just making the nodes manually i suppose.
if that's done with a large amount of players, it gets amusing
players find strange jumpy puzzles to get around the map
AI starts using them and surprising normal people