Stitching screenshots together to make a game level map

AlignImagesAladdin.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 [map for the \"Rug Ride\" level from the Aladdin game](https://vgmaps.com/Atlas/Genesis/index.htm#Aladdin).\n",
    "\n",
    "How were the screenshots generated? Using [BizHawk](https://tasvideos.org/BizHawk) and this trivial Lua script:\n",
    "\n",
    "```lua\n",
    "while true do\n",
    "\t-- Code here will run once when the script is loaded, then after each emulated frame.\n",
    "\tclient.screenshot(string.format(\"/home/foobar/AladdinScreenshots/rug-%06d.png\", emu.framecount()));\n",
    "\temu.frameadvance();\n",
    "end\n",
    "```"
   ]
  },
  {
   "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",
    "from collections import namedtuple\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.\n",
    "\n",
    "\n",
    "# For debugging: ipyplot or imshowtools\n",
    "\n",
    "# For debugging:\n",
    "# ipyplot had a great premise: being able to display images side-by-side.\n",
    "# Unfortunately, it's too buggy and is crashing with the images from this notebook.\n",
    "# import ipyplot\n",
    "\n",
    "# For debugging:\n",
    "# imshowtools doesn't support PIL images.\n",
    "# from imshowtools import imshow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6ad5a221-0f61-4b3e-87e5-377a19c1f50d",
   "metadata": {},
   "outputs": [],
   "source": [
    "SCREENSHOTS_PATH = Path(\"/home/foobar/AladdinScreenshots\")\n",
    "INITIAL_N = 4705\n",
    "FINAL_N  = 10461  # Inclusive"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f9ec5703-8cd2-46b0-8fbd-d6062457d32b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def load_image(n, size=\"small\"):\n",
    "    \"\"\"Loads and automatically crops the screenshots\n",
    "\n",
    "    Cropping is done to avoid HUD and other elements.\n",
    "    Cropping is fine-tuned for the \"Rug Ride\" level from Aladdin.\n",
    "    \"\"\"\n",
    "    fname = SCREENSHOTS_PATH / ('rug-%06d.png' % n)\n",
    "    with Image.open(fname) as bigimg:\n",
    "        if size == \"small\":\n",
    "            # Good crop for automatically finding offsets:\n",
    "            img = bigimg.crop((173, 0, 173+147, 18))\n",
    "        elif size == \"big\":\n",
    "            # Good crop for compositing:\n",
    "            img = bigimg.crop((173, 0, 173+147, 160))\n",
    "        elif size == \"full\":\n",
    "            img = bigimg.crop((0, 0, bigimg.width, bigimg.height))\n",
    "        else:\n",
    "            raise ValueError(\"Invalid value of parameter size={}\".format(size))\n",
    "    return img"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ad2314c7-c99d-4987-abbc-a84575e2dbb9",
   "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",
    "    diff = ImageChops.difference(cropped_a, cropped_b);\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(diff, total, offset)\n",
    "\n",
    "    return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6250e227-a884-47c9-a56f-0dc401c07d91",
   "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": "67d415f4-7675-4ece-b967-d6e1e625ebab",
   "metadata": {},
   "outputs": [],
   "source": [
    "diff_images(\n",
    "    load_image(INITIAL_N),\n",
    "    load_image(INITIAL_N+6),\n",
    "    (13, 0)\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b7fa1c34-fee4-499b-b7aa-128fa7c6330e",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "find_best_offset(\n",
    "    load_image(INITIAL_N),\n",
    "    load_image(INITIAL_N+6),\n",
    "    (6, 0),\n",
    "    range(-5, 17),\n",
    "    range(1),\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f2399014-f0ce-44ab-b8a4-9f693dbe5eab",
   "metadata": {},
   "outputs": [],
   "source": [
    "find_best_offset(\n",
    "    load_image(5274),\n",
    "    load_image(5275),\n",
    "    (7, 0),\n",
    "    range(-3, 32),\n",
    "    range(1),\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "348fac4e-a15c-4cca-b372-2edd6afc39c7",
   "metadata": {},
   "outputs": [],
   "source": [
    "find_best_offset(\n",
    "    load_image(6636),\n",
    "    load_image(6637),\n",
    "    (12, 0),\n",
    "    range(-16, 32),\n",
    "    range(1),\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f13ea71e-c745-4f76-988b-729107783148",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "ComputedOffset = namedtuple(\"ComputedOffset\", \"offset cummulative n name width height\")\n",
    "\n",
    "def compute_all_offsets():\n",
    "    a = None\n",
    "    offsets = []\n",
    "    off = (0, 0)\n",
    "    cummulative = (0, 0)\n",
    "    # If you have too many images large, you may want to try running this loop in parallel.\n",
    "    # If you wan to try that, good luck!\n",
    "    for i in tqdm(range(INITIAL_N, FINAL_N + 1)):\n",
    "        # Loading the full image just to compute the dimensions.\n",
    "        # Not super efficient, but good enough.\n",
    "        #raw = load_image(i, size=\"full\")\n",
    "        #w = raw.width\n",
    "        #h = raw.height\n",
    "        # Or I can just hardcode the dimensions to be quick\n",
    "        w = 320\n",
    "        h = 224\n",
    "\n",
    "        # Loading the small cropped image.\n",
    "        b = load_image(i, size=\"small\")\n",
    "        if a is not None:\n",
    "            # I know all the images here are moving horizontally, so I won't try any vertical offset.\n",
    "            off = find_best_offset(a, b, off, range(-off[0], 32), [0])\n",
    "            cummulative = (cummulative[0] + off[0], cummulative[1] + off[1])\n",
    "        offsets.append(\n",
    "            ComputedOffset(off, cummulative, i, (\"rug-%06d\" % i), w, h)\n",
    "        )\n",
    "        a = b\n",
    "    return offsets\n",
    "\n",
    "all_offsets = compute_all_offsets()\n",
    "pprint(all_offsets)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "821d879b-a528-4bf8-9758-41c54890bf87",
   "metadata": {},
   "outputs": [],
   "source": [
    "def save_composite_image(output_filename, computed_offsets, delta_offset=(0, 0)):\n",
    "    \"\"\"Compose all the images into a single multi-layer ORA file.\n",
    "\n",
    "    Parameters:\n",
    "    output_filename: String or Path for the ORA file.\n",
    "    computed_offsets: Sequence of ComputedOffset objects. Cannot be a generator.\n",
    "    delta_offset: Optional (dx, dy) to be added to all cummulative offsets.\n",
    "    \"\"\"\n",
    "    # Computing the overall dimensions:\n",
    "    width  = max(layer.width  + layer.cummulative[0] + delta_offset[0] for layer in computed_offsets)\n",
    "    height = max(layer.height + layer.cummulative[1] + delta_offset[1] for layer in computed_offsets)\n",
    "\n",
    "    project = pyora.Project.new(width, height)\n",
    "    for layer in computed_offsets:\n",
    "        project.add_layer(\n",
    "            # PIL.Image\n",
    "            # Note that this hack of loading the first image differently\n",
    "            # will make it incorrectly aligned with the rest.\n",
    "            # I know, and I'll fix it manually in GIMP.\n",
    "            image=load_image(layer.n, size=\"full\" if layer.n == INITIAL_N else \"big\"),\n",
    "            # Alternatively, it's easier to just load all the images the exact same way.\n",
    "            #image=load_image(layer.n, size=\"big\"),\n",
    "\n",
    "            # Absolute filesystem-like path of the group in the project.\n",
    "            # No relation to any real filesystem. It's used only for grouping layers.\n",
    "            path=layer.name,\n",
    "            # Layer position from the top-left of the canvas.\n",
    "            offsets=(layer.cummulative[0] + delta_offset[0], layer.cummulative[1] + delta_offset[1]),\n",
    "        )\n",
    "\n",
    "    # For performance, I'm using the first layer as the image thumbnail.\n",
    "    # Not ideal, but infinitely faster than waiting for the Renderer to render all the layers together.\n",
    "    # Note that this image may be modified by `pyora` itself, so you may want to supply a fresh `.copy()`.\n",
    "    thumbnail = load_image(computed_offsets[0].n)\n",
    "    project.save(output_filename, composite_image=thumbnail)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4ff410f4-57a5-4e39-8e47-dc37c3eb5231",
   "metadata": {},
   "outputs": [],
   "source": [
    "def make_batches():\n",
    "    batch_id = 1\n",
    "    batch_size = 500\n",
    "\n",
    "    with tqdm(total=len(all_offsets)) as progress:\n",
    "        start = 0\n",
    "        while start < len(all_offsets):\n",
    "            layers = []\n",
    "            skip_next = 0\n",
    "            base_off = all_offsets[start].cummulative\n",
    "            base_off = (-base_off[0], -base_off[1])\n",
    "            for i in range(start, start + batch_size):\n",
    "                if i >= len(all_offsets):\n",
    "                    break\n",
    "                if skip_next > 0:\n",
    "                    skip_next -= 1\n",
    "                    continue\n",
    "                co = all_offsets[i]\n",
    "                if co.offset == (0, 0) and co.n != INITIAL_N:\n",
    "                    # Skipping some dubious screenshots.\n",
    "                    continue\n",
    "                layers.append(co)\n",
    "                skip_next = 2\n",
    "            save_composite_image(SCREENSHOTS_PATH / (\"batch-%03d.ora\" % batch_id), layers, delta_offset=base_off)\n",
    "            batch_id += 1\n",
    "            start += batch_size\n",
    "            progress.update(batch_size)\n",
    "\n",
    "make_batches()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "23236145-651a-4973-b834-53a8926a4673",
   "metadata": {},
   "outputs": [],
   "source": [
    "def composite_last_image():\n",
    "    start = 0\n",
    "    for i in range(len(all_offsets)):\n",
    "        if all_offsets[i].n == 10204:\n",
    "            start = i\n",
    "            break\n",
    "\n",
    "    layers = []\n",
    "    skip_next = 0\n",
    "    base_off = all_offsets[start].cummulative\n",
    "    base_off = (-base_off[0], -base_off[1])\n",
    "    for i in range(start, len(all_offsets) + 1):\n",
    "        if i >= len(all_offsets):\n",
    "            break\n",
    "        if skip_next > 0:\n",
    "            skip_next -= 1\n",
    "            continue\n",
    "        co = all_offsets[i]\n",
    "        if co.offset == (0, 0):\n",
    "            # Skipping some dubious screenshots.\n",
    "            continue\n",
    "        layers.append(co)\n",
    "        skip_next = 1\n",
    "    save_composite_image(SCREENSHOTS_PATH / (\"batch-%03d.ora\" % 999), layers, delta_offset=base_off)\n",
    "\n",
    "composite_last_image()"
   ]
  }
 ],
 "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
}

AlignImagesLegendOfKage.ipynb

AlignImagesRoadFighter.ipynb

rug-ride-(long-image).png

rug-ride-(multiple-rows).png