Thread: Understanding regions and clipping

Results 1 to 5 of 5
  1. #1 Understanding regions and clipping 
    Registered Member
    Join Date
    Apr 2013
    Posts
    50
    Thanks given
    2
    Thanks received
    1
    Rep Power
    11
    Hi all.

    I'm really interested in the core of rsps and want to understand the code sources rather then just assume they work.

    Now, I'm reading into Regions, I tried to look online but there wasn't many people explaining the inner work of why certain code is there.

    I've added javoc documentation to the code below, but I really don't understand:

    Code:
    /**
    	 * Unsure how to explain this method
    	 * 
    	 * @[Only registered and activated users can see links. ] x
    	 * @[Only registered and activated users can see links. ] y
    	 * @[Only registered and activated users can see links. ] height
    	 * @[Only registered and activated users can see links. ]
    	 */
    	private int getClip(int x, int y, int height) {
    		int regionAbsX = (id >> 8) * 64;
    		int regionAbsY = (id & 0xff) * 64;
    		if (clips[height] == null) {
    			return 0;
    		}
    		return clips[height][x - regionAbsX][y - regionAbsY];
    	}
    Code:
    /**
    	 * Checks if the current position is legal
    	 * 
    	 *  @[Only registered and activated users can see links. ] x - current x position
    	 *  @[Only registered and activated users can see links. ] y - current y position
    	 *  @[Only registered and activated users can see links. ] height - current height
    	 *  @[Only registered and activated users can see links. ]
    	 */
    	public static int getClipping(int x, int y, int height) {
    		if (height > 3) {
    			height = 0;
    		}
    		int regionX = x >> 3;
    		int regionY = y >> 3;
    		int regionId = (regionX / 8 << 8) + regionY / 8;
    		for (Region r : regions) {
    			if (r.id() == regionId) {
    				return r.getClip(x, y, height);
    			}
    		}
    		return 0;
    	}
    From above:
    1. why is the x and y coordinates shifted by 3 bits to the right?
    2. why is the x and y coordinates after shift divided by 8? and why is x coord the only one shifted 8 bits to the left.


    In addition:

    Code:
    /**
    	 * Checks that the movement is legal.
    	 * 
    	 *  @[Only registered and activated users can see links. ] x - current x position
    	 *  @[Only registered and activated users can see links. ] y - current y position
    	 *  @[Only registered and activated users can see links. ] height - current height
    	 *  @[Only registered and activated users can see links. ] moveTypeX - end x position
    	 *  @[Only registered and activated users can see links. ] moveTypeY - end y position
    	 *  @[Only registered and activated users can see links. ]
    	 */
    
    	public static boolean getClipping(int x, int y, int height, int moveTypeX,
    			int moveTypeY) {
    		try {
    			if (height > 3) {
    				height = 0;
    			}
    			int checkX = x + moveTypeX;
    			int checkY = y + moveTypeY;
    			if (moveTypeX == -1 && moveTypeY == 0) {
    				return (getClipping(x, y, height) & 0x1280108) == 0;
    			} else if (moveTypeX == 1 && moveTypeY == 0) {
    				return (getClipping(x, y, height) & 0x1280180) == 0;
    			} else if (moveTypeX == 0 && moveTypeY == -1) {
    				return (getClipping(x, y, height) & 0x1280102) == 0;
    			} else if (moveTypeX == 0 && moveTypeY == 1) {
    				return (getClipping(x, y, height) & 0x1280120) == 0;
    			} else if (moveTypeX == -1 && moveTypeY == -1) {
    				return (getClipping(x, y, height) & 0x128010e) == 0
    						&& (getClipping(checkX - 1, checkY, height) & 0x1280108) == 0
    						&& (getClipping(checkX - 1, checkY, height) & 0x1280102) == 0;
    			} else if (moveTypeX == 1 && moveTypeY == -1) {
    				return (getClipping(x, y, height) & 0x1280183) == 0
    						&& (getClipping(checkX + 1, checkY, height) & 0x1280180) == 0
    						&& (getClipping(checkX, checkY - 1, height) & 0x1280102) == 0;
    			} else if (moveTypeX == -1 && moveTypeY == 1) {
    				return (getClipping(x, y, height) & 0x1280138) == 0
    						&& (getClipping(checkX - 1, checkY, height) & 0x1280108) == 0
    						&& (getClipping(checkX, checkY + 1, height) & 0x1280120) == 0;
    			} else if (moveTypeX == 1 && moveTypeY == 1) {
    				return (getClipping(x, y, height) & 0x12801e0) == 0
    						&& (getClipping(checkX + 1, checkY, height) & 0x1280180) == 0
    						&& (getClipping(checkX, checkY + 1, height) & 0x1280120) == 0;
    			} else {
    				System.out.println("[FATAL ERROR]: At getClipping: " + x + ", "
    						+ y + ", " + height + ", " + moveTypeX + ", "
    						+ moveTypeY);
    				return false;
    			}
    		} catch (Exception e) {
    			return true;
    		}
    	}
    Now, from above, I understand that this code is only checking 1 tile away from the player. However, I'm unsure what the
    Code:
     return (getClipping(x, y, height) & 0x1280120) == 0;
    is doing. Obviously, it checks the position 1 tile away, but what does the Mask mean here as they are different for each direction? I also understand that it returns false if not 0 etc.

    I'm looking for a explanation of what is occurring exactly here, I'm still very new to the rsps scene but I like to learn and understand. Thanks
    Reply With Quote  
     

  2. #2  
    Community Veteran

    George's Avatar
    Join Date
    Mar 2009
    Posts
    7,063
    Thanks given
    2,099
    Thanks received
    2,938
    Rep Power
    5000
    Collision checks works by flagging each individual tile with a value that can mean a variety things, one value could mean that the specific tile is "flagged" or defined as a water tile.

    The whole regionAbsX is probably to get the local coordinates relative to the player. I'm unsure to be fair.

    So something like (assumption).
    clips[height][localX][localY];


    Reply With Quote  
     

  3. #3  
    Contributor

    clem585's Avatar
    Join Date
    Sep 2013
    Posts
    3,547
    Thanks given
    646
    Thanks received
    637
    Rep Power
    334
    Quote Originally Posted by gilbo184 View Post
    From above:
    1. why is the x and y coordinates shifted by 3 bits to the right?
    2. why is the x and y coordinates after shift divided by 8? and why is x coord the only one shifted 8 bits to the left.
    Bitshift by 3 to the right and dividing by 8 is equivalent. The first >> 3 obtains the chunkX/Y (wrongly named regionX/Y in the code you provided). This is essentially 1/64 of a region, and it's 8x8 in size, containing 64 tiles in total. Then the 2nd division by 8 obtains the regionX/regionY which are the x/y coordinates of the region. A region is 64x64 in size, containing 4096 tiles in total. The left bitshift by 8 is to encode the regionY along with the regionX in a single int. The bits in red are the regionY and the bits in green are the regionX:

    Code:
    regionId  = 00000000 00000000 00000000 00000000
    You can look at this page to visualize the size of a single region, enable the grid on the left: [Only registered and activated users can see links. ]

    Quote Originally Posted by gilbo184 View Post
    Now, from above, I understand that this code is only checking 1 tile away from the player. However, I'm unsure what the
    Code:
     return (getClipping(x, y, height) & 0x1280120) == 0;
    is doing. Obviously, it checks the position 1 tile away, but what does the Mask mean here as they are different for each direction?
    I'm not too familiar with 317 so this might not be 100% exact, I'm going off my rs2 knowledge to write this.

    Each tile in the map has a clipping mask associated to it. This clipping mask can indicate many things like projectile clipping, but if we limit to movement:

    1 - If the tile is clipped, most likely because there is an object on it or it's some kind of place you shouldn't walk on, like water. I'm not sure if this is rs2-specific or if 317 has that.
    2 - If the movement coming from a certain direction is clipped. For example, you can't walk into walls, but you can walk from inside a wall to outside of it. Only the inwards direction is clipped.

    Quote Originally Posted by gilbo184 View Post
    I also understand that it returns false if not 0 etc.
    It's a basic AND operation with the mask, not much to say.

    Code:
    clipping mask = 00000000 00000000 01110000 11101001
    specific direction mask (ex: north) = 00000000 00000000 00000000 00000001
    result = 00000000 00000000 00000000 00000001
    If the result is not 0, it means the bit is flipped at this position in the clipping mask and that you cannot go in this direction. If the result is 0, it means the bit is not flipped and you can go in this direction.

    Edit:

    Quote Originally Posted by gilbo184 View Post

    Code:
    /**
    	 * Unsure how to explain this method
    	 * 
    	 * @[Only registered and activated users can see links. ] x
    	 * @[Only registered and activated users can see links. ] y
    	 * @[Only registered and activated users can see links. ] height
    	 * @[Only registered and activated users can see links. ]
    	 */
    	private int getClip(int x, int y, int height) {
    		int regionAbsX = (id >> 8) * 64;
    		int regionAbsY = (id & 0xff) * 64;
    		if (clips[height] == null) {
    			return 0;
    		}
    		return clips[height][x - regionAbsX][y - regionAbsY];
    	}
    For this part, you're just obtaining the clipping local to the region. The regionAbsX/regionAbsY are the TILE coords of the bottom-left corner tile of the region, almost directly where the red lines cross on the github page I linked above (for each region). By doing x - regionAbsX (and same for Y) it's finding the x offset between 0-63 of the tile inside the region.
    Project thread
    [Only registered and activated users can see links. ]
    Reply With Quote  
     

  4. Thankful users:


  5. #4  
    Registered Member
    Join Date
    Apr 2013
    Posts
    50
    Thanks given
    2
    Thanks received
    1
    Rep Power
    11
    Quote Originally Posted by clem585 View Post
    Bitshift by 3 to the right and dividing by 8 is equivalent. The first >> 3 obtains the chunkX/Y (wrongly named regionX/Y in the code you provided). This is essentially 1/64 of a region, and it's 8x8 in size, containing 64 tiles in total. Then the 2nd division by 8 obtains the regionX/regionY which are the x/y coordinates of the region. A region is 64x64 in size, containing 4096 tiles in total. The left bitshift by 8 is to encode the regionY along with the regionX in a single int. The bits in red are the regionY and the bits in green are the regionX:

    Code:
    regionId  = 00000000 00000000 00000000 00000000
    You can look at this page to visualize the size of a single region, enable the grid on the left: [Only registered and activated users can see links. ]



    I'm not too familiar with 317 so this might not be 100% exact, I'm going off my rs2 knowledge to write this.

    Each tile in the map has a clipping mask associated to it. This clipping mask can indicate many things like projectile clipping, but if we limit to movement:

    1 - If the tile is clipped, most likely because there is an object on it or it's some kind of place you shouldn't walk on, like water. I'm not sure if this is rs2-specific or if 317 has that.
    2 - If the movement coming from a certain direction is clipped. For example, you can't walk into walls, but you can walk from inside a wall to outside of it. Only the inwards direction is clipped.



    It's a basic AND operation with the mask, not much to say.

    Code:
    clipping mask = 00000000 00000000 01110000 11101001
    specific direction mask (ex: north) = 00000000 00000000 00000000 00000001
    result = 00000000 00000000 00000000 00000001
    If the result is not 0, it means the bit is flipped at this position in the clipping mask and that you cannot go in this direction. If the result is 0, it means the bit is not flipped and you can go in this direction.

    Edit:



    For this part, you're just obtaining the clipping local to the region. The regionAbsX/regionAbsY are the TILE coords of the bottom-left corner tile of the region, almost directly where the red lines cross on the github page I linked above (for each region). By doing x - regionAbsX (and same for Y) it's finding the x offset between 0-63 of the tile inside the region.
    Thanks a lot! This helps, I'm trying to implement a more random walk for the npcs. For example at the moment it only does 1 tile movements. So what I get from this is each direction (8 directions) has a mask. Is this mask always the same for every tile we are on? The random walk works with 1 tile from the npc, but when i add more then that it starts walking through walls.
    Reply With Quote  
     

  6. #5  
    Contributor

    clem585's Avatar
    Join Date
    Sep 2013
    Posts
    3,547
    Thanks given
    646
    Thanks received
    637
    Rep Power
    334
    Quote Originally Posted by gilbo184 View Post
    Thanks a lot! This helps, I'm trying to implement a more random walk for the npcs. For example at the moment it only does 1 tile movements. So what I get from this is each direction (8 directions) has a mask. Is this mask always the same for every tile we are on? The random walk works with 1 tile from the npc, but when i add more then that it starts walking through walls.
    Yes, the 8 directional masks to verify are the same for each tile. As for why your pathfinding algorithm allows NPCs to walk through walls, I cannot say. Normally a regular A* pathfinding algorithm would validate the clipping on the tile before adding the tile as a potential walkable tile. I'm not sure what your algorithm does.
    Project thread
    [Only registered and activated users can see links. ]
    Reply With Quote  
     


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. Replies: 2
    Last Post: 01-31-2012, 08:32 AM
  2. Regions and their usefulness
    By Maxi in forum Informative Threads
    Replies: 46
    Last Post: 12-13-2010, 09:16 AM
  3. Pathfinding and Clipping library
    By peterbjornx in forum Projects
    Replies: 22
    Last Post: 05-02-2009, 09:04 PM
  4. Replies: 6
    Last Post: 04-25-2009, 09:41 PM
  5. Understanding Packets and Unhandled Packets
    By Vastiko in forum Tutorials
    Replies: 10
    Last Post: 09-27-2008, 06:46 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
  •