Last active
June 3, 2025 17:33
-
-
Save stylophone/3448727 to your computer and use it in GitHub Desktop.
Unity C# implementation of A* algorithm
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Unity C# Port of Andrea Giammarchi's JavaScript A* algorithm (http://devpro.it/javascript_id_137.html) | |
| * | |
| * Usage: | |
| * | |
| int[][] map = new int[][] | |
| { | |
| new int[] {0, 0, 0, 0, 0, 0, 0, 0}, | |
| new int[] {0, 0, 0, 0, 0, 0, 0, 0}, | |
| new int[] {0, 0, 0, 1, 0, 0, 0, 0}, | |
| new int[] {0, 0, 0, 1, 0, 0, 0, 0}, | |
| new int[] {0, 0, 0, 1, 0, 0, 0, 0}, | |
| new int[] {1, 0, 1, 0, 0, 0, 0, 0}, | |
| new int[] {1, 0, 1, 0, 0, 0, 0, 0}, | |
| new int[] {1, 1, 1, 1, 1, 1, 0, 0}, | |
| new int[] {1, 0, 1, 0, 0, 0, 0, 0}, | |
| new int[] {1, 0, 1, 2, 0, 0, 0, 0} | |
| }; | |
| int[] start = new int[2] {0, 0}; | |
| int[] end = new int[2] {5, 5}; | |
| List<Vector2> path = new Astar(map, start, end, "DiagonalFree").result; | |
| */ | |
| using System; | |
| using System.Collections.Generic; | |
| using System.Collections; | |
| using UnityEngine; | |
| public class Astar | |
| { | |
| public List<Vector2> result = new List<Vector2>(); | |
| private string find; | |
| private class _Object { | |
| public int x { | |
| get; | |
| set; | |
| } | |
| public int y { | |
| get; | |
| set; | |
| } | |
| public double f { | |
| get; | |
| set; | |
| } | |
| public double g { | |
| get; | |
| set; | |
| } | |
| public int v { | |
| get; | |
| set; | |
| } | |
| public _Object p { | |
| get; | |
| set; | |
| } | |
| public _Object (int x, int y) { | |
| this.x = x; | |
| this.y = y; | |
| } | |
| } | |
| private _Object[] diagonalSuccessors (bool xN, bool xS, bool xE, bool xW, int N, int S, int E, int W, int[][] grid, int rows, int cols, _Object[] result, int i) { | |
| if (xN) { | |
| if (xE && grid[N][E] == 0) { | |
| result[i++] = new _Object(E, N); | |
| } | |
| if (xW && grid[N][W] == 0) { | |
| result[i++] = new _Object(W, N); | |
| } | |
| } | |
| if (xS) { | |
| if (xE && grid[S][E] == 0) { | |
| result[i++] = new _Object(E, S); | |
| } | |
| if (xW && grid[S][W] == 0) { | |
| result[i++] = new _Object(W, S); | |
| } | |
| } | |
| return result; | |
| } | |
| private _Object[] diagonalSuccessorsFree (bool xN, bool xS, bool xE, bool xW, int N, int S, int E, int W, int[][] grid, int rows, int cols, _Object[] result, int i) { | |
| xN = N > -1; | |
| xS = S < rows; | |
| xE = E < cols; | |
| xW = W > -1; | |
| if (xE) { | |
| if (xN && grid[N][E] == 0) { | |
| result[i++] = new _Object(E, N); | |
| } | |
| if (xS && grid[S][E] == 0) { | |
| result[i++] = new _Object(E, S); | |
| } | |
| } | |
| if (xW) { | |
| if (xN && grid[N][W] == 0) { | |
| result[i++] = new _Object(W, N); | |
| } | |
| if (xS && grid[S][W] == 0) { | |
| result[i++] = new _Object(W, S); | |
| } | |
| } | |
| return result; | |
| } | |
| private _Object[] nothingToDo (bool xN, bool xS, bool xE, bool xW, int N, int S, int E, int W, int[][] grid, int rows, int cols, _Object[] result, int i) { | |
| return result; | |
| } | |
| private _Object[] successors (int x, int y, int[][] grid, int rows, int cols) { | |
| int N = y - 1; | |
| int S = y + 1; | |
| int E = x + 1; | |
| int W = x - 1; | |
| bool xN = N > -1 && grid[N][x] == 0; | |
| bool xS = S < rows && grid[S][x] == 0; | |
| bool xE = E < cols && grid[y][E] == 0; | |
| bool xW = W > -1 && grid[y][W] == 0; | |
| int i = 0; | |
| _Object[] result = new _Object[8]; | |
| if (xN) { | |
| result[i++] = new _Object(x, N); | |
| } | |
| if (xE) { | |
| result[i++] = new _Object(E, y); | |
| } | |
| if (xS) { | |
| result[i++] = new _Object(x, S); | |
| } | |
| if (xW) { | |
| result[i++] = new _Object(W, y); | |
| } | |
| _Object[] obj = | |
| (this.find == "Diagonal" || this.find == "Euclidean") ? diagonalSuccessors (xN, xS, xE, xW, N, S, E, W, grid, rows, cols, result, i): | |
| (this.find == "DiagonalFree"|| this.find == "EuclideanFree")? diagonalSuccessorsFree (xN, xS, xE, xW, N, S, E, W, grid, rows, cols, result, i): | |
| nothingToDo (xN, xS, xE, xW, N, S, E, W, grid, rows, cols, result, i); | |
| return obj; | |
| } | |
| private double diagonal (_Object start, _Object end) { | |
| return Math.Max(Math.Abs(start.x - end.x), Math.Abs(start.y - end.y)); | |
| } | |
| private double euclidean(_Object start, _Object end) { | |
| var x = start.x - end.x; | |
| var y = start.y - end.y; | |
| return Math.Sqrt(x * x + y * y); | |
| } | |
| private double manhattan(_Object start, _Object end) { | |
| return Math.Abs(start.x - end.x) + Math.Abs(start.y - end.y); | |
| } | |
| public Astar (int[][] grid, int[] s, int[] e, string f) | |
| { | |
| this.find = (f == null) ? "Diagonal" : f; | |
| int cols = grid[0].Length; | |
| int rows = grid.Length; | |
| int limit = cols * rows; | |
| int length = 1; | |
| List<_Object> open = new List<_Object>(); | |
| open.Add(new _Object(s[0], s[1])); | |
| open[0].f = 0; | |
| open[0].g = 0; | |
| open[0].v = s[0]+s[1]*cols; | |
| _Object current; | |
| List<int> list = new List<int>(); | |
| double distanceS; | |
| double distanceE; | |
| int i; | |
| int j; | |
| double max; | |
| int min; | |
| _Object[] next; | |
| _Object adj; | |
| _Object end = new _Object(e[0], e[1]); | |
| end.v = e[0]+e[1]*cols; | |
| bool inList; | |
| do { | |
| max = limit; | |
| min = 0; | |
| for (i = 0; i < length; i++) { | |
| if (open[i].f < max) { | |
| max = open[i].f; | |
| min = i; | |
| } | |
| } | |
| current = open[min]; | |
| open.RemoveAt(min); | |
| if (current.v != end.v) { | |
| --length; | |
| next = successors(current.x, current.y, grid, rows, cols); | |
| for (i = 0, j = next.Length; i < j; ++i) | |
| { | |
| if (next[i] == null) { | |
| continue; | |
| } | |
| (adj = next[i]).p = current; | |
| adj.f = adj.g = 0; | |
| adj.v = adj.x + adj.y * cols; | |
| inList = false; | |
| foreach (int key in list) { | |
| if (adj.v == key) { | |
| inList = true; | |
| } | |
| } | |
| if (!inList) { | |
| if (this.find == "DiagonalFree" || this.find == "Diagonal") { | |
| distanceS = diagonal(adj, current); | |
| distanceE = diagonal(adj, end); | |
| } | |
| else if (this.find == "Euclidean" || this.find == "EuclideanFree") { | |
| distanceS = euclidean(adj, current); | |
| distanceE = euclidean(adj, end); | |
| } | |
| else { | |
| distanceS = manhattan(adj, current); | |
| distanceE = manhattan(adj, end); | |
| } | |
| adj.f = (adj.g = current.g + distanceS) + distanceE; | |
| open.Add(adj); | |
| list.Add(adj.v); | |
| length++; | |
| } | |
| } | |
| } | |
| else { | |
| i = length = 0; | |
| do { | |
| this.result.Add(new Vector2(current.x, current.y)); | |
| } | |
| while ((current = current.p) != null); | |
| result.Reverse(); | |
| } | |
| } | |
| while (length != 0); | |
| } | |
| } |
Does this algorithm allow going only in 4 directions (E, N, W, S) and not in diagonals?
Never mind, just needed to provide empty f parameter :)
Thanks for the port, saved me a LOT of time!
How do i add a penalty for walking over certain terrain like swamp or snow?
Excellent work @stylophone
Is it possible to add a turn penalty or restrict turns amount?
Author
Excellent work @stylophone
Is it possible to add a turn penalty or restrict turns amount?
Yes but turn penalty is a part of game logic that has nothing to do with pathfinding. Once the path has been found, you should track the player movement state yourself. Which node has been passed/which one has not, and so on.
Thanks for the quick reply @stylophone!
The problem is that the Astar returns only the best path (as it should) but if we consider the best path as the path with the least turns and not the shortest path then the turn penalty should be added to the Astar itself or am I missing something here?
Author
Thanks for the quick reply @stylophone!
The problem is that the Astar returns only the best path (as it should) but if we consider the best path as the path with the least turns and not the shortest path then the turn penalty should be added to the Astar itself or am I missing something here?
I see...Sorry for I misunderstood the term turn penalty. I think there's something that can be done as pathfinding cost as what Unity's nav pathfinding has done. But I have no idea how to achieve it so far. I think I'll look into it when I'm not too busy..
No problem at all, thanks for the help, it's highly appreciated!
I would love to hear from you when you'll have the time to dig into it, I
think the right direction for the solution will be adding a high cost for a
turn, but also allowing the path-finding algo to re-traverse the node that
had a turn on it again (when passed from a different direction).
…On Wed, Apr 28, 2021 at 4:13 AM stylophone ***@***.***> wrote:
***@***.**** commented on this gist.
------------------------------
Thanks for the quick reply @stylophone <https://github.com/stylophone>!
The problem is that the Astar returns only the best path (as it should)
but if we consider the best path as the path with the least turns and not
the shortest path then the turn penalty should be added to the Astar itself
or am I missing something here?
I see...Sorry for I misunderstood the term turn penalty. I think there's
something that can be done as pathfinding cost as what Unity's nav
pathfinding has done. But I have no idea how to achieve it so far. I think
I'll look into it when I'm not too busy..
—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
<https://gist.github.com/3448727#gistcomment-3722444>, or unsubscribe
<https://github.com/notifications/unsubscribe-auth/AGFUBQED3SOJVQYZO437PU3TK5VMRANCNFSM4IDVFMIQ>
.
Hello mate im kinda new to this, how would i implement this into my code so that my enemy uses this to path finding. Thanks!
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
You legend thanks for the port.