Stitching screenshots together to make a game level map

AlignImagesAladdin.ipynb

AlignImagesLegendOfKage.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "3dd39a99-b15c-4b68-9bc6-695c23d7f76c",
   "metadata": {},
   "source": [
    "This notebook gets a bunch of screenshots generated from an emulator and tries to align them. The objective is to make a video-game map of a level. In this notebook, I tried the NES game The Legend of Kage. This code is definitely not perfect.\n",
    "\n",
    "How were the screenshots generated? Using [BizHawk](https://tasvideos.org/BizHawk) and this Lua script that stores screenshots together with their scroll positions:\n",
    "\n",
    "```lua\n",
    "-- This template lives at `.../Lua/.template.lua`.\n",
    "while true do\n",
    "\t-- Code here will run once when the script is loaded, then after each emulated frame.\n",
    "\tnes.setdispsprites(false);\n",
    "\temu.frameadvance();\n",
    "    -- I thought these were the X and Y scroll coordinates, but I was wrong.\n",
    "    -- They are close to the real coordinates, but they are not exact.\n",
    "    -- Or maybe they are the real coordinates, but there is some delay between their value and the screenshot.\n",
    "\tx = mainmemory.read_u8(0x002E) * 256 + mainmemory.read_u8(0x0056);\n",
    "\ty = mainmemory.read_u8(0x0030) * 256 + mainmemory.read_u8(0x002F);\n",
    "\t-- Manually change this number after each level:\n",
    "\tlevel = 1\n",
    "\tclient.screenshot(string.format(\"/home/foobar/KageScreenshots/level%d-%04X-%04X.png\", level, x, y));\n",
    "\tnes.setdispsprites(true);\n",
    "\temu.frameadvance();\n",
    "end\n",
    "```\n",
    "\n",
    "Using the Game Genie code `SZNPVLSA` makes the player invincible, which really helps while making maps."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d8ef175-a20d-4681-9a28-c520fe36539e",
   "metadata": {},
   "source": [
    "This notebook was written for one single purpose.\n",
    "\n",
    "Feel free to edit it and adapt to your needs. The functions are small enough that they are easy to understand.\n",
    "\n",
    "This is also linked from: <https://www.vgmaps.com/forums/index.php?topic=4110.0>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2c130a6b-1817-402f-ad9b-a904304f3925",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Install:\n",
    "#     pip install pyora tqdm\n",
    "\n",
    "import math\n",
    "import re\n",
    "from collections import namedtuple\n",
    "from glob import glob\n",
    "from itertools import product\n",
    "from pathlib import Path\n",
    "from pprint import pprint\n",
    "from IPython.display import display\n",
    "from PIL import Image\n",
    "from PIL import ImageChops\n",
    "from PIL import ImageStat\n",
    "\n",
    "# For fancy progress bars\n",
    "from tqdm import tqdm\n",
    "# For writing the result as a layered image\n",
    "import pyora.Project\n",
    "# Alternatively, you may want to try the `layeredimage` module/project."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6ad5a221-0f61-4b3e-87e5-377a19c1f50d",
   "metadata": {},
   "outputs": [],
   "source": [
    "SCREENSHOTS_PATH = Path(\"/home/foobar/KageScreenshots/\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f9ec5703-8cd2-46b0-8fbd-d6062457d32b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def load_image(filename, crop=False):\n",
    "    \"\"\"Loads and automatically crops the screenshots\n",
    "\n",
    "    Cropping is done to avoid NES artifacts at the borders.\n",
    "    The lightning background effect is also negated by changing the color.\n",
    "    \"\"\"\n",
    "    with Image.open(filename) as bigimg:\n",
    "        # The screenshots are originally 256x224\n",
    "        if crop:\n",
    "            img = bigimg.crop((16, 16, bigimg.width - 16, bigimg.height - 16)).convert(\"RGB\")\n",
    "        else:\n",
    "            img = bigimg\n",
    "            img.load()\n",
    "        # Removing the lightining effect\n",
    "        if \"level1\" in str(filename):\n",
    "            data = img.load()\n",
    "            for y in range(img.height):\n",
    "                for x in range(img.width):\n",
    "                    if data[x, y] == (174, 174, 174):\n",
    "                        data[x, y] = (59, 0, 164)\n",
    "    return img"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cc81ff3d-dcef-4aa2-928c-8545197c5b40",
   "metadata": {},
   "outputs": [],
   "source": [
    "def diff_images(a, b, offset):\n",
    "    \"\"\"Calculates the difference between two images.\n",
    "\n",
    "    Tries to overlay b on top of a, moving b by the supplied offset.\n",
    "\n",
    "    Returns a number.\n",
    "\n",
    "    Parameters:\n",
    "    a, b  : PIL.Image\n",
    "    offset: (x,y) tuple\n",
    "    \"\"\"\n",
    "    (x, y) = offset\n",
    "    if x >= a.width or y >= a.height or x <= -b.width or y <= -b.height:\n",
    "        # No intersection between the two images.\n",
    "        return math.inf\n",
    "    cropped_a = a.crop((\n",
    "        max(0, x),  # Left\n",
    "        max(0, y),  # Top\n",
    "        min(a.width, b.width + x),  # Right\n",
    "        min(a.height, b.height + y),  # Bottom\n",
    "    ))\n",
    "    cropped_b = b.crop((\n",
    "        max(0, -x),  # Left\n",
    "        max(0, -y),  # Top\n",
    "        min(a.width - x, b.width),  # Right\n",
    "        min(a.height - y, b.height),  # Bottom\n",
    "    ))\n",
    "    # Ignoring pure black pixels, well, almost:\n",
    "    threshold_a = cropped_a.point(lambda value: 255 if value > 0 else 0)\n",
    "    diff = ImageChops.multiply(ImageChops.difference(cropped_a, cropped_b), threshold_a)\n",
    "    stats = ImageStat.Stat(diff)\n",
    "    # Idea: I could try dividing the sum by the total amount of pixels (width*height).\n",
    "    total = sum(stats.sum)\n",
    "\n",
    "    # For debugging with ipyplot, but it doesn't work:\n",
    "    #ipyplot.plot_images([a, b, cropped_a, cropped_b, diff], [\"A\", \"B\", \"Cropped A\", \"Cropped B\", \"Diff={}\".format(total)])\n",
    "    #ipyplot.plot_images([cropped_a, cropped_b, diff], [\"Cropped A\", \"Cropped B\", \"Diff={}\".format(total)])\n",
    "    # For debugging, without any extra library:\n",
    "    #display(a, b, cropped_a, cropped_b, diff, total, offset)\n",
    "    #display(cropped_a, cropped_b, diff, total, offset)\n",
    "    #display(diff, total, offset)\n",
    "\n",
    "    return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e87239e9-f6a5-4d16-bebe-c773fc0a0f18",
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_best_offset(a, b, initial, xrange, yrange):\n",
    "    \"\"\"Tries to find the best offset that minimizes the difference between two images.\n",
    "\n",
    "    Tries to put b over a, offsetted by the initial offset.\n",
    "    Then tries nudging the offset around until the best offset is found.\n",
    "    Stops early if a perfect offset (zero difference) is found.\n",
    "\n",
    "    Returns a (x, y) tuple.\n",
    "\n",
    "    Parameters:\n",
    "    a, b: PIL.Image\n",
    "    initial: (x, y) intial offset of b on top of a.\n",
    "    xrange, yrange: range (or sequence) of deltas to be applied to the initial offset.\n",
    "    \"\"\"\n",
    "    (x, y) = initial\n",
    "    all_deltas = sorted(product(xrange, yrange), key=lambda d: abs(d[0]) + abs(d[1]))\n",
    "    best_offset = initial\n",
    "    best_score = math.inf\n",
    "\n",
    "    for (dx, dy) in all_deltas:\n",
    "        offset = (x + dx, y + dy)\n",
    "        score = diff_images(a, b, offset)\n",
    "        if score < best_score:\n",
    "            best_offset = offset\n",
    "            best_score = score\n",
    "            if best_score == 0:\n",
    "                break\n",
    "\n",
    "    return best_offset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b7fa1c34-fee4-499b-b7aa-128fa7c6330e",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def process_images(glob_string, output_filename, crop, xrange, yrange):\n",
    "    max_x = 0\n",
    "    max_y = 0\n",
    "    items = []\n",
    "    for f in tqdm(glob(glob_string, root_dir=SCREENSHOTS_PATH)):\n",
    "        m = re.match(r\".*level([0-9])[a-z]*-([0-9A-Fa-f]+)-([0-9A-Fa-f]+)\\.png\", f)\n",
    "        level = int(m.group(1))\n",
    "        x = int(m.group(2), 16)\n",
    "        y = int(m.group(3), 16)\n",
    "        items.append((x, y, level, f))\n",
    "    \n",
    "        max_x = max(x, max_x)\n",
    "        max_y = max(y, max_y)\n",
    "    print(\"max_x = \", max_x, \"max_y = \", max_y)\n",
    "\n",
    "    canvas = Image.new(\"RGB\", (max_x + 256 + 128, max_y + 224 + 128))\n",
    "\n",
    "    first = True\n",
    "    for (x, y, level, f) in tqdm(sorted(items, key=lambda item: (-item[1], item[0]) )):\n",
    "        img = load_image(SCREENSHOTS_PATH / f, crop)\n",
    "        if first:\n",
    "            offset = (x+64, y+64)\n",
    "            first = False\n",
    "        else:\n",
    "            offset = find_best_offset(canvas, img, (x+64, y+64), xrange, yrange)\n",
    "        canvas.paste(img, offset)\n",
    "\n",
    "    canvas.save(SCREENSHOTS_PATH / output_filename)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "294734fd-c93c-43de-beea-110874250bd5",
   "metadata": {},
   "outputs": [],
   "source": [
    "process_images(\"level1-*.png\", \"stitched/level1.png\", True, range(-40, 40), range(-40, 40))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "00f9364c-9511-44a3-b5da-0d8b9c73912f",
   "metadata": {},
   "outputs": [],
   "source": [
    "process_images(\"level2-*.png\", \"stitched/level2.png\", False, range(1), range(1))\n",
    "process_images(\"level3-*.png\", \"stitched/level3.png\", False, range(1), range(-36, 36))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ddfcf6b9-7b0a-4c84-b4e3-697831db5d26",
   "metadata": {},
   "outputs": [],
   "source": [
    "#process_images(\"level4-*.png\", \"stitched/level4.png\", True, range(-36, 36), range(-36, 36))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d5aef3af-fe69-4138-8cae-1bc65bac6527",
   "metadata": {},
   "outputs": [],
   "source": [
    "process_images(\"level4-*-0000.png\", \"stitched/level4-xxxx-0000.png\", True, range(-36, 36), range(-36, 36))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2d7e1969-828d-4e52-81c2-b56536762bd7",
   "metadata": {},
   "outputs": [],
   "source": [
    "process_images(\"level4-*-0200.png\", \"stitched/level4-xxxx-0200.png\", True, range(-36, 36), range(-36, 36))\n",
    "process_images(\"level4-*-0300.png\", \"stitched/level4-xxxx-0300.png\", True, range(-36, 36), range(-36, 36))\n",
    "process_images(\"level4-*-0400.png\", \"stitched/level4-xxxx-0400.png\", True, range(-36, 36), range(-36, 36))\n",
    "process_images(\"level4-*-00FF.png\", \"stitched/level4-xxxx-00FF.png\", True, range(-36, 36), range(-36, 36))\n",
    "\n",
    "process_images(\"level4-0277-*.png\", \"stitched/level4-0277-yyyy.png\", True, range(-36, 36), range(-36, 36))\n",
    "process_images(\"level4-0078-*.png\", \"stitched/level4-0078-yyyy.png\", True, range(-36, 36), range(-36, 36))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3a907fad-8d60-4557-81c4-255b45a3eb27",
   "metadata": {},
   "outputs": [],
   "source": [
    "process_images(\"level4final-01DA-*.png\", \"stitched/level4-01DA-yyyy.png\", True, range(-36, 36), range(-36, 36))\n",
    "process_images(\"level4final-00*-*.png\", \"stitched/level4-00xx-yyyy.png\", True, range(-36, 36), range(-36, 36))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7df5cae6-e540-44c9-ab9f-b8cfc7b83c5e",
   "metadata": {},
   "source": [
    "After I created all the maps, I figured out the scrolling variables.\n",
    "\n",
    "With the help of the following script, and with the knowledge from [PPU scrolling](https://www.nesdev.org/wiki/PPU_scrolling), I concluded that the variables I was reading were, in fact, 2 frames delayed in relation to the scrolling. In other words, those memory locations are updated, and only two frames later the PPU scrolling was updated.\n",
    "\n",
    "I don't need it anymore for this game ([I've mapped everything already](https://vgmaps.com/Atlas/NES/index.htm#LegendOfKage)). I'm documenting the code here, so it can be helpful for getting the precise coordinates for other games.\n",
    "\n",
    "```lua\n",
    "local ppu_x = 0;\n",
    "local ppu_y = 0;\n",
    "local ppuscroll_turn = 0;\n",
    "\n",
    "local function watcher(addr, val, flags)\n",
    "\tif ppuscroll_turn == 0 then\n",
    "\t\tppu_x = val;\n",
    "\t\tppuscroll_turn = 1;\n",
    "\telseif ppuscroll_turn == 1 then\n",
    "\t\tppu_y = val;\n",
    "\t\tppppuscroll_turn = 2;\n",
    "\telse\n",
    "\t\tconsole.writeline(\"Too many PPUSCROLL writes. This shouldn't happen.\");\n",
    "\tend\n",
    "end\n",
    "\n",
    "local function reset_ppuscroll_counter()\n",
    "\tppuscroll_turn = 0\n",
    "end\n",
    "\n",
    "local last_delay <const> = 2;  -- Two frames of delay.\n",
    "local last_x = {};\n",
    "local last_y = {};\n",
    "\n",
    "local function push_delayed_value(tbl, val)\n",
    "\ttable.insert(tbl, val);\n",
    "\tif #tbl > last_delay then\n",
    "\t\treturn table.remove(tbl, 1);\n",
    "\tend\n",
    "\treturn nil\n",
    "end\n",
    "\n",
    "\n",
    "-- event.on_bus_write(watcher, 0x2005, \"PPUSCROLL\", \"System Bus\");\n",
    "event.on_bus_write(watcher, 0x2005);\n",
    "-- event.onmemorywrite(watcher, 0x2005);\n",
    "event.onframestart(reset_ppuscroll_counter);\n",
    "\n",
    "while true do\n",
    "\tlocal x = mainmemory.read_u8(0x002E) * 256 + mainmemory.read_u8(0x0056);\n",
    "\tlocal y = mainmemory.read_u8(0x0030) * 256 + mainmemory.read_u8(0x002F);\n",
    "\n",
    "\tlocal dx = push_delayed_value(last_x, x);\n",
    "\tlocal dy = push_delayed_value(last_y, y);\n",
    "\n",
    "\tif dx == nil then\n",
    "\t\tdx = -1;\n",
    "\tend\n",
    "\tif dy == nil then\n",
    "\t\tdy = -1\n",
    "\tend\n",
    "\n",
    "\tgui.drawText(2, 2, string.format(\"mem x=%d\\nold x=%d\\nppu x=%d\\n\\nmem y=%d\\nold y=%d\\nppu y=%d\", x, dx, ppu_x, y, dy, ppu_y), \"white\", \"black\", 12);\n",
    "\n",
    "    emu.frameadvance();\n",
    "end\n",
    "\n",
    "```"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "venv",
   "language": "python",
   "name": "venv"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}

AlignImagesRoadFighter.ipynb

rug-ride-(long-image).png

rug-ride-(multiple-rows).png