1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.
  2. Hey Guest, If you'd like to instant message with many other users, then join our
    Official Rune-Status Discord Server!
    Dismiss Notice
  3. Got your own Server? Looking for a Server to play right now??
    Make sure you check out the Public Server Directory!
    Dismiss Notice
  4. If you're new to the Rsps Scene and want to jump straight into learning how to Set-up and Customise your own RuneScape Private Sever then check out the Guides and Tutorials for RS2 here.
    Dismiss Notice
Dismiss Notice
Hey Guest,
Are you sure your posting in the Right Sections?
If your unsure which RuneTek version you are working with visit this page to find out.

Pathfinding Serverside Loaded From Cache

Discussion in 'Guides & Tutorials' started by Hydrozoa, May 4, 2017.

  1. Pathfinding

    In this post I will explain what I know about pathfinding. This isn’t all new information, but it’s scattered all over the interwebs. This is my attempt at relaying the most important parts relating to pathfinding. If you spot something wrong, please tell me. I will update this thread as new information comes up.


    At the very core of our problem is whether or not a tile is walkable. If we know this about all our tiles, we can simply implement some pathfinding algorithm. Those are heavily documented for gamedev on the web. Try searching for A* or Dijkstra.

    So, what we’re looking for is something like this:

    isTileWalkable(int x, int y, int layer)

    There are two different things you have to check for, when determining if a tile is walkable
    • If there’s an object there
    • If the terrain allows walking
    I will discuss these two below. After that, I will present a model you can query during pathfinding. This model will only contain data about terrains, though.

    The code I posted here works, but it’s not great. Some of it will create a ton of objects, choking your application. If you lack some classes, look at Hyperion. The cache loading is for the 377 cache, as is nearly every cache in RSPS emulating RS2.
     
    #1 Hydrozoa, May 4, 2017
    Last edited by a moderator: Jun 23, 2017
  2. World Objects
    First off, there are two different (maybe three) types of objects you need to take into consideration:

    1. Objects in the cache
    2. Objects you sent the client
    3. Objects you removed from the client
    A good place to start our search, is the cache. We know how to load all the objects in the world from the cache, and we’ve known this for a long time. If you don’t, I will show you how to do that in the code below.

    /**
     * A class which parses landscape files and fires events to a listener class.
     * @author Graham Edgecombe
     */
    public class LandscapeParser {
     
        /**
        * The cache.
        */
        private Cache cache;
     
        /**
        * The cache file.
        */
        private int area;
     
        /**
        * The listener.
        */
        private LandscapeListener listener;
     
        /**
        * Creates the parser.
        * @param cache The cache.
        * @param area The area id.
        * @param listener The listener.
        */
        public LandscapeParser(Cache cache, int area, LandscapeListener listener) {
            this.cache = cache;
            this.area = area;
            this.listener = listener;
        }
     
        /**
        * Parses the landscape file.
        * @throws IOException if an I/O error occurs.
        */
        public void parse() throws IOException {
            int x = ((area >> 8) & 0xFF) * 64;
            int y = (area & 0xFF) * 64;
     
            MapIndex index = cache.getIndexTable().getMapIndex(area);
     
            ByteBuffer buf = ZipUtils.unzip(cache.getFile(4, index.getLandscapeFile()));
            int objId = -1;
            while(true) {
                int objIdOffset = ByteBufferUtils.getSmart(buf);
                if(objIdOffset == 0) {
                    break;
                } else {
                    objId += objIdOffset;
                    int objPosInfo = 0;
                    while(true) {
                        int objPosInfoOffset = ByteBufferUtils.getSmart(buf);
                        if(objPosInfoOffset == 0) {
                            break;
                        } else {
                            objPosInfo += objPosInfoOffset - 1;
                  
                            int localX = objPosInfo >> 6 & 0x3f;
                            int localY = objPosInfo & 0x3f;
                            int plane = objPosInfo >> 12;
                  
                            int objOtherInfo = buf.get() & 0xFF;
                  
                            int type = objOtherInfo >> 2;
                            int rotation = objOtherInfo & 3;
                  
                            Location loc = Location.create(localX + x, localY + y, plane);
                  
                            listener.objectParsed(new GameObject(GameObjectDefinition.forId(objId), loc, type, rotation));
                        }
                    }
                }
            }
        }
    }

    Once you’ve got that loading down, you’ll need to worry about how you store these objects. Remember that it’s a lot of objects, so we don’t want to store them in an array and loop through that. My 377 cache has 1166825 world objects, so we need to be smart when selecting our data structure here. Think about how fast you can query if a tile has an object.

    Next, we need to worry about objects not present in the cache. These are objects you’ve sent the client, and these will impact some or all of your players. Many old servers use a “global objects”-file to spawn these objects, without editing the cache. I won’t go into detail about this, but bear in mind that you need to query these objects too.

    Finally, you have the option to remove objects from clients. This is pretty much the same story as the global objects above – if you’re removing objects that’re in the cache, you need to make sure your pathfinding knows about this change.

    That was our three main categories of objects. Now, it gets a bit more complicated. As you can tell from the parsing code, every object has a sizeX, sizeY, type and rotation (edit: you can't see the size in the code after all - the sizes are stored in the objects definition). The size is just how many tiles the object fills out on each axis, assuming the rotation is 0. There are four options for the rotation: 0, 1, 2, and 3. As I’ve just explained, 0 means no rotation. 1 means one rotation (I don’t know if this is clockwise or counter-clockwise though – feel free to post this if you know), 2 means two rotations, etc. What this means is that your sizeX will actually express how many tiles on the y-axis the object takes up, if the rotation is NOT 0 and NOT 2. This should be intuitive. If it’s not, grab a pen and paper and draw it.

    Now, we are left with the type of the object. This is an integer (in the mathematical sense), and it determines how the object will be clipped. Below are the different types, as I understand them. My understanding of these aren’t great, so feel free to contribute.
    • 0 -> 3 are walls. Their rotation will determine the clipping.
    • 9 is diagonal walls.
    • 10 and 11 are objects that cannot be walked on.
    • 22 is decoration, such as grass.
    There are many more, but I think these are the ones you’ll find interesting for pathfinding (edit: I don't know why I included type 22, as it is walkable).
     
    #2 Hydrozoa, May 4, 2017
    Last edited by a moderator: Jun 23, 2017
  3. Walkable terrain
    In the objects above, we had a few different places to look, to gather the information we need. For terrain, we only have the cache. Below, I will show you an example of how the cache can be parsed, to get information about terrains.

    /**
     * A class which parses map files in the game cache.
     */
    public class MapParser {
     
        /**
        * The cache.
        */
        private Cache cache;
     
        /**
        * The area id.
        */
        private int area;
     
        /**
        * The map listener.
        */
        private MapListener listener;
     
        /**
        * Creates the map parser.
        * @param cache The cache.
        * @param area The area id.
        * @param listener The listener.
        */
        public MapParser(Cache cache, int area, MapListener listener) {
            this.cache = cache;
            this.area = area;
            this.listener = listener;
        }
     
        /**
        * Parses the map file.
        * @throws IOException
        */
        public void parse() throws IOException {
            int x = ((area >> 8) & 0xFF) * 64;
            int y = (area & 0xFF) * 64;
    
            MapIndex index = cache.getIndexTable().getMapIndex(area);
            ByteBuffer buffer = ZipUtils.unzip(cache.getFile(4, index.getMapFile()));
    
            for (int plane = 0; plane < 4; plane++) {
                for (int localX = 0; localX < 64; localX++) {
                    for (int localY = 0; localY < 64; localY++) {
                        Location loc = Location.create(x + localX, y + localY, plane);
                        int flags = 0;
    
                        for (;;) {
                            int attributeId = buffer.get() & 0xFF;
    
                            if (attributeId == 0) {
                                listener.tileParsed(new Tile(loc, flags));
                                break;
                            } else if (attributeId == 1) {
                                buffer.get(); // don't know what this is
                                listener.tileParsed(new Tile(loc, flags));
                                break;
                            } else if (attributeId <= 49) {
                                buffer.get(); // don't know what this is
                            } else if (attributeId <= 81) {
                                flags = attributeId - 49;
                            }
                        }
                    }
                }
            }
        }
    }

    Just like objects, we get a few different variables for each tile: Coordinates, and a flags integer. I store the flags as an integer, but it’s not actually needed, as you’ll soon see. The integer is made of 32 bits, arranged into 4 bytes. Each of these bits represents some boolean data about the tile. Getting each bit is for many not an easy thing to do, so I’ll go into detail about this. The following statement will return true if the first bit is set to 1.

    (flags & 1) == 1

    The following statement will return true, if the second bit is set to 1.

    (flags & 2) == 2

    The following statement will return true, if the third bit is set to 1.

    (flags & 4) == 4

    The following statement will return true, if the fourth bit is set to 1.

    (flags & 8) == 8

    You’ll notice that the pattern is that the n’th bit represents a value of 2^n. You don’t need a good understanding of this though, as we only need the first two bits. The first bit of the flags int determines if the tile is unwalkable. If the bit 1, the tile is unwalkable. However, there is an exception to this: If the tile on layer above has the second bit of the flags set to 1, the tile will actually be walkable. This is true for bridges. We now know two masks for the flags:

    • If 0x1, then the tile is unwalkable
    • If 0x2, then the tile below it is walkable, independently of the 0x1 flag on that tile.

    Again, there are more masks than what I’ve described, but these are the ones useful for pathfinding.
     
    #3 Hydrozoa, May 4, 2017
    Last edited by a moderator: Jun 23, 2017
  4. Loading terrain data into memory
    As you saw, I call a listener whenever I parse a new tile. That listener will feed the data it receives, into a collisionmodel. This is just a data structure on the server that I can query real fast about a specific tile. It does require some memory though. I found that my heap usage was increased by about 70 MB after enabling the collisionmodel.

    The CollisionModel is just a huge data store, where you can request information about a tile in a location. The information you can query is if the tile is unwalkable, and if it has a bridge over it. Remember that the bridge mask is set on the tile above a given tile, but here we store if a tile has a tile with the bridge bit above it. I realize this is confusing, so I'm showing you below how I load the Tile that I pass the listener into the CollisionModel.

    When a new tile is parsed, I do this:

    CollisionModel map = World.getWorld().getCollisionModel();
    if ((tile.getFlags() & 0x1)==0x1) { // no walking for this tile
        map.updateWalkable(tile.getLoc(), false);
    } else if ((tile.getFlags() & 0x2)==0x2) { // bridge, so we set tile below to hasBridgeAbove
        if (tile.getLoc().getZ() > 0) { // this is the deepest layer, we cant go below
            map.updateBridgeAbove(Location.create(tile.getLoc().getX(), tile.getLoc().getY(), tile.getLoc().getZ()-1), true);
        }
    }

    In a central place on the server, I store this huge model. The code for the model is here:

    /**
     * Model of a map in layers. You can supply information to any coord, in any of the layers.
     * Amount of layers will be determined at initialization. Runescape has 5 layers.
     *
     * You can supply info about whether a location is walkable, and if it has a bridge above it.
     * TileMapBuilder will query this model for info on walkability, when building TileMaps.
     *
     * @author Hydrozoa
     */
    public class CollisionModel {
     
        private List<HashMap<Location, Information>> layers;
     
        public CollisionModel(int layers) {
            this.layers = new ArrayList<HashMap<Location, Information>>(layers);
            for (int i = 0; i < layers; i++) {
                this.layers.add(new HashMap<Location, Information>());
            }
        }
     
        public void updateWalkable(Location loc, boolean walkable) {
            if (layers.get(loc.getZ()) == null) {
                layers.add(new HashMap<Location,Information>());
            }
            HashMap<Location,Information> map = layers.get(loc.getZ());
            if (!map.containsKey(loc)) {
                map.put(loc, new Information(walkable, false));
            } else {
                map.get(loc).setWalkable(walkable);
            }
        }
     
        public void updateBridgeAbove(Location loc, boolean bridgeAbove) {
            if (layers.get(loc.getZ()) == null) {
                layers.add(new HashMap<Location,Information>());
            }
            HashMap<Location,Information> map = layers.get(loc.getZ());
            if (!map.containsKey(loc)) {
                map.put(loc, new Information(false, bridgeAbove));
            } else {
                map.get(loc).setBridgeAbove(bridgeAbove);
            }
        }
     
        public boolean isWalkable(int x, int y, int layer) {
            if (!hasInformation(x,y,layer)) {
                return false;
            }
            HashMap<Location,Information> map = layers.get(layer);
            return map.get(Location.create(x, y, layer)).isWalkable();
        }
     
        public boolean hasBridgeAbove(int x, int y, int layer) {
            if (!hasInformation(x,y,layer)) {
                return false;
            }
            HashMap<Location,Information> map = layers.get(layer);
            return map.get(Location.create(x, y, layer)).isBridgeAbove();
        }
     
        public boolean hasInformation(int x, int y, int layer) {
            if (layers.get(layer) == null) {
                return false;
            }
            HashMap<Location,Information> map = layers.get(layer);
            if (!map.containsKey(Location.create(x, y, layer))) {
                return false;
            }
            return true;
        }
     
        private class Information {
       
            private boolean walkable;
            private boolean bridgeAbove;
       
            public Information(boolean walkable, boolean bridgeAbove) {
                this.walkable = walkable;
                this.bridgeAbove = bridgeAbove;
            }
    
            public boolean isWalkable() {
                return walkable;
            }
    
            public void setWalkable(boolean walkable) {
                this.walkable = walkable;
            }
    
            public boolean isBridgeAbove() {
                return bridgeAbove;
            }
    
            public void setBridgeAbove(boolean bridgeAbove) {
                this.bridgeAbove = bridgeAbove;
            }
        }
    }

    Great! You now have the tools to load the terrain data into memory, and you’ll be able to query it when you need a new path. As I explained earlier, you should be able to use a properly documented pathfinding algorithm to find your paths now. Else, I will probably post the ones I use soon. Cheers!


    Final note: Remember that in Runescape, tiles are not either walkable or unwalkable. The tiles that have fences are walkable from some directions, but not from others. You can find out which direction a tile with a fence on it is walkable from, by looking at the object type (is it a diagonal fence or a straight fence?), as well as the rotation.


    Final final note: As you do this, you’ll notice that many caches are fucked. If you find one that isn’t glitched to hell, please contact me.
     
    #4 Hydrozoa, May 4, 2017
    Last edited by a moderator: Jun 23, 2017
    • Informative Informative x 2
    • List
  5. You may now post.
     
  6. This is some brilliant work, its also a very interesting read.
    Thanks for this contribution Hydrozoa :emoji_thumbsup:.
     
  7. Maaattteee you just solved a tile problem at my home location I've been having. Really informative, thank you
     
  8. Amazing little Tutorial bud!
     
  9. This was a nice read, refreshed my memory. Thank you :)
     
  10. thanks for this hydro very useful
     
Loading...