Pathfinding Without Pathmaps!
A proof-of-concept for a dynamic pathfinding system implemented in the Workshop that can theoretically find the shortest path (or something close) between any two points on the map, as long as one exists. It does not require any pre-made pathmaps or anything of the sort, which means it can be used on any map, though some work better than others. The path can go around obstacles, up or down stairs and it will still be found. It can even (usually) find the way from a low ground to a high ground position. It's not perfect, and is quite slow, but unfortunately I don't think the speed could be improved much due to the performance constraints of the Workshop.
It uses the A* pathfinding algorithm normally, but switches to the faster Greedy Best First Search for long distances (>75m), which means it will not always find the shortest path at long distances.
How to use:
- Walk to some position in the map.
- Press Interact (F) to specify the end position for pathfinding. This will be the position that the algorithm will attempt to find the path to.
- Walk to some other position in the map.
- Press Interact again to specify the start position. This will be the position that the path starts at. Once this is done, the algorithm will try to find a path between the two points. If it succeeds, a path made of grapple beams will appear between the two points specified. If it does not, the server will probably crash.
Please comment if you need help with anything, or anything else I guess.
At the top right there are a few HUD elements.
"Server Load" is the current server load value. If it stays above 200 for more than a few seconds the server will probably crash.
"Generated Nodes (flat)" is the amount of nodes generated by the algorithm in the current or last run IF the amount is less than or equal to than 1000. If it's greater...
"Generated Nodes (dual index)" is the same as above, but when the amount is greater than 1000. The reason for this is hard to explain, so I might do it in an update or smth idk.
Also, use the code KQBEH for the debug mode version, which will highlight every node generated by the algorithm with orange spheres.
If you want to use code from this, please credit me. This is written in OSTW, and i'll probably release the source code soon or if someone asks me to, so if you want to use this, I'd recommend just using the OSTW code, or just asking me about it if it's not public yet. Have fun I guess bye
UPDATE: source code (library version) available at https://github.com/kxtbit/OWWorkshopDynamicPathfinding/blob/main/astarpathfind_reduced.ostw
