#include "pathfinding.h"
#include "board.h"
#include <iostream>
#include <fstream>
using namespace std;
Pathfinding::Pathfinding()
{
StartLocation = 0;
GoalLocation = 0;
SelectedTile = -1;
SelectedTileIndex = -1;
OpenListIndex = 0;
ClosedListIndex = 0;
NumberOfTilesOnOpenList = 0;
NumberOfTilesOnClosedList = 0;
int counter = 0;
while (counter < NUMBER_OF_CELLS_ON_GRID)
{
OpenList[counter][0] = -1;
ClosedList[counter][0] = -1;
OpenList[counter][1] = -1;
ClosedList[counter][1] = -1;
FScore[counter] = -1;
GScore[counter] = -1;
HScore[counter] = -1;
FinalPath[counter] = -1;
counter++;
}
}
void Pathfinding::findPath(int start, int goal, Board &aBoardObject)
{
resetVariablesToStartNewSearch();
StartLocation = start;
GoalLocation = goal;
//add starting location to open list
SelectedTile = StartLocation;
SelectedTileIndex = 0;
OpenList[0][TileIndexDimension] = SelectedTile;
OpenList[0][ParentDimension] = SelectedTile;
NumberOfTilesOnOpenList++;
OpenListIndex++;
//set g score for the starting location and initialize the other two to invalid numbers
GScore[SelectedTile] = 0;
HScore[SelectedTile] = 9999;
FScore[SelectedTile] = 9999;
//initialize that shit
ClosedList[0][1] = 0;
bool IsGoalOnClosedList = false;
while (IsGoalOnClosedList == false)
{
//Get next tile to try
SelectedTile = FindLowestFScoreOnOpenList();
//look at each adjacent tile, adding the ones not on the open list or closed list to the open list
addAllAdjacentNodesToOpenList(aBoardObject);
//move the tile we just found from the open list and put it in the closed
addSelectedTileToClosedList();
if (determineIfGoalIsOnClosedList() == true)
IsGoalOnClosedList = true;
}
//find the ending tile on the closed list
int counter = 0, ClosedIndex = 0;
while (counter < NumberOfTilesOnClosedList)
{
if (ClosedList[counter][TileIndexDimension] == GoalLocation)
{
FinalPath[0] = ClosedList[counter][TileIndexDimension];
ClosedIndex = counter; // used in saving the path below
counter = 9999;
}
counter++;
}
//save the path
bool Continue = true;
int index = 0, PathSize = 0;
while (Continue == true)
{
index++;
PathSize++;
ClosedIndex = ClosedList[ClosedIndex][ParentDimension];
FinalPath[index] = ClosedList[ClosedIndex][TileIndexDimension];
if (FinalPath[index] == StartLocation)
Continue = false;
}
//reverse path
int Beginning = 0;
int End = 0;
int tempindex = NUMBER_OF_CELLS_ON_GRID - 1;
counter = 0;
while (counter < tempindex)
{
Beginning = FinalPath[counter];
End = FinalPath[tempindex];
if ((End != -1))
{
FinalPath[tempindex] = Beginning;
FinalPath[counter] = End;
counter++;
}
tempindex--;
}
printBug();
}
void Pathfinding::addAllAdjacentNodesToOpenList(Board &aBoardObject)
{
int AdjacentTileCounter = 1;
int AdjacentTile = -1;
ofstream myfile;
myfile.open ("Scores.txt");
const int NUMBER_OF_ADJACENT_NODES = 8;
while (AdjacentTileCounter <= NUMBER_OF_ADJACENT_NODES)
{
AdjacentTile = determineNeighboringTileNumber(SelectedTile, AdjacentTileCounter, aBoardObject);
if (AdjacentTile >= 0)
if ((aBoardObject.getIsCellOccupied(AdjacentTile) == false) && (aBoardObject.getColor(AdjacentTile) != RED))
{
if (isTileOnOpenList(AdjacentTile) == false)
{
if (isTileOnClosedList(AdjacentTile) == false)
{
OpenList[OpenListIndex][TileIndexDimension] = AdjacentTile;
OpenList[OpenListIndex][ParentDimension] = SelectedTile;
GScore[AdjacentTile] = determineGScore(SelectedTile, AdjacentTileCounter);
HScore[AdjacentTile] = determineHScore(AdjacentTile, aBoardObject);
FScore[AdjacentTile] = GScore[AdjacentTile] + HScore[AdjacentTile];
myfile << "Adjacent #: " << AdjacentTileCounter << " Fscore: " << FScore[AdjacentTile] << " Gscore: " << GScore[AdjacentTile] << " Hscore: " << HScore[AdjacentTile] << endl;
OpenListIndex++;
NumberOfTilesOnOpenList++;
//to make sure we're not overwriting anything already on the list
while (OpenList[OpenListIndex][TileIndexDimension] != -1)
{
OpenListIndex++;
if (OpenListIndex == NUMBER_OF_CELLS_ON_GRID)
OpenListIndex = 0;
}
}
}
//else if tile is on the open list, check the g score from this new path and see if it's lower. if it is, this is a better route
else
{
int TestGScore = determineGScore(AdjacentTile, AdjacentTileCounter);
if (TestGScore <= GScore[AdjacentTile])
{
OpenList[AdjacentTile][ParentDimension] = OpenList[SelectedTileIndex][TileIndexDimension];
GScore[AdjacentTile] = determineGScore(SelectedTile, AdjacentTileCounter);
HScore[AdjacentTile] = determineHScore(AdjacentTile, aBoardObject);
FScore[AdjacentTile] = GScore[AdjacentTile] + HScore[AdjacentTile];
}
}
}
AdjacentTileCounter++;
}
myfile.close();
}
void Pathfinding::addSelectedTileToClosedList()
{
//add to closed list
ClosedList[ClosedListIndex][TileIndexDimension] = OpenList[SelectedTileIndex][TileIndexDimension];
//save location on the closed list of the parent to the sqaure we just put on the closed list
int counter = 0;
while (counter < NumberOfTilesOnClosedList)
{
if (ClosedList[counter][TileIndexDimension] == OpenList[SelectedTileIndex][ParentDimension])
ClosedList[ClosedListIndex][ParentDimension] = counter;
counter++;
}
ClosedListIndex++;
NumberOfTilesOnClosedList++;
//remove from open list
OpenList[SelectedTileIndex][TileIndexDimension] = -1;
OpenList[SelectedTileIndex][ParentDimension] = -1;
NumberOfTilesOnOpenList--;
}
bool Pathfinding::determineIfGoalIsOnClosedList()
{
int counter = 0;
bool IsGoalOnClosedList = false;
while (counter < NumberOfTilesOnClosedList)
{
if (ClosedList[counter][TileIndexDimension] == GoalLocation)
{
IsGoalOnClosedList = true;
counter = 999999;
}
counter++;
}
if (IsGoalOnClosedList == false)
return false;
if (IsGoalOnClosedList == true)
return true;
return false;
}
void Pathfinding::resetVariablesToStartNewSearch()
{
StartLocation = 0;
GoalLocation = 0;
OpenListIndex = 0;
ClosedListIndex = 0;
NumberOfTilesOnOpenList = 0;
NumberOfTilesOnClosedList = 0;
SelectedTile = 0;
SelectedTileIndex = 0;
int counter = 0;
while (counter < NUMBER_OF_CELLS_ON_GRID)
{
OpenList[counter][0] = -1;
ClosedList[counter][0] = -1;
OpenList[counter][1] = -1;
ClosedList[counter][1] = -1;
FScore[NUMBER_OF_CELLS_ON_GRID] = -1;
GScore[NUMBER_OF_CELLS_ON_GRID] = -1;
HScore[NUMBER_OF_CELLS_ON_GRID] = -1;
FinalPath[counter] = -1;
counter++;
}
}
int Pathfinding::determineFScore(int index, int ParentIsWhichNeighbor, Board aBoardObject)
{
int Score = determineGScore(index, ParentIsWhichNeighbor) + determineHScore(index, aBoardObject);
return Score;
}
int Pathfinding::determineGScore(int Parent, int ParentIsWhichNeighbor)
{
int Score = 0;
int ValueToAddToG = 0;
//to determine whether this tile is diagonal or vertical/horizontal from its parent
const int CellToTopLeft = 1;
const int CellToTop = 2;
const int CellToTopRight = 3;
const int CellToLeft = 4;
const int CellToRight = 5;
const int CellToBottomLeft = 6;
const int CellToBottom = 7;
const int CellToBottomRight = 8;
if (ParentIsWhichNeighbor == CellToTopLeft)
ValueToAddToG = 14;
if (ParentIsWhichNeighbor == CellToTopRight)
ValueToAddToG = 14;
if (ParentIsWhichNeighbor == CellToBottomLeft)
ValueToAddToG = 14;
if (ParentIsWhichNeighbor == CellToBottomRight)
ValueToAddToG = 14;
if (ParentIsWhichNeighbor == CellToTop)
ValueToAddToG = 10;
if (ParentIsWhichNeighbor == CellToLeft)
ValueToAddToG = 10;
if (ParentIsWhichNeighbor == CellToRight)
ValueToAddToG = 10;
if (ParentIsWhichNeighbor == CellToBottom)
ValueToAddToG = 10;
Score = (GScore[Parent] + ValueToAddToG);
return Score;
}
int Pathfinding::determineHScore(int index, Board aBoardObject)
{
int VerticalMovesCounter = 0;
int HorizontalMovesCounter = 0;
SDL_Rect CurrentLocation = aBoardObject.getCell(index);
SDL_Rect EndCell = aBoardObject.getCell(GoalLocation);
//get to the same height
while (CurrentLocation.y != EndCell.y)
{
VerticalMovesCounter++;
if (CurrentLocation.y < EndCell.y)
CurrentLocation.y += SQUARE_HEIGHT;
else if (CurrentLocation.y > EndCell.y)
CurrentLocation.y -= SQUARE_HEIGHT;
}
//get same x value
while (CurrentLocation.x != EndCell.x)
{
HorizontalMovesCounter++;
if (CurrentLocation.x < EndCell.x)
CurrentLocation.x += SQUARE_WIDTH;
else if (CurrentLocation.x > EndCell.x)
CurrentLocation.x -= SQUARE_WIDTH;
}
return ((VerticalMovesCounter + HorizontalMovesCounter) * 10);
}
bool Pathfinding::isTileOnOpenList(int TileToCheck)
{
int counter = 0;
int index = 0;
bool OnOpenList = false;
while (counter < NumberOfTilesOnOpenList)
{
if (TileToCheck == OpenList[index][TileIndexDimension])
{
OnOpenList = true;
counter = 9999;
}
if (OpenList[index][TileIndexDimension] != -1)
counter++;
index++;
}
if (OnOpenList == false)
return false;
if (OnOpenList == true)
return true;
return false;
}
bool Pathfinding::isTileOnClosedList(int TileToCheck)
{
int counter = 0;
int index = 0;
while (counter < NumberOfTilesOnClosedList)
{
if (TileToCheck == ClosedList[index][TileIndexDimension])
return true;
if (ClosedList[index][TileIndexDimension] != -1)
counter++;
index++;
}
return false;
}
int Pathfinding::determineNeighboringTileNumber(int index, int WhichNeighbor, Board &aBoardObject)
{
const int LastSquareOnxPlane = SCREEN_WIDTH - SQUARE_WIDTH;
const int LastSquareOnyPlane = SCREEN_HEIGHT - SQUARE_HEIGHT;
const int CellToLeft = index - 1;
const int CellToRight = index + 1;
const int CellToTop = index - NUMBER_OF_CELLS_HORIZONTAL;
const int CellToBottom = index + NUMBER_OF_CELLS_HORIZONTAL;
const int CellToBottomLeft = index + NUMBER_OF_CELLS_HORIZONTAL - 1;
const int CellToBottomRight = index + NUMBER_OF_CELLS_HORIZONTAL + 1;
const int CellToTopLeft = index - NUMBER_OF_CELLS_HORIZONTAL - 1;
const int CellToTopRight = index - NUMBER_OF_CELLS_HORIZONTAL + 1;
//top left
if (WhichNeighbor == 1)
if (aBoardObject.getCell(index).x != 0)
if (aBoardObject.getCell(index).y != 0)
return CellToTopLeft;
//top
if (WhichNeighbor == 2)
if (aBoardObject.getCell(index).y != 0)
return CellToTop;
//top right
if (WhichNeighbor == 3)
if (aBoardObject.getCell(index).x != LastSquareOnxPlane)
if (aBoardObject.getCell(index).y != 0)
return CellToTopRight;
//left
if (WhichNeighbor == 4)
if (aBoardObject.getCell(index).x != 0)
return CellToLeft;
//right
if (WhichNeighbor == 5)
if (aBoardObject.getCell(index).x != LastSquareOnxPlane)
return CellToRight;
//bottom left
if (WhichNeighbor == 6)
if (aBoardObject.getCell(index).x != 0)
if (aBoardObject.getCell(index).y != LastSquareOnyPlane)
return CellToBottomLeft;
//down
if (WhichNeighbor == 7)
if (aBoardObject.getCell(index).y != LastSquareOnyPlane)
return CellToBottom;
//bottom right
if (WhichNeighbor == 8)
if (aBoardObject.getCell(index).x != LastSquareOnxPlane)
if (aBoardObject.getCell(index).y != LastSquareOnyPlane)
return CellToBottomRight;
return -2;
}
int Pathfinding::FindLowestFScoreOnOpenList()
{
int LowestFScore = -1;
int counter = 0, index = 0;
while (counter < NumberOfTilesOnOpenList)
{
if (FScore[OpenList[index][TileIndexDimension]] != -1)
{
if (LowestFScore == -1)
{
LowestFScore = OpenList[index][TileIndexDimension];
SelectedTileIndex = index;
}
else if (FScore[OpenList[index][TileIndexDimension]] <= FScore[LowestFScore])
{
LowestFScore = OpenList[index][TileIndexDimension];
SelectedTileIndex = index;
}
counter++;
}
index++;
}
return LowestFScore;
}
void Pathfinding::printBug()
{
ofstream myfile;
myfile.open ("bug.txt");
myfile << "Start: " << StartLocation << endl;
myfile << "End: " << GoalLocation << endl;
myfile << "Selected: " << SelectedTile << endl;
int counter = 0;
while (counter < NUMBER_OF_CELLS_ON_GRID)
{
if (FinalPath[counter] != -1)
{
myfile << counter << ": Path: " << FinalPath[counter];
myfile << endl;
}
counter++;
}
myfile << endl << endl ;
counter = 0;
while (counter < NUMBER_OF_CELLS_ON_GRID)
{
if (OpenList[counter][0] != -1)
{
myfile << counter << ": OpenList: " << OpenList[counter][0] << " Parent " << OpenList[counter][1];
myfile << endl;
}
counter++;
}
myfile << endl << endl;
counter = 0;
while (counter < NUMBER_OF_CELLS_ON_GRID)
{
if (ClosedList[counter][0] != -1)
{
myfile << counter << ": ClosedList: " << ClosedList[counter][0] << " Parent: " << ClosedList[counter][1];
myfile << endl;
}
counter++;
}
myfile << endl << endl;
counter = 0;
while (counter < NUMBER_OF_CELLS_ON_GRID)
{
if (FScore[counter] != -1)
{
myfile << counter << ": FScore: " << FScore[counter] << ": GScore: " << GScore[counter] << ": HScore: " << HScore[counter];
myfile << endl;
}
counter++;
}
myfile.close();
}
int Pathfinding::getFinalPath(int index)
{
return FinalPath[index];
}