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