Sign in to follow this  

Free easy-to-read A* search and others!

This topic is 4828 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
File not available.

Too bad, i was actually interested in comparing it with mine. =)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
copy&paste the link

Share this post


Link to post
Share on other sites
Weird, it worked.

Anyhow, some documentation would probably be in order.

Share this post


Link to post
Share on other sites
Well, the code is documented. [smile]

[Edited by - Zefrieg on October 22, 2004 11:10:38 PM]

Share this post


Link to post
Share on other sites
Well, here is an example of using the searches:



#include <iostream>
#include <math.h>
#include "Search.h"
#include "InformedSearch.h"

// Node type
struct Vertex2d
{
float x;
float y;
int id;
bool operator==(const Vertex2d& _vert) const
{
return (id == _vert.id);
}
};

// Node to node cost calculation
float 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[i].m_object.x = float(i) + (rand()%10000);
searchSpace[i].m_object.y = float(i) + (rand()%10000);
searchSpace[i].m_object.id = i;
}

// Insure a connection from start to goal exists
for(int i = 0; i < 9999; i++)
{
searchSpace[i].Connect(searchSpace[i + 1]);
}

// Randomly connect nodes
for(int i = 0; i < 100000; i++)
{
int index1 = rand()%10000;
int index2 = rand()%10000;
if(index1 != index2)
{
searchSpace[index1].Connect(searchSpace[index2]);
}
}

// Set start and goal nodes
informedSearch.Set(&searchSpace[0], &searchSpace[9999]);
search.Set(&searchSpace[0], &searchSpace[9999]);

if(informedSearch.Greedy())
{
// Print goal path
std::cout << "Greedy" << std::endl;
while(!informedSearch.m_goalPath.empty())
{
currentNode = informedSearch.GetGoalNode();
std::cout << " id = " << currentNode->m_object.id << " "
<< ",x = " << currentNode->m_object.x << " "
<< ",y = " << currentNode->m_object.y << " "
<< std::endl;
informedSearch.PopGoalNode();
}
std::cout << std::endl;
}
if(informedSearch.UniformCost())
{
// Print goal path
std::cout << "UniformCost" << std::endl;
while(!informedSearch.m_goalPath.empty())
{
currentNode = informedSearch.GetGoalNode();
std::cout << " id = " << currentNode->m_object.id << " "
<< ",x = " << currentNode->m_object.x << " "
<< ",y = " << currentNode->m_object.y << " "
<< std::endl;
informedSearch.PopGoalNode();
}
std::cout << std::endl;
}
if(informedSearch.A())
{
// Print goal path
std::cout << "A*" << std::endl;
while(!informedSearch.m_goalPath.empty())
{
currentNode = informedSearch.GetGoalNode();
std::cout << " id = " << currentNode->m_object.id << " "
<< ",x = " << currentNode->m_object.x << " "
<< ",y = " << currentNode->m_object.y << " "
<< std::endl;
informedSearch.PopGoalNode();
}
std::cout << std::endl;
}

if(search.BreadthFirst())
{
// Print goal path
std::cout << "BreadthFirst" << std::endl;
while(!search.m_goalPath.empty())
{
currentNode = search.GetGoalNode();
std::cout << " id = " << currentNode->m_object.id << " "
<< ",x = " << currentNode->m_object.x << " "
<< ",y = " << currentNode->m_object.y << " "
<< std::endl;
search.PopGoalNode();
}
std::cout << std::endl;
}
if(search.IterativeDeepening())
{
// Print goal path
std::cout << "Iterative Deepening" << std::endl;
while(!search.m_goalPath.empty())
{
currentNode = search.GetGoalNode();
std::cout << " id = " << currentNode->m_object.id << " "
<< ",x = " << currentNode->m_object.x << " "
<< ",y = " << currentNode->m_object.y << " "
<< std::endl;
search.PopGoalNode();
}
std::cout << std::endl;
}
if(search.DepthLimited(4))
{
// Print goal path
std::cout << "Depth Limited" << std::endl;
while(!search.m_goalPath.empty())
{
currentNode = search.GetGoalNode();
std::cout << " id = " << currentNode->m_object.id << " "
<< ",x = " << currentNode->m_object.x << " "
<< ",y = " << currentNode->m_object.y << " "
<< std::endl;
search.PopGoalNode();
}
std::cout << std::endl;
}
if(search.DepthFirst())
{
// Print goal path
std::cout << "Depth First" << std::endl;
while(!informedSearch.m_goalPath.empty())
{
currentNode = informedSearch.GetGoalNode();
std::cout << " id = " << currentNode->m_object.id << " "
<< ",x = " << currentNode->m_object.x << " "
<< ",y = " << currentNode->m_object.y << " "
<< std::endl;
informedSearch.PopGoalNode();
}
std::cout << std::endl;
}

getchar();
return 0;
}





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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:

Well, the code is documented.


Where? Do you mean the comments in the source files?

Share this post


Link to post
Share on other sites
Sign in to follow this