Search Unity

[SOLVED]Looking for a simplistic, fast and light-weight A-Star( A* ) library ( C# )

Discussion in 'Navigation' started by rob_vld, May 5, 2015.

  1. rob_vld

    rob_vld

    Joined:
    Jul 9, 2013
    Posts:
    158
    I've been spending a lot of time searching/testing working C# A* solutions... so far i have only encountered 1 good one as being simplistic... unfortunately it is quite slow... https://github.com/juhgiyo/EpPathFinding.cs

    Years ago when i was still playing with HTML/Javascript i found/used a A* solution that worked really well for me... but unfortunately this does not work with unity3D and since i am not skillfull enough to make any kind of adjustments or/and convert it to C#, ... i am hoping someone is able and willing to pick this up?

    Code (JavaScript):
    1. var AStar = (function () {
    2.  
    3.     /**
    4.      * A* (A-Star) algorithm for a path finder
    5.      * @author  Andrea Giammarchi
    6.      * @license Mit Style License
    7.      code:http://devpro.it/code/137.html
    8.      example:http://devpro.it/examples/astar/index2.html
    9.      */
    10.  
    11.     function diagonalSuccessors($N, $S, $E, $W, N, S, E, W, grid, rows, cols, result, i) {
    12.         if($N) {
    13.             $E && !grid[N][E] && (result[i++] = {x:E, y:N});
    14.             $W && !grid[N][W] && (result[i++] = {x:W, y:N});
    15.         }
    16.         if($S){
    17.             $E && !grid[S][E] && (result[i++] = {x:E, y:S});
    18.             $W && !grid[S][W] && (result[i++] = {x:W, y:S});
    19.         }
    20.         return result;
    21.     }
    22.  
    23.     function diagonalSuccessorsFree($N, $S, $E, $W, N, S, E, W, grid, rows, cols, result, i) {
    24.         $N = N > -1;
    25.         $S = S < rows;
    26.         $E = E < cols;
    27.         $W = W > -1;
    28.         if($E) {
    29.             $N && !grid[N][E] && (result[i++] = {x:E, y:N});
    30.             $S && !grid[S][E] && (result[i++] = {x:E, y:S});
    31.         }
    32.         if($W) {
    33.             $N && !grid[N][W] && (result[i++] = {x:W, y:N});
    34.             $S && !grid[S][W] && (result[i++] = {x:W, y:S});
    35.         }
    36.         return result;
    37.     }
    38.  
    39.     function nothingToDo($N, $S, $E, $W, N, S, E, W, grid, rows, cols, result, i) {
    40.         return result;
    41.     }
    42.  
    43.     function successors(find, x, y, grid, rows, cols){
    44.         var
    45.             N = y - 1,
    46.             S = y + 1,
    47.             E = x + 1,
    48.             W = x - 1,
    49.             $N = N > -1 && !grid[N][x],
    50.             $S = S < rows && !grid[S][x],
    51.             $E = E < cols && !grid[y][E],
    52.             $W = W > -1 && !grid[y][W],
    53.             result = [],
    54.             i = 0
    55.         ;
    56.         $N && (result[i++] = {x:x, y:N});
    57.         $E && (result[i++] = {x:E, y:y});
    58.         $S && (result[i++] = {x:x, y:S});
    59.         $W && (result[i++] = {x:W, y:y});
    60.         return find($N, $S, $E, $W, N, S, E, W, grid, rows, cols, result, i);
    61.     }
    62.  
    63.     function diagonal(start, end, f1, f2) {
    64.         return f2(f1(start.x - end.x), f1(start.y - end.y));
    65.     }
    66.  
    67.     function euclidean(start, end, f1, f2) {
    68.         var
    69.             x = start.x - end.x,
    70.             y = start.y - end.y
    71.         ;
    72.         return f2(x * x + y * y);
    73.     }
    74.  
    75.     function manhattan(start, end, f1, f2) {
    76.         return f1(start.x - end.x) + f1(start.y - end.y);
    77.     }
    78.  
    79.     function AStar(grid, start, end, f) {
    80.         var
    81.             cols = grid[0].length,
    82.             rows = grid.length,
    83.             limit = cols * rows,
    84.             f1 = Math.abs,
    85.             f2 = Math.max,
    86.             list = {},
    87.             result = [],
    88.             open = [{x:start[0], y:start[1], f:0, g:0, v:start[0]+start[1]*cols}],
    89.             length = 1,
    90.             adj, distance, find, i, j, max, min, current, next
    91.         ;
    92.         end = {x:end[0], y:end[1], v:end[0]+end[1]*cols};
    93.         switch (f) {
    94.             case "Diagonal":
    95.                 find = diagonalSuccessors;
    96.             case "DiagonalFree":
    97.                 distance = diagonal;
    98.                 break;
    99.             case "Euclidean":
    100.                 find = diagonalSuccessors;
    101.             case "EuclideanFree":
    102.                 f2 = Math.sqrt;
    103.                 distance = euclidean;
    104.                 break;
    105.             default:
    106.                 distance = manhattan;
    107.                 find = nothingToDo;
    108.                 break;
    109.         }
    110.         find || (find = diagonalSuccessorsFree);
    111.         do {
    112.             max = limit;
    113.             min = 0;
    114.             for(i = 0; i < length; ++i) {
    115.                 if((f = open[i].f) < max) {
    116.                     max = f;
    117.                     min = i;
    118.                 }
    119.             };
    120.             current = open.splice(min, 1)[0];
    121.             if (current.v != end.v) {
    122.                 --length;
    123.                 next = successors(find, current.x, current.y, grid, rows, cols);
    124.                 for(i = 0, j = next.length; i < j; ++i){
    125.                     (adj = next[i]).p = current;
    126.                     adj.f = adj.g = 0;
    127.                     adj.v = adj.x + adj.y * cols;
    128.                     if(!(adj.v in list)){
    129.                         adj.f = (adj.g = current.g + distance(adj, current, f1, f2)) + distance(adj, end, f1, f2);
    130.                         open[length++] = adj;
    131.                         list[adj.v] = 1;
    132.                     }
    133.                 }
    134.             } else {
    135.                 i = length = 0;
    136.                 do {
    137.                     result[i++] = [current.x, current.y];
    138.                 } while (current = current.p);
    139.                 result.reverse();
    140.             }
    141.         } while (length);
    142.         return result;
    143.     }
    144.  
    145.     return AStar;
    146.  
    147. }());
    Or any suggestions to other simplistic, fast and light-weight A-Star( A* ) library ( C# ) are appreciated!

    Thank you for your time :)
     
  2. mgear

    mgear

    Joined:
    Aug 3, 2010
    Posts:
    5,627
  3. rob_vld

    rob_vld

    Joined:
    Jul 9, 2013
    Posts:
    158
    @mgear: a 4 minute reply... sigh...
    nice find, thank you a lot! ; testing!


    edit: I have tested it, and it is 50% faster then what i was using!!
    you made my day :D
     
    Last edited: May 5, 2015
  4. juhgiyo

    juhgiyo

    Joined:
    Aug 30, 2013
    Posts:
    1
    Hi, I am the author of https://github.com/juhgiyo/EpPathFinding.cs.
    Sorry to hear that you are not satisfied with performance of EpPathFinding.cs.
    You said that it is slow, but I was wondering if you have tried it with "StaticGrid" type.
    Other grid types (DynamicGrid or DynamicGridWPool) degrade performance to improve memory usage.
    If you haven't tried with StaticGrid, I recommend trying it! (It will be a lot faster compare to other grid type!)
     
  5. Immanuel-Scholz

    Immanuel-Scholz

    Joined:
    Jun 8, 2013
    Posts:
    217
    Also remember, that the A* algorithm itself is definetely NOT the best choice for every problem. E.g. searching through a regular grid (the worst-case scenario for A*), its rather expensive compared to many other algorithms or A* modifcations.

    A* is one of these swizz knifes you can throw at most search problems and get some reasonable result. But depending on your exact data, modifcations like the Jump Search (google "astar jump point search") are up to 20 times faster.

    Oh, and if path searching is one of your bottlenecks, considering other levels of optimization. For example, doing multiple searches in one go. Like if you use good'ol'Dijkstra to flood the whole search grid, you can simultanously calculate paths for ALL agents that share a common goal..