I’m about to show you a very simple code for a Unity 2D A Star project.
For the game, I needed a way-finding system. Like, for example, that a character can walk from pottery to a camp. But also to see if city walls are closed. So-called search algorithms are suitable for this.
As a non-programmer, I had a lot of trouble getting to grips with the subject at the beginning. I found one of the best instructions in my opinion here: [Link click here]. You should take some time to click through the sliders and see what happens. This way you will quickly get an understanding of how such an algorithm works.
FOR BEGINNERS BUT NO TUTORIAL
I deliberately don’t want to publish a tutorial here, however, I want to help every Unity3D beginner. What we do: We create a field of 7 x 7 squares, place a start and a finish element, set obstacles, and let the computer search for the shortest path.
What I am about to show you is based on the following C# code: [Click here]. A YouTuber has made a tutorial based exactly on this code: [Click here]. His tutorial explains the whole thing very clearly, but I thought it could be even simpler. So I tried to develop an absolutely simple A Star system for Unity. Of course, the system could be programmed much better and more attractive. But it was important to me to simplify everything as much as possible so that even absolute beginners can understand it. You can also make further improvements based on this code.
PREPARATION IN UNITY3D
First, you create a new scene and insert the following elements:
The GameObject Logic is an Empty. Then come four standard cubes, each with a collider and a material. The Start is green (material), End is the goal and blue (material), Block represents an obstacle and is red (material). In contrast, Neutral Blocks represent no obstacles and are white (Material).
Next, create a C# script which you call “test”.
IMPORTANT:
1. I have created the cubes with the size 0.9 X/Y/Z so that you can see better where they stop. You can leave them at 1.0.
2. place all cubes at this position: -2/-2/-2. It doesn’t matter if it is -2 or -5 or another value – the main thing is that it’s negative. This is to prevent these dummy cubes from wandering around in the playing field later:
THE CODE
I’m not doing a tutorial here, but the individual code blocks should be explained very briefly so that you know where to continue working later. The whole code is at the bottom of the page:
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");
}We have now defined a map size of 7 x 7 fields.
Our function will run as a coroutine. This works almost the same as a normal function, but we have the further option to pause it. We want to do this so that we can see how the program works. So we’ll build in short pauses later after each calculation to see what our algorithm is doing.
It’s been really easy so far, isn’t it?. 🙂 And don’t panic, it doesn’t get much more complicated. So let’s take it a step further:
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>();We have now defined the algorithm with IEnumerator. I have defined some fields by hand. Block means that here are the obstacles. It is perhaps a little irritating that afterward a var start and a var target are defined again. This has only to do with the fact that I can show the code more easily this way. If you have an error in the program, 99% of the time it will be because you have not defined the same values in the array and on the list start and end. Remember, the arrays start at 0. Therefore, at the very bottom left, is the field X = 0 and Y = 0.
Now we draw the map in the scene. We do this by going through the 2D array and copying the game blocks (dummy blocks).
// 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);
}
}We see here again: 1 = Start, 2 = Finish, 99 = Blockage, 0 = Free lane
NOW COMES THE ALGORITHM
So far we have only done preparatory work so that we can see anything at all. So let’s start with the algorithm:
// 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);I don’t want to explain the algorithm. It is only important to know that we work with three lists. The first list is the openList. There we store all positions on the 2D playing field that we have NOT yet checked. In the second list, the closedList, we store all positions on the 2D playing field that we have already calculated. So we will take out all positions from the openList one after the other, process them and throw them into the closedList.
Wooooow, so simple! 🙂
But now comes something irritating. We now check whether we have found the end. This is a bit confusing because we haven’t searched yet. That is correct. It is a neck loop and the check or the search for the path comes later. So stay calm. We are just preparing something:
// 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;
}Your compiler will now complain because it doesn’t know the function Show_Best_Path(). No problem. We’ll define it later.
So now comes the magic. Now we look for the best path:
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();What’s actually happening? Never mind. The shortest path between the start and the end is sought. You only need to know the following: At the very beginning there is an IF that queries the following: current.X < map_max_size – 1 && current.Y < map_max_size – 1
The minus one (- 1) is there because an array always starts at 0 and would search for 8 fields instead of 7. Otherwise, there would be an “out of range” error.
That’s almost it. We are getting closer to the end. I have added something so that we can see which fields the computer is checking:
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;
}The computer now shoots a beam at a white cube and colors it green if it is currently calculating there. Cool, isn’t it? This way we can see what the computer is doing. However, this is not so necessary.
If we haven’t found a target, we now tell the Unity Console.
if (path_found == false)
{
Debug.Log("<color=red>KEIN Ziel gefunden</color>");
}
yield return null;
}
You might remember – we already built in the shortest path at the beginning of our calculations. We now apply this function:
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 the list bestWayList all elements are stored that belong to the shortest path. This puzzled me a lot at the beginning. How does the system know which is the shortest path? Doesn’t it just search through every possibility? The secret lies in the fact that the bestWayList is emptied after each pass. Then the program continues along the “so far” most optimal path and empties the list again. When the program has hit the target, it no longer empties the list, but reads it out in the code above and marks the best way in black.
One more thing about the 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);
}Simply insert this code as well. As a rule, nothing is changed here.
And finally, add a new class outside the class:
class Location
{
public int X;
public int Y;
public int F;
public int G;
public int H;
public Location Parent;
}As a beginner, you are a bit overwhelmed here. What is a class? To put it simply, it is something in which you can store many values at the same time.
And this is what it looks like:
Now, of course, you want the whole code. I have loaded everything ready-to-use into a Unity3D project, which you only need to download. Have fun!
Download: http://www.paxaugusta.ch/downloads/Simple_A_Star.zip
ADAPT CODE
Once you understand the fairly simple code, you will want to experiment with it. You will notice that the algorithm has a right-up twist and thus forces this way. This can be easily adjusted by adjusting the check of the neighboring fields:
Right-Top Twist:
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 },
};Left-Bottom Twist:
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 },
};If you want to check diagonal direction as well, change the GetWalkableAdjacentSquares Liste to this:
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();
}
