3 Commits

Author	SHA1	Message	Date
LemonInTheDark	77823ad210	Pathfinding Visualization, JPS fixes, Misc Improvement (#90233) ... ## About The Pull Request [cleans up poor namespacing on light debugging tools](https://github.com/tgstation/tgstation/commit/93cc9070d56ee4dbeb600ebd4616b047adf9d648) [Implements a pathfinding visualization tool](https://github.com/tgstation/tgstation/commit/ed91f69ac42a92329c10ccdbba308d213fc8c759) It holds a set of inputs from the client, and uses them to generate and display paths from source/target. Left click sets the source, right click sets the target. Pathmap support too, if no target is set we display the paths from every turf in the map to the source, if one is set we build a path TO it from the source. I had to add COMSIG_MOB_CLICKON to observers to make this work (tho idk why it didn't exist already), I also removed the everpresent colorblind datum from admin datums, only needs to exist if they're using it. [Adds a mutable_appearance helper that dirlocks them, wallening port which I thought might be useful here, and will likely be useful elsewhere in future](https://github.com/tgstation/tgstation/commit/87f752e7c361ff47d62452f2f1ea805458f71b66) [Fixes an infinite loop in pathmaps if we tried to pull a cached path to an unreachable target, && not || 4head](https://github.com/tgstation/tgstation/commit/10086a655df817c9f4494f9aac879c85a6059719) [Fixes JPS not dealing with border objects properly. They violate some of the assumptions JPS makes, so we need to backfill them with checks. These basically read as (if the thing that should normally take this path can't reach this turf, can we?)](https://github.com/tgstation/tgstation/commit/f56cc4dd434cecee89879aea500bd1c9d2f38ce6) ## Why It's Good For The Game Maybe deals with #80619? Adds more robust testing tools for pathfinding, should allow people to better understand/debug these systems. I added this with the idea of adding multiz support but I don't have the time for that rn. JPS will work around thindows better, that's nice. https://file.house/IrBiR0bGxoKw1jJJoxgMRQ==.mp4 ## Changelog 🆑 fix: Fixed our pathfinding logic getting deeply confused by border objects admin: Added clientside displayed pathfinding debug tools, give em a go /🆑	2025-03-28 01:51:57 +02:00
LemonInTheDark	2532911353	Adds pathmaps, refactors pathfinding a bit (#78684) ... ## About The Pull Request Implements /datum/pathfind/sssp, which generates /datum/path_map /datum/path_maps allow us to very efficently generate paths to any turf they contain from their central point. We're effectively running the single source shortest paths algorithm. We expand from the center turf, adding turfs as they're found, and then processing them in order of addition. As we go, we remember what turf "found" us first. Reversing this chain gives us the shortest possible path from the center turf to any turf in its range (or the inverse). This isn't all that useful on its own, outside of a few niche cases (Like if we wanted to get the farthest reachable turf from the center) but if we could reuse the map more then once, we'd be able to swarm to/from a point very easily. Reuse is a bit troublesome, reqiures a timeout system and a way to compare different movables trying to get paths. I've implemented it tho. I've refactored CanAStarPass to take a datum, /datum/can_pass_info. This is built from a movable and a list of access, and copies all the properties that would impact pathfinding over onto itself. There is one case where we don't do this, pathing over openspace requires checking if we'd fall through the openspace, and the proc for that takes an atom. So instead we use the weakref to the owner that we hold onto, and hold copies of all the values that would impact the check on the datum. When someone requests a swarmed path their pass info is compared with the pass info of all other path_maps centered on their target turf. If it matches and their requested timeout isn't too short, we just reuse the map. Timeout is a tricky thing because the longer a map exists the more out of date it gets. I've added a few age defines that let you modulate your level of risk here. We default to only allowing maps that are currently being generated, or finished generating in our tick. Hopefully this prevents falling into trouble, but consumers will need to allow "failed" movements. As a part of this datumized pass info, I've refactored pathfinding to use access lists, rather then id cards directly. This also avoids some dumbass harddel oppertunities, and prevents an idcard from changing mid path. Did a few things to the zPass procs, they took args that they did NOT need, and I thought it'd be better to yeet em. If you'd all like I could undo the caching/can_pass_info stuff if you'd all like. I think it's useful generally because it avoids stuff changing mid pathfind attempt, but if it's too clunky I could nuke it. Oh also I added optional args to jps that constricts how it handles diagonals. I've used this to fix bot paths. ## Why It's Good For The Game Much of this is redundant currently. I'm adding it because it could have saved hugglebippers, and because I get the feeling it'll be useful for "grouping" mobs like bees and such. We're doing more basic mob work currently and I want to provide extra tools for that work. https://github.com/tgstation/tgstation/assets/58055496/66aca1f9-c6e7-4173-9c38-c40516d6d853 ## Changelog 🆑 add: Adds swarmed pathfinding, trading accuracy for potential optimization of used correctly fix: Bots will no longer take diagonal paths, preventing weirdo looking path visuals refactor: Refactored bits of pathfinding code, hopefully easier to add new pathfinding strategies now /🆑	2023-10-17 23:52:54 -06:00
LemonInTheDark	1409e4b026	JPS Optimization (Light Botcode) (#70623) ... ## About The Pull Request Alright. So. Right now, JPS works like this: ``` code requests path we enter the actual pathfinding pathfinding sleeps when it overruns a tick if it sleeps, it'll then wake up before the mc starts continue ``` This has annoying side effects. Primarily that we have no real control over JPS, we just sorta have to eat its cost. So if there's like 10 different things pathfinding at once, the mc will have no time to do anything. Hell we might even end up eating into maptick's time if the jps work is expensive enough (note the cost of sleeping is not accounted for, and that has overhead) This has happen before, usually when someone makes a lot of bots, and it's really annoying. So then, lets put JPS on a subsystem. That way the MC has control over it. But wait, existing code expects to yield and get back a path list, and that's a sane request. This is solvable, but requires abusing pass by reference lists, and the ability to make callbacks into partials (preinsert arguments into them before they're called, and accept other args later) Because of this, we can now pass callbacks into pathfinders, allowing for async use, rather then JUST yielding. Of note: I've removed the 10 pathfinding datums limit, since ratelimiting like that is handled nicely by the MC. I've also removed the 15 second timeout, since mc yielding would trigger it too often. I'm unsure if this means we don't have exit conditions for pathfinding, need to talk to ryll. (@Ryll-Ryll what happens if jps just like, fails to find a path?) Also of note: I think bots will fire off more then one pathfinding attempt at a time if their first takes too long to complete. This is dumb, why do we do this? Optimizes JPS by more then 40% by removing redundant for(thing in turf) loops, and avoiding making proc calls if objects are non dense. This makes things slightly more fragile, but saves a LOT of time. I think it's worth it, tho talking to mso it might be possible to do better. Maybe I should do a LINDA system style thing. (I did a linda system style thing I fixed it) Optimizes botscanning, fixes bots not seeing things adjacent to them The list of types could be a cached typecache We could inline both checkscan and check_bot check_bot SHOULD NOT BE CALLED ON EVERY OBJECT IN VIEW HOLY SHIT WHY We don't need to process adjacent and the shuffled view separately, it's in fact easier to process them in one block Renames a var Moves bot's pathing images to above most floor objects, so they're visible in maint ## Why It's Good For The Game Speed. Also manuel will stop killing their server by placing 20000 medibots (fucking icebox man every time) ## Changelog 🆑 fix: Bots will now "notice" you if you're standing right next to them fix: Bot paths will now draw above things like pipes, rather then below them refactor: Changed how pathfinding paths get generated refactor: Made pathfinding and bot searching significantly faster /🆑 Co-authored-by: Mothblocks <35135081+Mothblocks@users.noreply.github.com>	2022-11-22 07:29:35 +00:00