Funktion und Nutzung des A* Algorithmus

Für mein Projekt, ein Echtszeitstrategiespiel (RTS) zu entwickeln, habe ich mich konsequenterweise mit der Wegfindung einer KI beschäftigt.

In diesem Beitrag möchte ich die Funktion des A* Algorithmus erklären und demonstrieren, wie dies mit Unity realisiert werden kann. Genutzt wird hierbei das bereits bestehende A*-Project von Aron Granberg.

Beginnen wir mit dem Konzept der Wegfindung. Als Gottgleiches Individuum können wir einem Pixelhaufen das Kommando geben, sich von Punkt A nach B im Raum zu bewegen. Diese Punkte sind in Unity als Vector3 (x,y,z) verfügbar.
Ein einfaches Bewegungsskript würde die beiden Punkte entgegennehmen und die Einheit auf direktem Wege (Stichwort: Abstand zweier Vektoren) mit einer Geschwindigkeit moveSpeed bewegen. Beispiel:

private void MakeMove(Vector3 dir)
    {
        transform.LookAt(dir);
        transform.position = Vector3.MoveTowards(transform.position, dir, Time.deltaTime * moveSpeed);
        if (transform.position == destination) move = false;
}
if(move) MakeMove(B)

Dies mag für einen Prototypen oder das Pendant eines Hallo Welt Programmes in der Spieleentwicklung durchgehen. Doch was passiert, wenn die Einheit (im Falle ohne Collider) auf ein Hindernis, z.B eine Mauer stößt? Sie läuft durch. Für das Bewegungsskript gibt es keine Hindernisse.

Hierbei kommt die Wegfindung in’s Spiel (wortwörtlich). Salopp gesagt ist folgendes die Aufgabe der Wegfindungsskripte: Finde den Schnellstmöglichen weg von A nach B, ohne gegen eine Wand zu laufen.

Und das geht am besten mit effizienten Algorithmen wie dem A*.

Definition: Der A* Algorithmus ist ein heuristischer Suchagorithmus zur Berechnung des  kürzesten Pfades zweier Punkte auf einem Graphen.

A* Iterationsdarstellung
A* Iterationsdarstellung

Kurze Erklärung zum GIF: Es sind 2 Punkte gegeben, A (rot) und B (grün). Diese liegen auf einem Raster mit gleichgroßern Felder = Knoten.
Würde man sich frontal (o/l/u/r) bewegen, ergibt es die Kosten 10 für die Bewegung. Diagonale Bewegungen haben einen Wert von 14. Somit sind Gerade Bewegungen zu bevorzugen. Die Sogenannten G-Kosten bezeichnen die Distanz des Knotens vom Startpunkt.
Dazu kommen zwei weitere Werte: H-Kosten; wie weit ist der Punkt vom Zielpunkt entfernt ist; und die F Kosten; die Summe beider Werte.

Während jeder Iteration werden um alle Knoten die angrenzenden Knoten markiert und die G/H/F Kosten berechnet. Dann wird der geringste F Wert gesichtet, iteriert, dann der zweithöchste, etc, solange, bis ein Pfad zum Ziel gefunden wurde; der Pfad mit den geringsten F Kosten.
Kleine Grafik:

Beispielgraph A*
Beispielgraph A*

Der blaue Weg ist konsequenterweise der Schnellste.

Dieser Algorithmus ist eine nette Alternative zum nativen Unity Nav-Mesh System, weshalb ich es auch für meine Projekte nutzen werde.

Neues Fenster mit JS browserunabhängig erzwingen

Durch Browsereinstellungen kann es passieren, dass trotz der JavaScript Methode

window.open()

die Links trotz des Defaultwertes _blank in einem neuen Tab geöffnet werden.

Um das zu umgehen, kann eine Eigenart der Funktion genutzt werden; werden Höhe und Breite angegeben, wird immer ein neues Fenster in der gewählten Dimension geöffnet. Ein kleiner Workaround, den ich gerade für mich entdeckt habe ist im Zusammenahg damit folgender: Mit dem Wissen, dass durch die Größenangabe immer ein neues Fenster geöffnet wird, benötigt man theoretisch nur die Verfügbare Bildschrimdimension (nicht die absolute, z.B HD/FullHD, 2k, etc.). Hierbei bietet uns ebenfalls JavaScript sehr simpel Hilfe an, da die Werte durch

window.screen.availWidth

beziehungsweise

window.screen.availWidth

ermittelt werden können.

Werden beide Grundlagen kombiniert erhält man folgendes Konstrukt:

<a href="#"  onclick="window.open(  \'http://www.google.de\',
\'_blank\',
\'toolbar=1,
location=1,
menubar=1,
width=window.screen.availWidth,
height=window.screen.availHeight\');"> Neues Fenster </a>

Durch die Parameter

toolbar, location, menubar

kann das neue Fenster noch genauer angepasst werden.