Thread: BFS Path Finder

Page 3 of 3 FirstFirst 123
Results 21 to 29 of 29
  1. #21  
    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 don't see the point in serverPathConstructOnIteration, serverPathCoroutineDispatcherThreadLocal & serverPathCoroutineDispatcherConstruct
    The point of them is to see what kind of performance you'd get with different implementations

    Quote Originally Posted by Greg View Post
    Surely you wouldn't recommend creating a path finding instance for each search or sharing one between multiple coroutines, so what's the benefit from benchmarking them?
    serverPathCoroutineDispatcherThreadLocal uses ThreadLocal
    serverPathCoroutineDispatcherConstruct constructs a new SmartPathFinder per coroutine

    Quote Originally Posted by Greg View Post
    Also I don't think serverPathCoroutineDispatcherThreadLocal is working, it's probably just resetting the instance 2k times then calculating the path once?
    Not sure what you mean by this. Where would you get the idea that it "resets" the instance 2k times but doesn't calculate the path 2k times (both handled in findPath).
    Reply With Quote  
     

  2. #22  
    Renown Programmer
    Greg's Avatar
    Join Date
    Jun 2010
    Posts
    1,179
    Thanks given
    260
    Thanks received
    1,012
    Rep Power
    2003
    Quote Originally Posted by Tomm0017 View Post
    The point of them is to see what kind of performance you'd get with different implementations.
    Ugh yeah I'm assuming that creating an instance each time will be slower than reusing a single instance based on intuition not data

    Quote Originally Posted by Tomm0017 View Post
    serverPathCoroutineDispatcherThreadLocal uses ThreadLocal
    serverPathCoroutineDispatcherConstruct constructs a new SmartPathFinder per coroutine
    Per thread, but yeah I was thinking it's based on the assumption that each coroutine will run sequentially in it's thread, but you're right that is the case in this scenario.


    The other thing to mention is you're not including the cost of copying the data from the collision data to the clipped map, and then you could also compare that and not using a clipped map at all.

    If you're really worried about performance, here's some other ways to optimise or to test if they perform better:

    • Directions & distances arrays can be combined into one
    • ringbufferX/Y can be combined into one
    • The "max turns" can be included into the backtrace
    • Remove the path array creation and reuse it/pass it in as a parameter
    • Arrays.setAll can be replaced with keeping track of visited tiles (although scu argues that it's a cheap call, I see 1-5% performance increase from it, definitely an over-optimisation though)
    Attached imageAttached image
    Reply With Quote  
     

  3. #23  
    Renown Programmer

    Join Date
    Oct 2017
    Posts
    198
    Thanks given
    167
    Thanks received
    302
    Rep Power
    1567
    Quote Originally Posted by Greg View Post
    The other thing to mention is you're not including the cost of copying the data from the collision data to the clipped map
    This is pointed out in the README

    Quote Originally Posted by Greg View Post
    and then you could also compare that and not using a clipped map at all.
    The benchmarks are using real collision data. They are just preloaded via the resource files instead of being copied on demand.

    Quote Originally Posted by Greg View Post
    If you're really worried about performance, here's some other ways to optimise or to test if they perform better:
    ...
    Thanks, will keep the list handy. For now, the performance is fine. If in the future I want to add features that will hit perf, I'll look into this.
    Reply With Quote  
     

  4. #24  
    Registered Member
    thing1's Avatar
    Join Date
    Aug 2008
    Posts
    2,111
    Thanks given
    131
    Thanks received
    1,099
    Rep Power
    2402
    Nice contribution .
    Reply With Quote  
     

  5. #25  
    Renown Programmer
    Greg's Avatar
    Join Date
    Jun 2010
    Posts
    1,179
    Thanks given
    260
    Thanks received
    1,012
    Rep Power
    2003
    Quote Originally Posted by Tomm0017 View Post
    The benchmarks are using real collision data. They are just preloaded via the resource files instead of being copied on demand.
    I mean instead of taking a 128x128 clipping of the collision data and searching with coordinates 0-128 you can just call the original data directly using the original coordinates, removing all the copying and the baseX/Y. It in theory would be slower but in practise doesn't seem to make much difference and significantly simplifies the code
    Attached imageAttached image
    Reply With Quote  
     

  6. #26  
    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 mean instead of taking a 128x128 clipping of the collision data and searching with coordinates 0-128 you can just call the original data directly using the original coordinates, removing all the copying and the baseX/Y. It in theory would be slower but in practise doesn't seem to make much difference and significantly simplifies the code
    Don't see it being worth the hit just to use "real"/in-game coords within the internals of the lib. Copying 128x128 clipping flags shouldn't be such an intensive task to warrant it.
    Reply With Quote  
     

  7. #27  
    Renown Programmer
    Greg's Avatar
    Join Date
    Jun 2010
    Posts
    1,179
    Thanks given
    260
    Thanks received
    1,012
    Rep Power
    2003
    Quote Originally Posted by Tomm0017 View Post
    Don't see it being worth the hit just to use "real"/in-game coords within the internals of the lib. Copying 128x128 clipping flags shouldn't be such an intensive task to warrant it.
    Yeah the performance difference is minor compared to the benefit of simplifying the code imo
    Attached imageAttached image
    Reply With Quote  
     

  8. #28  
    Renown Programmer

    Join Date
    Oct 2017
    Posts
    198
    Thanks given
    167
    Thanks received
    302
    Rep Power
    1567
    For archive sake (and anyone who stumbles upon this) - updating the thread. The pathfinder has been moved to https://github.com/rsmod/rsmod/game/pathfinder and has been updated with all of @Kris' fixes/improvements from their blurite fork.
    Reply With Quote  
     

  9. Thankful users:


  10. #29  
    Chemist

    Advocatus's Avatar
    Join Date
    Dec 2009
    Posts
    2,622
    Thanks given
    201
    Thanks received
    813
    Rep Power
    1462
    Quote Originally Posted by Tomm0017 View Post
    For archive sake (and anyone who stumbles upon this) - updating the thread. The pathfinder has been moved to https://github.com/rsmod/rsmod/game/pathfinder and has been updated with all of @Kris' fixes/improvements from their blurite fork.
    Thanks for clarifying. I noticed the pathfinder repo disappeared the other day and I wasnt sure what happened. Glad to know it was just being moved into the main project.
    Quote Originally Posted by blakeman8192 View Post
    Quitting is the only true failure.
    Reply With Quote  
     

Page 3 of 3 FirstFirst 123

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
  •