A* Implementation for shortest path between 2 cities given map data from input file.

AStar.cpp

/*
Alex Marroquin
CSCI 4350 Artificial Intelligence

Homework 1: A* Implementation
main.cpp

Given an input file with the list of all the cities, edges, and other data the A* algorithm
must find the shortest path between 2 locations depending on the heuristic. In this case
the heuristic must depend on the straight line distance to the destination, distance from the 
previous city, total traveled distance, presence of a road, and danger of the road.
*/

#include<iostream>
#include<string>
#include<fstream>
#include<time.h>
#include<math.h>
#include"ItemList.h"
using namespace std;

//Used to keep track of which cities have been visited
class GoneThrough
{
public:
	GoneThrough * nxt;
	string name;
	GoneThrough(){nxt = NULL; name = "";};
};

//Data structure used to run A* algorithm
//Using the Child or Table elements would get messier
class Node
{
public:
	Node *parent;
	GoneThrough *list;
	double g,h,f,path,straight_dist,risk;
	string name;
	Node(){parent = NULL;list = NULL;g=0;f=0;h=0;path=0;risk=0;straight_dist=0;name="";};
};

//Used to store neighbors and their data
class Child
{
public:
	string name;
	Child *parent,*next;
	double distance;
	double path;
	double risk;
	double straight_dist;
	Child(const Child&);
	Child(){name = "NULL";distance = 0;path = 0; risk = 0; straight_dist = 0;parent = NULL;};
	Child(string nm, double d, double p, double r, double std){name = nm;distance = d;path = p; risk = r;straight_dist = std;parent = NULL;};
	void print(){cout<<name<<"\n Path: "<<path<<" Dist.: "<<distance<<" Risk: "<<risk<<" Straight Dist.: "<<straight_dist<<endl;};
};

Child::Child(const Child &s)
{
	name = s.name;
	parent = s.parent;
	distance = s.distance;
	path = s.path;
	risk = s.risk;
	straight_dist = s.straight_dist;
}

//Table used to store the city data for later search
//Only stores the city name, straight distance, and neighbors
//represented by the Child array
class Table
{
public:
	Child neigh[25];
	double straight_dist;
	string name;
	void printData();
	void printChildren();
	Table();
};

Table::Table()
{
	for(int i = 0; i < 25; i++)
	{
		neigh[i].name = "NULL";
	}
	name = "NULL";
}

void Table::printData()
{
	cout<<name<<",  "<<straight_dist<<endl;
}

void Table::printChildren()
{
	for(int i = 0; i < 25; i++)
	{
		if(neigh[i].name != "NULL")
			neigh[i].print();
	}
}
//For string parsing
void cutstring(string &input, int pos)
{
        string dummy = "";

        for(int i = pos; i < input.length(); i++)
        {
			dummy += input[i];
        }
        input = dummy;
}
//Also for string parsing
string concatenate(string &input)
{
        string ls = "";
        if(input == "")
        {
                return "";
        }
        int size = input.length();
        int cnt = 0;
        int i = 0;
        while(isspace(input[cnt]))
        {
                cnt ++;
                if(cnt == size)
                        return "";
        }
        if(cnt == size)
        {
                return "";
        }
        while(cnt < size)
        {
                if(isspace(input[cnt]))
                        break;
                ls += input[cnt];
                cnt++;
        }
        cutstring(input,cnt);
        return ls;
}

//To look up city data on the table
Table Find(Table look[], string item, int size)
{
	for(int i = 0; i < size; i++)
	{
		if(look[i].name == item)
		{
			return look[i];
		}
	}

	cout<<"Item not found"<<endl;
	Table tabs;
	return tabs;
}

//Check whether a city has already been traveled through
bool traveled(GoneThrough *list, string nm)
{
	GoneThrough *s = list;
	while(s != NULL)
	{
		if(s->name == nm)
			return true;
		s = s->nxt;
	}
	return false;
}

int main()
{
	Table data[25];					//Table used to store city data including neighbors
	ifstream inFile("dats.txt");

	if(inFile.is_open())
	{
		string s, s1, s2, s3, s4, s5, s6;
		string goal, start;
		getline(inFile,s);
		start = s;
		getline(inFile,s);
		goal = s;

		//This entire for loop is to fill the table with city data. This data can then be searched
		//for using the Find function
		for(int i = 0; i < 25; i++)
		{
			string s, s1, s2, s3, s4, s5, s6;
			getline(inFile,s);
			s1 = concatenate(s);
			s2 = concatenate(s);
			s3 = concatenate(s);

			if(s1 == "# ")	//Denotes the end of the file
			{
				data[i].name = "Null";
			}
			else
			{
				if(!isdigit(s2[0]))
				{
					data[i].name = s1 + " " + s2;
					data[i].straight_dist = atof(s3.c_str());
				}
				else
				{
					data[i].name = s1;
					data[i].straight_dist = atof(s2.c_str());
					s = s3 + s;
				}
				int cnt = 0;
				while(!s.empty())
				{
					s1 = concatenate(s);
					s2 = concatenate(s);
					s3 = concatenate(s);
					s4 = concatenate(s);
					s5 = concatenate(s);
					s6 = concatenate(s);
					if(s1 == "@")
						break;
					if(!isdigit(s2[0]))
					{
						data[i].neigh[cnt].name = s1 + " " + s2;
						data[i].neigh[cnt].distance = atof(s3.c_str());
						data[i].neigh[cnt].path = 1/atof(s4.c_str());	//This will be used as a speed value for the heuristic
						data[i].neigh[cnt].risk = atof(s5.c_str());		//Should be more significant than all other elements
						data[i].neigh[cnt].straight_dist = atof(s6.c_str());
					}
					else
					{
						data[i].neigh[cnt].name = s1;
						data[i].neigh[cnt].distance = atof(s2.c_str());
						data[i].neigh[cnt].path = 1/atof(s3.c_str());
						data[i].neigh[cnt].risk = atof(s4.c_str());
						data[i].neigh[cnt].straight_dist = atof(s5.c_str());
						s = s6 + s;
					}
					cnt++;
				}
				for(cnt; cnt < 25; cnt++)
				{
					data[i].neigh[cnt].name = "NULL";
				}

			}
		}
		
		//To view the data read
		/*for(int i = 0; i < 25; i++)
		{
			data[i].printData();
			data[i].printChildren();
			cout<<endl;
		}*/
		cout<<"Start: "<<start<<", Goal: "<<goal<<endl;

		clock_t clock_start = clock();	//To measure how much time it takes to run the algorithm

		//Start A* algorithm
		ItemList<Node*> L1,L2;	//Opened and Closed lists
		Table found;
		Node *st = new Node;
		Node *exp = new Node;
		bool FD = false;
		string name = "";
		
		double dist_trav = 0;

		if(start == goal)
		{
			cout<<"Already there"<<endl;
			FD = true;
		}

		//Initializing first point on map
		found = Find(data,start,25);
		st->parent = NULL;
		st->name = found.name;
		st->straight_dist = found.straight_dist;
		L2.push(st,0,0);

		exp = st;
		name = st->name;

		//Will continue looping until a solution has been found or the 
		//Opened list is empty
		while(!FD)
		{
			//Add all neighbors to List 1, L1
			for(int i = 0; i < 25; i++)
			{
				if(found.neigh[i].name != "NULL")
				{
					//Storing all the data in a Node structure for insertion in 
					//the opened list
					Node * b = new Node;
					b->name = found.neigh[i].name;
					b->parent = exp;
					b->straight_dist = found.neigh[i].straight_dist;
					b->list = new GoneThrough;
					b->list->name = exp->name;
					if(exp->parent != NULL)
					{
						b->list->nxt = exp->list;
						bool t = !traveled(b->list, b->name);	//Check if already visited
						if(t)
							L1.push(b,dist_trav, found.neigh[i].distance);
					}
					else
					{
						L1.push(b,dist_trav, found.neigh[i].distance);
					}
				}
				else
				{
					break;
				}
			}

			//Retrieve the best solution so far
			exp = L1.findSmallest();
			dist_trav = L1.distance_traveled(exp);
			L2.push(exp,dist_trav);
			L1.remove(exp);

			//Reinitialize variables for next iteration
			found = Find(data,exp->name,25);
			if(exp->name == goal)
			{
				FD = true;
			}
			if(L1.empty())
				break;
		}

		

		double time_c = (double)(clock()- clock_start)/CLOCKS_PER_SEC;
		
		//Retrieve the path taken and print it out
		GoneThrough *gt = exp->list;
		string route = "";
		while(gt != NULL)
		{
			route = gt->name + "\n" + route;
			gt = gt->nxt;
		}
		route += exp->name;
		cout<<route<<endl;
		cout<<"Time to find solution: "<<time_c<<" seconds"<<endl;

	}  

	
	

	system("pause");
	return 0;
}

input.txt

Blue Mountains
Iron Hills
Blue Mountains	1250	Lake Evendim	250	2	4	1025	Michel Delving	270	5	2	1075	White Towers	225	5	2	1150	Grey Havens	240	5	2 	1200	@
Lake Evendim	1025	Blue Mountains	250	2	4	1250	Fornost		85	2	6	925	Michel Delving	110	2	5 	1075	@
Grey Havens	1200	Blue Mountains	240	5	2 	1250	White Towers	100	5	1	1150	Sarn Ford	270	2	3 	975	@
White Towers	1150	Blue Mountains	225	5	2	1250	Michel Delving	40	5	1	1075	Hobbiton	70	5	1	1050	Grey Havens	100	5	1	1200	@
Michel Delving	1075	Blue Mountains	270	5	2	1250	Hobbiton	35	5	0.5	1050	Brandy Hall	80	5	0.5 	1000	White Towers	40	5	1	1150	Lake Evendim	110	2	5 	1025	@
Hobbiton	1050	Brandy Hall	50	5	0.5	1000	Bree		100	5	1.5	900	Sarn Ford	130	5	3 	975	Michel Delving	35	5	0.5	1075	White Towers	70	5	1	1150	@
Brandy Hall	1000	Bree		50	5	1.5 	900	Hobbiton	50	5	0.5	1050	Michel Delving	80	5	0.5 	1075	@
Bree		900	Brandy Hall	50	5	1.5 	1000	Hobbiton	100	5	1.5	1050	Fornost		115	5	3	925	Weathertop	100	5	4	825	Sarn Ford	105	5	3	975	@
Fornost		925	Lake Evendim	85	2	6	1025	Bree		115	5	3	900	Weathertop	160	2	3	825	Rivendell	375	2	5 	580	@
Sarn Ford	975	Grey Havens	270	2	3 	1200	Hobbiton	130	5	3 	1050	Bree		105	5	3	900	Weathertop	180	2	5.5	825	Rivendell	400	2	5.5	580	Isengard	500	2	6 	890	@
Weathertop	825	Fornost		160	2	3	925	Bree		100	5	4	900	Sarn Ford	180	2	5.5	975	Rivendell	230	5	4.5 	580	@
Rivendell	580	Fornost		375	2	5 	925	Sarn Ford	400	2	5.5	975	Weathertop	230	5	4.5 	825	North Pass	100	2	6.5	500	Caradhras	60	5	6.5	550	Moria		180	2	9	620	Isengard	500	2	8.5 	890	@
North Pass	500	Rivendell	100	2	6.5	580	Carrock		80	2	7 	450	@
Caradhras	550	Rivendell	60	5	6.5	580	Carrock		70	2	7	450	Gladden Fields	150	2	6	500	Lothlorien	300	2	5.5	660	 @
Moria		620	Rivendell	180	2	9	580	Gladden Fields	140	2	9.5	500	Lothlorien	20	2	9.5 	660	@
Gladden Fields	500	Caradhras	150	2	6	550	Moria		140	2	9.5	620	Esgaroth	400	2	6	175	Dol Guldur	175	2	8	500	Lothlorien	190	2	7 	660	@
Lothlorien	660	Caradhras	300	2	5.5	550	Moria		20	2	9.5 	620	Gladden Fields	190	2	7 	500	Dol Guldur	180	2	8.5	500	Isengard	240	2	8 	890	@
Carrock		450	North Pass	80	2	7 	500	Caradhras	70	2	7	550	Wood Elves	175	2	8	275	Erebor		250	2	8	200	Esgaroth	240	2	8	175	Dol Guldur	300	2	8.5 	500	@
Dol Guldur	500	Lothlorien	180	2	8.5	660	Carrock		300	2	8.5 	450	Gladden Fields	175	2	8	500	Isengard	390	2	8.5 	890	@
Isengard	890	Sarn Ford	500	2	6 	975	Rivendell	500	2	8.5 	580	Lothlorien	240	2	8	660	Dol Guldur	390	2	8.5	500	@
Wood Elves	275	Carrock		175	2	8	450	Dale		90	5	3	180	Erebor		100	5	3 	200	@
Esgaroth	175	Carrock		240	2	8	450	Gladden Fields	400	2	6	500	Dale		40	5	1.5	180	Erebor		50	5	1.5	200	Iron Hills	175	5	3 	0	@
Dale		180	Wood Elves	90	5	3	275	Esgaroth	40	5	1.5	175	Erebor		10	5	1	200	Iron Hills	180	5	3 		@
Erebor		200	Carrock		250	2	8	450	Wood Elves	100	5	3 	275	Esgaroth	50	5	1.5	175	Dale		10	5	1	180	Iron Hills	200	5	3	0	@
Iron Hills	0	Erebor		200	5	3	200	Dale		180	5	3	180	Esgaroth	175	5	3	175	@
#

Start			1		dist.	p	r	std	2		dist.	p	r	std	3		dist.	p	r	std	4		dist.	p	r	std	5		dist.	p	r	std	6		dist.	p	r	std	7		dist.	p	r	std	

First 2 cities denote the start and goal cities respectively.
The 2nd column denotes the straight line distance from the column 1 city to the goal, in this
case the Iron Hills.

3rd column shows the name of a neighboring city
4th column shows the distance from that city to its parent, the one in the 1st column
5th column shows whether a road exists or not. 5 denotes a road, 2 denotes no road.
6th column shows the risk in traveling through the road
7th column shows the straight line distance to the goal, Iron Hills

The above structure repeats for all the neighboring cities. A @ symbol denotes the end of the line,
i.e. the last city

ItemList.h

/*
Alex Marroquin
CSCI 4350 Artificial Intelligence

Homework 1: A* Implementation
ItemList.h
*/

#ifndef HEAP_AM
#define HEAP_AM

#include <iostream>
using namespace std;

template<class THING>

class ItemList
{	
public:
	//To store the data in a linked list. Opted for a linked
	//list to simplify the coding implementation
	class node
	{
	public:
		THING data;
		node * next;
		node *prev;
		double heuristic;
		double dist_trav;
		bool mark;
		node(){prev = NULL; next = NULL;heuristic = 0;dist_trav = 0;mark = false;};
		node(THING dt){data = dt;prev = NULL; next = NULL;heuristic = 0;dist_trav = 0;mark = false;};
	};
	node *head;

	ItemList()
	{
		head = NULL;
	}

	void push(THING s, double dst, double p)
	{
		node *temp = new node(s);
		if(head == NULL)
		{
			temp->dist_trav = dst + p;
			//temp->heuristic = dst;   //To test heuristic with just shortest distance
			temp->heuristic = dst + p*s->path + exp(s->risk) + s->straight_dist;
			head = temp;
		}
		else
		{
			temp->dist_trav = dst + p;
			temp->next = head;
			//temp->heuristic = dst;   //To test heuristic with just shortest distance
			temp->heuristic = dst + p*s->path + exp(s->risk) + s->straight_dist;
			head->prev = temp;
			head = temp;
		}
	}

	//Old push method, not the one currently used
	void push(THING s, double dst)
	{
		node *temp = new node(s);
		if(head == NULL)
		{
			temp->dist_trav = dst;
			temp->heuristic = (dst/s->path + s->straight_dist)*exp(s->risk);
			head = temp;
		}
		else
		{
			temp->dist_trav = dst;
			temp->next = head;
			temp->heuristic = (dst/s->path + s->straight_dist)*exp(s->risk);
			//temp->heuristic = dst;
			head->prev = temp;
			head = temp;
		}
	}

	bool empty()
	{
		 if(head == NULL)
		 {
			 return true;
		 }
		return false;      
	}

	void printList()
	{
		node *search = head;
		if(empty())
		{
			cout<<"Empty List"<<endl;
			return;
		}

		while (search != NULL)
		{
			cout<<search->data->name<<"  ";
			cout<<search->heuristic<<endl;
			search = search->next;
		}
		cout<<endl;
	}

	//Retrieve the node with the smallest heuristic
	THING findSmallest()
	{
		node *small = head;
		if(empty())
		{
			THING x;
			x->name = "NULL";
			return x;
		}

		node *search = head->next;
		if(search == NULL)
		{
			return small->data;
		}
		
		while(search != NULL)
		{
			if(small->heuristic > search->heuristic)
				small = search;
			search = search->next;
		}

		small->mark = true;
		return small->data;
	}

	//Retrieve the distance traveled by a particular path
	double distance_traveled(THING s)
	{
		node *search = head;
		if(empty())
		{
			return 0;
		}

		while(search != NULL)
		{
			if(s->name == search->data->name && search->mark)
			{
				return search->dist_trav;
			}
			search = search->next;
		}
		return 0;
	}

	void remove(THING s)
	{
		node *search = head;
		node *p,*n;
		if(empty())
		{
			return;
		}

		while(search != NULL)
		{
			if(s->name == search->data->name && search->mark)
			{
				p = search->prev;
				n = search->next;
				if(p != NULL)
					p->next = n;
				if(n != NULL)
					n->prev = p;
				break;
			}
			search = search->next;
		}
		
	}


};
#endif