Ich zeige dir gleich einen sehr einfachen Code für ein Unity 2D A Star Projekt.
Für das Spiel brauchte ich ein Weg-Such-System. Wie zum Beispiel, dass eine Spielfigur von einer Töpferei zu einem Lager laufen kann. Aber auch um zu schauen, ob Stadtmauern geschlossen sind. Hierfür eignen sich sogenannte Suchalgorithmen.
Als Nicht- Programmierer hatte ich am Anfang recht Mühe mich in das Thema einzuarbeiten. Eine der meiner Meinung nach besten Anleitungen fand ich hier: [Link hier klicken]. Man sollte sich etwas Zeit nehmen, um sich durch die Sliders zu klicken und schauen, was passiert. So kriegt man schnell ein Verständnis, wie ein solcher Algorithmus funktioniert.
Für Anfänger aber kein Tutorial
Ich will bewusst kein Tutorial hier veröffentlichen, jedoch möchte ich jedem Unity3D Anfänger helfen. Was wir machen: Wir erstellen ein Feld von 7 x 7 Felder, platzieren ein Start- und ein Ziel-Element, setzen Hindernisse und lassen den Computer den kürzesten Weg suchen.
Das, was ich Dir gleich zeige, basiert auf folgendem C# Code: [Hier klicken]. Ein YouTuber hat daraus ein Tutorial gemacht, das genau auf diesem Code basiert: [Hier klicken]. Sein Tutorial erklärt das ganze sehr anschaulich, jedoch fand ich, dass es noch etwas einfacher gehen könnte. Ich habe daher versucht, ein absolut einfaches A Star System für Unity zu entwickeln. Das System könnte man natürlich viel besser und schöner programmieren. Mir war es aber wichtig, alles so weit wie möglich zu vereinfachen, damit es auch absolute Anfänger verstehen. Ebenfalls kann man basierend auf diesem Code weitere Verbesserungen vornehmen.
Vorbereitung in Unity3D
Als erstes erstellst du eine neue Szene und fügst folgende Elemente ein:
Das GameObject Logic ist ein Empty, das leer ist. Danach kommen vier Standardcubes mit jeweils einem Collider und einem Material. Start ist Grün (Material), End ist das Ziel sowie blau (Material), Block repräsentiert ein Hindernis und ist rot (Material). Im Gegensatz stellen die Neutral Blöcke keine Hindernisse dar und sind weiss (Material).
Als nächstes erstellst du ein C# Script, welches du „test“ nennst.
Wichtig:
- Ich habe die Cubes mit der Grösse 0.9 X/Y/Z erstellt, damit man besser sieht, wo diese aufhören. Du kannst diese aber bei 1.0 belassen.
- Platziere alle Cubes an dieser Position: -2/-2/-2. Ob es -2 oder -5 oder ein anderer Wert ist, spielt keine Rolle – Hauptsache negativ. Das soll verhindern, dass diese Dummy-Cubes nachher nicht im Spielfeld rumgeistern:
Der Code
Ich mache hier kein Tutorial, aber die einzelnen Codeblöcke sollen ganz kurz erklärt werden, damit du später auch weisst, wo du weiterarbeiten kannst. Der ganze Code befindet sich am Ende der Seite:
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using System.Linq;
public class test : MonoBehaviour
{
/// <summary>
/// Based on: Daniel D'Agostino's Code:
/// https://bitbucket.org/dandago/experimental/src/bd19cef6fb2e0709d10e10a2ad854fe9d8249066/AStarPathfinding/AStarPathfinding/Program.cs
/// </summary>
public GameObject Kind_Start;
public GameObject Kind_End;
public GameObject Kind_Block;
public GameObject Kind_Neutral;
public int map_max_size = 7;
bool path_found = false;
List<Location> bestWayList = new List<Location>(); // Contains the Elements of the best way - What we actually looking for
RaycastHit hit; // Needed to hit Cubes
void Start()
{
StartCoroutine("Algorithmus");
}Wir haben nun eine Kartengrösse von 7 x 7 Felder definiert.
Unsere Funktion wird als Coroutine laufen. Das funktioniert fast gleich wie eine normale Funktion, jedoch haben wir die Möglichkeit, diese zu pausieren. Das wollen wir machen, damit wir sehen, wie das Programm arbeitet. Wir bauen also später nach jeder Berechnung kurze Pausen ein, um zu sehen, was unser Algorithmus macht.
Ganz im Ernst, bis jetzt war es doch wirklich sehr einfach. 🙂 Und keine Panik, es wird nicht viel komplizierter. Also lasst uns einen Schritt weitergehen:
IEnumerator Algorithmus()
{
Debug.Log("A* Pathfinding Project ist starting");
int[,] karte = new int[map_max_size, map_max_size];
karte[1, 1] = 1; // Start
karte[4, 5] = 2; // End
karte[0, 2] = 99; // Block
karte[1, 2] = 99; // Block
karte[2, 2] = 99; // Block
karte[3, 4] = 99; // Block
karte[4, 3] = 99; // Block
karte[5, 3] = 99; // Block
// Setzen der Variablen
Location current = null;
var start = new Location { X = 1, Y = 2 };// Wird nachher gleich geändert
var ziel = new Location { X = 4, Y = 5 };// Wird nachher gleich geändert
int g = 0;
var openList = new List<Location>();
var closedList = new List<Location>();Wir haben mit IEnumerator nun den Algorithmus definiert. Ich habe von Hand einige Felder bestimmt. Block bedeutet, dass hier die Hindernisse sind. Etwas irritierend ist vielleicht, dass anschliessend nochmals ein var start und ein var ziel definiert werden. Das hat nur damit zu tun, dass ich so den Code einfacher zeigen kann. Wenn du einen Fehler im Programm hast, dann wird es zu 99% so sein, dass Du im Array und auf der Liste Start bzw. Ende nicht die gleichen Werte definiert hast. Bedenke, die Arrays beginnen bei 0. Daher ist ganz unten links das Feld X = 0 und Y = 0.
Nun zeichnen wir die Karte in die Szene. Wir machen das, indem wir durch das 2D Array gehen und die Spielblöcke (Dummy-Blöcke) instanziieren (kopieren).
// Karte zeichnen
for (int x = 0; x < map_max_size; x++)
{
for (int y = 0; y < map_max_size; y++)
{
if (karte[x, y] == 1)
{
Instantiate(Kind_Start, new Vector3(x, 0, y), Quaternion.identity);
start = new Location { X = x, Y = y };// Setze die Start Position
}
if (karte[x, y] == 2)
{
Instantiate(Kind_End, new Vector3(x, 0, y), Quaternion.identity);
ziel = new Location { X = x, Y = y };// Setze die End Position
}
if (karte[x, y] == 99)
{
Instantiate(Kind_Block, new Vector3(x, 0, y), Quaternion.identity);
}
if (karte[x, y] == 0)
Instantiate(Kind_Neutral, new Vector3(x, 0, y), Quaternion.identity);
}
}Wir sehen hier nochmals: 1 = Start, 2 = Ziel, 99 = Blockade, 0 = Freie Bahn
Jetzt kommt der Algorithmus
Bisher haben wir eigentlich nur Vorbereitungsarbeiten gemacht, damit wir überhaupt etwas sehen. Starten wir also mit dem Algorithmus:
// Algorithmus
// start by adding the original position to the open list
openList.Add(start);
while (openList.Count > 0)
{
// get the square with the lowest F score
var lowest = openList.Min(l => l.F);
current = openList.First(l => l.F == lowest);
// add the current square to the closed list
closedList.Add(current);
// remove it from the open list
openList.Remove(current);Ich will den Algorithms nicht erklären. Wichtig ist nur zu wissen, dass wir mit drei Listen arbeiten. Die erste Liste ist die openList. Dort speichern wir alle Positionen auf dem 2D Spielfeld, die wir noch NICHT geprüft haben. In der zweiten Liste, der closedList, speichern wir alle Positionen auf dem 2D Spielfeld, die wir bereits berechnet haben. Wir werden also nacheinander alle Positionen aus der openList rausnehmen, verarbeiten und in die closedList werfen.
Wooooow, so simple! 🙂
Jetzt aber kommt etwas Irritierendes. Wir prüfen nun, ob wir das Ende gefunden haben. Das verwirrt ein wenig, weil wir ja noch gar nicht gesucht haben. Das ist richtig. Es handelt sich um eine Whileschleife und die Prüfung bzw. das Weg-Suchen kommt erst später. Also ganz ruhig bleiben. Wir bereiten nur etwas vor:
// Ziel gefunden
// if we added the destination to the closed list, we've found a path
if (closedList.FirstOrDefault(l => l.X == ziel.X && l.Y == ziel.Y) != null)
{
Debug.Log("<color=green>Ziel gefunden</color>");
Show_Best_Path();
path_found = true;
break;
}Dein Compiler wird nun reklamieren, da er die Funktion Show_Best_Path() nicht kennt. Kein Problem. Die definieren wir später.
So und jetzt kommt die Magie. Jetzt wird der beste Weg gesucht:
if (current.X > 0 && current.Y > 0 && current.X < map_max_size - 1 && current.Y < map_max_size - 1)
{
var adjacentSquares = GetWalkableAdjacentSquares(current.X, current.Y, karte);
g++;
foreach (var adjacentSquare in adjacentSquares)
{
// if this adjacent square is already in the closed list, ignore it
if (closedList.FirstOrDefault(l => l.X == adjacentSquare.X
&& l.Y == adjacentSquare.Y) != null)
continue;
// if it's not in the open list...
if (openList.FirstOrDefault(l => l.X == adjacentSquare.X
&& l.Y == adjacentSquare.Y) == null)
{
// compute its score, set the parent
adjacentSquare.G = g;
adjacentSquare.H = ComputeHScore(adjacentSquare.X, adjacentSquare.Y, ziel.X, ziel.Y);
adjacentSquare.F = adjacentSquare.G + adjacentSquare.H;
adjacentSquare.Parent = current;
// and add it to the open list
openList.Insert(0, adjacentSquare);
}
else
{
// test if using the current G score makes the adjacent square's F score
// lower, if yes update the parent because it means it's a better path
if (g + adjacentSquare.H < adjacentSquare.F)
{
adjacentSquare.G = g;
adjacentSquare.F = adjacentSquare.G + adjacentSquare.H;
adjacentSquare.Parent = current;
}
}
}
}
bestWayList.Clear();Was passiert da eigentlich? Egal. Es wird der kürzeste Weg zwischen Start und Ende gesucht. Man muss nur folgendes wissen: Ganz zu Beginn steht ein IF, das folgendes abfragt: current.X < map_max_size – 1 && current.Y < map_max_size – 1
Das Minus Eins (- 1) ist dazu da, weil ein Array immer bei 0 beginnt und hier statt 7 Felder ganze 8 Felder suchen würde. Sonst gäbe es einen „out of Range„-Fehler.
Das war’s schon fast. Wir kommen dem Ende näher. Damit wir auch jeweils sehen, welche Felder der Computer gerade prüft, habe ich noch etwas eingebaut:
while (current != null)
{
if (Physics.Raycast(new Vector3(current.X, 2, current.Y), transform.TransformDirection(Vector3.down), out hit, 100))
{
hit.transform.gameObject.GetComponent<Renderer>().material.color = Color.green;
bestWayList.Add(current);
}
yield return new WaitForSeconds(0.03F);
current = current.Parent;
}Der Computer schiesst nun einen Strahl auf einen weissen Cube und färbt diesen Grün, wenn er gerade dort am rechnen ist. Cool, oder? So sehen wir, was der Computer gerade macht. Dies ist jedoch nicht notwendig.
Falls wir kein Ziel gefunden haben, teilen wir das nun der Unity Console mit.
if (path_found == false)
{
Debug.Log("<color=red>KEIN Ziel gefunden</color>");
}
yield return null;
}
Vielleicht magst Du dich noch erinnern – wir haben am Anfang unserer Berechnungen den kürzesten Pfad bereits eingebaut. Diese Funktion wenden wir nun an:
void Show_Best_Path()
{
foreach(var item in bestWayList)
{
if (Physics.Raycast(new Vector3(item.X, 2, item.Y), transform.TransformDirection(Vector3.down), out hit, 100))
{
Debug.DrawRay(new Vector3(item.X, 2, item.Y), transform.TransformDirection(Vector3.down) * hit.distance, Color.red, 30);
hit.transform.gameObject.GetComponent<Renderer>().material.color = Color.black;
}
}
}In der Liste bestWayList sind alle Elemente gespeichert, die zum kürzesten Weg gehören. Das hat mich zu Beginn sehr irritiert. Von wo weiss nun das System, welches der kürzeste Weg ist? Sucht es nicht einfach alles Mögliche ab? Das Geheimnis liegt darin, dass die Liste bestWayList nach jedem Durchgang geleert wird. Dann geht das Programm den „bisher“ optimalsten Weg weiter und leert die Liste wieder. Wenn das Programm auf das Ziel gestossen ist, leert es die Liste nicht mehr, sondern liest diese im obigen Code aus und markiert den besten Weg in schwarz.
Noch etwas zum Code:
static List<Location> GetWalkableAdjacentSquares(int x, int y, int[,] karte)
{
var proposedLocations = new List<Location>()
{
new Location { X = x, Y = y - 1 },
new Location { X = x, Y = y + 1 },
new Location { X = x - 1, Y = y },
new Location { X = x + 1, Y = y },
};
return proposedLocations.Where(l => karte[l.X, l.Y] == 0 || karte[l.X, l.Y] == 2).ToList();
}
//Heuristische Distanz zwischen aktuellem und end Punkt
static int ComputeHScore(int x, int y, int targetX, int targetY)
{
return Mathf.Abs(targetX - x) + Mathf.Abs(targetY - y);
}Einfach diesen Code auch noch einfügen. Hier wird i.d.R nichts verändert.
Und ganz zum Schluss, füge ausserhalb der Klasse noch eine neue Klasse ein:
class Location
{
public int X;
public int Y;
public int F;
public int G;
public int H;
public Location Parent;
}Als Anfänger ist man hier etwas überfordert. Was ist denn nun eine Class? Vereinfacht gesagt ist das etwas, in dem man viele Werte gleichzeitig speichern kann.
Und so sieht das nun aus:
Nun willst du natürlich den ganzen Code haben. Ich habe Dir alles fix-fertig in ein Unity3D Projekt geladen, welches du nur noch downloaden musst. Viel Spass!
Download: http://www.paxaugusta.ch/downloads/Simple_A_Star.zip
Code anpassen
Wenn man einmal den recht einfachen Code verstanden hat, will man damit sicher herumexperimentieren. Man stellt fest, dass der Algorithmus einen Rechts-Oben Drall hat und somit diesen Weg forciert. Das lässt sich einfach anpassen, in dem man die Prüfung der Nachbarfelder anpasst:
Rechts-Oben Drall:
var proposedLocations = new List<Location>()
{
new Location { X = x, Y = y - 1 },
new Location { X = x, Y = y + 1 },
new Location { X = x - 1, Y = y },
new Location { X = x + 1, Y = y },
};Links-Unten Drall:
var proposedLocations = new List<Location>()
{
new Location { X = x, Y = y + 1 },
new Location { X = x, Y = y - 1 },
new Location { X = x + 1, Y = y },
new Location { X = x - 1, Y = y },
};Wenn Du auch Diagonal prüfen willst, ändere die GetWalkableAdjacentSquares Liste einfach so ab (bzw. erweitere sie):
static List<Location> GetWalkableAdjacentSquares(int x, int y, int[,] karte)
{
var proposedLocations = new List<Location>()
{
new Location { X = x, Y = y - 1 },
new Location { X = x, Y = y + 1 },
new Location { X = x - 1, Y = y },
new Location { X = x + 1, Y = y },
new Location { X = x + 1, Y = y + 1 },
new Location { X = x + 1, Y = y - 1 },
new Location { X = x - 1, Y = y + 1 },
new Location { X = x - 1, Y = y - 1 },
};
return proposedLocations.Where(l => karte[l.X, l.Y] == 0 || karte[l.X, l.Y] == 2).ToList();
}
