Free easy-to-read A* search and others!
October 22, 2004 01:15 AM
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.
516
October 22, 2004 05:09 AM
File not available.
Too bad, i was actually interested in comparing it with mine. =)
Too bad, i was actually interested in comparing it with mine. =)
516
October 22, 2004 05:51 AM
Weird, it worked.
Anyhow, some documentation would probably be in order.
Anyhow, some documentation would probably be in order.
October 22, 2004 10:10 PM
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]
October 22, 2004 11:31 PM
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.October 22, 2004 11:43 PM
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.
516
October 23, 2004 04:49 AM
Quote:
Well, the code is documented.
Where? Do you mean the comments in the source files?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement