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

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

 

could work?
https://gist.github.com/stylophone/3448727

 

@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

 

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!)

 

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..