Hi guys,
i have been working on a A* pathfinding algorithm and have run in some trouble. It doesn't connect the start point to the finish right. At the beginning it adds so many tiles to the closed list and not just the right path. towards the End the code only hast the best way and avoids the walls
Here an example to make it better to understand i inverted the tiles. spaces are walkable, the . are not walkable and represent the walls and the # represent the path
Code:
######################################.
######################################. ###
#######################################. #.#
#######################################.##########################.##########
#######################################.# .
#.# .
#.# .
#.# .
#.# .
#.#
#.#
#.# ..................
###
I hope someone understands what i am doing here with the given comments in the code and can help :-( i have no idea where my misstake is.
main.cpp
Code:
#include <iostream>
#include "PathNode.h"
#include "PathFinding.h"
#include "MapDimensions.h"
using namespace std;
int main()
{
tile start,finish;
char temp[mapx][mapy]=
{
"################################################################################",
"########################################.#######################################",
"########################################.#######################################",
"########################################.##########################.############",
"##s#####################################.##########################.#########f##",
"########################################.##########################.############",
"########################################.##########################.############",
"########################################.##########################.############",
"########################################.##########################.############",
"########################################.##########################.############",
"########################################.#######################################",
"########################################.#######################################",
"########################################.###############..................######",
"################################################################################",
"################################################################################",
"################################################################################",
"################################################################################",
"################################################################################",
"################################################################################",
"################################################################################",
"################################################################################",
"################################################################################"
};
//get from start and finish the x and y coords
for(int i=0; i < mapx; i++)
{
for(int j=0; j< mapy; j++)
{
if(temp[i][j]=='s')
{
start.x=i;
start.y=j;
}
if(temp[i][j]=='f')
{
finish.x=i;
finish.y=j;
}
}
}
PathFinding path;
path.findPath(temp,'#',' ','.',start,finish);
//print path
for(int t=0;t<path.closedList.size();t++)
{
temp[path.closedList[t].x][path.closedList[t].y] = ' ';
}
//output complete map
for(int a=0; a<mapx; a++)
{
cout<<temp[a]<<endl;
}
return 0;
}
PathNode.h
Code:
#ifndef PATHNODE_H_
#define PATHNODE_H_
struct tile
{
//x and y coord of the current tile
int x;
int y;
//total score so f=g+h
int f;
// g is the steps needed from start to current point
int g;
//estimated length needed to get to goal. abs(goal.x -x) + abs(goal.y - y)
int h;
//parents x and y coords
int pX;
int pY;
};
#endif
MapDimensions.h
Code:
#ifndef MAPDIMENSIONS_H_
#define MAPDIMENSIONS_H_
//Map dimensions
const int mapx =22;
const int mapy =82;
const int mapz =10;
#endif
PathFinding.h
Code:
#ifndef PATHFINDING_H_
#define PATHFINDING_H_
#include <vector>
#include "PathNode.h"
#include "MapDimensions.h"
using namespace std;
class PathFinding
{
private:
vector<tile> openList;
bool isInClosed(tile a);
bool isInOpen(tile a);
tile getBestTile(const vector<tile> a);
int getgScore(char matrix[mapx][mapy], char walkable, char hardwalkable,char notWalkable, tile a);
void deleteElement(vector<tile>& a, tile b);
public:
PathFinding();
vector<tile> closedList;
void findPath(char matrix[mapx][mapy], char walkable, char hardwalkable,char notWalkable, tile start, tile finish);
};
#endif
PathFinding.cpp
Code:
#include <cmath>
#include "PathFinding.h"
#include "PathNode.h"
#include <iostream>
using namespace std;
PathFinding::PathFinding()
{
openList.clear();
closedList.clear();
}
bool PathFinding::isInClosed(tile a)
{
//go through open list and if there's a match return true
for(int i=0; i < closedList.size(); i++)
{
if(a.x == closedList[i].x && a.y == closedList[i].y)
{
return true;
}
}
return false;
}
bool PathFinding::isInOpen(tile a)
{
//go through open list and if there's a match return true
for(int i=0; i < openList.size(); i++)
{
if(a.x == openList[i].x && a.y == openList[i].y)
{
return true;
}
}
return false;
}
tile PathFinding::getBestTile(const vector<tile> a)
{
tile best;
/*
best.x=a[0].x;
best.y=a[0].y;
best.g=a[0].g;
best.f=a[0].f;
best.h=a[0].h;
best.pX=a[0].pX;
best.pY=a[0].pY;
*/
best =a[0];
//find the coord with minimun f cost
for(int i=1; i< a.size(); i++)
{
if(a[i].f < best.f)
{
/*
best.x=a[i].x;
best.y=a[i].y;
best.g=a[i].g;
best.f=a[i].f;
best.h=a[i].h;
best.pX=a[i].pX;
best.pY=a[i].pY;
*/
best=a[i];
}
}
return best;
}
int PathFinding::getgScore(char matrix[mapx][mapy], char walkable, char hardwalkable,char notWalkable, tile a)
{
int score;
//if floor should be avoided because its not passable give it high value
if(matrix[a.x][a.y] == notWalkable)
{
score =9;
}
//if the floor is walkable then tile is 1
if(matrix[a.x][a.y] == walkable)
{
score =1;
}
//tile is hardwalkable so the cost to get there will be 2
if(matrix[a.x][a.y] == hardwalkable)
{
score =2;
}
return score;
}
void PathFinding::deleteElement(vector<tile>& a, tile b)
{
//find coord b and then if found delete it
for(int i =0; i <a.size(); i++)
{
//if x and y are same we found coord
if(a[i].x ==b.x && a[i].y == b.y)
{
a.erase(a.begin()+i);
}
}
}
void PathFinding::findPath(char matrix[mapx][mapy], char walkable, char hardwalkable,char notWalkable, tile start, tile finish)
{
closedList.clear();
openList.clear();
//add the start to the closedList
closedList.push_back(start);
//create a variable which will be checked
tile nCheck,parent;
parent.x=start.x;
parent.y=start.y;
parent.g=0;
parent.h=0;
parent.f=0;
parent.pX=start.x;
parent.pY=start.y;
bool endLoop =false;
do
{
openList.clear();
//check coord north
nCheck.x=parent.x-1;
nCheck.y=parent.y;
nCheck.g=parent.g + getgScore(matrix,walkable,hardwalkable,notWalkable,nCheck);
nCheck.h=abs(finish.x-nCheck.x) + abs(finish.y-nCheck.y);
nCheck.f = nCheck.g + nCheck.h;
nCheck.pX=parent.x;
nCheck.pY=parent.y;
if(nCheck.x >0 && nCheck.x < mapx && nCheck.y >0 && nCheck.y < mapy && isInClosed(nCheck) == false && isInOpen(nCheck) == false)
{
openList.push_back(nCheck);
}
//check south
nCheck.x=parent.x+1;
nCheck.y=parent.y;
nCheck.g=parent.g + getgScore(matrix,walkable,hardwalkable,notWalkable,nCheck);
nCheck.h=abs(finish.x-nCheck.x) + abs(finish.y-nCheck.y);
nCheck.f = nCheck.g + nCheck.h;
nCheck.pX=parent.x;
nCheck.pY=parent.y;
if(nCheck.x >0 && nCheck.x < mapx && nCheck.y >0 && nCheck.y < mapy && isInClosed(nCheck) == false && isInOpen(nCheck) == false)
{
openList.push_back(nCheck);
}
//check west
nCheck.x=parent.x;
nCheck.y=parent.y-1;
nCheck.g=parent.g + getgScore(matrix,walkable,hardwalkable,notWalkable,nCheck);
nCheck.h=abs(finish.x-nCheck.x) + abs(finish.y-nCheck.y);
nCheck.f = nCheck.g + nCheck.h;
nCheck.pX=parent.x;
nCheck.pY=parent.y;
if(nCheck.x >0 && nCheck.x < mapx && nCheck.y >0 && nCheck.y < mapy && isInClosed(nCheck) == false && isInOpen(nCheck) == false)
{
openList.push_back(nCheck);
}
//check east
nCheck.x=parent.x;
nCheck.y=parent.y+1;
nCheck.g=parent.g + getgScore(matrix,walkable,hardwalkable,notWalkable,nCheck);
nCheck.h=abs(finish.x-nCheck.x) + abs(finish.y-nCheck.y);
nCheck.f = nCheck.g + nCheck.h;
nCheck.pX=parent.x;
nCheck.pY=parent.y;
if(nCheck.x >0 && nCheck.x < mapx && nCheck.y >0 && nCheck.y < mapy && isInClosed(nCheck) == false && isInOpen(nCheck) == false)
{
openList.push_back(nCheck);
}
//if a coord in the open list is the finish set its values so that it will definitly be added
for(int i =0; i < openList.size(); i++)
{
if(openList[i].x == finish.x && openList[i].y == finish.y)
{
openList[i].g=0;
openList[i].h=0;
openList[i].f=0;
}
}
//get best f score from the added tiles in the openList
closedList.push_back(getBestTile(openList));
//setting parent to the best connection tile
parent=getBestTile(openList);
deleteElement(openList,getBestTile(openList));
//to end the while loop since finish was reached
if(isInClosed(finish) == true)
{
endLoop=true;
}
//just to see what is in the open list
for(int i =0; i <openList.size(); i++)
{
if(i==0)
{
cout<<"openList"<<endl;
}
cout<<"x:"<<openList[i].x<<" y:"<<openList[i].y<<endl;
}
}
while(endLoop != true);
//to see what is in closed list
for(int i=0; i<closedList.size(); i++)
{
cout<<"x"<<closedList[i].x<<" y"<<closedList[i].y<<endl;
}
}