This is a code to solve a maze using A* search algorithm. When I run it, it gives me the following error: Exception in thread "main" java.lang.NullPointerException
Can someone help me out?
Below is all the code:
import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.util.PriorityQueue;
import java.util.Stack;
public class MiFoMaze
{
public static void main(String[] args)
{
AStar solution = new AStar(new Maze(new String[]
{
"S X X X "
, "XX XX XXXXX XXX X XX"
, "X X X X X "
, "XX XX X XXX XXX X "
, "XXXX XX X "
, " X X XX"
, " XXXXX X XX XXXX "
, " XX XX X X XX "
, " XX XX X XXXXXX XX "
, " X X X X XX "
, " X XX X X X X "
, "XXXXXXXX X XXXX G"
}));
solution.find();
System.out.println(solution);
}
}
class Maze
{
protected Tile[][] tile;
protected Position SS;
protected Position GS;
public Maze(String[] mazeEntries)
{
tile = new Tile[mazeEntries.length][];
for(int row=0; row<tile.length; row++)
{
String Row = mazeEntries[row];
tile[row] = new Tile[Row.length()];
for(int column=0; column<tile.length; column++)
{
tile[row][column] = new Tile(row, column, Row.charAt(column));
}
if(SS==null && Row.indexOf('S')>-1)
{
SS = new Position(row, Row.indexOf('S'));
}
if(GS==null && Row.indexOf('G')>-1)
{
GS = new Position(row, Row.indexOf('G'));
}
}
}
public Position[] getSteps(Position position)
{
List<Position> steps = new ArrayList<Position>();
if(isPassable(position.row-1, position.column))
{
steps.add(tile[position.row-1][position.column].finalPosition);
}
if(isPassable(position.row+1, position.column))
{
steps.add(tile[position.row+1][position.column].finalPosition);
}
if(isPassable(position.row, position.column-1))
{
steps.add(tile[position.row][position.column-1].finalPosition);
}
if(isPassable(position.row, position.column+1))
{
steps.add(tile[position.row][position.column+1].finalPosition);
}
return steps.toArray(new Position[]{});
}
private boolean isPassable(int row, int column)
{
return row>=0 && row<tile.length && column>=0 && column<tile[0].length && !tile[row][column].isWall;
}
}
class Tile
{
final Position finalPosition;
final boolean isWall;
public Tile(int row, int column, char wall)
{
this.finalPosition = new Position(row, column);
this.isWall = (wall=='X');
}
}
class Position
{
final int row;
final int column;
public Position(int row, int column)
{
this.row=row;
this.column=column;
}
@Override
@SuppressWarnings("EqualsWhichDoesntCheckParameterClass")
public boolean equals(Object other)
{
Position pos = (Position)other;
return this.row==pos.row && this.column==pos.column;
}
@Override
public int hashCode()
{
return row*10000 + column;
}
@Override
public String toString()
{
return "("+row+","+column+")";
}
}
class Path implements Comparable<Path>
{
protected Stack<Position> Spath;
protected Position end;
public Path(Position end)
{
this.Spath = new Stack<Position>();
this.end = end;
}
public Path(Position start, Position end)
{
this(end);
Spath.add(start);
}
public Path(Path path, Position position, Position end)
{
this(end);
Spath.addAll(path.Spath);
Spath.add(position);
}
public int compareTo(Path other)
{
return probableCostOf(this.Spath)-probableCostOf(other.Spath);
}
protected int probableCostOf(Stack<Position> Path)
{
return costSoFar(Path)+estimatedCostToExit(Path);
}
protected int costSoFar(Stack<Position> Path)
{
return Path.size();
}
protected int estimatedCostToExit(Stack<Position> Path)
{
Position endPath = Path.peek();
return Math.abs(endPath.row-end.row) + Math.abs(endPath.column-end.column);
}
public boolean contains(Position position)
{
return Spath.contains(position);
}
public Position peek()
{
return Spath.peek();
}
@Override
public String toString()
{
return Spath.toString();
}
}
class AStar
{
final Maze finalMaze;
private Queue<Path> Qpath;
private Path shortestPath;
public AStar(Maze maze)
{
this.finalMaze = maze;
this.Qpath = new PriorityQueue<Path>();
this.Qpath.add(new Path(maze.SS, maze.GS));
this.shortestPath = null;
}
public boolean find()
{
Position end = this.finalMaze.GS;
while(!this.Qpath.isEmpty())
{
Path path = Qpath.poll();
Position current = path.peek();
for(Position next: finalMaze.getSteps(current))
{
if(path.contains(next))
{
continue;
}
Path newPath = new Path(path, next, end);
if(next.equals(end))
{
shortestPath = newPath;
return true;
}
else
{
Qpath.add(newPath);
}
}
}
return false;
}
@Override
public String toString()
{
if(shortestPath==null)
{
return "MiFo couldn't find the path! ";
}
return toString(shortestPath);
}
public String toString(Path path)
{
StringBuilder result = new StringBuilder();
for (Tile[] row : this.finalMaze.tile)
{
for (Tile tile: row)
{
if (this.finalMaze.SS.equals(tile.finalPosition))
{
result.append('S');
}
else if (this.finalMaze.GS.equals(tile.finalPosition))
{
result.append('G');
}
else if (path.contains(tile.finalPosition))
{
result.append('O');
}
else
{
result.append(tile.isWall ? 'X' : ' ');
}
}
result.append('\n');
}
result.append("Total number of steps = ");
result.append(path.Spath.size());
result.append('\n');
return result.toString();
}
}To add to it, this is the output that i get when i run the program:
run:
Exception in thread "main" java.lang.NullPointerException
at Maze.isPassable(MiFoMaze.java:79)
at Maze.getSteps(MiFoMaze.java:71)
at AStar.find(MiFoMaze.java:189)
at MiFoMaze.main(MiFoMaze.java:26)
Java Result: 1
BUILD SUCCESSFUL (total time: 0 seconds)