From here to there

Von hier nach dort

A spider sees you. Between you and the spider is a wall. How does the spider know to walk around it?

Eine Spinne sieht dich. Zwischen dir und der Spinne ist eine Wand. Woher weiß die Spinne, dass sie drumherum laufen muss?

The spider does not have eyes like you. It cannot look at the room and "just see" the way. It needs a method, a step-by-step recipe. In computer science, such a recipe is called an algorithm.

Die Spinne hat keine Augen wie du. Sie kann nicht in den Raum schauen und den Weg "einfach sehen". Sie braucht eine Methode, ein Schritt-für-Schritt-Rezept. In der Informatik heißt so ein Rezept Algorithmus.

Finding a way is needed all over the game:

Wege finden braucht man überall im Spiel:

  • Monsters chase you, walk home, and wander around.
  • Monster jagen dich, laufen nach Hause und wandern herum.
  • You click on the floor, and the hero walks there, around obstacles.
  • Du klickst auf den Boden, und der Held läuft dorthin, um Hindernisse herum.
  • The world builder plans routes between the gates of every cube.
  • Der Weltbauer plant Routen zwischen den Toren jedes Würfels.

The floor is a grid

Der Boden ist ein Gitter

Each cube is 16 by 16 cells. For walking, the game only asks: from this cell, which of my four neighbours (east, west, south, north) can I step to?

Jeder Würfel hat 16 mal 16 Zellen. Fürs Laufen fragt das Spiel nur: Von dieser Zelle aus, auf welche meiner vier Nachbarn (Osten, Westen, Süden, Norden) kann ich treten?

A neighbour is blocked by walls, cliffs that are too high, fences, water, and ceilings too low for your body. (A big Stunder needs more headroom than a little spider!)

Ein Nachbar ist versperrt durch Wände, zu hohe Klippen, Zäune, Wasser und Decken, die zu niedrig für deinen Körper sind. (Ein großer Stunder braucht mehr Kopffreiheit als eine kleine Spinne!)

A map of "who can step where" is called a graph.

Eine Karte von "wer kann wohin treten" heißt Graph.

Try it: the flood

Probier es: die Flut

Press Flood. The search spreads out like water poured on the floor: first every square 1 step away, then 2 steps, then 3... The first time the water reaches the goal, we have found the shortest way. Draw walls and try to trap it!

Drück Flut. Die Suche breitet sich aus wie Wasser, das man auf den Boden gießt: zuerst jedes Feld 1 Schritt entfernt, dann 2 Schritte, dann 3... Wenn das Wasser zum ersten Mal das Ziel erreicht, haben wir den kürzesten Weg gefunden. Mal Wände und versuch, es einzusperren!

S is the start, G the goal. The colours show how many steps away each square is. Ignore the A* button for now, it comes next.

S ist der Start, Z das Ziel. Die Farben zeigen, wie viele Schritte jedes Feld entfernt ist. Den A*-Knopf kannst du erst mal ignorieren, der kommt gleich.

Breadth-first search, and breadcrumbs

Breitensuche und Brotkrumen

The flood has a real name: breadth-first search, or BFS. "Breadth first" means it goes wide before it goes far.

Die Flut hat einen echten Namen: Breitensuche (Breadth-First Search, BFS). "Breite zuerst" heißt: Sie geht erst in die Breite, bevor sie weit geht.

How does it know the way back? Every time the water reaches a new square, it leaves a breadcrumb there: "I came from that square". At the goal, follow the breadcrumbs back to the start, and turn the list around. That's the path!

Woher kennt sie den Weg zurück? Jedes Mal, wenn das Wasser ein neues Feld erreicht, lässt es dort eine Brotkrume liegen: "Ich kam von dem Feld da." Am Ziel folgst du den Brotkrumen zurück zum Start und drehst die Liste um. Das ist der Weg!

Monsters use BFS to chase you. Your hero uses it too when you click on the floor. If the spot cannot be reached, the hero walks to the reachable square closest to it.

Monster benutzen die Breitensuche, um dich zu jagen. Dein Held benutzt sie auch, wenn du auf den Boden klickst. Wenn die Stelle nicht erreichbar ist, läuft der Held zum erreichbaren Feld, das am nächsten dran ist.

Monsters give up

Monster geben auf

Searching a whole cube for every monster, many times a second, would be slow. So each search has a limit:

Für jedes Monster mehrmals pro Sekunde einen ganzen Würfel zu durchsuchen, wäre langsam. Darum hat jede Suche eine Grenze:

chasing you dich jagen24 steps 24 Schritte
walking home nach Hause laufen40 steps 40 Schritte
wandering or searching about herumwandern oder suchen6 steps 6 Schritte

If you are further away than the limit, the monster cannot find a way to you. Stairs, ramps and bridges are squares of the flood too, so they follow you up and down. But climb a ladder, and they lose you: they walk as close as they can get, wait a little, then give up.

Bist du weiter weg als die Grenze, findet das Monster keinen Weg zu dir. Treppen, Rampen und Brücken sind auch Felder der Flut, also folgen sie dir hinauf und hinunter. Aber kletter eine Leiter hoch, und sie verlieren dich: Sie laufen so nah heran, wie es geht, warten ein bisschen und geben dann auf.

Monster brains Monster-Gehirne

A*: searching with a hunch

A*: Suchen mit einer Ahnung

The flood is a bit silly: it searches in all directions, even away from the goal. A* (say "A star") is smarter.

Die Flut ist ein bisschen dumm: Sie sucht in alle Richtungen, auch weg vom Ziel. A* (sprich "A-Stern") ist schlauer.

For every square it could look at next, it adds up two numbers:

Für jedes Feld, das es als Nächstes anschauen könnte, zählt es zwei Zahlen zusammen:

  • how many steps it took to get there, and
  • wie viele Schritte es gebraucht hat, um dorthin zu kommen, und
  • a guess of how many steps are left: just the distance across and down, as if there were no walls.
  • eine Schätzung, wie viele Schritte noch fehlen: einfach die Strecke quer und runter, als gäbe es keine Wände.

It always continues from the square with the smallest total. So it heads towards the goal first, and only spreads out when a wall is in the way.

Es macht immer beim Feld mit der kleinsten Summe weiter. So geht es zuerst Richtung Ziel und breitet sich nur aus, wenn eine Wand im Weg ist.

Go back to the demo and compare: A* usually looks at far fewer squares, and still finds a shortest path.

Geh zurück zur Demo und vergleiche: A* schaut meistens viel weniger Felder an und findet trotzdem einen kürzesten Weg.

The world builder uses A*

Der Weltbauer benutzt A*

When the builder plans the routes through a cube, a step is not just "walk": it can be a stair, a bridge, a ladder, a jump or a drop. Each costs a different amount, so the builder prefers walking.

Wenn der Baumeister die Routen durch einen Würfel plant, ist ein Schritt nicht nur "gehen": Es kann eine Treppe sein, eine Brücke, eine Leiter, ein Sprung oder ein Fall. Jeder kostet unterschiedlich viel, darum geht der Baumeister lieber zu Fuß.

Two more tricks:

Zwei weitere Tricks:

  • Moves already used by another route cost almost nothing. So routes share stairs and bridges instead of building new ones.
  • Bewegungen, die schon eine andere Route benutzt, kosten fast nichts. So teilen sich Routen Treppen und Brücken, statt neue zu bauen.
  • Every square gets a small random extra cost. So two cubes with the same shape still get different routes.
  • Jedes Feld bekommt kleine zufällige Extrakosten. So bekommen zwei Würfel mit derselben Form trotzdem verschiedene Routen.

Can it see me? Line of sight

Kann es mich sehen? Die Sichtlinie

A monster only starts chasing you if it can see you. The Fire-face only spits fireballs if nothing is in the way.

Ein Monster fängt erst an, dich zu jagen, wenn es dich sehen kann. Das Fire-face spuckt nur Feuerbälle, wenn nichts im Weg ist.

The test is simple: walk along the straight line from the eye to you, in tiny steps of 0.15 cells, and at each step ask "is this inside something solid?". If any step is, the view is blocked.

Der Test ist einfach: Geh die gerade Linie vom Auge zu dir in winzigen Schritten von 0,15 Zellen entlang und frag bei jedem Schritt: "Ist das in etwas Festem drin?" Wenn auch nur ein Schritt es ist, ist die Sicht versperrt.

Simple, and fast enough to do for every monster several times a second.

Einfach, und schnell genug, um es für jedes Monster mehrmals pro Sekunde zu machen.

The real code: a monster's path

Der echte Code: der Weg eines Monsters


    

      
a and b are floors (cells you can stand on). height is how tall the monster is.

      
a und b sind Böden (Zellen, auf denen man stehen kann). height ist, wie groß das Monster ist.

      
prev is the breadcrumb map: for each floor, where we came from.

      
prev ist die Brotkrumen-Karte: für jeden Boden, woher wir kamen.

      
front is the edge of the water. Each round of the loop makes the next ring, next, from all neighbours not seen before.

      
front ist der Rand des Wassers. Jede Runde der Schleife macht den nächsten Ring, next, aus allen Nachbarn, die noch nicht gesehen wurden.

      
The loop stops after maxLen rounds (the "give up" limit), when the water cannot spread, or when b is reached.

      
Die Schleife hört nach maxLen Runden auf (die "Aufgeben"-Grenze), wenn sich das Wasser nicht mehr ausbreiten kann oder wenn b erreicht ist.

      
The last loop follows the breadcrumbs back from b, and unshift puts each one at the front of the list, so the path comes out in the right order.

      
Die letzte Schleife folgt den Brotkrumen von b zurück, und unshift legt jede an den Anfang der Liste, damit der Weg richtig herum herauskommt.

    

  






  
The real code: A* in the world builder

  
Der echte Code: A* im Weltbauer

  

    

    

      
gs: the cheapest cost found so far to reach each floor. hfn: the hunch, the distance across plus the distance down.

      
gs: die bisher billigsten Kosten, um jeden Boden zu erreichen. hfn: die Ahnung, die Strecke quer plus die Strecke runter.

      
open is a heap: a to-do list that always hands you the item with the smallest number first. The game's heap is in src/core/heap.js, only 30 lines long. The A* in the demo uses it too.

      
open ist ein Heap: eine Aufgabenliste, die dir immer zuerst das Ding mit der kleinsten Zahl gibt. Der Heap des Spiels steht in src/core/heap.js und ist nur 30 Zeilen lang. Das A* in der Demo benutzt ihn auch.

      
See the trick from the last slide? A move already in have costs only 0.2. Otherwise it costs its normal cost plus a little random jitter.

      
Siehst du den Trick von der letzten Folie? Eine Bewegung, die schon in have ist, kostet nur 0.2. Sonst kostet sie ihre normalen cost plus ein bisschen zufälliges jitter.