Thread: Handling pathfinding on different threads

Page 2 of 2 FirstFirst 12
Results 11 to 20 of 20
  1. #11  
    Registered Member
    Join Date
    Dec 2013
    Posts
    260
    Thanks given
    91
    Thanks received
    56
    Rep Power
    309
    Quote Originally Posted by Kris View Post
    It is not the cheapest process, but the problem is - 9/10 cases where you actually use intelligent pathfinding, you require the path to be available immediately. There is no point in passing calculations to another thread if you have to block this thread, waiting for the operation to complete.
    The only case where you could and realistically should execute it on another thread is within the MoveGameClick packet(walk packet basically, as people call). When receiving the packet, I immediately perform the calculations within the same netty thread and pass the result off to the main game thread when it's ready.
    The remaining cases are within combat or similar circumstances and those require you to know the path immediately.
    Well of course it would be silly to off-load to another thread if the current is blocked anyway. I was under the assumption that we're talking about the walking packet this whole time.
    Reply With Quote  
     

  2. #12  
    Donator

    Jonatino's Avatar
    Join Date
    Dec 2008
    Posts
    4,234
    Thanks given
    394
    Thanks received
    415
    Rep Power
    1633
    Quote Originally Posted by Dragonsevery View Post
    The reason I've asked about this, is because finding a path from (x=3222, y=3222) to (x=3222, y=3230) sometimes takes between 15-17ms and more the longer the path. That's quite a bit if one hundred people are clicking at the same time, then the main thread is stalled by that amount of time until the path is found. If you're using it on your 'network thread', then the network thread is stalled by that time, and then you also have lag there.


    Well, of course I would have a lock for it. Lock and Semaphore. There's plenty of ways to synchronize things like this, so that isn't a problem

    Sounds like you need new pathfinding.
    Reply With Quote  
     

  3. #13  
    Registered Member
    Join Date
    May 2017
    Posts
    64
    Thanks given
    15
    Thanks received
    28
    Rep Power
    51
    Quote Originally Posted by Jonatino View Post
    Sounds like you need new pathfinding.
    I have continually tried to improve the speed of AStar by different heuristics and caching and so far have gotten it a third of the time I had said at three times the distance. So, 5-7ms for distance of 30. That still seems like much, so if you could show me some things you have written that are much faster, I would love it.

    Just noticed, most of the time it's 1-3ms after caching and 5-21ms before caching
    [Only registered and activated users can see links. ]
    Reply With Quote  
     

  4. #14  




    Scu11's Avatar
    Join Date
    Aug 2007
    Age
    25
    Posts
    16,024
    Thanks given
    7,039
    Thanks received
    11,744
    Rep Power
    5000
    Quote Originally Posted by Dragonsevery View Post
    I have continually tried to improve the speed of AStar by different heuristics and caching and so far have gotten it a third of the time I had said at three times the distance. So, 5-7ms for distance of 30. That still seems like much, so if you could show me some things you have written that are much faster, I would love it.

    Just noticed, most of the time it's 1-3ms after caching and 5-21ms before caching
    need to see how you're benchmarking for anyone to give valuable advice

    [Only registered and activated users can see links. ]
    Reply With Quote  
     

  5. #15  
    Textures developer

    Kris's Avatar
    Join Date
    Jun 2016
    Age
    21
    Posts
    3,404
    Thanks given
    563
    Thanks received
    2,044
    Rep Power
    2811
    Quote Originally Posted by Dragonsevery View Post
    I have continually tried to improve the speed of AStar by different heuristics and caching and so far have gotten it a third of the time I had said at three times the distance. So, 5-7ms for distance of 30. That still seems like much, so if you could show me some things you have written that are much faster, I would love it.

    Just noticed, most of the time it's 1-3ms after caching and 5-21ms before caching
    My best guess for as to why it's taking that long for you is that you're loading it the same way matrix sources do, which is loading regions on-demand - and often through pathfinding.
    So in order to populate local 128x128 palette with clip flags, it would first be forced to load the region from cache, and this can easily take as long as you've mentioned here.

    But regardless, pathfinding should be a lot faster than the numbers you're spewing here. I was reaching ~58ms per 2000 calls within gnome maze - for a distance of 64 tiles. I know for a fact even that could be optimized to give far better results. Nothing about that is multithreaded.
    Spoiler for sig too large:

    [Only registered and activated users can see links. ]

    Discord: Kris#1337
    Reply With Quote  
     

  6. #16  
    Registered Member
    Join Date
    May 2017
    Posts
    64
    Thanks given
    15
    Thanks received
    28
    Rep Power
    51
    Quote Originally Posted by Scu11 View Post
    need to see how you're benchmarking for anyone to give valuable advice
    Stopwatch class gives the same output
    Code:
    Instant start = Instant.now();
    findPath();
    Instant finish = Instant.now();
    System.out.println(Duration.between(start, finish).toMillis());
    Quote Originally Posted by Kris View Post
    My best guess for as to why it's taking that long for you is that you're loading it the same way matrix sources do, which is loading regions on-demand - and often through pathfinding.
    So in order to populate local 128x128 palette with clip flags, it would first be forced to load the region from cache, and this can easily take as long as you've mentioned here.

    But regardless, pathfinding should be a lot faster than the numbers you're spewing here. I was reaching ~58ms per 2000 calls within gnome maze - for a distance of 64 tiles. I know for a fact even that could be optimized to give far better results. Nothing about that is multithreaded.
    Actually, chunk data is kept in an array and is only loaded ONCE. So any collision data is cached. Also, I would like to see the code you're using for this. I have tried multiple different methods, but I do not get any better performance

    Code:
    package lib.entity.world;
    
    import lombok.Getter;
    
    /**
     * 
     * @author Albert Beaupre
     */
    
    public class Chunk {
    
    	public static final int CHUNK_SIZE = 8;
    	public static final int CHUNK_BITS = 3;
    	public static final int Z_PLANE_LIMIT = 4;
    
    	private final Tile[][][] tiles = new Tile[Z_PLANE_LIMIT][CHUNK_SIZE][CHUNK_SIZE];
    	@Getter private final int cacheX, cacheY;
    	@Getter private final World parent;
    
    	/**
    	 * 
    	 * @param parent
    	 * @param cacheX
    	 * @param cacheY
    	 */
    	public Chunk(World parent, int cacheX, int cacheY) {
    		this.parent = parent;
    		this.cacheX = cacheX;
    		this.cacheY = cacheY;
    	}
    
    	/**
    	 * Returns the {@code Tile} within this {@code Chunk} based on the given
    	 * local coordinates. If the coordinates are out of the chunk bounds, the
    	 * tile is grabbed from other chunks, if able. If the {@code Tile} has not
    	 * been initialized, it will be initialized and returns with no collision
    	 * data.
    	 * 
    	 * @param localX
    	 *            the local x coordinate of the tile
    	 * @param localY
    	 *            the local y coordinate of the tile
    	 * @param z
    	 *            the z coordinate of the tile
    	 * @return the tile at the given coordinates
    	 */
    	public Tile getTile(int localX, int localY, int z) {
    		try {
    			Tile tile = this.tiles[z][localX][localY];
    			if (tile == null) // if the tile has not been initialized, it will be with no collision data
    				this.tiles[z][localX][localY] = new Tile(this, localX, localY, z, CollisionFlags.OPEN);
    			return tile;
    		} catch (ArrayIndexOutOfBoundsException e) {
    			/**
    			 * Attempts to grab any tiles that are out of this chunk. More than
    			 * likely, the other tiles it is grabbing will be in another chunk.
    			 */
    			return parent.getTile((cacheX << CHUNK_BITS) + localX, (cacheY << CHUNK_BITS) + localY, z);
    		}
    	}
    
    	/**
    	 * Sets the given {@code tile} at the coordinates.
    	 * 
    	 * @param tile
    	 *            the tile to set
    	 * @param localX
    	 *            the local x coordinate
    	 * @param localY
    	 *            the local y coordinate
    	 * @param z
    	 *            the z coordinate
    	 */
    	public void setTile(Tile tile, int localX, int localY, int z) {
    		this.tiles[z][localX][localY] = tile;
    	}
    
    	/*
    	 * (non-Javadoc)
    	 * 
    	 * @see java.lang.Object#toString()
    	 */
    	public String toString() {
    		return String.format("chunk[cache_x=%d, cache_y=%d]", cacheX, cacheY);
    	}
    
    }
    [Only registered and activated users can see links. ]
    Reply With Quote  
     

  7. #17  
    Textures developer

    Kris's Avatar
    Join Date
    Jun 2016
    Age
    21
    Posts
    3,404
    Thanks given
    563
    Thanks received
    2,044
    Rep Power
    2811
    Quote Originally Posted by Dragonsevery View Post
    Code:
    Instant start = Instant.now();
    findPath();
    Instant finish = Instant.now();
    System.out.println(Duration.between(start, finish).toMillis());


    Actually, chunk data is kept in an array and is only loaded ONCE. So any collision data is cached. Also, I would like to see the code you're using for this. I have tried multiple different methods, but I do not get any better performance

    Code:
    package lib.entity.world;
    
    import lombok.Getter;
    
    /**
     * 
     * @author Albert Beaupre
     */
    
    public class Chunk {
    
    	public static final int CHUNK_SIZE = 8;
    	public static final int CHUNK_BITS = 3;
    	public static final int Z_PLANE_LIMIT = 4;
    
    	private final Tile[][][] tiles = new Tile[Z_PLANE_LIMIT][CHUNK_SIZE][CHUNK_SIZE];
    	@Getter private final int cacheX, cacheY;
    	@Getter private final World parent;
    
    	/**
    	 * 
    	 * @param parent
    	 * @param cacheX
    	 * @param cacheY
    	 */
    	public Chunk(World parent, int cacheX, int cacheY) {
    		this.parent = parent;
    		this.cacheX = cacheX;
    		this.cacheY = cacheY;
    	}
    
    	/**
    	 * Returns the {@code Tile} within this {@code Chunk} based on the given
    	 * local coordinates. If the coordinates are out of the chunk bounds, the
    	 * tile is grabbed from other chunks, if able. If the {@code Tile} has not
    	 * been initialized, it will be initialized and returns with no collision
    	 * data.
    	 * 
    	 * @param localX
    	 *            the local x coordinate of the tile
    	 * @param localY
    	 *            the local y coordinate of the tile
    	 * @param z
    	 *            the z coordinate of the tile
    	 * @return the tile at the given coordinates
    	 */
    	public Tile getTile(int localX, int localY, int z) {
    		try {
    			Tile tile = this.tiles[z][localX][localY];
    			if (tile == null) // if the tile has not been initialized, it will be with no collision data
    				this.tiles[z][localX][localY] = new Tile(this, localX, localY, z, CollisionFlags.OPEN);
    			return tile;
    		} catch (ArrayIndexOutOfBoundsException e) {
    			/**
    			 * Attempts to grab any tiles that are out of this chunk. More than
    			 * likely, the other tiles it is grabbing will be in another chunk.
    			 */
    			return parent.getTile((cacheX << CHUNK_BITS) + localX, (cacheY << CHUNK_BITS) + localY, z);
    		}
    	}
    
    	/**
    	 * Sets the given {@code tile} at the coordinates.
    	 * 
    	 * @param tile
    	 *            the tile to set
    	 * @param localX
    	 *            the local x coordinate
    	 * @param localY
    	 *            the local y coordinate
    	 * @param z
    	 *            the z coordinate
    	 */
    	public void setTile(Tile tile, int localX, int localY, int z) {
    		this.tiles[z][localX][localY] = tile;
    	}
    
    	/*
    	 * (non-Javadoc)
    	 * 
    	 * @see java.lang.Object#toString()
    	 */
    	public String toString() {
    		return String.format("chunk[cache_x=%d, cache_y=%d]", cacheX, cacheY);
    	}
    
    }
    Do a measurement using System.nanoTime() instead of relying on Instant - which I believe relies on System#currentTimeMillis() - which is less than ideal for precise measurements as it can be up to 15.625ms(timeslice granularity of 1000ms / 64) off in precision on windows operating systems.
    Spoiler for sig too large:

    [Only registered and activated users can see links. ]

    Discord: Kris#1337
    Reply With Quote  
     

  8. Thankful user:


  9. #18  




    Scu11's Avatar
    Join Date
    Aug 2007
    Age
    25
    Posts
    16,024
    Thanks given
    7,039
    Thanks received
    11,744
    Rep Power
    5000
    Quote Originally Posted by Dragonsevery View Post
    Stopwatch class gives the same output
    Code:
    Instant start = Instant.now();
    findPath();
    Instant finish = Instant.now();
    System.out.println(Duration.between(start, finish).toMillis());


    Actually, chunk data is kept in an array and is only loaded ONCE. So any collision data is cached. Also, I would like to see the code you're using for this. I have tried multiple different methods, but I do not get any better performance

    Code:
    package lib.entity.world;
    
    import lombok.Getter;
    
    /**
     * 
     * @author Albert Beaupre
     */
    
    public class Chunk {
    
    	public static final int CHUNK_SIZE = 8;
    	public static final int CHUNK_BITS = 3;
    	public static final int Z_PLANE_LIMIT = 4;
    
    	private final Tile[][][] tiles = new Tile[Z_PLANE_LIMIT][CHUNK_SIZE][CHUNK_SIZE];
    	@Getter private final int cacheX, cacheY;
    	@Getter private final World parent;
    
    	/**
    	 * 
    	 * @param parent
    	 * @param cacheX
    	 * @param cacheY
    	 */
    	public Chunk(World parent, int cacheX, int cacheY) {
    		this.parent = parent;
    		this.cacheX = cacheX;
    		this.cacheY = cacheY;
    	}
    
    	/**
    	 * Returns the {@code Tile} within this {@code Chunk} based on the given
    	 * local coordinates. If the coordinates are out of the chunk bounds, the
    	 * tile is grabbed from other chunks, if able. If the {@code Tile} has not
    	 * been initialized, it will be initialized and returns with no collision
    	 * data.
    	 * 
    	 * @param localX
    	 *            the local x coordinate of the tile
    	 * @param localY
    	 *            the local y coordinate of the tile
    	 * @param z
    	 *            the z coordinate of the tile
    	 * @return the tile at the given coordinates
    	 */
    	public Tile getTile(int localX, int localY, int z) {
    		try {
    			Tile tile = this.tiles[z][localX][localY];
    			if (tile == null) // if the tile has not been initialized, it will be with no collision data
    				this.tiles[z][localX][localY] = new Tile(this, localX, localY, z, CollisionFlags.OPEN);
    			return tile;
    		} catch (ArrayIndexOutOfBoundsException e) {
    			/**
    			 * Attempts to grab any tiles that are out of this chunk. More than
    			 * likely, the other tiles it is grabbing will be in another chunk.
    			 */
    			return parent.getTile((cacheX << CHUNK_BITS) + localX, (cacheY << CHUNK_BITS) + localY, z);
    		}
    	}
    
    	/**
    	 * Sets the given {@code tile} at the coordinates.
    	 * 
    	 * @param tile
    	 *            the tile to set
    	 * @param localX
    	 *            the local x coordinate
    	 * @param localY
    	 *            the local y coordinate
    	 * @param z
    	 *            the z coordinate
    	 */
    	public void setTile(Tile tile, int localX, int localY, int z) {
    		this.tiles[z][localX][localY] = tile;
    	}
    
    	/*
    	 * (non-Javadoc)
    	 * 
    	 * @see java.lang.Object#toString()
    	 */
    	public String toString() {
    		return String.format("chunk[cache_x=%d, cache_y=%d]", cacheX, cacheY);
    	}
    
    }
    You can't check a single path in isolation, you need to benchmark with both randomisation and over a large amount of iterations

    [Only registered and activated users can see links. ]
    Reply With Quote  
     

  10. #19  
    Registered Member
    Join Date
    May 2017
    Posts
    64
    Thanks given
    15
    Thanks received
    28
    Rep Power
    51
    Quote Originally Posted by Scu11 View Post
    You can't check a single path in isolation, you need to benchmark with both randomisation and over a large amount of iterations
    I looped 2000 paths to be found for a long while last night and got between 100ms to 250ms time
    [Only registered and activated users can see links. ]
    Reply With Quote  
     

  11. #20  




    Scu11's Avatar
    Join Date
    Aug 2007
    Age
    25
    Posts
    16,024
    Thanks given
    7,039
    Thanks received
    11,744
    Rep Power
    5000
    Quote Originally Posted by Dragonsevery View Post
    I looped 2000 paths to be found for a long while last night and got between 100ms to 250ms time
    250ms for 2000 paths is only 0.125ms per path, not 5-7ms as claimed earlier

    [Only registered and activated users can see links. ]
    Reply With Quote  
     

  12. Thankful user:


Page 2 of 2 FirstFirst 12

Thread Information
Users Browsing this Thread

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

Similar Threads

  1. Deleting objects on different heights
    By Oxygen in forum Help
    Replies: 0
    Last Post: 05-12-2009, 10:48 PM
  2. Items on 525 Thread Deleted?
    By Kok in forum Show-off
    Replies: 3
    Last Post: 04-22-2009, 05:29 PM
  3. Handling timer on the most efficient way
    By Meanz in forum RS2 Server
    Replies: 14
    Last Post: 02-07-2009, 07:39 PM
  4. Replies: 5
    Last Post: 01-27-2009, 03:01 AM
  5. DuhPK 7000+ downloads on different sites
    By Nickg23 in forum Downloads
    Replies: 12
    Last Post: 02-14-2008, 12:50 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
  •