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

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

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 on other sites
File not available.

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

Share on other sites
Weird, it worked.

Anyhow, some documentation would probably be in order.

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

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

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 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[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 on other sites
Nice I will look into it.

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 on other sites
Quote:
 Well, the code is documented.

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

Share on other sites
Anybody check this out?

1. 1
2. 2
Rutin
21
3. 3
4. 4
frob
14
5. 5

• 12
• 9
• 17
• 19
• 9
• Forum Statistics

• Total Topics
632598
• Total Posts
3007334

×