1 package cz.cuni.amis.pathfinding.map;
2
3 import java.util.Set;
4
5 import cz.cuni.amis.utils.heap.IHeap;
6
7 /**
8 * General interface that is describing the goal for the exploratory path-finder
9 * such as A-Star algorithm.
10 *
11 * @author Jimmy
12 */
13 public interface IPFGoal<NODE> {
14
15 /**
16 * Returns start node that the algorithm will begin with.
17 * @return
18 */
19 public NODE getStart();
20
21 /**
22 * Goal-recognition function, i.e., it recognizes which node is actually the goal.
23 * <p><p>
24 * Returns true, if we've reached the goal ... actualNode is node we
25 * were trying to get to in the algorithm (e.g. A-Star) if this function never returns true,
26 * path-finding algorithm will run until all nodes are evaluated.
27 *
28 * @param actualNode
29 */
30 public boolean isGoalReached(NODE actualNode);
31
32 /**
33 * This is heuristic function that returns how far is "node" from your
34 * goal, i.e., estimated "cost" it will take the agent to get from
35 * "node" to the goal.
36 * <p><p>
37 * <b>WARNING:</b>
38 * <p><p>
39 * This heuristic must be correct for A* to work correctly, that means the
40 * returned distance must be smaller or equal to the real distance and.
41 * <p><p>
42 * Moreover as you will likely search "graphs" and not "trees" you will also
43 * need the heuristic to be monotonic.
44 * <p><p>
45 * In 2D, 3D an Euclidean metric will do the job.
46 *
47 * @return how far is to the goal from the node
48 */
49 public int getEstimatedCostToGoal(NODE node);
50
51 /**
52 * This is called at the beginning of the A* algorithm to bind the open list
53 * to the goal (you may use it check which nodes we've visited, etc... for
54 * extra cost for instance).
55 * <p><p>
56 * IMMUTABLE! DON'T CHANGE IT!
57 *
58 * @param openList
59 */
60 public void setOpenList(IHeap<NODE> openList);
61
62 /**
63 * This is called at the beginning of the A* algorithm to bind the close
64 * list to the goal (you may use it check which nodes we've visited, etc...
65 * for extra cost for instance).
66 * <p><p>
67 * IMMUTABLE! DON'T CHANGE IT!
68 *
69 * @param closedList
70 */
71 public void setCloseList(Set<NODE> closedList);
72
73 }