|
0
|
1 /*+++++++++++++++++++++++++++++++++++++++++++
|
|
|
2 + A* algorithm +
|
|
|
3 + By Matt Peterson +
|
|
|
4 +++++++++++++++++++++++++++++++++++++++++++*/
|
|
|
5
|
|
|
6 module aid.astar;
|
|
|
7
|
|
|
8 import mintl.arrayheap;
|
|
1
|
9 import mintl.arraylist;
|
|
0
|
10
|
|
|
11 class Node(DATA) {
|
|
|
12 int xloc;
|
|
|
13 int yloc;
|
|
|
14 int fitness;
|
|
1
|
15 private int g;
|
|
|
16 private int h;
|
|
0
|
17 Node* parent = null;
|
|
|
18 DATA data;
|
|
|
19
|
|
|
20 this(DATA d, int g){
|
|
|
21 data = d;
|
|
|
22 fitness = g;
|
|
|
23 fitg = g;
|
|
|
24 }
|
|
|
25 this(DATA d, int g, Node* p){
|
|
|
26 data = d;
|
|
|
27 parent = p;
|
|
|
28 if(parent) fitness = parent.fitness + g;
|
|
|
29 fitg = g;
|
|
|
30 }
|
|
|
31 int opCmp(Node other){
|
|
|
32 return this.fitness - other.fitness;
|
|
|
33 }
|
|
|
34 }
|
|
|
35
|
|
|
36 class AStar(DATA) {
|
|
|
37 alias Node!(DATA) Node;
|
|
|
38 alias DATA[] delegate(DATA) getChildren;
|
|
|
39 ArrayHeap!(Node) openList;
|
|
1
|
40 ArrayList!(Node) closedList;
|
|
0
|
41 DATA[] run(DATA start){
|
|
|
42
|
|
|
43 }
|
|
|
44 } |
