Skip to content

Instantly share code, notes, and snippets.

@stylophone

stylophone/Astar.cs

Last active June 3, 2025 17:33
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save stylophone/3448727 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save stylophone/3448727 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. stylophone revised this gist Aug 17, 2023. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion Astar.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -143,7 +143,7 @@ private Node[] Successors(int x, int y, bool[][] grid, int rows, int cols)
    bool bE = E < cols && !grid[y][E];
    bool bW = W > -1 && !grid[y][W];

    Node[] result = new Node[4];
    Node[] result = new Node[8]; // fix bug: should be length 8
    int i = 0;

    if (bN)
  2. stylophone revised this gist Nov 7, 2020. 1 changed file with 235 additions and 235 deletions.
    470 changes: 235 additions & 235 deletions Astar.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -35,182 +35,182 @@

    public class Astar
    {
    public List<Vector2Int> Result { private set; get; }
    public List<Vector2Int> Result { private set; get; }

    private delegate Node[] Find(bool bN, bool bS, bool bE, bool bW, int N, int S, int E, int W, bool[][] grid, int rows, int cols, Node[] result, int i);
    private delegate double Distance(Node start, Node end);
    private delegate Node[] Find(bool bN, bool bS, bool bE, bool bW, int N, int S, int E, int W, bool[][] grid, int rows, int cols, Node[] result, int i);
    private delegate double Distance(Node start, Node end);

    private readonly Find m_Find;
    private readonly Find m_Find;

    public enum Type
    public enum Type
    {
    Manhattan,
    Diagonal,
    DiagonalFree,
    Euclidean,
    EuclideanFree
    }

    private class Node
    {
    public int x;
    public int y;
    public Node p;
    public double g;
    public double f;
    public int v;

    public Node(int x, int y)
    {
    this.x = x;
    this.y = y;
    }
    }

    private Node[] DiagonalSuccessors(bool bN, bool bS, bool bE, bool bW, int N, int S, int E, int W, bool[][] grid, int rows, int cols, Node[] result, int i)
    {
    if (bN)
    {
    if (bE && !grid[N][E])
    {
    result[i++] = new Node(E, N);
    }
    if (bW && !grid[N][W])
    {
    result[i++] = new Node(W, N);
    }
    }
    if (bS)
    {
    if (bE && !grid[S][E])
    {
    result[i++] = new Node(E, S);
    }
    if (bW && !grid[S][W])
    {
    result[i++] = new Node(W, S);
    }
    }
    return result;
    }

    private Node[] DiagonalSuccessorsFree(bool bN, bool bS, bool bE, bool bW, int N, int S, int E, int W, bool[][] grid, int rows, int cols, Node[] result, int i)
    {
    bN = N > -1;
    bS = S < rows;
    bE = E < cols;
    bW = W > -1;

    if (bE)
    {
    if (bN && !grid[N][E])
    {
    result[i++] = new Node(E, N);
    }
    if (bS && !grid[S][E])
    {
    result[i++] = new Node(E, S);
    }
    }
    if (bW)
    {
    if (bN && !grid[N][W])
    {
    result[i++] = new Node(W, N);
    }
    if (bS && !grid[S][W])
    {
    result[i++] = new Node(W, S);
    }
    }
    return result;
    }

    private Node[] NothingToDo(bool bN, bool bS, bool bE, bool bW, int N, int S, int E, int W, bool[][] grid, int rows, int cols, Node[] result, int i)
    {
    return result;
    }

    private Node[] Successors(int x, int y, bool[][] grid, int rows, int cols)
    {
    int N = y - 1;
    int S = y + 1;
    int E = x + 1;
    int W = x - 1;

    bool bN = N > -1 && !grid[N][x];
    bool bS = S < rows && !grid[S][x];
    bool bE = E < cols && !grid[y][E];
    bool bW = W > -1 && !grid[y][W];

    Node[] result = new Node[4];
    int i = 0;

    if (bN)
    {
    result[i++] = new Node(x, N);
    }
    if (bE)
    {
    result[i++] = new Node(E, y);
    }
    if (bS)
    {
    result[i++] = new Node(x, S);
    }
    if (bW)
    {
    result[i++] = new Node(W, y);
    }

    return m_Find(bN, bS, bE, bW, N, S, E, W, grid, rows, cols, result, i);
    }

    private double Diagonal(Node start, Node end)
    {
    return Math.Max(Math.Abs(start.x - end.x), Math.Abs(start.y - end.y));
    }

    private double Euclidean(Node start, Node end)
    {
    var x = start.x - end.x;
    var y = start.y - end.y;

    return Math.Sqrt(x * x + y * y);
    }

    private double Manhattan(Node start, Node end)
    {
    return Math.Abs(start.x - end.x) + Math.Abs(start.y - end.y);
    }

    public static bool[][] ConvertToBoolArray(int[][] grid)
    Manhattan,
    Diagonal,
    DiagonalFree,
    Euclidean,
    EuclideanFree
    }

    private class Node
    {
    public int x;
    public int y;
    public Node p;
    public double g;
    public double f;
    public int v;

    public Node(int x, int y)
    {
    this.x = x;
    this.y = y;
    }
    }

    private Node[] DiagonalSuccessors(bool bN, bool bS, bool bE, bool bW, int N, int S, int E, int W, bool[][] grid, int rows, int cols, Node[] result, int i)
    {
    if (bN)
    {
    if (bE && !grid[N][E])
    {
    result[i++] = new Node(E, N);
    }
    if (bW && !grid[N][W])
    {
    result[i++] = new Node(W, N);
    }
    }
    if (bS)
    {
    if (bE && !grid[S][E])
    {
    result[i++] = new Node(E, S);
    }
    if (bW && !grid[S][W])
    {
    result[i++] = new Node(W, S);
    }
    }
    return result;
    }

    private Node[] DiagonalSuccessorsFree(bool bN, bool bS, bool bE, bool bW, int N, int S, int E, int W, bool[][] grid, int rows, int cols, Node[] result, int i)
    {
    bN = N > -1;
    bS = S < rows;
    bE = E < cols;
    bW = W > -1;

    if (bE)
    {
    if (bN && !grid[N][E])
    {
    result[i++] = new Node(E, N);
    }
    if (bS && !grid[S][E])
    {
    result[i++] = new Node(E, S);
    }
    }
    if (bW)
    {
    if (bN && !grid[N][W])
    {
    result[i++] = new Node(W, N);
    }
    if (bS && !grid[S][W])
    {
    result[i++] = new Node(W, S);
    }
    }
    return result;
    }

    private Node[] NothingToDo(bool bN, bool bS, bool bE, bool bW, int N, int S, int E, int W, bool[][] grid, int rows, int cols, Node[] result, int i)
    {
    return result;
    }

    private Node[] Successors(int x, int y, bool[][] grid, int rows, int cols)
    {
    bool[][] arr = new bool[grid.Length][];
    int N = y - 1;
    int S = y + 1;
    int E = x + 1;
    int W = x - 1;

    for (int y = 0; y < grid.Length; y++)
    bool bN = N > -1 && !grid[N][x];
    bool bS = S < rows && !grid[S][x];
    bool bE = E < cols && !grid[y][E];
    bool bW = W > -1 && !grid[y][W];

    Node[] result = new Node[4];
    int i = 0;

    if (bN)
    {
    result[i++] = new Node(x, N);
    }
    if (bE)
    {
    result[i++] = new Node(E, y);
    }
    if (bS)
    {
    arr[y] = new bool[grid[0].Length];
    result[i++] = new Node(x, S);
    }
    if (bW)
    {
    result[i++] = new Node(W, y);
    }

    return m_Find(bN, bS, bE, bW, N, S, E, W, grid, rows, cols, result, i);
    }

    private double Diagonal(Node start, Node end)
    {
    return Math.Max(Math.Abs(start.x - end.x), Math.Abs(start.y - end.y));
    }

    private double Euclidean(Node start, Node end)
    {
    var x = start.x - end.x;
    var y = start.y - end.y;

    return Math.Sqrt(x * x + y * y);
    }

    private double Manhattan(Node start, Node end)
    {
    return Math.Abs(start.x - end.x) + Math.Abs(start.y - end.y);
    }

    for (int x = 0; x < arr[y].Length; x++)
    public static bool[][] ConvertToBoolArray(int[][] grid)
    {
    bool[][] arr = new bool[grid.Length][];

    for (int y = 0; y < grid.Length; y++)
    {
    arr[y] = new bool[grid[0].Length];

    for (int x = 0; x < arr[y].Length; x++)
    {
    arr[y][x] = grid[y][x] == 1;
    arr[y][x] = grid[y][x] == 1;
    }
    }

    return arr;
    return arr;
    }

    public Astar(bool[][] grid, Vector2Int s, Vector2Int e, Type type = Type.Manhattan)
    {
    int cols = grid[0].Length;
    int rows = grid.Length;
    int limit = cols * rows;
    public Astar(bool[][] grid, Vector2Int s, Vector2Int e, Type type = Type.Manhattan)
    {
    int cols = grid[0].Length;
    int rows = grid.Length;
    int limit = cols * rows;

    Result = new List<Vector2Int>();
    Result = new List<Vector2Int>();

    Dictionary<int, int> list = new Dictionary<int, int>();
    List<Node> open = new List<Node>(new Node[limit]);
    Dictionary<int, int> list = new Dictionary<int, int>();
    List<Node> open = new List<Node>(new Node[limit]);

    Node node = new Node(s.x, s.y)
    {
    @@ -221,106 +221,106 @@ public Astar(bool[][] grid, Vector2Int s, Vector2Int e, Type type = Type.Manhatt

    open.Insert(0, node);

    int length = 1;
    Node adj;
    int length = 1;
    Node adj;

    int i;
    int j;
    double max;
    int min;
    int i;
    int j;
    double max;
    int min;

    Node current;
    Node[] next;
    Distance distance;
    Node current;
    Node[] next;
    Distance distance;

    Node end = new Node(e.x, e.y)
    Node end = new Node(e.x, e.y)
    {
    v = e.x + e.y * cols
    };

    if (type == Type.Diagonal)
    if (type == Type.Diagonal)
    {
    m_Find = DiagonalSuccessors;
    distance = Diagonal;
    }
    else if (type == Type.DiagonalFree)
    m_Find = DiagonalSuccessors;
    distance = Diagonal;
    }
    else if (type == Type.DiagonalFree)
    {
    m_Find = DiagonalSuccessorsFree;
    distance = Diagonal;
    m_Find = DiagonalSuccessorsFree;
    distance = Diagonal;
    }
    else if (type == Type.Euclidean)
    else if (type == Type.Euclidean)
    {
    m_Find = DiagonalSuccessors;
    distance = Euclidean;
    }
    else if (type == Type.EuclideanFree)
    m_Find = DiagonalSuccessors;
    distance = Euclidean;
    }
    else if (type == Type.EuclideanFree)
    {
    m_Find = DiagonalSuccessorsFree;
    distance = Euclidean;
    }
    else
    m_Find = DiagonalSuccessorsFree;
    distance = Euclidean;
    }
    else
    {
    m_Find = NothingToDo;
    distance = Manhattan;
    m_Find = NothingToDo;
    distance = Manhattan;
    }

    do
    {
    max = limit;
    min = 0;
    do
    {
    max = limit;
    min = 0;

    for (i = 0; i < length; i++)
    {
    double f = open[i].f;
    for (i = 0; i < length; i++)
    {
    double f = open[i].f;

    if (f < max)
    {
    max = f;
    min = i;
    }
    }
    if (f < max)
    {
    max = f;
    min = i;
    }
    }

    current = open[min];
    open.RemoveRange(min, 1);
    open.RemoveRange(min, 1);

    if (current.v != end.v)
    {
    --length;
    next = Successors(current.x, current.y, grid, rows, cols);
    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)
    for (i = 0, j = next.Length; i < j; ++i)
    {
    if (next[i] == null)
    {
    continue;
    continue;
    }

    (adj = next[i]).p = current;
    adj.f = adj.g = 0;
    adj.v = adj.x + adj.y * cols;
    adj.f = adj.g = 0;
    adj.v = adj.x + adj.y * cols;

    if (!list.ContainsKey(adj.v))
    if (!list.ContainsKey(adj.v))
    {
    adj.f = (adj.g = current.g + distance(adj, current)) + distance(adj, end);
    open[length++] = adj;
    list[adj.v] = 1;
    }
    }
    }
    else
    {
    i = length = 0;

    do
    {
    Vector2Int point = new Vector2Int(current.x, current.y);
    Result.Add(point);
    }
    while ((current = current.p) != null);

    Result.Reverse();
    }
    }
    while (length != 0);
    }
    adj.f = (adj.g = current.g + distance(adj, current)) + distance(adj, end);
    open[length++] = adj;
    list[adj.v] = 1;
    }
    }
    }
    else
    {
    i = length = 0;

    do
    {
    Vector2Int point = new Vector2Int(current.x, current.y);
    Result.Add(point);
    }
    while ((current = current.p) != null);

    Result.Reverse();
    }
    }
    while (length != 0);
    }
    }
  3. stylophone revised this gist Nov 7, 2020. 1 changed file with 241 additions and 185 deletions.
    426 changes: 241 additions & 185 deletions Astar.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -2,267 +2,323 @@
    Unity C# Port of Andrea Giammarchi's JavaScript A* algorithm (http://devpro.it/javascript_id_137.html)
    Usage:
    0 = walkable;
    1 = wall;
    int[][] map = new int[][]
    int[][] map = new int[][]
    {
    new int[] {0, 0, 1, 0, 0 },
    new int[] {0, 0, 1, 0, 0 },
    new int[] {0, 0, 1, 0, 0 },
    new int[] {0, 0, 0, 0, 0 },
    };
    Vector2Int start = new Vector2Int
    {
    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}
    x = 0,
    y = 0,
    };
    int[] start = new int[2] {0, 0};
    int[] end = new int[2] {5, 5};
    Vector2Int end = new Vector2Int
    {
    x = 4,
    y = 3,
    };
    List<Vector2> path = new Astar(map, start, end, "DiagonalFree").result;
    List<Vector2Int> result = new Astar(Astar.ConvertToBoolArray(map), start, end).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) {
    public List<Vector2Int> Result { private set; get; }

    private delegate Node[] Find(bool bN, bool bS, bool bE, bool bW, int N, int S, int E, int W, bool[][] grid, int rows, int cols, Node[] result, int i);
    private delegate double Distance(Node start, Node end);

    private readonly Find m_Find;

    public enum Type
    {
    Manhattan,
    Diagonal,
    DiagonalFree,
    Euclidean,
    EuclideanFree
    }

    private class Node
    {
    public int x;
    public int y;
    public Node p;
    public double g;
    public double f;
    public int v;

    public Node(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);

    private Node[] DiagonalSuccessors(bool bN, bool bS, bool bE, bool bW, int N, int S, int E, int W, bool[][] grid, int rows, int cols, Node[] result, int i)
    {
    if (bN)
    {
    if (bE && !grid[N][E])
    {
    result[i++] = new Node(E, N);
    }
    if (xW && grid[N][W] == 0) {
    result[i++] = new _Object(W, N);
    if (bW && !grid[N][W])
    {
    result[i++] = new Node(W, N);
    }
    }
    if (xS) {
    if (xE && grid[S][E] == 0) {
    result[i++] = new _Object(E, S);
    if (bS)
    {
    if (bE && !grid[S][E])
    {
    result[i++] = new Node(E, S);
    }
    if (xW && grid[S][W] == 0) {
    result[i++] = new _Object(W, S);
    if (bW && !grid[S][W])
    {
    result[i++] = new Node(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);

    private Node[] DiagonalSuccessorsFree(bool bN, bool bS, bool bE, bool bW, int N, int S, int E, int W, bool[][] grid, int rows, int cols, Node[] result, int i)
    {
    bN = N > -1;
    bS = S < rows;
    bE = E < cols;
    bW = W > -1;

    if (bE)
    {
    if (bN && !grid[N][E])
    {
    result[i++] = new Node(E, N);
    }
    if (xS && grid[S][E] == 0) {
    result[i++] = new _Object(E, S);
    if (bS && !grid[S][E])
    {
    result[i++] = new Node(E, S);
    }
    }
    if (xW) {
    if (xN && grid[N][W] == 0) {
    result[i++] = new _Object(W, N);
    if (bW)
    {
    if (bN && !grid[N][W])
    {
    result[i++] = new Node(W, N);
    }
    if (xS && grid[S][W] == 0) {
    result[i++] = new _Object(W, S);
    if (bS && !grid[S][W])
    {
    result[i++] = new Node(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) {

    private Node[] NothingToDo(bool bN, bool bS, bool bE, bool bW, int N, int S, int E, int W, bool[][] grid, int rows, int cols, Node[] result, int i)
    {
    return result;
    }

    private _Object[] successors (int x, int y, int[][] grid, int rows, int cols) {
    int N = y - 1;

    private Node[] Successors(int x, int y, bool[][] 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;


    bool bN = N > -1 && !grid[N][x];
    bool bS = S < rows && !grid[S][x];
    bool bE = E < cols && !grid[y][E];
    bool bW = W > -1 && !grid[y][W];

    Node[] result = new Node[4];
    int i = 0;

    _Object[] result = new _Object[8];

    if (xN) {
    result[i++] = new _Object(x, N);

    if (bN)
    {
    result[i++] = new Node(x, N);
    }
    if (xE) {
    result[i++] = new _Object(E, y);
    if (bE)
    {
    result[i++] = new Node(E, y);
    }
    if (xS) {
    result[i++] = new _Object(x, S);
    if (bS)
    {
    result[i++] = new Node(x, S);
    }
    if (xW) {
    result[i++] = new _Object(W, y);
    if (bW)
    {
    result[i++] = new Node(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;

    return m_Find(bN, bS, bE, bW, N, S, E, W, grid, rows, cols, result, i);
    }

    private double diagonal (_Object start, _Object end) {

    private double Diagonal(Node start, Node end)
    {
    return Math.Max(Math.Abs(start.x - end.x), Math.Abs(start.y - end.y));
    }

    private double euclidean(_Object start, _Object end) {

    private double Euclidean(Node start, Node 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) {
    private double Manhattan(Node start, Node end)
    {
    return Math.Abs(start.x - end.x) + Math.Abs(start.y - end.y);
    }

    public Astar (int[][] grid, int[] s, int[] e, string f)

    public static bool[][] ConvertToBoolArray(int[][] grid)
    {
    bool[][] arr = new bool[grid.Length][];

    for (int y = 0; y < grid.Length; y++)
    {
    arr[y] = new bool[grid[0].Length];

    for (int x = 0; x < arr[y].Length; x++)
    {
    arr[y][x] = grid[y][x] == 1;
    }
    }

    return arr;
    }

    public Astar(bool[][] grid, Vector2Int s, Vector2Int e, Type type = Type.Manhattan)
    {
    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>();
    int cols = grid[0].Length;
    int rows = grid.Length;
    int limit = cols * rows;

    Result = new List<Vector2Int>();

    Dictionary<int, int> list = new Dictionary<int, int>();
    List<Node> open = new List<Node>(new Node[limit]);

    Node node = new Node(s.x, s.y)
    {
    f = 0,
    g = 0,
    v = s.x + s.y * cols
    };

    open.Insert(0, node);

    int length = 1;
    Node adj;

    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 {

    Node current;
    Node[] next;
    Distance distance;

    Node end = new Node(e.x, e.y)
    {
    v = e.x + e.y * cols
    };

    if (type == Type.Diagonal)
    {
    m_Find = DiagonalSuccessors;
    distance = Diagonal;
    }
    else if (type == Type.DiagonalFree)
    {
    m_Find = DiagonalSuccessorsFree;
    distance = Diagonal;
    }
    else if (type == Type.Euclidean)
    {
    m_Find = DiagonalSuccessors;
    distance = Euclidean;
    }
    else if (type == Type.EuclideanFree)
    {
    m_Find = DiagonalSuccessorsFree;
    distance = Euclidean;
    }
    else
    {
    m_Find = NothingToDo;
    distance = Manhattan;
    }

    do
    {
    max = limit;
    min = 0;

    for (i = 0; i < length; i++) {
    if (open[i].f < max) {
    max = open[i].f;

    for (i = 0; i < length; i++)
    {
    double f = open[i].f;

    if (f < max)
    {
    max = f;
    min = i;
    }
    }

    current = open[min];
    open.RemoveAt(min);

    if (current.v != end.v) {

    current = open[min];
    open.RemoveRange(min, 1);

    if (current.v != end.v)
    {
    --length;
    next = successors(current.x, current.y, grid, rows, cols);
    next = Successors(current.x, current.y, grid, rows, cols);

    for (i = 0, j = next.Length; i < j; ++i)
    {
    if (next[i] == null) {
    if (next[i] == null)
    {
    continue;
    }
    (adj = next[i]).p = current;
    }

    (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++;

    if (!list.ContainsKey(adj.v))
    {
    adj.f = (adj.g = current.g + distance(adj, current)) + distance(adj, end);
    open[length++] = adj;
    list[adj.v] = 1;
    }
    }
    }
    else {
    else
    {
    i = length = 0;
    do {
    this.result.Add(new Vector2(current.x, current.y));

    do
    {
    Vector2Int point = new Vector2Int(current.x, current.y);
    Result.Add(point);
    }
    while ((current = current.p) != null);
    result.Reverse();

    Result.Reverse();
    }
    }
    while (length != 0);
  4. stylophone revised this gist Aug 24, 2012. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions Astar.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -17,8 +17,8 @@
    new int[] {1, 0, 1, 2, 0, 0, 0, 0}
    };
    int[] start = new int[2] {0, 0};
    int[] end = new int[2] {5, 5};
    int[] start = new int[2] {0, 0};
    int[] end = new int[2] {5, 5};
    List<Vector2> path = new Astar(map, start, end, "DiagonalFree").result;
    */
  5. stylophone revised this gist Aug 24, 2012. 1 changed file with 9 additions and 11 deletions.
    20 changes: 9 additions & 11 deletions Astar.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -1,14 +1,13 @@
    /**
    * Unity C# Port of Andrea Giammarchi's JavaScript A* algorithm (http://devpro.it/javascript_id_137.html)
    *
    * Usage:
    *
    /*
    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, 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},
    @@ -22,8 +21,7 @@
    int[] end = new int[2] {5, 5};
    List<Vector2> path = new Astar(map, start, end, "DiagonalFree").result;
    */
    */

    using System;
    using System.Collections.Generic;
  6. stylophone revised this gist Aug 24, 2012. 1 changed file with 27 additions and 0 deletions.
    27 changes: 27 additions & 0 deletions Astar.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,30 @@
    /**
    * 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;
  7. stylophone revised this gist Aug 24, 2012. 1 changed file with 4 additions and 4 deletions.
    8 changes: 4 additions & 4 deletions Astar.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -60,10 +60,10 @@ private _Object[] diagonalSuccessors (bool xN, bool xS, bool xE, bool xW, int N,
    }

    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;
    xN = N > -1;
    xS = S < rows;
    xE = E < cols;
    xW = W > -1;

    if (xE) {
    if (xN && grid[N][E] == 0) {
  8. stylophone revised this gist Aug 24, 2012. 1 changed file with 20 additions and 20 deletions.
    40 changes: 20 additions & 20 deletions Astar.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -9,26 +9,26 @@ public class Astar
    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 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;
  9. stylophone revised this gist Aug 24, 2012. 1 changed file with 7 additions and 7 deletions.
    14 changes: 7 additions & 7 deletions Astar.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -128,16 +128,16 @@ 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;
    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);
    }
    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);
    }
    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)
    {
  10. stylophone revised this gist Aug 24, 2012. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions Astar.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -233,9 +233,9 @@ public Astar (int[][] grid, int[] s, int[] e, string f)
    }
    else {
    i = length = 0;
    do {
    do {
    this.result.Add(new Vector2(current.x, current.y));
    }
    }
    while ((current = current.p) != null);
    result.Reverse();
    }
  11. stylophone revised this gist Aug 24, 2012. 1 changed file with 7 additions and 7 deletions.
    14 changes: 7 additions & 7 deletions Astar.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -117,9 +117,9 @@ private _Object[] successors (int x, int y, int[][] grid, int rows, int cols) {
    }

    _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);
    (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;
    }
    @@ -180,10 +180,10 @@ public Astar (int[][] grid, int[] s, int[] e, string f)
    min = 0;

    for (i = 0; i < length; i++) {
    if (open[i].f < max) {
    max = open[i].f;
    min = i;
    }
    if (open[i].f < max) {
    max = open[i].f;
    min = i;
    }
    }

    current = open[min];
  12. stylophone created this gist Aug 24, 2012.
    245 changes: 245 additions & 0 deletions Astar.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,245 @@
    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);
    }
    }