I am in the process of writing the best first algorithm. i have not yet implemented the "best" part of it to select only the best node to expand. currently it is expanded each node created. However the while loop expanding the nodes stops executing before it should thus never finding the goal node. I cant figure out why. This is my code so far:
#include <iostream>
#include <list>
#include <fstream>
#include <algorithm>
using namespace std;
///STRUCT STORING EACH NODES VALUES///
struct coords
{
int y;
int x;
int score;
coords* parent;
};
///COMPARISION///
bool Compare(coords* nodeOne, coords*nodeTwo)
{
return(nodeOne->score < nodeTwo->score);
}
///CHECK NODE HAS NOT ALREADY BEEN VISITED///
bool Check(list <coords*> openList, coords* temp)
{
list <coords*>::iterator iterator3;
iterator3 = openList.begin();
bool check = false;
while (iterator3 != openList.end())
{
if ((*iterator3)->x == temp->x && (*iterator3)->y == temp->y)
{
return true;
}
iterator3 ++;
}
return false;
}
int main()
{
///CREATE OPEN AND CLOSED LISTS///
list <coords*> openList;
list <coords*> closedList;
///STORE START AND GOAL NODES///
coords* start = new (coords);
coords* goal = new (coords);
///CREATE CURRENT NODE///
coords* current;
///CREATE EACH NODE TO EXPAND///
coords* north;
coords* east;
coords* south;
coords* west;
///READ IN START AND GOAL FROM TEXT FILE
STORED IN PROGRAM FILE WITH MAIN.CPP///
ifstream input;
input.open("coords.txt");
if (!input.good())
{
cerr << "Failed to open file." << endl;
}
else
{
char temp;
input >> temp;
start->x = temp - 48;
input >> temp;
start->y = temp - 48;
input >> temp;
goal->x = temp - 48;
input >> temp;
goal->y = temp - 48;
}
///SET START NODES PARENT AND SCORE///
start->parent = NULL;
start->score = (goal->x - start->x) + (goal->y - start->y);
///SET GOAL NODES PARENT AND SCORE///
goal->parent = NULL;
goal->score = NULL;
///PUSH START ONTO OPENLIST AND SET CURRENT TO START///
openList.push_back(start);
current = openList.front();
///WHILE GOAL NODE IS NOT FOUND///
while(current->x != goal->x && current->y != goal->y
&& !openList.empty())
{
///SORT OPENLIST TO PLACE CLOSEST NODE TO GOAL IN FRONT///
openList.sort(Compare);
///SEARCH FAIL IS OPENLIST IS EMPTY///
if(openList.empty())
{
cout << "Search failed." << endl;
}
///SET FRONT OF OPENLIST TO NEW CURRENT
AND POP FRONT OF OPENLIST///
current = openList.front();
openList.pop_front();
///EXPAND NODES NORTH HERE (MOVE ONE NODE FORWARD IN GRID)///
north = new coords;
north->x = current->x;
north->y = current->y + 1;
if(Check(openList, north) == false)
{
north->parent = current;
north->score = (goal->x - north->x) +
(goal->y - north->y);
openList.push_back(north);
}
///EXPAND NODES EAST HERE (MOVE ONE NODE RIGHT IN GRID)///
east = new coords;
east->x = current->x + 1;
east->y = current->y;
if(Check(openList, east) == false)
{
east->parent = current;
east->score = (goal->x - east->x) + (goal->y - east->y);
openList.push_back(east);
}
///EXPAND NODES SOUTH HERE (MOVE ONE NODE BACK IN GRID)///
south = new coords;
south->x = current->x;
south->y = current->y - 1;
if(Check(openList, south) == false)
{
south->parent = current;
south->score = (goal->x - south->x) +
(goal->y - south->y);
openList.push_back(south);
}
///EXPAND NODES WEST HERE (MOVE ONE NODE LEFT IN GRID)///
west = new coords;
west->x = current->x - 1;
west->y = current->y;
if(Check(openList, west) == false)
{
west->parent = current;
west->score = (goal->x - west->x) + (goal->y - west->y);
openList.push_back(west);
}
///DISPLAY OPENLIST///
cout << "openList" << endl;
list <coords*>::iterator iterator;
iterator = openList.begin();
while (iterator != openList.end())
{
cout << (*iterator)->x;
cout << (*iterator)->y << endl;
iterator++;
}
///DISPLAY CLOSEDLIST///
cout << "closedList" << endl;
list <coords*>::iterator iterator2;
iterator2 = closedList.begin();
while (iterator2 != closedList.end())
{
cout << (*iterator2)->x;
cout << (*iterator2)->y << endl;
iterator2++;
}
///PUST CURRENT ONTO CLOSEDLIST///
closedList.push_back(current);
///PAUSE BEFORE EACH ITERATION///
system("pause");
}
///GOAL FOUND IF CLOSEDLISTS FRONT NODE IS EQUAL TO GOAL NODE///
if(closedList.front()->x == goal->x && closedList.front()->y == goal->y)
{
cout << "goal found!" << endl;
///BUILD PATH///
///FINISH BUILDING PATH///
}
///PAUSE BEFORE PROGRAM CLOSES///
system ("pause");
}The text file it read in simply contains:
3 4
5 6
