Algorithm Details Map Adjusting

Verification Of Maps

Warcraft III Replays store the path and checksum of the map the recorded game was played on. This way, Warcraft III can ensure that a given map is valid. Exactly the same algorithm is used by RK to verify maps. Since it is very slow to simply compute the checksums of all files in the Warcraft III map folder, the search is divided into several levels (explained underneath). As a result, maps are found a lot faster in the average case.
- - -

Basic Search Algorithm

Step 1

At first RK tries to verify the map file of the replay. Trivially, if this succeeds no must be done.

Step 2

The map path is not valid. At first RK compares the checksum of the required map with all stored checksums in the Harcoded Table. If this does not succeed we go to Step 3. If the returned map exists, search is over. If it does not exist, RK tries to find the returned map name via Map Folder Search. When the result is valid, search is done.

Step 3

Now exactly the same from Step 2 is done for the Extern Table. Success => Done

Step 4

This time Patch Table is used. If the map is detected, it gets extracted out of the MPQ and saved into the Warcraft III Map folder as a temporary => Done

Step 5

If all previous steps failed, the map name is searched via Map Folder Search. Success => Done

Step 6

The last option to find the replay is a Exhaustive Search. If this search failes, the required map is non-existent and needs to be downloaded.

---

Hardcoded Table

A hardcoded table with almost all frequently played ladder maps that are placed in the installation default folders.

Search speed : Very fast
Detection rate: Low (just detects standard ladder maps)

---

Extern Table

An extern table with no entries at the beginning. This table grows with every watched replay. Everytime a valid map path was encountered that is not already part of one of those two tables, the checksum and the path are stored.

Search speed : Between Very fast and Fast (depending on the table size)
Detection rate: Between Bad and Very good (depending on the table size)

---

Patch Table

An extern table that is saved in the ReplayKitPatch.mpq. It contains all checksums of deprecated Warcraft 3 Maps.

Search speed : Very fast
Detection rate: Bad (works just for deprecated patches)

---

Map Folder Search

A search by name in the Warcraft III map directory. This method only works for unmodified map names.

Search speed : Between Average and Slow (depending on the amount of maps)
Detection rate: Good

---

Exhaustive Search

Brute force approach. Computes the checksum for every file in the Warcraft III map directory and compares it to the searched checksum. This method can take several seconds, but the result is final!

Search speed : Between Slow and Horrible slow (depending on the amount of maps)
Detection rate: Perfect