1 package cz.cuni.amis.pathfinding.map;
2
3 import java.util.Collection;
4 import java.util.HashMap;
5
6 /**
7 * This class represents the discrete search space for path-finding algorithms for games. It conceptualize the map/location/environment of the game for
8 * the purpose of planners as finite graph whose nodes are easily distinguishable from each others (it is suitable for NavigationGraphs using discrete navigation
9 * points, but it is not suitable for GOAP planners for strategic games such as Defcon).
10 * <p><p>
11 * The map is perceived as oriented graph that does not have "multi-edges" (it is not a multigraph).
12 * <p><p>
13 * Every environment must at least provide:
14 * <ol>
15 * <li>function that can compute neighbors of every node ({@link IPFMap#getNeighbors(Object)})</li>
16 * <li>function that provides "cost" of the node (i.e., what is the cost of having the node in the path) ({@link IPFMap#getNodeCost(Object)})</li>
17 * <li>function that provides "cost" of the arc (arc == directed edge, i.e., what is the cost of traveling through edge between two nodes in the graph) ({@link IPFMap#getArcCost(Object)})</li>
18 * </ol>
19 * <p><p>
20 * Note that the interface is parameterized by "NODE" which might be arbitrary object, that is you may use POJOs here. But be careful
21 * as algorithms using the map usually assumes that {@link Object#hashCode()} and {@link Object#equals(Object)} are correctly implemented
22 * for them (i.e., they may use the nodes as keys inside {@link HashMap}s).
23 * <p><p>
24 * Note that the implementation of such interface should not provide any "view hacks", i.e., means for suppressing the presence of some nodes/arc of the graph.
25 * Such tweaks should be implemented using {@link IPFMapView}.
26 * <p><p>
27 * Note that this interface is suitable for "exploratory" algorithms such as A-Star, that is, algorithms which gradually search the space given some "seed" (starting point).
28 * If you wish to use "grand-scale" algorithms such as Floyd-Warshall (where you have to know number of all nodes in advance), use {@link IPFKnownMap}.
29 *
30 * @param NODE
31 */
32 public interface IPFMap<NODE> {
33
34 /**
35 * This should return a collection of nodes which are connected to this one by some arc (== oriented edge).
36 * I.e., return collection of nodes that are directly accessible from "node".
37 * <p><p>
38 * "node" MUST NOT BE PART OF THE COLLECTION!
39 * <p><p>
40 * Returned collection must not contain multiple references to a single neighbor (multi-graph is forbidden).
41 *
42 * @param node
43 * @return all neighbors of the node (arc exists between 'node' and every node inside returned collection)
44 */
45 public Collection<NODE> getNeighbors(NODE node);
46
47 /**
48 * General cost of having this node at your path. This allows you to say how much each node appeals to the agent,
49 * it may specify "this is a cool node, try to get it on your path" (negative cost) or "this is neutral node"
50 * (zero cost) or "this is a bad node to have on your path" (positive cost).
51 * <p><p>
52 * This might be highly dependent on the agent so the default implementation will probably just return "0".
53 *
54 * @param node
55 * @return cost of the node
56 */
57 public int getNodeCost(NODE node);
58
59 /**
60 * Should return the cost of traveling from "nodeFrom" to "nodeTo".
61 * You can be sure that "nodeTo" is among the neighbors of "nodeFrom" as they were returned by
62 * {@link IPFMap#getNeighbors(Object)} or from {@link IPFMapView#getExtraNeighbors(Object)}.
63 * <p><p>
64 * Note that notion of "cost" might be highly dependent on the agent, thus it may have the sense to provide it
65 * only a general distance between "nodeFrom" and "nodeTo".
66 * <p><p>
67 * The method can be also perceived as having name "getDistance".
68 *
69 * @param nodeFrom
70 * @param nodeTo
71 * @return cost of an arc
72 */
73 public int getArcCost(NODE nodeFrom, NODE nodeTo);
74
75 }