search

Skretzo / shortest-path

Pathfinding for Old School RuneScape
BSD 2-Clause "Simplified" License
14 stars 34 forks source link

How did you get the collision map? #15

Open OlZe opened 2 years ago

OlZe commented 2 years ago

Hey,

I can't find a way to contact you, so I'm trying this way.

As part of my bachelor thesis I'm working on a runelite project, which involves pathing around the map. Naturally your shortest-path plugin has been very helpful to me.

As I can tell, the entire Collision Map has been saved in collision-map.zip

Runelite API has the option to give you a collision map, but for the current scene only. So my question is, what was your method to get a collision map which covers the entire osrs map? How do your update the collision-map.zip if the map updates in future?

Thank you very much

Skretzo commented 2 years ago

I can't find a way to contact you, so I'm trying this way.

If you want a more chat-like conversation with me (Skretzo#1303) then Discord private messages is a good place.

what was your method to get a collision map which covers the entire osrs map?

TL;DR: I run some sloppy code on some map data by Mejrs to find walls and fully blocked tiles, but the proper way is to generate it directly from the game cache files.

I will now briefly explain 3 methods to generate a collision map of OSRS with some pros and cons:

1) The future method of the shortest-path plugin 2) My snapshot method 3) The proper snapshot method

  1. The future method of this plugin involves using the RuneLite API for the scene and storing this data locally as you run around exploring the game. This is the only way to get get rid of the static collision-map.zip file, which is just a snapshot of the collision map at the time of its creation. My understanding is that in-game objects can only be changed roughly once every week, possibly also through intra-weekly coldfixes (following unannounced in-game countdowns), but not through hotfixes (silent updates without in-game countdowns), meaning I actually should push a new collision map every week. Another advantage of instead using the current scene is that it is the only way to know whether a gate/door is currently open or closed, which will have an impact on the in-game path (even if the door changed after you started pathfinding). I highly recommend you check out GeChallengeM's Path Marker if you want to know the technical details of correct OSRS pathfinding, but do know that OSRS does not use up-to-date technology for pathfinding (no A* or Dijkstra, it's most likely flood-fill [info from Mod Ash] or Breadth-first search [info on the OSRS Wiki]).
  2. My current method of generating the collision map is a bit weird, but it was the first idea I came up with when the original developer of this plugin (Runemoro) disappeared without documenting the creation process (looks like I did not learn from his mistake, hehe). I download the image data used in Mejrs's OSRS map, in particular the purple nomove and the red and yellow locations[Jagex name for game objects]. Each image represents a 64x64 tile area (called a region) in OSRS with 4x4 pixels to draw doors and walls on each tile. That gives 256x256 pixel images named according to which region they refer to (z_regionX_regionY.png, e.g. 0_50_50.png for Lumbridge). I then run some Python code over these images to find where movement in west, east, south, north, south-west, south-east, north-west and north-east is possible/not possible. Due to a total file size limit of 10 MB for RuneLite plugin-hub plugins and the RuneLite creator Adam urging plugin-hub plugins to reduce download bandwidth usage (the plugins are re-downloaded on every update) Runemoro made the collision map as small as possible while almost preserving perfect OSRS pathfinding by limiting to only 2 bits per tile (is west-east movement possible and is north-south movement possible?). From this you can also determine if diagonal movement is possible (checking west-east, north-south and diagonal for the neighbour tiles), but not edge case one-way diagonal movement. There are also 4 possible z-levels for each tile so we end up with 8 bits per tile (see this code for the full details). Finally I remove most doors and gates from the collision map because this plugin is notorious for using a lot of memory when it is impossible to reach the target of your selected path. I should maybe document and upload my silly collision map generation method somewhere, but don't expect it to happen soon.
  3. The proper way to generate a collision map file (or even read the collision map data only on demand?) is to rely on the OSRS game cache files. However retrieving collision map data from the cache does require fetching and using up-to-date XTEA decryption keys from the OpenRS2 Archive. This is the only way to get weekly up-to-date collision map data without actually running around in-game. The reason I don't use this method is simply that I have not looked into how to do it yet. The code to do it can probably be extracted and modified from the MapImageDumper in the RuneLite cache tools.

If your project is more about pathfinding and less about collision maps then I would recommend you check out the OSRS Wiki Pathfinding project. I am not sure what kind of state that project is in, but wiki admin Cook Me Plox will probably answer questions about that project and graph theory (or anything technical about OSRS really) if that is your cup of tea :)

uckfayer commented 2 years ago

I don't know if it would help with the third method but the code used to generate the osrs wiki's maps is available here and the wiki page about it is here.

I'd give it a go but Java hurts me

Skretzo commented 1 year ago

A follow up to 3) Generating a collision map from the cache:

I have now modified the MapImageDumper in RuneLite to create a Collision Map Dumper.

  1. Download a cache and XTEA keys from a specific point in time (e.g. latest) from https://archive.openrs2.org/caches.

  2. Replace all instances of the words mapsquare with region and key with keys in the keys.json file.

  3. Run the CollisionMapDumper with program arguments --cachedir "input-path" --xteapath "keys.json" --outputdir "output-path".

  4. Finally, I recommend removing empty collision maps which are typically inaccessible mapsquares out in the ocean or the void that are filled with only nomove tiles. This is about 600 mapsquares or so of the current total of roughly 2100 mapsquares.

miamilabs commented 6 months ago

A follow up to 3) Generating a collision map from the cache:

I have now modified the MapImageDumper in RuneLite to create a Collision Map Dumper.

1. Download a cache and XTEA keys from a specific point in time (e.g. latest) from https://archive.openrs2.org/caches.

2. Replace all instances of the words `mapsquare` with `region` and `key` with `keys` in the `keys.json` file.

3. Run the [CollisionMapDumper](https://github.com/Skretzo/runelite/blob/f5a286d71c8a7e083accc2035078cc1b738a86b9/cache/src/main/java/net/runelite/cache/CollisionMapDumper.java#L88) with program arguments `--cachedir "input-path" --xteapath "keys.json" --outputdir "output-path"`.

4. Finally, I recommend removing empty collision maps which are typically inaccessible mapsquares out in the ocean or the void that are filled with only nomove tiles. This is about 600 mapsquares or so of the current total of roughly 2100 mapsquares.

Just learning all the stuff and how items are working.

Did you had the issues to run the dumper?

[main] INFO net.runelite.cache.util.XteaKeyManager - Loaded 1772 keys
Exception in thread "main" java.lang.NullPointerException: Cannot invoke "net.runelite.cache.fs.Index.getArchive(int)" because "index" is null
    at net.runelite.cache.ObjectManager.load(ObjectManager.java:60)
    at net.runelite.cache.CollisionMapDumper.load(CollisionMapDumper.java:74)
    at net.runelite.cache.CollisionMapDumper.main(CollisionMapDumper.java:125)

It look like this cache file is empty and not existing. main_file_cache.idx255