1 | #include <boost/graph/adjacency_list.hpp>
|
---|
2 | #include <boost/graph/astar_search.hpp>
|
---|
3 |
|
---|
4 | using namespace std;
|
---|
5 |
|
---|
6 |
|
---|
7 | template <typename Functor, typename Arg>
|
---|
8 | struct function_property_map {
|
---|
9 | private:
|
---|
10 | Functor f;
|
---|
11 |
|
---|
12 | public:
|
---|
13 | typedef typename boost::property_traits<
|
---|
14 | function_property_map<Functor, Arg>
|
---|
15 | >::value_type
|
---|
16 | value_type;
|
---|
17 |
|
---|
18 | explicit function_property_map(const Functor& f): f(f) {}
|
---|
19 |
|
---|
20 | friend value_type get(const function_property_map& pm, const Arg& x) {
|
---|
21 | return pm.f(x);
|
---|
22 | }
|
---|
23 | };
|
---|
24 |
|
---|
25 | namespace boost {
|
---|
26 | template <typename Functor, typename Arg>
|
---|
27 | struct property_traits<function_property_map<Functor, Arg> > {
|
---|
28 | typedef typename boost::result_of<Functor(Arg)>::type value_type;
|
---|
29 | typedef value_type reference;
|
---|
30 | typedef Arg key_type;
|
---|
31 | typedef boost::readable_property_map_tag category;
|
---|
32 | };
|
---|
33 | }
|
---|
34 |
|
---|
35 | template <typename Arg, typename Functor>
|
---|
36 | function_property_map<Functor, Arg>
|
---|
37 | make_function_property_map(const Functor& f) {
|
---|
38 | return function_property_map<Functor, Arg>(f);
|
---|
39 | }
|
---|
40 |
|
---|
41 | struct Hex
|
---|
42 | {
|
---|
43 | size_t id;
|
---|
44 | };
|
---|
45 |
|
---|
46 | struct Unit
|
---|
47 | {
|
---|
48 | Hex* hex;
|
---|
49 |
|
---|
50 | virtual int moveCost(Hex& hex)
|
---|
51 | {
|
---|
52 | return 1;
|
---|
53 | }
|
---|
54 | };
|
---|
55 |
|
---|
56 | typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Hex*> Graph;
|
---|
57 | typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
|
---|
58 | typedef boost::graph_traits<Graph>::edge_descriptor Edge;
|
---|
59 |
|
---|
60 | struct GoalDistanceHeuristic : public boost::astar_heuristic<Graph, int>
|
---|
61 | {
|
---|
62 | GoalDistanceHeuristic(Graph& g, Vertex goal) : g_(g), goal_(goal)
|
---|
63 | {
|
---|
64 |
|
---|
65 | }
|
---|
66 |
|
---|
67 | int operator() (Vertex v)
|
---|
68 | {
|
---|
69 | return 1;
|
---|
70 | }
|
---|
71 |
|
---|
72 | Graph& g_;
|
---|
73 | Vertex goal_;
|
---|
74 | };
|
---|
75 |
|
---|
76 | struct AStarVisitor : public boost::default_astar_visitor
|
---|
77 | {
|
---|
78 | AStarVisitor(Graph& graph, Vertex goal, int maxDist)
|
---|
79 | : graph_(graph), goal_(goal), maxDist_(maxDist)
|
---|
80 | {
|
---|
81 |
|
---|
82 | }
|
---|
83 |
|
---|
84 | void examine_vertex(Vertex u, const Graph& g)
|
---|
85 | {
|
---|
86 | /*
|
---|
87 | if (graph_.distances_[u] > maxDist_)
|
---|
88 | {
|
---|
89 | throw MaxDepthReached();
|
---|
90 | }
|
---|
91 |
|
---|
92 | if (u == goal_)
|
---|
93 | {
|
---|
94 | throw GoalFound();
|
---|
95 | }
|
---|
96 | */
|
---|
97 | }
|
---|
98 |
|
---|
99 | Graph& graph_;
|
---|
100 | Vertex goal_;
|
---|
101 | int maxDist_;
|
---|
102 | };
|
---|
103 |
|
---|
104 | struct EdgeWeight
|
---|
105 | {
|
---|
106 | typedef int result_type;
|
---|
107 |
|
---|
108 | EdgeWeight(Graph& g, Unit& unit) : g_(g), unit_(unit)
|
---|
109 | {
|
---|
110 |
|
---|
111 | }
|
---|
112 |
|
---|
113 | result_type operator()(Edge e) const
|
---|
114 | {
|
---|
115 | Vertex v = target(e, g_);
|
---|
116 |
|
---|
117 | return unit_.moveCost(*g_[v]);
|
---|
118 | }
|
---|
119 |
|
---|
120 | Graph& g_;
|
---|
121 | Unit& unit_;
|
---|
122 | };
|
---|
123 |
|
---|
124 | int main()
|
---|
125 | {
|
---|
126 | Graph graph;
|
---|
127 |
|
---|
128 | std::vector<Vertex> predecessors;
|
---|
129 |
|
---|
130 | std::vector<int> distances;
|
---|
131 |
|
---|
132 | Unit unit;
|
---|
133 | Hex start, goal;
|
---|
134 |
|
---|
135 | boost::astar_search(graph, start.id,
|
---|
136 | GoalDistanceHeuristic(graph, goal.id),
|
---|
137 | boost::visitor(AStarVisitor(graph, goal.id, 5))
|
---|
138 | .predecessor_map(&predecessors[0])
|
---|
139 | .distance_map(&distances[0])
|
---|
140 | .weight_map(make_function_property_map<Edge>(EdgeWeight(graph, unit))));
|
---|
141 | }
|
---|