Happy New Year everyone.
I'm having some trouble implementing a A-Star Algorithm into C++, I do understand what it's supposed to be doing, but unsure on how to program it:
The Task is as follows:
"Implement a A* Pathfinding search that includes backtracking
and using the Manhattan Distance"
I have 2 text files to read in from, 1 contains the Start and End goals (dCoords.txt) and the other text file is a map with costs (dMap) like so :
1 2 3 4 5 6 7 8 9 10
|
1100011111
1001000011
1032111011
1030301011
1030301011
1030301011
1012111011
1010000011
1000111111
1111111111
|
the Main points I'm stuck on are:
- the heuristic itself (where to call it, how to actually implement it).
- How to make the start and end equal the dCoords.txt file, whilst running
through the dMap.txt file and saving the shortest path
- checking around current to check the costs of moving to them
Please any help is valuable to help me learn this
Here is all the code I've wrote so far:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
|
struct pNode
{
int xPos;
int yPos;
char ch;
int score;
pNode* Parent;
};
class dMap
{
public:
static const int ARRAY_SIZE = 100;
void LoadFile();
void Display() const;
void aStar();
private:
pNode mArray[ARRAY_SIZE];
pNode mArrayCoords[ARRAY_SIZE];
};
void dMap::LoadFile()
{
ifstream infile("dMap.txt");
if (!infile)
{
cout << "Cannot open File";
exit(1);
}
for (int i = 0; i < ARRAY_SIZE; i++)
{
infile >> mArray[i].xPos >> mArray[i].yPos;
}
ifstream infile("dCoords.txt");
if (!infile)
{
cout << "Cannot open File";
exit(1);
}
for (int i = 0; i <9; i++)
{
infile >> mArrayCoords[i].xPos >> mArrayCoords[i].yPos;
}
}
void push_back(const int& _Val);
void dMap::aStar()
{
LoadFile();
list<pNode*>openList;
//openList = mArray[ARRAY_SIZE];
pNode* startNode = new (pNode);
list <pNode*>closedList;
pNode* endNode = new (pNode);
endNode ->xPos = mArrayCoords[i].xPos;
endNode ->yPos = mArrayCoords[i].yPos;
startNode -> xPos = mArrayCoords[i].xPos;
startNode -> yPos = mArrayCoords[i].yPos;
openList.push_back(startNode);
while (openList.empty())
{
current = openList.front();
openList.pop_front;
if (current->xPos == endNode -> xPos && current -> yPos == endNode->yPos)
{
cout << "success" << endl;
}
closedList.push_back(current);
}
}
}
|