Abstract
The main focus on this mini test project is to find the path to the exit by only using recursion.
Introduction
There are three testers with a 2-D array map. Inside the map are 0's and 1's. The 0's are walls and the 1's are passable paths.
Source Code
Tester 1:
import java.awt.Point;
import java.util.ArrayList;
public class A5_Final_Tester
{
public static void main(String[] args)
{
int[][] Map = new int[][]{
{ 1, 1, 1, 1 },
{ 0, 0, 1, 0 },
{ 0, 0, 1, 0 },
{ 0, 0, 1, 0 }
};
Path_Finder pf = new Path_Finder();
System.out.println("Test 1...");
boolean PathExists = pf.FindPath(new Point(0, 0), new Point(0, -3), Map);
System.out.println("Actual: PathExists: " + PathExists);
System.out.println("Expected: PathExists: false");
if( PathExists )
{
ArrayList Path = pf.GetPath();
for( Point p : Path )
{
System.out.print("(" + p.x + ", " + p.y + ") ");
}
}
System.out.println("");
System.out.println("Test 2...");
PathExists = pf.FindPath(new Point(0, 0), new Point(0, 3), Map);
System.out.println("Actual: PathExists: " + PathExists);
System.out.println("Expected: PathExists: true");
System.out.print("Actual: ");
if( PathExists )
{
ArrayList Path = pf.GetPath();
for( Point p : Path )
{
System.out.print("(" + p.x + ", " + p.y + ") ");
}
}
System.out.println("\nExpected: (0, 3) (0, 2) (0, 1) (0, 0) ");
System.out.println("");
System.out.println("Test 3...");
PathExists = pf.FindPath(new Point(0, 2), new Point(3, 2), Map);
System.out.println("Actual: PathExists: " + PathExists);
System.out.println("Expected: PathExists: true");
System.out.print("Actual: ");
if( PathExists )
{
ArrayList Path = pf.GetPath();
for( Point p : Path )
{
System.out.print("(" + p.x + ", " + p.y + ") ");
}
}
System.out.println("\nExpected: (3, 2) (2, 2) (1, 2) (0, 2) ");
System.out.println("");
}
}import java.awt.Point;
import java.util.ArrayList;
public class A5_Final_Tester2
{
public static void main(String[] args)
{
int[][] Map = new int[][]{
{ 1, 1, 1, 0, 0, 1 },
{ 0, 0, 1, 0, 0, 1 },
{ 0, 0, 1, 0, 0, 1 },
{ 0, 0, 1, 0, 0, 1 },
{ 0, 0, 1, 1, 1, 1 },
{ 0, 0, 1, 0, 0, 1 },
};
Path_Finder pf = new Path_Finder();
System.out.println("Test 1...");
boolean PathExists = pf.FindPath(new Point(0, 0), new Point(0, 5), Map);
System.out.println("Actual: PathExists: " + PathExists);
System.out.println("Expected: PathExists: true");
System.out.print("Actual: ");
if( PathExists )
{
ArrayList Path = pf.GetPath();
for( Point p : Path )
{
System.out.print("(" + p.x + ", " + p.y + ") ");
}
}
System.out.println("\nExpected: (0, 5) (1, 5) (2, 5) (3, 5) (4, 5) (4, 4) (4, 3) (4, 2) (3, 2) (2, 2) (1, 2) (0, 2) (0, 1) (0, 0) ");
System.out.println("");
System.out.println("Test 2...");
PathExists = pf.FindPath(new Point(0, 5), new Point(0, 0), Map);
System.out.println("Actual: PathExists: " + PathExists);
System.out.println("Expected: PathExists: true");
System.out.print("Actual: ");
if( PathExists )
{
ArrayList Path = pf.GetPath();
for( Point p : Path )
{
System.out.print("(" + p.x + ", " + p.y + ") ");
}
}
System.out.println("\nExpected: (0, 0) (0, 1) (0, 2) (1, 2) (2, 2) (3, 2) (4, 2) (4, 3) (4, 4) (4, 5) (3, 5) (2, 5) (1, 5) (0, 5) ");
System.out.println("");
System.out.println("Test 3...");
PathExists = pf.FindPath(new Point(4, 2), new Point(0, 5), Map);
System.out.println("Actual: PathExists: " + PathExists);
System.out.println("Expected: PathExists: true");
System.out.print("Actual: ");
if( PathExists )
{
ArrayList Path = pf.GetPath();
for( Point p : Path )
{
System.out.print("(" + p.x + ", " + p.y + ") ");
}
}
System.out.println("\nExpected: (0, 5) (1, 5) (2, 5) (3, 5) (4, 5) (4, 4) (4, 3) (4, 2) ");
System.out.println("");
}
}import java.awt.Point;
import java.util.ArrayList;
public class A5_Final_Tester3
{
public static void main(String[] args)
{
int[][] Map = new int[][]{
{ 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 1, 1, 1, 1, 1, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 0, 1, 0 },
{ 1, 1, 1, 0, 0, 0, 0, 0, 1, 1 },
{ 0, 0, 1, 0, 1, 0, 0, 0, 1, 0 },
{ 0, 0, 1, 0, 1, 0, 0, 0, 1, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 1, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 1, 0 },
{ 0, 1, 1, 1, 1, 0, 0, 0, 1, 1 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
};
Path_Finder pf = new Path_Finder();
System.out.println("Test 1...");
boolean PathExists = pf.FindPath(new Point(0, 0), new Point(3, 0), Map);
System.out.println("Actual: PathExists: " + PathExists);
System.out.println("Expected: PathExists: true");
System.out.print("Actual: ");
if( PathExists )
{
ArrayList Path = pf.GetPath();
for( Point p : Path )
{
System.out.print("(" + p.x + ", " + p.y + ") ");
}
}
System.out.println("\nExpected: (3, 0) (3, 1) (3, 2) (2, 2) (1, 2) (0, 2) (0, 1) (0, 0) ");
System.out.println("");
System.out.println("Test 2...");
PathExists = pf.FindPath(new Point(0, 0), new Point(8, 1), Map);
System.out.println("Actual: PathExists: " + PathExists);
System.out.println("Expected: PathExists: false");
if( PathExists )
{
ArrayList Path = pf.GetPath();
for( Point p : Path )
{
System.out.print("(" + p.x + ", " + p.y + ") ");
}
}
System.out.println("");
System.out.println("Test 3...");
PathExists = pf.FindPath(new Point(8, 9), new Point(0, 1), Map);
System.out.println("Actual: PathExists: " + PathExists);
System.out.println("Expected: PathExists: true");
System.out.print("Actual: ");
if( PathExists )
{
ArrayList Path = pf.GetPath();
for( Point p : Path )
{
System.out.print("(" + p.x + ", " + p.y + ") ");
}
}
System.out.println("\nExpected: (0, 1) (0, 2) (1, 2) (1, 3) (1, 4) (1, 5) (1, 6) (1, 7) (1, 8) (2, 8) (3, 8) (4, 8) (5, 8) (6, 8) (7, 8) (8, 8) (8, 9) ");
System.out.println("");
}
}import java.awt.Point;
import java.util.ArrayList;
/**
* This class is used to chart a path from one position
* on a map to another position. The map is a two dimensional
* array of integers, where 0 is an unpassable space, and 1
* is a passable space. The character can only move up, down,
* left and right. It cannot move diagonally.
*/
public class Path_Finder
{
// this ArrayList will contain the Path that is constructed recursively
ArrayList Path = null;
/**
* Empty constructor. It initializes the Path ArrayList. Do not modify this.
*/
public Path_Finder()
{
Path = new ArrayList();
}
/**
* Return the Path. Do not modify this.
*
* @return the Path as an ArrayList of type Point
*/
public ArrayList GetPath()
{
return Path;
}
/**
*
*
*
* @param StartPosition the initial position of the entity that needs to find a path
* @param EndPosition the final position of the entity that needs to find a path
* @param Map the two dimensional map to navigate. 0 is not passable, 1 is passable.
* @return true if such a path exists, and false otherwise.
*/
public boolean FindPath(Point StartPosition, Point EndPosition, int[][] Map)
{
// YOUR CODE
// DRAFT: Make a copy of Map, by calling the method below. Always return false.
// FINAL: Call GetPath.
//know it's the right path if the GetPath doesn't return a null
Path = GetPath(StartPosition, EndPosition, Map);
if(Path == null)
{
return false;
}
return true;
}
/** * @param CurrentPosition the current position of the entity.
* @param EndPosition the final position to navigate to.
* @param Map the Map to traverse. 0 = blocked. 1 = not blocked.
* @return an ArrayList of type Point containing the points in the path between the CurrentPosition and the EndPosition. If there is no path to EndPosition that contains CurrentPosition, then return null. The positions should be in reverse order, from the destination point to the starting point.
*/
private ArrayList GetPath(Point CurrentPosition, Point EndPosition, int[][] Map)
{
int[][] leMap = CopyMap(Map);
if(CurrentPosition.equals(EndPosition))
{
ArrayList temp = new ArrayList<>();
temp.add(CurrentPosition);
return temp;
}
//use these temp arraylists to put in the valid points
ArrayList up = null;
ArrayList down = null;
ArrayList right = null;
ArrayList left = null;
/*check to see which four possible directions are 1 and not out of bounds.
Same conditionals for all four sides.
*/
//up
if((CurrentPosition.x-1 >=0) && (CurrentPosition.x-1 < leMap.length))
{
if(leMap[CurrentPosition.x-1][CurrentPosition.y] == 1)
{
leMap[CurrentPosition.x-1][CurrentPosition.y] = -1;
up = GetPath(new Point(CurrentPosition.x-1, CurrentPosition.y), EndPosition, leMap);
}
}
//down
if((CurrentPosition.x+1 >= 0) && (CurrentPosition.x+1 < leMap.length)){
if(leMap[CurrentPosition.x+1][CurrentPosition.y] == 1)
{
leMap[CurrentPosition.x+1][CurrentPosition.y] = -1;
down = GetPath(new Point(CurrentPosition.x+1, CurrentPosition.y), EndPosition, leMap);
}
}
//left
if((CurrentPosition.y -1 >=0 ) && (CurrentPosition.y-1 < leMap[0].length)){
if(leMap[CurrentPosition.x][CurrentPosition.y-1] == 1)
{
leMap[CurrentPosition.x][CurrentPosition.y-1] = -1;
left = GetPath(new Point(CurrentPosition.x, CurrentPosition.y-1), EndPosition, leMap);
}
}
//right
if((CurrentPosition.y+1 >=0) && (CurrentPosition.y+1 < leMap[0].length))
{
if(leMap[CurrentPosition.x][CurrentPosition.y+1] == 1)
{
leMap[CurrentPosition.x][CurrentPosition.y+1] = -1;
right = GetPath(new Point(CurrentPosition.x, CurrentPosition.y+1), EndPosition, leMap);
}
}
//check all those valid points who has the smallest arraylist
/*
After all the conditionals stop being true and each four temporary arraylists has taken
their turns until the last one finishes,
it comes to here and check for the smallest path.
I use this, incase there's a path with the same final destination but one is longer than the other.
*/
ArrayList shortest = GetSmallestArrayList(up, down, left, right);
if(shortest != null)
{
shortest.add(CurrentPosition);
return shortest;
}
return null;
}
/**
*
*
* @param Paths an array of the ArrayLists passed in as arguments. They should not be passed in as an array, rather the calling program should pass each as its own argument.
* @return the smallest ArrayList
*/
@SafeVarargs
private static ArrayList GetSmallestArrayList(ArrayList ... Paths)
{
ArrayList first = null;
for(int i = 0; i < Paths.length; i++)
{
if(Paths[i] != null)
{
first = Paths[i];
break;
}
}
for(int i = 0; i < Paths.length; i++)
{
if(Paths[i] != null){
if((first.size() > Paths[i].size()))
{
first = Paths[i];
}
}
}
return first;
}
/**
* Make a copy of a two-dimensional array of type int. This will be used to make sure that
* the initial Map is not modified. This is public only for the draft.
*
* @param Map the Map to copy
* @return a copy of the values in the Map array. This should not simply return a new reference to the Map argument.
*/
private int[][] CopyMap(int[][] Map)
{
// YOUR CODE
// DRAFT: Make a copy of Map, and return it.
int[][] theMap = new int[Map.length][Map[0].length];
for(int i = 0; i < Map.length; i++)
{
for(int j = 0; j<Map[0].length; j++)
{
theMap[i][j] = Map[i][j];
}
}
return theMap;
}
}
Tester 1:
Tester 2:
Tester 3:
