|
Recently there's been a lot of talk about pathfinding, which I coincidentally had to start on for rsmod. Decided to make an open-source solution for anyone who might be wanting to use it in its entirety, or use it as reference.
Code can be found on GitHub: https://github.com/rsmod/game/pathfinder
Installation, example usage, and benchmark can be found above. To make the thread not look as empty, will include the example usage code.
Why use this pathfinding implementation?
- One of the only (if not only) standalone pathfinding impl. on github, which means it can be a collaborative effort from the rsps community since we all want 100% rs pathing!!
- Performs faster than client (gains mainly from using 1d array vs 2d). Though the big gains would come from using something like coroutines (as demonstrated here), it outperforms the client most of the time.
- As far as I've been able to test and compare to OSRS, all paths have been 100% accurate.
- On maven central, so can be easily included into any project
What is left to do?
- DumbPathFinder has only been recently added and I've not had the chance to compare to OSRS for accuracy (credits to @Jire who pointed out on Discord how it worked)
- Add tests for object interactions ("exit strategies")
Credits
- @Kris: spoke a bunch about how path finding works on OSRS and came up with theories for certain interactions (player 'turn' limit, accepting destinations up to 74 tiles, etc)
@Scu11: I had previously asked for ways to contribute and scu suggested to write libraries instead of frameworks
@Jire: as previously mentioned, DumbPathFinder logic came from something they explained on Discord a while back
Example usage
Code:fun smartRoute(srcX: Int, srcY: Int, destX: Int, destY: Int, level: Int): Route { val pf = SmartPathFinder() val flags = clipFlags(srcX, srcY, level, pf.searchMapSize) return pf.findPath(flags, srcX, srcY, destX, destY) } fun clipFlags(centerX: Int, centerY: Int, level: Int, size: Int): IntArray { val half = size / 2 val flags = IntArray(size * size) val rangeX = centerX - half until centerX + half val rangeY = centerY - half until centerY + half for (y in rangeY) { for (x in rangeX) { val coords = Coordinates(x, y, level) /* * collision map stores tile collision flags for all * tiles in the world. */ val flag = collisionMap.get(coords) val lx = x - (centerX - half) val ly = y - (centerY - half) val index = (ly * size) + lx flags[index] = flag } } return flags }
Last edited by Tomm0017; 03-18-2023 at 04:50 PM.
nice =]
What's the benefit of it being standalone? That seems annoying to work with. If you want to make a change you have to republish.
Nice release,
I would suggest splitting it up into: Collision, Clipping, Interaction/Target checking & Algorithm.
Why? Because currently your only supporting player movement on land, you'll need support for flying and swimming npcs too which means checking against different collision flags.
Once collision checking is abstracted you can remove the 3 separate sized bfs's entirely because they're just different checks for different sized npcs.
Another consequence of abstracting collision checking is it can also be used for checking everywhere, including the check at movement time.
Same goes for interaction, you've got 3 hardcoded values there for wall and rectangle strategies, I should be able to add my own "is in reach of rainbow pikachu"
I'd also expect the choice of using clipping vs real coordinates to be optional.
Although it needs a bit of a refresher (and re-add the 4 or so lines to support ducks and implings) take a look at my impl and bfs, which I did/do plan on separating out into a library but hadn't got around to yet.
Though I can see why, pathfinding is probably one of the most expensive things your server will have to handle. Went with a bit more functional approach where I could.
Yeah, I'll have to cross that bridge when I get there (don't have npc updating yet lol!) But this is where your first suggestion would come into play a bit.
I'm not planning on making this pfer as extensible as that. I'll give it some thought, but unless I can add it without any perf hit/cost, I probably won't make it a priority.
Fair
Benefit is that it can be shared/used easily by other members in the community. Like I mentioned in the thread, it was mainly done to contribute to the rsps scene with a lib rather than being tied to a custom framework.
Takes a few minutes to republish if necessary. I'm of the mindset that if I want to add a new feature/change something, I should be creating an actual test for it and not have to log into my server to "test" it
Was initially going to, but decided against it simply because newer programmers / r-s users seem to be scared of modules. Seeing a bunch of them in the root directory would be off-putting for most of them.
edit:
That's irrelevant to my point. I was talking about new developers for rsmod
« Previous Thread | Next Thread » |
Thread Information |
Users Browsing this ThreadThere are currently 1 users browsing this thread. (0 members and 1 guests) |