<div>Having finally gotten this working, I wanted to share it. �As the topic states, this is an implementation of an infinite, implicit graph, and an example that searches the graph with <font face="&#39;courier new&#39;, monospace">astar_search_no_init</font>. �I didn&#39;t find any examples out there of anyone doing this particular thing, so I hope it may be helpful to my fellow travelers.</div>

<div><br></div><div>This code is a bastardization of some stuff from a game I&#39;m working on (blatant plug: <a href="http://snarglequest.blogspot.com/">http://snarglequest.blogspot.com/</a>) and the &quot;city search&quot; example code from the BGL docs. �I&#39;m sure it could be more concise, but I hope you&#39;ll find it accessible.</div>

<div><br></div><div>Oh, and critiques would of course be welcome. �I said it&#39;s working, not perfect; I&#39;m sure there are many things I could be doing in better ways, and I&#39;d love to know about them.</div><div>
<br>
</div><div>Luke</div><div><br></div><div><font face="&#39;courier new&#39;, monospace">/**</font></div><div><font face="&#39;courier new&#39;, monospace">�* Example use of boost::astar_search_no_init on an infinite, implicitly-defined graph.</font></div>

<div><font face="&#39;courier new&#39;, monospace">�*</font></div><div><font face="&#39;courier new&#39;, monospace">�* The graph type used here is XYGraph, representing an infinite grid of squares. �Each</font></div><div>

<font face="&#39;courier new&#39;, monospace">�* square is connected to its eight neighbors; however, the example shows how to use</font></div><div><font face="&#39;courier new&#39;, monospace">�* boost::filtered_graph to make the search take place only along orthogonal edges.</font></div>

<div><font face="&#39;courier new&#39;, monospace">�*/</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">#include &lt;iostream&gt;</font></div>

<div><font face="&#39;courier new&#39;, monospace">#include &lt;list&gt;</font></div><div><font face="&#39;courier new&#39;, monospace">#include &lt;map&gt;</font></div><div><font face="&#39;courier new&#39;, monospace">#include &lt;set&gt;</font></div>

<div><font face="&#39;courier new&#39;, monospace">#include &lt;utility&gt;</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">#include &lt;boost/graph/graph_traits.hpp&gt;</font></div>

<div><font face="&#39;courier new&#39;, monospace">#include &lt;boost/graph/astar_search.hpp&gt;</font></div><div><font face="&#39;courier new&#39;, monospace">#include &lt;boost/graph/filtered_graph.hpp&gt;</font></div>
<div>
<font face="&#39;courier new&#39;, monospace">#include &lt;boost/operators.hpp&gt;</font></div><div><font face="&#39;courier new&#39;, monospace">#include &lt;boost/ref.hpp&gt;</font></div><div><font face="&#39;courier new&#39;, monospace"><br>

</font></div><div><font face="&#39;courier new&#39;, monospace">namespace Direction</font></div><div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">enum id</font></div>

<div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">� � MIN = 0,</font></div><div><font face="&#39;courier new&#39;, monospace">� � N = MIN, S, E, W, NW, NE, SE, SW, NONE</font></div>

<div><font face="&#39;courier new&#39;, monospace">};</font></div><div><font face="&#39;courier new&#39;, monospace">}</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">struct XY : public boost::additive&lt;XY,</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � boost::totally_ordered&lt;XY,</font></div><div><font face="&#39;courier new&#39;, monospace">� � boost::equivalent&lt;XY&gt;</font></div><div><font face="&#39;courier new&#39;, monospace">� � &gt; &gt;</font></div>

<div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">� � typedef int X;</font></div><div><font face="&#39;courier new&#39;, monospace">� � typedef int Y;</font></div>

<div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">� � XY(X x = 0, Y y = 0);</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div>

<div><font face="&#39;courier new&#39;, monospace">� � // Same square counts.</font></div><div><font face="&#39;courier new&#39;, monospace">� � bool adjacentTo(XY const&amp; that) const;</font></div><div><font face="&#39;courier new&#39;, monospace"><br>

</font></div><div><font face="&#39;courier new&#39;, monospace">� � XY &amp; operator=(XY const&amp; that);</font></div><div><font face="&#39;courier new&#39;, monospace">� � XY &amp; operator+=(XY const&amp; that);</font></div>

<div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">� � bool operator&lt;(XY const&amp; that) const;</font></div><div><font face="&#39;courier new&#39;, monospace"><br>

</font></div><div><font face="&#39;courier new&#39;, monospace">� � X x;</font></div><div><font face="&#39;courier new&#39;, monospace">� � Y y;</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div>

<div><font face="&#39;courier new&#39;, monospace">� � XY neighbor(Direction::id direction) const;</font></div><div><font face="&#39;courier new&#39;, monospace">� � std::set&lt;XY&gt; allNeighbors() const;</font></div><div>

<font face="&#39;courier new&#39;, monospace">};</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">std::ostream &amp; operator&lt;&lt;(std::ostream &amp; os, XY const&amp; xy);</font></div>

<div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">struct neighbor_iterator;</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div>

<div><font face="&#39;courier new&#39;, monospace">/*</font></div><div><font face="&#39;courier new&#39;, monospace">�* Model of:</font></div><div><font face="&#39;courier new&#39;, monospace">�* �* Graph</font></div><div>

<font face="&#39;courier new&#39;, monospace">�* �* IncidenceGraph</font></div><div><font face="&#39;courier new&#39;, monospace">�*/</font></div><div><font face="&#39;courier new&#39;, monospace">struct XYGraph</font></div>

<div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">� � XYGraph();</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">� � // Graph concept requirements</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � typedef XY � � � � � � � � � � � � � � � �vertex_descriptor;</font></div><div><font face="&#39;courier new&#39;, monospace">� � typedef std::pair&lt;XY, XY&gt; � � � � � � � � edge_descriptor;</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � typedef boost::undirected_tag � � � � � � directed_category;</font></div><div><font face="&#39;courier new&#39;, monospace">� � typedef boost::disallow_parallel_edge_tag edge_parallel_category;</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � typedef boost::incidence_graph_tag � � � �traversal_category;</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">� � // IncidenceGraph concept requirements</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � typedef neighbor_iterator � � � � �out_edge_iterator;</font></div><div><font face="&#39;courier new&#39;, monospace">� � typedef int � � � � � � � � � � � �degree_size_type;</font></div>

<div><font face="&#39;courier new&#39;, monospace">};</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">namespace boost</font></div><div><font face="&#39;courier new&#39;, monospace">{</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � template &lt;&gt; struct graph_traits&lt;XYGraph&gt;</font></div><div><font face="&#39;courier new&#39;, monospace">� � {</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � typedef XYGraph G;</font></div>

<div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">� � � � typedef G::vertex_descriptor � � �vertex_descriptor;</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � typedef G::edge_descriptor � � � �edge_descriptor;</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � typedef G::out_edge_iterator � � �out_edge_iterator;</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">� � � � typedef G::directed_category � � �directed_category;</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � typedef G::edge_parallel_category edge_parallel_category;</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � typedef G::traversal_category � � traversal_category;</font></div>

<div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">� � � � typedef G::degree_size_type � � � degree_size_type;</font></div><div><font face="&#39;courier new&#39;, monospace"><br>

</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � typedef void in_edge_iterator;</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � typedef void vertex_iterator;</font></div><div>

<font face="&#39;courier new&#39;, monospace">� � � � typedef void vertices_size_type;</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � typedef void edge_iterator;</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � typedef void edges_size_type;</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � };</font></div><div><font face="&#39;courier new&#39;, monospace">}</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">// IncidenceGraph concept requirements</font></div>

<div><font face="&#39;courier new&#39;, monospace">std::pair&lt;XYGraph::out_edge_iterator,�</font></div><div><font face="&#39;courier new&#39;, monospace">XYGraph::out_edge_iterator&gt; out_edges(XYGraph::vertex_descriptor v, XYGraph const&amp; g);</font></div>

<div><font face="&#39;courier new&#39;, monospace">XYGraph::degree_size_type out_degree(XYGraph::vertex_descriptor v, XYGraph const&amp; g);</font></div><div><font face="&#39;courier new&#39;, monospace">XYGraph::vertex_descriptor source(XYGraph::edge_descriptor e, XYGraph const&amp; g);</font></div>

<div><font face="&#39;courier new&#39;, monospace">XYGraph::vertex_descriptor target(XYGraph::edge_descriptor e, XYGraph const&amp; g);</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div>

<font face="&#39;courier new&#39;, monospace">// Iterator</font></div><div><font face="&#39;courier new&#39;, monospace">struct neighbor_iterator :�</font></div><div><font face="&#39;courier new&#39;, monospace">� � public boost::iterator_facade&lt;neighbor_iterator,</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � � � � � � � � � � � � � � std::pair&lt;XY,XY&gt;,</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � � � � � � � � � � � � � � boost::forward_traversal_tag,</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � � � � � � � � � � � � � � std::pair&lt;XY,XY&gt; &gt;</font></div><div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">public:</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � neighbor_iterator();</font></div><div><font face="&#39;courier new&#39;, monospace">� � neighbor_iterator(XY xy, Direction::id direction);</font></div><div><font face="&#39;courier new&#39;, monospace"><br>

</font></div><div><font face="&#39;courier new&#39;, monospace">� � neighbor_iterator &amp; operator=(neighbor_iterator const&amp; that);</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div>

<font face="&#39;courier new&#39;, monospace">� � std::pair&lt;XY,XY&gt; operator*() const;</font></div><div><font face="&#39;courier new&#39;, monospace">� � void operator++();</font></div><div><font face="&#39;courier new&#39;, monospace">� � bool operator==(neighbor_iterator const&amp; that) const;</font></div>

<div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">� � bool equal(neighbor_iterator const&amp; that) const { return operator==(that); }</font></div><div>

<font face="&#39;courier new&#39;, monospace">� � void increment() { operator++(); }</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">private:</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � XY xy;</font></div><div><font face="&#39;courier new&#39;, monospace">� � Direction::id direction;</font></div><div><font face="&#39;courier new&#39;, monospace">};</font></div>

<div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">struct orthogonal_only;</font></div>

<div><font face="&#39;courier new&#39;, monospace">template &lt;typename Graph&gt; class distance_heuristic;</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">struct found_goal {}; // exception for termination</font></div>

<div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">// visitor that terminates when we find the goal</font></div><div><font face="&#39;courier new&#39;, monospace">class astar_goal_visitor : public boost::default_astar_visitor</font></div>

<div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">public:</font></div><div><font face="&#39;courier new&#39;, monospace">� � astar_goal_visitor(XY goal) : m_goal(goal) {}</font></div>

<div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">� � virtual void examine_vertex(XY xy, XYGraph const&amp; g) {</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � std::cout &lt;&lt; &quot;Exploring &quot; &lt;&lt; xy &lt;&lt; &quot;...&quot; &lt;&lt; std::endl;</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � if(xy == m_goal)</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � � � throw found_goal();</font></div><div><font face="&#39;courier new&#39;, monospace">� � }</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � virtual void examine_vertex(XY xy, boost::filtered_graph&lt;XYGraph, orthogonal_only&gt; const&amp; g) {</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � std::cout &lt;&lt; &quot;Exploring &quot; &lt;&lt; xy &lt;&lt; &quot;...&quot; &lt;&lt; std::endl;</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � if(xy == m_goal)</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � � � throw found_goal();</font></div><div><font face="&#39;courier new&#39;, monospace">� � }</font></div>

<div><font face="&#39;courier new&#39;, monospace">private:</font></div><div><font face="&#39;courier new&#39;, monospace">� � XY m_goal;</font></div><div><font face="&#39;courier new&#39;, monospace">};</font></div><div>

<font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">template &lt;typename K, typename V&gt;</font></div><div><font face="&#39;courier new&#39;, monospace">class default_map</font></div>

<div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">public:</font></div><div><font face="&#39;courier new&#39;, monospace">� � typedef K key_type;</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � typedef V data_type;</font></div><div><font face="&#39;courier new&#39;, monospace">� � typedef std::pair&lt;K,V&gt; value_type;</font></div><div><font face="&#39;courier new&#39;, monospace"><br>

</font></div><div><font face="&#39;courier new&#39;, monospace">� � default_map(V const&amp; defaultValue)</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � : defaultValue(defaultValue)</font></div><div>

<font face="&#39;courier new&#39;, monospace">� � {}</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">� � V &amp; operator[](K const&amp; k)</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � {</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � if (m.find(k) == m.end())</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � {</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � � � m[k] = defaultValue;</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � }</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � return m[k];</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � }</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">private:</font></div><div><font face="&#39;courier new&#39;, monospace">� � std::map&lt;K,V&gt; m;</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � V const defaultValue;</font></div><div><font face="&#39;courier new&#39;, monospace">};</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div>

<div><font face="&#39;courier new&#39;, monospace">struct PredecessorMap</font></div><div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">� � PredecessorMap() {}</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � PredecessorMap(PredecessorMap const&amp; that) : m(that.m) {}</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">� � typedef XY key_type;</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � typedef XY value_type;</font></div><div><font face="&#39;courier new&#39;, monospace">� � typedef XY &amp; reference_type;</font></div><div><font face="&#39;courier new&#39;, monospace">� � typedef boost::read_write_property_map_tag category;</font></div>

<div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">� � XY &amp; operator[](XY xy) { return m[xy]; }</font></div><div><font face="&#39;courier new&#39;, monospace"><br>

</font></div><div><font face="&#39;courier new&#39;, monospace">� � std::map&lt;XY,XY&gt; m;</font></div><div><font face="&#39;courier new&#39;, monospace">};</font></div><div><font face="&#39;courier new&#39;, monospace"><br>

</font></div><div><font face="&#39;courier new&#39;, monospace">XY get(PredecessorMap const&amp; pm, XY xy)</font></div><div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">� � std::map&lt;XY,XY&gt;::const_iterator found = pm.m.find(xy);</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � return (found != pm.m.end()) ? found-&gt;second : xy;</font></div><div><font face="&#39;courier new&#39;, monospace">}</font></div><div><font face="&#39;courier new&#39;, monospace"><br>

</font></div><div><font face="&#39;courier new&#39;, monospace">void put(PredecessorMap &amp; pm, XY key, XY value)</font></div><div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">� � pm.m[key] = value;</font></div>

<div><font face="&#39;courier new&#39;, monospace">}</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">// Filter used to traverse grid only along orthogonal (non-diagonal) edges.</font></div>

<div><font face="&#39;courier new&#39;, monospace">struct orthogonal_only</font></div><div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">� � typedef std::pair&lt;XY,XY&gt; Edge;</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � bool operator()(Edge const&amp; edge) const</font></div><div><font face="&#39;courier new&#39;, monospace">� � {</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � return edge.first.x == edge.second.x || edge.first.y == edge.second.y;</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � }</font></div><div><font face="&#39;courier new&#39;, monospace">};</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">// Euclidean distance heuristic (square root omitted)</font></div>

<div><font face="&#39;courier new&#39;, monospace">template &lt;typename Graph&gt;</font></div><div><font face="&#39;courier new&#39;, monospace">class distance_heuristic : public boost::astar_heuristic&lt;Graph, int&gt;</font></div>

<div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">public:</font></div><div><font face="&#39;courier new&#39;, monospace">� � distance_heuristic(XY goal)</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � : m_goal(goal) {}</font></div><div><font face="&#39;courier new&#39;, monospace">� � unsigned operator()(XY xy)</font></div><div><font face="&#39;courier new&#39;, monospace">� � {</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � int dx = m_goal.x - xy.x;</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � int dy = m_goal.y - xy.y;</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � unsigned retval = static_cast&lt;unsigned&gt;(dx * dx + dy * dy);</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � return retval;</font></div><div><font face="&#39;courier new&#39;, monospace">� � }</font></div><div><font face="&#39;courier new&#39;, monospace">private:</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � XY m_goal;</font></div><div><font face="&#39;courier new&#39;, monospace">};</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">int main(int argc, char **argv)</font></div>

<div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">� � XYGraph baseGraph;</font></div><div><font face="&#39;courier new&#39;, monospace">� � boost::filtered_graph&lt;XYGraph, orthogonal_only&gt; g(baseGraph, orthogonal_only());</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � //BOOST_CONCEPT_ASSERT((IncidenceGraphConcept&lt; boost::filtered_graph&lt;XYGraph, orthogonal_only&gt; &gt;));</font></div><div><font face="&#39;courier new&#39;, monospace"><br>

</font></div><div><font face="&#39;courier new&#39;, monospace">� � XY start(0,0);</font></div><div><font face="&#39;courier new&#39;, monospace">� � XY goal(5,7);</font></div><div><font face="&#39;courier new&#39;, monospace"><br>

</font></div><div><font face="&#39;courier new&#39;, monospace">� � std::cout &lt;&lt; &quot;Start vertex: &quot; &lt;&lt; start &lt;&lt; std::endl;</font></div><div><font face="&#39;courier new&#39;, monospace">� � std::cout &lt;&lt; &quot;Goal vertex: &quot; &lt;&lt; goal &lt;&lt; std::endl;</font></div>

<div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">� � PredecessorMap p;</font></div><div><font face="&#39;courier new&#39;, monospace">� � typedef boost::associative_property_map&lt; default_map&lt;XY,unsigned&gt; &gt; DistanceMap;</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � typedef default_map&lt;XY,unsigned&gt; WrappedDistanceMap;</font></div><div><font face="&#39;courier new&#39;, monospace">� � WrappedDistanceMap wrappedMap = WrappedDistanceMap(std::numeric_limits&lt;unsigned&gt;::max());</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � wrappedMap[start] = 0;</font></div><div><font face="&#39;courier new&#39;, monospace">� � DistanceMap d = DistanceMap(wrappedMap);</font></div><div><font face="&#39;courier new&#39;, monospace"><br>

</font></div><div><font face="&#39;courier new&#39;, monospace">� � try {</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � astar_search_no_init(g,�</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � � � start,</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � � � distance_heuristic&lt;XYGraph&gt;(goal)</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � � � , visitor(astar_goal_visitor(goal))</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � � � . distance_map(d)</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � � � . predecessor_map(boost::ref(p))</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � � � . weight_map(boost::associative_property_map&lt; default_map&lt;std::pair&lt;XY,XY&gt;,unsigned&gt; &gt;(</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � � � � � default_map&lt;std::pair&lt;XY,XY&gt;,unsigned&gt;(1)))</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � � � . vertex_index_map(boost::associative_property_map&lt; std::map&lt;XY,unsigned&gt; &gt;(std::map&lt;XY,unsigned&gt;()))</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � � � . rank_map(boost::associative_property_map&lt; std::map&lt;XY,unsigned&gt; &gt;(std::map&lt;XY,unsigned&gt;()))</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � � � . color_map(boost::associative_property_map&lt; std::map&lt;XY,boost::default_color_type&gt; &gt;(</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � � � � � std::map&lt;XY,boost::default_color_type&gt;()))</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � � � . distance_compare(std::less&lt;unsigned&gt;())</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � � � . distance_combine(std::plus&lt;unsigned&gt;())</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � � � );</font></div><div><font face="&#39;courier new&#39;, monospace">� � } catch(found_goal const&amp;) { // found a path to the goal</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � std::list&lt;XY&gt; shortest_path;</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � for(XY xy = goal;; xy = p[xy]) {</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � � � shortest_path.push_front(xy);</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � � � if(p[xy] == xy)</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � � � � � break;</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � }</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � std::cout &lt;&lt; &quot;Shortest path from &quot; &lt;&lt; start &lt;&lt; &quot; to &quot;</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � � � &lt;&lt; goal &lt;&lt; &quot;: &quot;;</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � std::list&lt;XY&gt;::iterator spi = shortest_path.begin();</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � std::cout &lt;&lt; start;</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � for(++spi; spi != shortest_path.end(); ++spi)�</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � � � std::cout &lt;&lt; &quot; -&gt; &quot; &lt;&lt; (*spi);</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � std::cout &lt;&lt; std::endl;</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � return 0;</font></div><div><font face="&#39;courier new&#39;, monospace">� � }</font></div>

<div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">� � std::cout &lt;&lt; &quot;Didn&#39;t find a path from &quot; &lt;&lt; start &lt;&lt; &quot;to&quot;</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � &lt;&lt; goal &lt;&lt; &quot;!&quot; &lt;&lt; std::endl;</font></div><div><font face="&#39;courier new&#39;, monospace">� � return 0;</font></div><div><font face="&#39;courier new&#39;, monospace">}</font></div>

<div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">XYGraph::XYGraph()</font></div><div><font face="&#39;courier new&#39;, monospace">{}</font></div><div>

<font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">std::pair&lt;XYGraph::out_edge_iterator, XYGraph::out_edge_iterator&gt;�</font></div><div><font face="&#39;courier new&#39;, monospace">out_edges(XYGraph::vertex_descriptor v,</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � � XYGraph const&amp; g)</font></div><div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">� � return std::make_pair(</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � XYGraph::out_edge_iterator(v, Direction::MIN),�</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � XYGraph::out_edge_iterator(v, Direction::NONE) );</font></div>

<div><font face="&#39;courier new&#39;, monospace">}</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">XYGraph::degree_size_type�</font></div>

<div><font face="&#39;courier new&#39;, monospace">out_degree(XYGraph::vertex_descriptor v,</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � � �XYGraph const&amp; g)</font></div><div><font face="&#39;courier new&#39;, monospace">{</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � return v.allNeighbors().size();</font></div><div><font face="&#39;courier new&#39;, monospace">}</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div>

<div><font face="&#39;courier new&#39;, monospace">XYGraph::vertex_descriptor�</font></div><div><font face="&#39;courier new&#39;, monospace">source(XYGraph::edge_descriptor e,</font></div><div><font face="&#39;courier new&#39;, monospace">� � � �XYGraph const&amp; g)</font></div>

<div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">� � return e.first;</font></div><div><font face="&#39;courier new&#39;, monospace">}</font></div><div><font face="&#39;courier new&#39;, monospace"><br>

</font></div><div><font face="&#39;courier new&#39;, monospace">XYGraph::vertex_descriptor target(</font></div><div><font face="&#39;courier new&#39;, monospace">� � XYGraph::edge_descriptor e,</font></div><div><font face="&#39;courier new&#39;, monospace">� � XYGraph const&amp; g)</font></div>

<div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">� � return e.second;</font></div><div><font face="&#39;courier new&#39;, monospace">}</font></div><div><font face="&#39;courier new&#39;, monospace"><br>

</font></div><div><font face="&#39;courier new&#39;, monospace">neighbor_iterator::neighbor_iterator()</font></div><div><font face="&#39;courier new&#39;, monospace">{}</font></div><div><font face="&#39;courier new&#39;, monospace"><br>

</font></div><div><font face="&#39;courier new&#39;, monospace">neighbor_iterator::neighbor_iterator(XY xy, Direction::id direction)</font></div><div><font face="&#39;courier new&#39;, monospace">: xy(xy)</font></div><div>

<font face="&#39;courier new&#39;, monospace">, direction(direction)</font></div><div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">}</font></div><div><font face="&#39;courier new&#39;, monospace"><br>

</font></div><div><font face="&#39;courier new&#39;, monospace">neighbor_iterator &amp; neighbor_iterator::operator=(neighbor_iterator const&amp; that)</font></div><div><font face="&#39;courier new&#39;, monospace">{</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � xy = that.xy;</font></div><div><font face="&#39;courier new&#39;, monospace">� � direction = that.direction;</font></div><div><font face="&#39;courier new&#39;, monospace">� � return *this;</font></div>

<div><font face="&#39;courier new&#39;, monospace">}</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">std::pair&lt;XY,XY&gt; neighbor_iterator::operator*() const</font></div>

<div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">� � std::pair&lt;XY,XY&gt; const retval = std::make_pair(xy, xy.neighbor(direction));</font></div><div><font face="&#39;courier new&#39;, monospace">� � return retval;</font></div>

<div><font face="&#39;courier new&#39;, monospace">}</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">void neighbor_iterator::operator++()</font></div>

<div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">� � direction = static_cast&lt;Direction::id&gt;(int(direction) + 1);</font></div><div><font face="&#39;courier new&#39;, monospace">}</font></div>

<div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">bool neighbor_iterator::operator==(neighbor_iterator const&amp; that) const</font></div><div><font face="&#39;courier new&#39;, monospace">{</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � return xy == that.xy &amp;&amp; direction == that.direction;</font></div><div><font face="&#39;courier new&#39;, monospace">}</font></div><div><font face="&#39;courier new&#39;, monospace"><br>

</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">XY::XY(X x, Y y)</font></div><div><font face="&#39;courier new&#39;, monospace">: x(x)</font></div>

<div><font face="&#39;courier new&#39;, monospace">, y(y)</font></div><div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">}</font></div><div><font face="&#39;courier new&#39;, monospace"><br>

</font></div><div><font face="&#39;courier new&#39;, monospace">bool XY::adjacentTo(XY const&amp; that) const</font></div><div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">� � return abs(x - that.x) &lt;= 1 &amp;&amp; abs(y - that.y) &lt;= 1;</font></div>

<div><font face="&#39;courier new&#39;, monospace">}</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">XY &amp; XY::operator=(XY const&amp; that)</font></div>

<div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">� � x = that.x;</font></div><div><font face="&#39;courier new&#39;, monospace">� � y = that.y;</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � return *this;</font></div><div><font face="&#39;courier new&#39;, monospace">}</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">XY &amp; XY::operator+=(XY const&amp; that)</font></div>

<div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">� � x += that.x;</font></div><div><font face="&#39;courier new&#39;, monospace">� � y += that.y;</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � return *this;</font></div><div><font face="&#39;courier new&#39;, monospace">}</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">bool XY::operator&lt;(XY const&amp; that) const</font></div>

<div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">� � return x &lt; that.x || (x == that.x &amp;&amp; y &lt; that.y);</font></div><div><font face="&#39;courier new&#39;, monospace">}</font></div>

<div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">std::ostream &amp; operator&lt;&lt;(std::ostream &amp; os, XY const&amp; xy)</font></div><div><font face="&#39;courier new&#39;, monospace">{</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � os &lt;&lt; &quot;(&quot; &lt;&lt; xy.x &lt;&lt; &quot;,&quot; &lt;&lt; xy.y &lt;&lt; &quot;)&quot;;</font></div><div><font face="&#39;courier new&#39;, monospace">� � return os;</font></div>

<div><font face="&#39;courier new&#39;, monospace">}</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">XY XY::neighbor(Direction::id direction) const</font></div>

<div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">� � using namespace Direction;</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div>

<div><font face="&#39;courier new&#39;, monospace">� � int dx = 0, dy = 0;</font></div><div><font face="&#39;courier new&#39;, monospace">� � switch (direction)</font></div><div><font face="&#39;courier new&#39;, monospace">� � {</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � case NW:</font></div><div><font face="&#39;courier new&#39;, monospace">� � case W:</font></div><div><font face="&#39;courier new&#39;, monospace">� � case SW:</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � dx = -1;</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � break;</font></div><div><font face="&#39;courier new&#39;, monospace">� � case NE:</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � case E:</font></div><div><font face="&#39;courier new&#39;, monospace">� � case SE:</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � dx = 1;</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � }</font></div><div><font face="&#39;courier new&#39;, monospace">� � switch (direction)</font></div><div><font face="&#39;courier new&#39;, monospace">� � {</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � case NW:</font></div><div><font face="&#39;courier new&#39;, monospace">� � case N:</font></div><div><font face="&#39;courier new&#39;, monospace">� � case NE:</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � � � dy = -1; ��</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � break;</font></div><div><font face="&#39;courier new&#39;, monospace">� � case SW:</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � case S:</font></div><div><font face="&#39;courier new&#39;, monospace">� � case SE:</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � dy = 1;</font></div>

<div><font face="&#39;courier new&#39;, monospace">� � }</font></div><div><font face="&#39;courier new&#39;, monospace">� � XY const neighbor(x + dx, y + dy);</font></div><div><font face="&#39;courier new&#39;, monospace">� � return neighbor;</font></div>

<div><font face="&#39;courier new&#39;, monospace">}</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">std::set&lt;XY&gt; XY::allNeighbors() const</font></div>

<div><font face="&#39;courier new&#39;, monospace">{</font></div><div><font face="&#39;courier new&#39;, monospace">� � std::set&lt;XY&gt; neighbors;</font></div><div><font face="&#39;courier new&#39;, monospace"><br></font></div>

<div><font face="&#39;courier new&#39;, monospace">� � for (int dx = -1; dx &lt;= 1; ++dx)</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � for (int dy = -1; dy &lt;= 1; ++dy)</font></div><div><font face="&#39;courier new&#39;, monospace">� � � � � � neighbors.insert(XY(x+dx,y+dy));</font></div>

<div><font face="&#39;courier new&#39;, monospace"><br></font></div><div><font face="&#39;courier new&#39;, monospace">� � return neighbors;</font></div><div><font face="&#39;courier new&#39;, monospace">}</font></div><div>

<br></div>