COM00143M - AI Assignment: IDDFS Algorithm for Grid Pathfinding

This assignment solution provides an implementation of the Iterative Deepening Depth-First Search (IDDFS) algorithm in Java to find the shortest path in a grid, given a source and destination. The code includes a SearchNode class with methods to determine neighboring nodes. The iterativeDeepening method iteratively calls the depthLimitedSearch method, incrementing the maximum depth until the goal is found. The depthLimitedSearch method uses a stack to explore the grid, tracking visited nodes and the current depth. The calcpostion method determines the source and destination positions within the grid. The main method initializes a sample grid and executes the IDDFS algorithm, printing the frontier and depth at each iteration until the goal is reached. This solution aligns with the COM00143M Artificial Intelligence and Machine Learning module requirements.

The following is an efficient and debugged version of the java program that takes into account the
specific positions of the source and destination given in some cases the goal appears first before the
source.
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Stack;
public class IDSearch {
private Stack<Integer> stack;
private int numberOfNodes;
//private static SearchNode node;
private static SearchNode srcnode;
private static SearchNode destNode;
private int depth;
private int maxDepth;
private static int xsrc;
private static int ysrc;
private static int xdest;
private static int ydest;
private boolean goalFound = false;
private IDSearch()
{
stack = new Stack<Integer>();
}
static class SearchNode
{
int x,y, depth;
SearchNode(int x, int y)
{
this.x = x;
this.y = y;
//this.depth = depth;
}
//This method requires a new Node then establishes if the Node is a neighbour
//to the current Node or not.
private boolean neighbour(SearchNode curr)
{
if(curr.x == this.x + 1 || curr.x == this.y - 1)
{
return true;
}
return false;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof SearchNode)) return false;
SearchNode that = (SearchNode) o;
return x == that.x &&
y == that.y;
}
@Override
public String toString() {
return "SearchNode{" +
"x=" + x +
", y=" + y +
'}' + "depth" + this.depth;
}

}
public void iterativeDeepening( int matrixGrid[][], int source, int destination)
{
//numberOfNodes = matrixGrid[1].length - 1;
while (!goalFound && maxDepth < numberOfNodes)
{
depthLimitedSearch(matrixGrid, matrixGrid[xsrc][ysrc], destination);
maxDepth++;
}
System.out.println("\n Goal found at depth " + depth);
}
private void depthLimitedSearch(int matrixGrid[][], int source, int goal)
{
int element, destination = 1;
int[] visited = new int[numberOfNodes + 1];
stack.push(source);
depth = 0;
System.out.println("\nAt Depth " + maxDepth + "\t" );
System.out.println( "Frontier (" + (maxDepth - 1) + "," + maxDepth + ")");
System.out.print( source + "\t");
if( maxDepth == depth && goalFound )
{
return;
}
else
{
Outer:
while (!stack.isEmpty())
{
element = stack.peek();
while(destination < numberOfNodes && matrixGrid[element][destination]
!= 3)
{
if(depth < maxDepth && maxDepth < numberOfNodes)
{
if(matrixGrid[element][destination] == 0 &&
matrixGrid[element][destination] != 1 && matrixGrid[element][destination] != 2)
{
stack.push(destination);
visited[destination] = 3;
System.out.print(destination + "\t");
depth++;
if(matrixGrid[element][destination] == 3 || element ==
xdest && destination == ydest)
{
goalFound = true;
break Outer;
}
element = destination;
destination = 3;
break;
}
}
else
{
break;
}
destination++;
}
destination = stack.pop() + 1;
//depth--;

}
depth--;
}
}
//to calculate the source and destination in the matrix
private static void calcpostion(int [][] matrix)
{
for(int i = 0; i < matrix.length; i++)
{
for(int j = 0; j < matrix[0].length; j++)
{
if(matrix[i][j] == 2)
{
xsrc = i;
ysrc = j;
srcnode = new SearchNode(xsrc,ysrc);
}
else if(matrix[i][j] == 3)
{
ysrc = i;
ydest = j;
destNode = new SearchNode(ysrc,ydest);
}
}
}
// System.out.println(xsrc + " " + xdest + " " + ysrc + " " + ydest);
}
public static void main( String... arg)
{
try {
int NodesNumber = 15;
int[][] grid1 = new int [][] {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};
IDSearch idSearch = new IDSearch();
idSearch.numberOfNodes = 15;//Number of nodes
calcpostion(grid1);
// System.out.println(xsrc);
idSearch.iterativeDeepening(grid1, grid1[xsrc][ydest], grid1[xdest]
[ydest]);
/* for(int i = 0; i < grid1.length; i++)
{
for(int j = 0; j < grid1[0].length;j++)
{
System.out.print(grid1[i][j] + "\t");
}
}*/

// System.out.println(Arrays.deepToString(grid1));//make sure the array
elements are displayed with 2 (source) and 3 (dest) correctly .
}
catch (InputMismatchException exception)
{
System.out.println("Check your input array");
}
}
}