import javax.swing.JFrame;
import java.awt.Point;
public class NavigationBot
{
private static NavigationBot NavBot;
private static Environment NavArea;
private static GUIManager GMan;
PathCoord[] PathCoordArray; //PathCoord Array
PathCoord[] HeuristicArray; //Heuristic Array
static Point Start;
static Point End;
static Point OldStep;
static Point NewStep;
static Point Vector;
static Point[] History;
static int availLocs;
static int eWidth;
static int eHeight;
static int Area;
public NavigationBot()
{
//Environment variables
availLocs = 0;
eWidth = 300;
eHeight = 200;
Area = eWidth * eHeight;
//Actual size of the area in the assignment is only 300 X 200 and I adjusted the values to match
//Start Coordinates
Start = new Point();
Start.setLocation(20, 150);
//End Coordinates
End = new Point();
End.setLocation(280, 60);
PathCoordArray = new PathCoord[Area];
HeuristicArray = new PathCoord[Area];
OldStep = Start;
NewStep = new Point();
Vector = new Point();
History = new Point[12];
}
public static void main(String[] args) throws Exception
{
NavBot = new NavigationBot();
NavArea = new Environment(Start, End, eWidth, eHeight);
NavArea.InitializePolygonArray();
CalculateArea();
InitMenu();
}
//For displaying the number of polygons in the area that are not inside the
//bounds of the polygons
public static void CalculateArea()
{
int counter = 0;
int index = 0;
for(int w = 0; w < eWidth; w++)
{
for(int h = 0; h < eHeight; h++)
{
index++;
for(int n = 0; n < NavArea.PolygonArray.length; n++)
{
if(NavArea.PolygonArray[n].contains(w, h) == true)
{
counter++;
}
}
}
}
availLocs = index - counter;
//System.err.println("Counter: " + counter); //for testing
}
//Removes the null coordinates from the array to compact the size
public void CleanUpPath()
{
int Index = 0;
for(int i = 0; i < PathCoordArray.length; i++)
{
if(PathCoordArray[i] != null)
Index++;
}
PathCoord[] TempCoordArray = new PathCoord[Index];
for(int i = 0; i < Index; i++)
{
TempCoordArray[i] = PathCoordArray[i];
}
PathCoordArray = TempCoordArray;
}
//Creates a GUI Manager instance to display the startup menu where the
//user can select what algorithm they want to use
public static void InitMenu()
{
GMan = new GUIManager("Choose Algorithm", eWidth, eHeight, NavBot, NavArea);
GMan.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
GMan.setSize(300, 74);
GMan.setLocationByPlatform(true);
GMan.setLocationRelativeTo(null);
GMan.setVisible(true);
GMan.AlgorithmMenu();
}
//For the button in the sim area that returns the user to the startup menu
public void Reset()
{
//Remove any existing GUIManager
GMan.dispose();
NavBot = new NavigationBot();
NavArea = new Environment(Start, End, eWidth, eHeight);
NavArea.InitializePolygonArray();
CalculateArea();
InitMenu();
}
//The A-Star algorith simulation
public void AStar()
{
//Remove any existing GUIManager
GMan.dispose();
//Create GUIManager instance for displaying simulation
GMan = new GUIManager("A* Algorithm Simulation", eWidth, eHeight, NavBot, NavArea);
GMan.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
GMan.setSize(340, 300);
GMan.setLocationByPlatform(true);
GMan.setLocationRelativeTo(null);
GMan.setVisible(true);
//The beginning of the simulation
boolean found = false;
int Index = 0;
UpdateHistory(Start);
//Loops until the end coordinate is reached
while(found == false)
{
//Temporarily added to prevent locks created from the while statement never reaching completion
if(Index > 100)
break;
//Call function to select a new coordinate basedupon the current location
//The intial value is the Start location
NewStep = AStarFindNext(OldStep);
//Add the new coordinate to history
UpdateHistory(NewStep);
//To reduce the number of coordinates stored, we only add the coordinate
//when the bot has had to change direction. This will provide longer line segments
if(AStarChangedDirection(OldStep, NewStep))
{
System.err.println("Direction Change: " + Index); //for testing
//Update the directional vector value
Vector.x = OldStep.x - NewStep.x;
Vector.y = OldStep.y - NewStep.y;
//Add the coordinate at the directional change to the array
PathCoord newCoord = new PathCoord();
newCoord.Coord = OldStep;
//The coordinate cost is the distance from the start
newCoord.Cost = NavArea.GetDistFromStart(OldStep);
PathCoordArray[Index] = newCoord;
Index++;
}
//Check if the new coordinate is the end location
if(NewStep.equals(End) == true)
{
System.err.println("End Found"); //for testing
//Add the final coordinate to the array
PathCoord lastCoord = new PathCoord();
lastCoord.Coord = NewStep;
lastCoord.Cost = NavArea.GetDistFromStart(NewStep);
PathCoordArray[Index] = lastCoord;
//set the flag to break the while statement
found = true;
}
//Save the new step as the old step
OldStep = NewStep;
}
CleanUpPath();//Remove nulls spaces from the array for memory
//Send the number of locations not within one of the polygons for reference use only
//Also send the path so it can be displayed
GMan.DisplaySimulation(availLocs, PathCoordArray);
}
//Find the next coordinate for the bot to travel to
public Point AStarFindNext(Point now)
{
//System.err.println("AStarFindNext"); //for testing
Point next = now; //So we don't send back a zeroed coordinate
Point test = new Point(); //For use in calculations
PathCoord[] TestCoordArray; //Testing Array
TestCoordArray = new PathCoord[8]; //only 8 possible directions
int index = 0;
//Cycle through each possible direction and creat an array of PathCoords
for(int x = -1; x < 2; x++)
{
for(int y = -1; y < 2; y++)
{
//the current position plus the directional change to create a coordinate to test
test.x = now.x + x;
test.y = now.y + y;
if(test.equals(now) == false)
{
//Get the test coordinate's distance from the end location
int testDist = NavArea.GetDistFromEnd(test);
PathCoord testCoord = new PathCoord();
testCoord.Coord.setLocation(test);
testCoord.Cost = testDist;
TestCoordArray[index] = testCoord;
index++;
}
}
}
int lastCost = Area;
for(int i = 0; i < index; i++)
{
//Check if the test location is within the bounds of the environment
if(IsInBounds(TestCoordArray[i].Coord) == true)
{
//check to see if the test location is not within the bounds of one of the polygons
if(IsClear(TestCoordArray[i].Coord) == true)
{
if(InHistory(TestCoordArray[i].Coord) == false)
{
//System.err.println("Cost: " + TestCoordArray[i].Cost); //for testing
if(TestCoordArray[i].Cost < lastCost)
{
//If all of those tests pass, then store the test location as the best candidate to be
//the next coordiante the bot will travel.
next = TestCoordArray[i].Coord;
lastCost = TestCoordArray[i].Cost;
}
}
//else
//System.err.println("In History"); //for testing
}
//else
//System.err.println("Not Clear"); //for testing
}
//else
//System.err.println("Not In Bounds"); //for testing
}
System.err.println("next X: " + next.x); //for testing
System.err.println("next Y: " + next.y); //for testing
return next;
}
//Compare the difference between the old step and new step to the directional
//vector from the last step to determine if the bot is still traveling in the
//same direction
public boolean AStarChangedDirection(Point old, Point now)
{
int CurrX = OldStep.x - NewStep.x;
int CurrY = OldStep.y - NewStep.y;
System.err.println("CurrX: " + CurrX); //for testing
System.err.println("CurrY: " + CurrY); //for testing
System.err.println("Vector X: " + Vector.x); //for testing
System.err.println("Vector Y: " + Vector.y); //for testing
if(CurrX != Vector.x)
return true;
if(CurrY != Vector.y)
return true;
return false;
}
//Checks if the coordinate is in history
public boolean InHistory(Point pnt)
{
for(int i = 0; i < 12; i++)
{
if(History[i] != null)
if(History[i].equals(pnt))
return true;
}
return false;
}
//Adds a new coordinate to historyv at location 0 and pushes the rest back, dropping the last
public void UpdateHistory(Point pnt)
{
Point[] temp = new Point[12];
for(int i = 0; i < 12; i++)
{
temp[i] = History[i];
}
History[0] = pnt;
for(int i = 0; i < 11; i++)
{
History[i+1] = temp[i];
}
}
//Check if the coordinate is within the environment boundries
public boolean IsInBounds(Point test)
{
boolean clear = true;
if(test.x < 0)
{
clear = false;
}
if(test.x > eWidth)
{
clear = false;
}
if(test.y < 0)
{
clear = false;
}
if(test.y > eHeight)
{
clear = false;
}
return clear;
}
//Check if the coordinate is not within one of the polygons
public boolean IsClear(Point test)
{
boolean clear = true;
for(int n = 0; n < NavArea.PolygonArray.length; n++)
{
if(NavArea.PolygonArray[n].contains(test) == true)
{
clear = false;
}
}
return clear;
}
public void BreadthFirst()
{
GMan.dispose();
GMan = new GUIManager("Breadth-First Algorithm Simulation", eWidth, eHeight, NavBot, NavArea);
GMan.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
GMan.setSize(340, 300);
GMan.setLocationByPlatform(true);
GMan.setLocationRelativeTo(null);
GMan.setVisible(true);
GMan.DisplaySimulation(availLocs, PathCoordArray);
}
public void DepthFirst()
{
GMan.dispose();
GMan = new GUIManager("Depth-First Algorithm Simulation", eWidth, eHeight, NavBot, NavArea);
GMan.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
GMan.setSize(340, 300);
GMan.setLocationByPlatform(true);
GMan.setLocationRelativeTo(null);
GMan.setVisible(true);
GMan.DisplaySimulation(availLocs, PathCoordArray);
}
}
LinkBack URL
About LinkBacks
AI Search Simulator Assistance
Reply With Quote
Related threads:
