Thread: BFS Path Finder

Page 1 of 3 123 LastLast
Results 1 to 10 of 29
  1. #1 BFS Path Finder 
    Renown Programmer

    Join Date
    Oct 2017
    Posts
    198
    Thanks given
    167
    Thanks received
    302
    Rep Power
    1567
    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.
    Reply With Quote  
     


  2. #2  
    ⚔️ Battle614 - Superiority ⚔️

    Battle614's Avatar
    Join Date
    Aug 2020
    Posts
    243
    Thanks given
    72
    Thanks received
    472
    Rep Power
    803
    Good contribution, hopefully people make use of this.

    Attached image
    Reply With Quote  
     

  3. #3  
    pride, love, happiness
    .alycia's Avatar
    Join Date
    Jun 2010
    Age
    28
    Posts
    4,106
    Thanks given
    1,714
    Thanks received
    2,062
    Rep Power
    5000
    Sick release Tomm!
    Reply With Quote  
     

  4. #4  
    Registered Member
    rebecca's Avatar
    Join Date
    Aug 2017
    Posts
    1,071
    Thanks given
    862
    Thanks received
    915
    Rep Power
    5000
    nice =]
    Reply With Quote  
     

  5. #5  
    Renown Programmer
    Bartvh's Avatar
    Join Date
    May 2017
    Posts
    370
    Thanks given
    89
    Thanks received
    208
    Rep Power
    497
    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.
    Attached image
    Guthix Open Source Emulation Framework
    Reply With Quote  
     

  6. Thankful user:


  7. #6  
    Renown Programmer
    Greg's Avatar
    Join Date
    Jun 2010
    Posts
    1,179
    Thanks given
    260
    Thanks received
    1,012
    Rep Power
    2003
    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.
    Attached imageAttached image
    Reply With Quote  
     

  8. Thankful users:


  9. #7  
    Renown Programmer

    Join Date
    Oct 2017
    Posts
    198
    Thanks given
    167
    Thanks received
    302
    Rep Power
    1567
    Quote Originally Posted by Greg View Post
    I would suggest splitting it up into: Collision, Clipping, Interaction/Target checking & Algorithm.
    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.

    Quote Originally Posted by Greg View Post
    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.
    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.

    Quote Originally Posted by Greg View Post
    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'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.

    Quote Originally Posted by Greg View Post
    I'd also expect the choice of using clipping vs real coordinates to be optional.
    Fair

    Quote Originally Posted by Bartvh View Post
    What's the benefit of it being standalone?
    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.

    Quote Originally Posted by Bartvh View Post
    That seems annoying to work with. If you want to make a change you have to republish.
    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
    Reply With Quote  
     

  10. #8  
    Renown Programmer
    Bartvh's Avatar
    Join Date
    May 2017
    Posts
    370
    Thanks given
    89
    Thanks received
    208
    Rep Power
    497
    Quote Originally Posted by Tomm0017 View Post
    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.
    You can have your pfing code as a separate module in your rsmod repo and achieve the same thing.
    Attached image
    Guthix Open Source Emulation Framework
    Reply With Quote  
     

  11. #9  
    Renown Programmer

    Join Date
    Oct 2017
    Posts
    198
    Thanks given
    167
    Thanks received
    302
    Rep Power
    1567
    Quote Originally Posted by Bartvh View Post
    You can have your pfing code as a separate module in your rsmod repo and achieve the same thing.
    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:
    Quote Originally Posted by Bartvh View Post
    I don't think many 'new' developers are going to integrate third-party pathfinding anyway.
    That's irrelevant to my point. I was talking about new developers for rsmod
    Reply With Quote  
     

  12. #10  
    Renown Programmer
    Bartvh's Avatar
    Join Date
    May 2017
    Posts
    370
    Thanks given
    89
    Thanks received
    208
    Rep Power
    497
    Quote Originally Posted by Tomm0017 View Post
    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.
    I don't think many 'new' developers are going to integrate third-party pathfinding anyway.
    Attached image
    Guthix Open Source Emulation Framework
    Reply With Quote  
     

  13. Thankful users:


Page 1 of 3 123 LastLast

Thread Information
Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)


User Tag List

Similar Threads

  1. Path finder issue!
    By Kiissmyswagb in forum Help
    Replies: 14
    Last Post: 04-20-2016, 09:33 PM
  2. paths and compilers! for xp
    By king swintell in forum Tutorials
    Replies: 8
    Last Post: 04-21-2008, 01:42 AM
  3. Fix For "Path Cannot Be Specified" Jdk.
    By Jonny J in forum Tutorials
    Replies: 4
    Last Post: 03-11-2008, 01:36 AM
  4. Frame ID Finder
    By flash214 in forum Configuration
    Replies: 10
    Last Post: 02-21-2008, 08:27 AM
  5. Environment Variables, An End to Paths.
    By Whitey in forum Tutorials
    Replies: 2
    Last Post: 07-23-2007, 09:28 AM
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •