Skip to content

Instantly share code, notes, and snippets.

@macroxela

macroxela/AStar.cpp

Created April 24, 2014 00:44
Show Gist options
  • Save macroxela/11237566 to your computer and use it in GitHub Desktop.
Save macroxela/11237566 to your computer and use it in GitHub Desktop.
Download ZIP
A* Implementation for shortest path between 2 cities given map data from input file.
Raw
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;
}
Raw
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
Raw
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment