15-Aufgabe.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Wegfindung in Labyrinthen\n",
    "### - Aufgabe - "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Der Weg ist das Ziel\n",
    "\n",
    "In der Aufgabe \"Labyrinthgenerator\" hast du einen Labyrinthgenerator entwickelt, der zufällige Labyrinthe erzeugen kann.\n",
    "Diesmal hast du die Aufgabe, ein Verfahren zu implementieren, dass den Weg vom Start zum Ziel in diesen Labyrinthen findet.\n",
    "\n",
    "### Labyrinth als Graph\n",
    "Ein Labyrinth kann auch als sogenannter Graph betrachtet werden. Graphen kann man wie Netze veranschaulichen; sie haben Kanten (Linien) und Knoten (Punkte). An Knoten können sich mehrere Kanten treffen. Wenn man die freien Pfade eines Labyrinths als Kanten versteht und die potenziellen Kreuzungen und Kurven als Knoten, wird aus dem Labyrinth (in schwarz-weiß) ein Graph (in orange). Das folgende Bild veranschaulicht diese Idee:\n",
    "\n",
    "<img src=\"http://caeze.bplaced.net/bwki/labyrinth1.png\" alt=\"labyrinth_1\" width=\"300\"/>\n",
    "\n",
    "An Graphen wird schon lange geforscht, daher gibt es eine Vielzahl an Verfahren und Algorithmen um verschiedenste Werte und Eigenschaften in einem Graphen zu bestimmen.\n",
    "\n",
    "### Datenformat und Ablauf des Algorithmus\n",
    "Deine Abgabe soll die Labyrinthe als png-Bilder einlesen können. Daraufhin soll aus dem Bild ein Graph erstellt werden, so wie in der Abbildung oben gezeigt. Ein schon länger bekanntes Verfahren zur Wegfindung in Graphen ist der Dijkstra-Algorithmus, den du in dieser Aufgabe implementieren sollst. Damit soll der Weg vom Start (rote Zelle) zum Ziel (blaue Zelle) gefunden und angezeigt werden. Wie der Dijkstra-Algorithmus funktioniert, ist weiter unten in der Aufgabe beschrieben.\n",
    "\n",
    "Zunächst einmal geben wir einige Funktionen vor, mit denen die Labyrinthe angezeigt werden können. Diesen übergeben wir eintweder ein Labyrinth-Feld in einer Datenstruktur, die weiter unten genauer beschrieben wird, ober ein Bild, das mit dem Modul 'matplotlib' von einer Webquelle geladen wurde.\n",
    "\n",
    "Wenn Bilder geladen werden sollen, wird von 'matplotlib.image.imread(\"png-Bild\")' ein Array aus Arrays zurückgegeben, das als Elemente die Farbwerte pro Pixel enthält. Ein Farbwert ist ein Array mit vier Elementen: der Wert für rot, grün, blau und die Transparenz des Pixels. Alle Werte haben den Wertebereich 0 bis 1. Der Wert für die Transparenz und die genaue Datenstruktur sind für diese Aufgabe jedoch nicht so wichtig, da weiter unten eine Funktion vorgegeben ist, die den Farbwert eines Pixels zurückgibt.\n",
    "\n",
    "Wichtig ist jedoch das Koordinatensystem der Bilder. Da es ein Array aus Arrays ist, ist die Indizierung umgekehrt, als sonst üblich (hier ein 3x2 Pixel großes Beispielbild):\n",
    "\n",
    "<code>bild = [[pixel0, pixel1, pixel2],</code>  \n",
    "<code>        [pixel3, pixel4, pixel5]]</code>\n",
    "\n",
    "Willst du nun auf <code>pixel5</code> zugreifen, so musst du zuerst die y-Koordinate angeben, um die richtige Zeile auszuwählen, und dann die x-Koordinate, um den richtigen Pixel in dieser Zeile auszuwählen. Also ist <code>bild[1][2] == pixel5</code>. Willst du nun den Wert für blau aus <code>pixel5</code> ermitteln, so musst du auf Index 2 von <code>pixel5</code> zugreifen, z. B.: <code>bild[1][2][2] == 0.237</code>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# importiere die nötigen Module, um Bilder von Labyrinthen anzeigen zu können\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.image as mpimg\n",
    "import matplotlib.cm as cm\n",
    "import numpy as np\n",
    "\n",
    "# mit dieser Funktion kannst du ein Array von Arrays anzeigen,\n",
    "# das benötigen wir später, um die Labyrinthe mit dem Weg anzuzeigen\n",
    "def zeige_labyrinth_an(feld, breite=10, höhe=10):\n",
    "    labyrinth = np.zeros([len(feld), len(feld[0]), 3])\n",
    "    for x in range(len(feld)):\n",
    "        for y in range(len(feld[x])):\n",
    "            zelle = feld[x][y]\n",
    "            # die verschiedenen Typen von Zellen werden weiter unten definiert\n",
    "            if zelle.typ == 'p':\n",
    "                labyrinth[x, y] = [1.0, 1.0, 1.0]\n",
    "            elif zelle.typ == 'w':\n",
    "                labyrinth[x, y] = [0.0, 0.0, 0.0]\n",
    "            elif zelle.typ == 's':\n",
    "                labyrinth[x, y] = [1.0, 0.0, 0.0]\n",
    "            elif zelle.typ == 'z':\n",
    "                labyrinth[x, y] = [0.0, 0.0, 1.0]\n",
    "            else:\n",
    "                labyrinth[x, y] = [0.6, 0.6, 0.6]\n",
    "    fig = plt.figure(figsize = (breite, höhe)) \n",
    "    ax = fig.add_subplot(111)\n",
    "    ax.imshow(labyrinth)\n",
    "    ax.axis('off')\n",
    "\n",
    "# mit dieser Funktion kannst du ein Bild anzeigen\n",
    "def zeige_bild_an(bild, breite=10, höhe=10):\n",
    "    fig = plt.figure(figsize = (breite, höhe)) \n",
    "    ax = fig.add_subplot(111)\n",
    "    ax.imshow(bild, clim=(0, 1))\n",
    "    ax.axis('off')\n",
    "\n",
    "# die folgenden Labyrinthe stehen dir zum Testen zur Verfügung\n",
    "einfaches_labyrinth = mpimg.imread('http://caeze.bplaced.net/bwki/easyMaze.png')\n",
    "einfaches_labyrinth_2 = mpimg.imread('http://caeze.bplaced.net/bwki/easyMaze2.png')\n",
    "normales_labyrinth = mpimg.imread('http://caeze.bplaced.net/bwki/normalMaze.png')\n",
    "normales_labyrinth_2 = mpimg.imread('http://caeze.bplaced.net/bwki/normalMaze2.png')\n",
    "unlösbares_labyrinth = mpimg.imread('http://caeze.bplaced.net/bwki/unsolvableMaze.png')\n",
    "unlösbares_labyrinth_2 = mpimg.imread('http://caeze.bplaced.net/bwki/unsolvableMaze2.png')\n",
    "\n",
    "# zeige ein Labyrinth an\n",
    "zeige_bild_an(einfaches_labyrinth, 3, 3)\n",
    "zeige_bild_an(einfaches_labyrinth_2, 3, 3)\n",
    "zeige_bild_an(normales_labyrinth, 3, 3)\n",
    "zeige_bild_an(normales_labyrinth_2, 3, 3)\n",
    "zeige_bild_an(unlösbares_labyrinth, 3, 3)\n",
    "zeige_bild_an(unlösbares_labyrinth_2, 3, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der Start (rote Zelle) ist in der linken oberen Ecke und das Ziel (blaue Zelle) ist in der rechten unteren Ecke.\n",
    "\n",
    " - Das ersten beiden Labyrinthe sind einfach lösbar, d.h. ein Weg vom Start zum Ziel ist auffindbar.\n",
    " - Die folgenden beiden Labyrinthe ist etwas komplexer, aber auch lösbar.\n",
    " - Die letzten beiden Labyrinthe sind nicht lösbar, aber haben einige Wege, die abgesucht werden können.\n",
    "\n",
    "Im Folgenden geben wir Klassen vor, mit denen du das Labyrinth-Feld aus dem png-Bild aufbauen kannst."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# um die Wände und Wege im Labyrinth darzustellen, verwenden wir Objekte\n",
    "# der folgenden Klassen  \n",
    "class UndefinierteZelle():\n",
    "    def __init__(self):\n",
    "        self.typ = 'uz'\n",
    "    def __str__(self):\n",
    "        return self.typ\n",
    "\n",
    "# Superklasse Zelle, von der die anderen Zellen (Wand, Pfad, Start, Ziel) erben\n",
    "class Zelle():\n",
    "    def __init__(self, x, y, nachbar_nord, nachbar_süd, nachbar_west, nachbar_ost):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.nachbar_nord = nachbar_nord\n",
    "        self.nachbar_süd = nachbar_süd\n",
    "        self.nachbar_west = nachbar_west\n",
    "        self.nachbar_ost = nachbar_ost\n",
    "        self.typ = 'z'\n",
    "        self.entfernung_vom_startknoten = float('inf')\n",
    "        self.nächste_weg_zelle = None\n",
    "    def __str__(self):\n",
    "        s = self.typ + ': ' + str(self.x) + '|' + str(self.y)\n",
    "        if self.nachbar_nord != None:\n",
    "            s += ', nord=' + self.nachbar_nord.typ\n",
    "        if self.nachbar_süd != None:\n",
    "            s += ', süd=' + self.nachbar_süd.typ\n",
    "        if self.nachbar_west != None:\n",
    "            s += ', west=' + self.nachbar_west.typ\n",
    "        if self.nachbar_ost != None:\n",
    "            s += ', ost=' + self.nachbar_ost.typ\n",
    "        s += ', entfernung_vom_startknoten=' + str(self.entfernung_vom_startknoten)\n",
    "        if self.nächste_weg_zelle != None:\n",
    "            s += ', vorherige_weg_zelle=' + str(self.nächste_weg_zelle.x) + '|' + str(self.nächste_weg_zelle.y)\n",
    "        return s\n",
    "    def __eq__(self, other):\n",
    "        if other == None:\n",
    "            return False\n",
    "        return self.x == other.x and self.y == other.y\n",
    "    \n",
    "class Pfad(Zelle):\n",
    "    def __init__(self, x, y, nachbar_nord=UndefinierteZelle(), nachbar_süd=UndefinierteZelle(), nachbar_west=UndefinierteZelle(), nachbar_ost=UndefinierteZelle()):\n",
    "        super().__init__(x, y, nachbar_nord, nachbar_süd, nachbar_west, nachbar_ost)\n",
    "        self.typ = 'p'\n",
    "    \n",
    "class Wand(Zelle):\n",
    "    def __init__(self, x, y, nachbar_nord=UndefinierteZelle(), nachbar_süd=UndefinierteZelle(), nachbar_west=UndefinierteZelle(), nachbar_ost=UndefinierteZelle()):\n",
    "        super().__init__(x, y, nachbar_nord, nachbar_süd, nachbar_west, nachbar_ost)\n",
    "        self.typ = 'w'\n",
    "    \n",
    "class Start(Zelle):\n",
    "    def __init__(self, x, y, nachbar_nord=UndefinierteZelle(), nachbar_süd=UndefinierteZelle(), nachbar_west=UndefinierteZelle(), nachbar_ost=UndefinierteZelle()):\n",
    "        super().__init__(x, y, nachbar_nord, nachbar_süd, nachbar_west, nachbar_ost)\n",
    "        self.typ = 's'\n",
    "    \n",
    "class Ziel(Zelle):\n",
    "    def __init__(self, x, y, nachbar_nord=UndefinierteZelle(), nachbar_süd=UndefinierteZelle(), nachbar_west=UndefinierteZelle(), nachbar_ost=UndefinierteZelle()):\n",
    "        super().__init__(x, y, nachbar_nord, nachbar_süd, nachbar_west, nachbar_ost)\n",
    "        self.typ = 'z'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bild zu Graph\n",
    "\n",
    "Nun wollen wir die png-Bilder der Labyrinthe in Graphen umwandeln. Eine Funktion, die die Farbe eines Bildes an einer Pixelposition ermittelt und eine, die die Größe des Bilds bestimmt, ist vorgegeben."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# diese Funktion gibt die Farbe an der Position (x|y) im gegebenen Bild zurück \n",
    "def farbe_an_position(bild, x, y):\n",
    "    rot = bild[y][x][0]\n",
    "    grün = bild[y][x][1]\n",
    "    blau = bild[y][x][2]\n",
    "    rgb = (rot, grün, blau)\n",
    "    if rgb == (1, 0, 0):\n",
    "        return 'rot'\n",
    "    if rgb == (0, 0, 1):\n",
    "        return 'blau'\n",
    "    if rgb == (1, 1, 1):\n",
    "        return 'weiß'\n",
    "    return 'schwarz'\n",
    "\n",
    "# diese Funktion gibt die Größe (Breite x Höhe) eines Bildes zurück\n",
    "def abmessungen(bild):\n",
    "    return (len(bild[0]), len(bild))\n",
    "\n",
    "# Beispielaufrufe\n",
    "print(farbe_an_position(unlösbares_labyrinth, 1, 1))\n",
    "print(abmessungen(unlösbares_labyrinth))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Hinweis*: die Startzelle ist bei (1|1) und die Zielzelle bei (19|11).\n",
    "\n",
    "*Beachte*: wenn du Arrays von Arrays verwendest, musst du bei der Indizierung aufpassen. Wenn die inneren Arrays die Zeilen des Labyrinth-Felds sind, so kehren sich die x- und y-Koordinate um!\n",
    "\n",
    "Schreibe nun eine Funktion, die ein Bild einliest und ein Array von Arrays der Zellen-Objekte zurückgibt, die das Labyrinth darstellen. Wichtig dabei ist, dass du die Nachbarobjekte der Zellen korrekt setzt!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# In dieser Funktion wird das Bild des Labyrinths in eine Datenstruktur\n",
    "# umgewandelt, mit der es einfacher ist, weiterzuarbeiten.\n",
    "# Schreibe die korrekten Zellen-Objekte an die richtge Stelle des\n",
    "# zweidimensionalen Arrays 'feld', welches du dann zurückgibst.\n",
    "def bild_zu_labyrinth_feld(bild):\n",
    "    breite, höhe = abmessungen(bild)\n",
    "    feld = []\n",
    "    for y in range(höhe):\n",
    "        zeile = []\n",
    "        for x in range(breite):\n",
    "            if farbe_an_position(bild, x, y) == 'weiß':\n",
    "                zeile.append(...)\n",
    "            if farbe_an_position(bild, x, y) == 'schwarz':\n",
    "                ...\n",
    "            if ...:\n",
    "                ...\n",
    "        feld.append(zeile)\n",
    "    \n",
    "    # setze alle Nachbarn aller Zellen korrekt\n",
    "    # die Zellen am Rand haben nicht in jede Richtung Nachbarn\n",
    "    ...\n",
    "    \n",
    "    return feld\n",
    "\n",
    "# das zu testende Labyrinth\n",
    "labyrinth = normales_labyrinth\n",
    "\n",
    "# erstelle die Datenstruktur aus dem Bild\n",
    "feld = bild_zu_labyrinth_feld(labyrinth)\n",
    "\n",
    "# gib die Informationen einer Zelle testweise aus\n",
    "print(feld[5][5])\n",
    "\n",
    "# teste deine Funktion, ob die beiden Bilder identisch sind\n",
    "zeige_bild_an(labyrinth, 3, 3)\n",
    "zeige_labyrinth_an(feld, 3, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nun wollen wir den Dijkstra-Algorithmus implementieren. Dazu benötigen wir nur noch die Pfad-, Start- und Zielzellen, die Wände sind nicht Teil des Graphen und werden ignoriert.\n",
    "\n",
    "Der Dijkstra-Algorithmus sucht den kürzesten Weg (den Pfad mit den geringsten Kosten) von einem Startknoten zu einem Zielknoten oder allen anderen Knoten in einem Graphen. Der Algorithmus gehört zu den Greedy-Algorithmen.\n",
    "Weitere Informationen findest du z. B. hier: https://de.wikipedia.org/wiki/Dijkstra-Algorithmus.\n",
    "\n",
    "Der Dijkstra-Algorithmus funktioniert folgendermaßen:\n",
    "\n",
    "<code>1. setze die Entfernung von der Startzelle zur Startzelle auf 0 (in 'Zelle.entfernung_vom_startknoten')</code>  \n",
    "<code>2. setze die Entfernung von allen anderen Zellen zur Startzelle auf unendlich (ist bereits so initialisiert)</code>  \n",
    "<code>3. initialisiere eine Liste, die eine Warteschlange darstellt</code>  \n",
    "<code>4. schreibe in die Warteschlange alle Zellen, die Teil des Graphen sind (Wege-, Start- und Zielzellen)</code>  \n",
    "<code>5. WHILE die Warteschlange ist nicht leer:</code>  \n",
    "<code>    5.1 wähle aus der Warteschlange diejenige Zelle beste_zelle, deren Entfernung zur Startzelle am kleinsten ist</code>  \n",
    "<code>    5.2 entferne diese Zelle beste_zelle aus der Warteschlange</code>  \n",
    "<code>    5.3 FOR Nachbar n aus allen Nachbarn der Zelle beste_zelle im Graphen:</code>  \n",
    "<code>        5.3.1 setze die alternative Weglänge aw = Entfernung zur Startzelle von beste_zelle + Kantenlänge</code>  \n",
    "<code>        5.3.2 WENN aw kleiner ist als die Entfernung zur Startzelle von n:</code>  \n",
    "<code>            5.3.2.1 setze die Entfernung zur Startzelle von n = aw</code>  \n",
    "<code>            5.3.2.2 speichere beste_zelle als nächste Wegzelle von n (in 'Zelle.nächste_weg_zelle')</code>  \n",
    "\n",
    "Diesen Pseudocode sollst du im nächsten Codeblock implementieren.\n",
    "\n",
    "Von der Funktion 'dijkstra' soll nichts zurückgegeben werden, sondern es sollen die Änderungen an den Zellen-Objekten direkt im übergebenen Labyrinth-Feld vorgenommen werden."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# da bei dieser Aufgabe die Pixel des Labyrinths immer nebeneinander liegen,\n",
    "# ist die Kantenlänge zwischen zwei Knoten im Graph immer 1\n",
    "kantenlänge = 1\n",
    "\n",
    "# diese Funktion gibt diejenige Zelle zurück, die den kleinsten Wert\n",
    "# von 'entfernung_vom_startknoten' in der Warteschlange hat\n",
    "def hole_zelle_mit_kürzester_entfernung_vom_startknoten(warteschlange):\n",
    "    zelle = None\n",
    "    ...\n",
    "    return zelle\n",
    "\n",
    "# diese Funktion gibt die Nachbarpfad-, Nachbarstart- und Nachbarzielzellen\n",
    "# der gegebenen zelle zurück, jedoch niemals Wände oder nichtvorhandene\n",
    "# Zellen außerhalb des Felds!\n",
    "def hole_nachbarn(feld, zelle):\n",
    "    nachbarn = []\n",
    "    ...\n",
    "    return nachbarn\n",
    "\n",
    "# der Djikstra-Algorithmus soll hier implementiert werden\n",
    "def dijkstra(feld, start):\n",
    "    ...\n",
    "\n",
    "# wähle das zu testende Labyrinth aus\n",
    "# bei unlösbaren Labyrinthen soll nach erfolgloser Suche einfach nichts geschehen\n",
    "labyrinth = normales_labyrinth\n",
    "#labyrinth = normales_labyrinth_2\n",
    "#labyrinth = einfaches_labyrinth\n",
    "#labyrinth = einfaches_labyrinth_2\n",
    "#labyrinth = unlösbares_labyrinth\n",
    "#labyrinth = unlösbares_labyrinth_2\n",
    "\n",
    "# lade das Feld jedes Mal neu, weil es in der Funktion 'dijkstra' verändert wird\n",
    "feld = bild_zu_labyrinth_feld(labyrinth)\n",
    "start = feld[1][1]\n",
    "ziel = feld[11][19]\n",
    "\n",
    "# führe den Dijkstra-Algorithmus aus\n",
    "dijkstra(feld, start)\n",
    "\n",
    "# laufe von der Ziel- zur Startzelle und markiere den gefundenen Weg\n",
    "n = ziel\n",
    "while n != None:\n",
    "    n = n.nächste_weg_zelle\n",
    "    if n != None and n != start:\n",
    "        n.typ = 'weg'\n",
    "\n",
    "# zeige den Weg an\n",
    "zeige_labyrinth_an(feld, 3, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fragen & Feedback:\n",
    "\n",
    "**Wenn ihr Fragen oder Anregungen zu der Aufgabe (oder Lösung) habt, dann tauscht euch gerne im [Chat](https://spectrum.chat/bwki/aufgabenarchiv/) darüber aus oder schreibt uns eine E-Mail (an info@bw-ki.de).**\n",
    "\n",
    "Wir freuen uns auch immer über **Feedback** (auch unter info@bw-ki.de):\n",
    "\n",
    "- War diese Aufgabe zu leicht, zu schwer oder genau richtig?\n",
    "- Wie lang hast du für diese Aufgabe ungefähr gebraucht?\n",
    "- Welche Art von Aufgaben wünschst du dir in Zukunft?"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda env:bwki_env]",
   "language": "python",
   "name": "conda-env-bwki_env-py"
  },
  "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.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}