import java.awt.BorderLayout;
import java.util.ArrayList;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
public class AStar extends MatrixButtons
{
ArrayList<MatrixButtons> openList = new ArrayList<MatrixButtons>();
ArrayList<MatrixButtons> tempList = new ArrayList<MatrixButtons>();
ArrayList<MatrixButtons> closedList = new ArrayList<MatrixButtons>();
MatrixButtons[][] current;
MatrixButtons[][] endButton;
MatrixButtons[][] startButton;
MatrixButtons[][] nextCurrent;
MatrixButtons[][] temp;
MatrixButtons bestNextMove;
//stores the location of the next best move in order to find it
//inside tempList from another method
int nextMoveIndex;
//these variables will be used to find the rows and columns
//in order to get the heuristic
int startRow;
int startCol;
int endRow;
int endCol;
//loop though all buttons and finds the end icon
void findEndButton()
{
for(int i=0;i<20;i++)
{
for(int j =0;j<20;j++)
{
if(temp[i][j].getIcon()!= null)
{
//find end icon and setting it to endButton
if(temp[i][j].getIcon().equals(end))
{
endButton[i][j]=temp[i][j];
endRow = i;//will be used to find the heuristic
endCol = j;//will be used to find the heuristic
}
}
}
}
}
//loops through all the buttons and finds the start icon
void findStartButton()
{
for(int i=0;i<20;i++)
{
for(int j =0;j<20;j++)
{
if(temp[i][j].getIcon() != null)
{
//find start icon and setting it to startButton
if(temp[i][j].getIcon().equals(begin))
{
startButton[i][j]=temp[i][j];
startRow = i;//will be used to find the heuristic
startCol = j;//will be used to find the heuristic
}
}
}
}
}
/*
if movement is diagonal g_value is set to 15
else it is vertical and set to 10
This method gets the current nodes row and column and
sets the g_value instead of using a loop
*/
void setValues(int row, int col)
{
//diagonal top left
current[row-1][col-1].g_value=15;
current[row-1][col-1].heuristic = getHeuristic(current,row-1,col-1);
current[row-1][col-1].f_value = getFvalue(current,row-1,col-1);
//diagonal top right
current[row-1][col+1].g_value=15;
current[row-1][col+1].heuristic = getHeuristic(current,row-1,col+1);
current[row-1][col+1].f_value = getFvalue(current,row-1,col+1);
//diagonal bottom right
current[row+1][col+1].g_value=15;
current[row+1][col+1].heuristic = getHeuristic(current,row+1,col+1);
current[row+1][col+1].f_value = getFvalue(current,row+1,col+1);
//diagonal bottom left
current[row+1][col-1].g_value=15;
current[row+1][col-1].heuristic = getHeuristic(current,row+1,col-1);
current[row+1][col-1].f_value = getFvalue(current,row+1,col-1);
//vertical top
current[row-1][col].g_value=10;
current[row-1][col].heuristic = getHeuristic(current,row-1,col);
current[row-1][col].f_value = getFvalue(current,row-1,col);
//vertical right
current[row][col+1].g_value=10;
current[row][col+1].heuristic = getHeuristic(current,row,col+1);
current[row][col+1].f_value = getFvalue(current,row,row+1);
//vertical bottom
current[row+1][col].g_value=10;
current[row+1][col].heuristic = getHeuristic(current,row+1,col);
current[row+1][col].f_value = getFvalue(current,row+1,col);
//vertical left
current[row][col-1].g_value=10;
current[row][col-1].heuristic = getHeuristic(current,row,col-1);
current[row][col-1].f_value = getFvalue(current,row,col-1);
}
/*
Total distance from start button to end button. Walls
will not be considered as barriers.
*/
int getHeuristic(MatrixButtons[][] h, int row, int col)
{
return h[row][col].heuristic = (endRow-row) + (endCol-col);
}
/*
getFvalue returns getHeuristic() + getGvalue() to later decide
the best move to make next
*/
int getFvalue(MatrixButtons[][] f,int row, int col)
{
return f[row][col].f_value = f[row][col].g_value
+ getHeuristic(f,row,col);
}
/*this method will receive the row and column of the current button
and return a matrixButton with a lesser f_value by placing each option
on the ArrayList openList, sorting openList least to greatest, and
returning the first matrixButton on the list. The rest of the buttons will
be moved to the closed list so they are never searched again and the
open listed is cleared.
*/
MatrixButtons findNextMove(int row, int col)
{
int value=0;
int temp=0;
//adding elements on the temp list to be checked
//diagonal top left
tempList.add(current[row-1][col-1]);
//diagonal top right
tempList.add(current[row-1][col+1]);
//diagonal bottom right
tempList.add(current[row+1][col+1]);
//diagonal bottom left
tempList.add(current[row+1][col-1]);
//vertical top
tempList.add(current[row-1][col]);
//vertical right
tempList.add(current[row][col+1]);
//vertical bottom
tempList.add(current[row+1][col]);
//vertical left
tempList.add(current[row][col-1]);
//setting temp to the first number
//assuming it is the smallest number
temp = tempList.get(0).f_value;
for(int i=0; i<tempList.size();i++)
{
value = tempList.get(i).f_value;
if(temp > value)
{
//temp is not equal to the smallest number again
temp=value;
bestNextMove = tempList.get(i);
nextMoveIndex =i;
}
}
//returns the button with the smallest f_value
return bestNextMove;
}
//puts checked and unused buttons onto closed list
// and keeps used button on closed list.
void cleanTempList()
{
//moves the bestNextMove into the open list
openList.add(tempList.get(nextMoveIndex));
//removes the bestNextMove from tempList
tempList.remove(nextMoveIndex);
//store remaining buttons that were searched and
//found not to be the shortest path to closed List
for(int i=0;i<tempList.size();i++)
{
closedList.set(i, tempList.get(i));
}
//clears tempList
tempList.clear();
}
void findPath()
{
//setting current button to start button
current = startButton;
JLabel found;
JPanel panel;
int row = startRow;
int col = startCol;
//setting g_value,and Heuristic to start buttons position
setValues(row,col);
while(nextCurrent != endButton)
{
nextCurrent[row][col]=findNextMove(row,col);
if(nextCurrent==endButton)
{
JFrame j = new JFrame("FOUND!!!");
panel = new JPanel();
panel.setLayout(new BorderLayout());
found = new JLabel("END BUTTON WAS FOUND!!!");
panel.add(found);
j.add(panel);
j.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
j.setVisible(true);
}
//resetting tempList and putting values checked value that were
//not used onto closed list
cleanTempList();
//recursion
findPath();
}
}
void markPath()
{
for(int i=0;i<openList.size();i++)
{
openList.get(i).setIcon(begin);
}
}
public static void main(String[] args)
{
new Screen();
}
}