Free easy-to-read A* search and others!
Author
Among other things that I have been doing lately, I completed some of my searches. They should all work correctly. The classes are documented, and the code should be fairly easy to interpret. You can download it at:
http://zefrieggame.tripod.com/AILibrary.zip <-- Right-Click and Save As...
Oh, and do me a favor and send me some feedback on how they worked.
Author
Well, the code is documented. [smile]
[Edited by - Zefrieg on October 22, 2004 11:10:38 PM]
[Edited by - Zefrieg on October 22, 2004 11:10:38 PM]
Author
Well, here is an example of using the searches:
#include <iostream>#include <math.h>#include "Search.h"#include "InformedSearch.h"// Node typestruct Vertex2d{ float x; float y; int id; bool operator==(const Vertex2d& _vert) const { return (id == _vert.id); }};// Node to node cost calculationfloat NodeCost(const Node<Vertex2d, float>& _node1, const Node<Vertex2d, float>& _node2){ float x = _node1.m_object.x - _node2.m_object.x; float y = _node1.m_object.y - _node2.m_object.y; return sqrt((x * x) + (y * y));}// Node to node comparision (optional)int NodeCompare(const InformedNode<Vertex2d, float>& _node1, const InformedNode<Vertex2d, float>& _node2){ return (_node1.m_cost < _node2.m_cost);}int main(){ // Vertex2d = type of node, float = measure of cost Node<Vertex2d, float>* currentNode; Node<Vertex2d, float> searchSpace[10000]; InformedSearch<Vertex2d, float> informedSearch; Search<Vertex2d, float> search; informedSearch.SetCostFunction(NodeCost); // Must supply node cost function informedSearch.SetCompareFunction(NodeCompare); // Optional // Put nodes in random locations for(int i = 0; i < 10000; i++) { searchSpace.m_object.x = float(i) + (rand()%10000); searchSpace.m_object.y = float(i) + (rand()%10000); searchSpace.m_object.id = i; } // Insure a connection from start to goal exists for(int i = 0; i < 9999; i++) { searchSpace.Connect(searchSpace);<br> }<br><br> <span class="cpp-comment">// Randomly connect nodes</span><br> <span class="cpp-keyword">for</span>(<span class="cpp-keyword">int</span> i = <span class="cpp-number">0</span>; i < <span class="cpp-number">100000</span>; i++)<br> {<br> <span class="cpp-keyword">int</span> index1 = rand()%<span class="cpp-number">10000</span>;<br> <span class="cpp-keyword">int</span> index2 = rand()%<span class="cpp-number">10000</span>;<br> <span class="cpp-keyword">if</span>(index1 != index2)<br> {<br> searchSpace[index1].Connect(searchSpace[index2]);<br> }<br> }<br><br> <span class="cpp-comment">// Set start and goal nodes</span><br> informedSearch.Set(&searchSpace[<span class="cpp-number">0</span>], &searchSpace[<span class="cpp-number">9999</span>]);<br> search.Set(&searchSpace[<span class="cpp-number">0</span>], &searchSpace[<span class="cpp-number">9999</span>]);<br><br> <span class="cpp-keyword">if</span>(informedSearch.Greedy())<br> {<br> <span class="cpp-comment">// Print goal path</span><br> std::cout << <span class="cpp-literal">"Greedy"</span> << std::endl;<br> <span class="cpp-keyword">while</span>(!informedSearch.m_goalPath.empty())<br> {<br> currentNode = informedSearch.GetGoalNode();<br> std::cout << <span class="cpp-literal">" id = "</span> << currentNode->m_object.id << <span class="cpp-literal">" "</span><br> << <span class="cpp-literal">",x = "</span> << currentNode->m_object.x << <span class="cpp-literal">" "</span><br> << <span class="cpp-literal">",y = "</span> << currentNode->m_object.y << <span class="cpp-literal">" "</span><br> << std::endl;<br> informedSearch.PopGoalNode(); <br> }<br> std::cout << std::endl;<br> }<br> <span class="cpp-keyword">if</span>(informedSearch.UniformCost())<br> {<br> <span class="cpp-comment">// Print goal path</span><br> std::cout << <span class="cpp-literal">"UniformCost"</span> << std::endl;<br> <span class="cpp-keyword">while</span>(!informedSearch.m_goalPath.empty())<br> {<br> currentNode = informedSearch.GetGoalNode();<br> std::cout << <span class="cpp-literal">" id = "</span> << currentNode->m_object.id << <span class="cpp-literal">" "</span><br> << <span class="cpp-literal">",x = "</span> << currentNode->m_object.x << <span class="cpp-literal">" "</span><br> << <span class="cpp-literal">",y = "</span> << currentNode->m_object.y << <span class="cpp-literal">" "</span><br> << std::endl;<br> informedSearch.PopGoalNode(); <br> }<br> std::cout << std::endl;<br> }<br> <span class="cpp-keyword">if</span>(informedSearch.A())<br> {<br> <span class="cpp-comment">// Print goal path</span><br> std::cout << <span class="cpp-literal">"A*"</span> << std::endl;<br> <span class="cpp-keyword">while</span>(!informedSearch.m_goalPath.empty())<br> {<br> currentNode = informedSearch.GetGoalNode();<br> std::cout << <span class="cpp-literal">" id = "</span> << currentNode->m_object.id << <span class="cpp-literal">" "</span><br> << <span class="cpp-literal">",x = "</span> << currentNode->m_object.x << <span class="cpp-literal">" "</span><br> << <span class="cpp-literal">",y = "</span> << currentNode->m_object.y << <span class="cpp-literal">" "</span><br> << std::endl;<br> informedSearch.PopGoalNode(); <br> }<br> std::cout << std::endl;<br> }<br><br> <span class="cpp-keyword">if</span>(search.BreadthFirst())<br> {<br> <span class="cpp-comment">// Print goal path</span><br> std::cout << <span class="cpp-literal">"BreadthFirst"</span> << std::endl;<br> <span class="cpp-keyword">while</span>(!search.m_goalPath.empty())<br> {<br> currentNode = search.GetGoalNode();<br> std::cout << <span class="cpp-literal">" id = "</span> << currentNode->m_object.id << <span class="cpp-literal">" "</span><br> << <span class="cpp-literal">",x = "</span> << currentNode->m_object.x << <span class="cpp-literal">" "</span><br> << <span class="cpp-literal">",y = "</span> << currentNode->m_object.y << <span class="cpp-literal">" "</span><br> << std::endl;<br> search.PopGoalNode(); <br> }<br> std::cout << std::endl;<br> }<br> <span class="cpp-keyword">if</span>(search.IterativeDeepening())<br> {<br> <span class="cpp-comment">// Print goal path</span><br> std::cout << <span class="cpp-literal">"Iterative Deepening"</span> << std::endl;<br> <span class="cpp-keyword">while</span>(!search.m_goalPath.empty())<br> {<br> currentNode = search.GetGoalNode();<br> std::cout << <span class="cpp-literal">" id = "</span> << currentNode->m_object.id << <span class="cpp-literal">" "</span><br> << <span class="cpp-literal">",x = "</span> << currentNode->m_object.x << <span class="cpp-literal">" "</span><br> << <span class="cpp-literal">",y = "</span> << currentNode->m_object.y << <span class="cpp-literal">" "</span><br> << std::endl;<br> search.PopGoalNode(); <br> }<br> std::cout << std::endl;<br> }<br> <span class="cpp-keyword">if</span>(search.DepthLimited(<span class="cpp-number">4</span>))<br> {<br> <span class="cpp-comment">// Print goal path</span><br> std::cout << <span class="cpp-literal">"Depth Limited"</span> << std::endl;<br> <span class="cpp-keyword">while</span>(!search.m_goalPath.empty())<br> {<br> currentNode = search.GetGoalNode();<br> std::cout << <span class="cpp-literal">" id = "</span> << currentNode->m_object.id << <span class="cpp-literal">" "</span><br> << <span class="cpp-literal">",x = "</span> << currentNode->m_object.x << <span class="cpp-literal">" "</span><br> << <span class="cpp-literal">",y = "</span> << currentNode->m_object.y << <span class="cpp-literal">" "</span><br> << std::endl;<br> search.PopGoalNode(); <br> }<br> std::cout << std::endl;<br> }<br> <span class="cpp-keyword">if</span>(search.DepthFirst())<br> {<br> <span class="cpp-comment">// Print goal path</span><br> std::cout << <span class="cpp-literal">"Depth First"</span> << std::endl;<br> <span class="cpp-keyword">while</span>(!informedSearch.m_goalPath.empty())<br> {<br> currentNode = informedSearch.GetGoalNode();<br> std::cout << <span class="cpp-literal">" id = "</span> << currentNode->m_object.id << <span class="cpp-literal">" "</span><br> << <span class="cpp-literal">",x = "</span> << currentNode->m_object.x << <span class="cpp-literal">" "</span><br> << <span class="cpp-literal">",y = "</span> << currentNode->m_object.y << <span class="cpp-literal">" "</span><br> << std::endl;<br> informedSearch.PopGoalNode(); <br> }<br> std::cout << std::endl;<br> }<br><br> getchar();<br> <span class="cpp-keyword">return</span> <span class="cpp-number">0</span>;<br>}<br><br><br><br></pre></div><!–ENDSCRIPT–><br><br>I'm updating the download to include this. If you are not familiar with searches, then I should mention that DepthFirst might not find the goal path, and it might search forever given certain situations. DepthLimited could suffer the same fate if its depth is set too high. All other searches should complete though.
Author
The cool thing about being able to change comparison and cost functions on the fly is that you can search with different heuritics over the same search space.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
