pinkninjajess · August 31, 2020 22:16
diff --git a/MazeSolver b/MazeSolver
 package Maze;

 import java.util.*;

 /*
 Learned about the A* algorithm from many sources including
 https://www.raywenderlich.com/3016-introduction-to-a-pathfinding - strategy adopted from this post
 http://csis.pace.edu/~benjamin/teaching/cs627/webfiles/Astar.pdf
 */


 public class MazeSolver{

    private static final int MOVE_COST = 1;
    private static boolean mazeSolved = false;
    private static Map<MazeCell, MazeCell> mazeCellToParent = new HashMap<MazeCell, MazeCell>();

    private MazeSolver() {
    }

    private static Maze drawPath(final Maze maze) {
        Position goal = maze.getGoal();
        MazeCell goalCell = maze.getCell(goal);

        Position start = maze.getStart();
        MazeCell startingCell = maze.getCell(start);

        // update the maze to show the path, if the maze is solve-able
        if (mazeSolved) {
            int movesFromStartToGoal = 1;
            MazeCell currentCell = mazeCellToParent.get(goalCell);
            currentCell.setCellInfo(CellInfo.PATH);
            MazeCell previousCell = currentCell;

            while (currentCell != startingCell) {
                movesFromStartToGoal +=1;
                currentCell = mazeCellToParent.get(previousCell);

                // mark the cell with character representing the path
                currentCell.setCellInfo(CellInfo.PATH);
                previousCell = currentCell;
            }

            System.out.println("Moves from start to goal: " + movesFromStartToGoal);
        }
        return maze;
    }

    public static Maze solve(final Maze maze) {

        Set<MazeCell> closedCells = new HashSet<MazeCell>();
        Map<MazeCell, Position> mazeCellPositions = new HashMap<MazeCell, Position>();

        // h = best guess cost from current node to the destination - using Manhattan distance
        // g = cost from the start to the current node
        // calculate g by taking g of its parent and add movement cost to it
        // f cost = g + h

        TreeSet<MazeCell> openCells = new TreeSet<MazeCell>(
                Comparator.comparingDouble((MazeCell cell) -> (cell.getHeuristicCost() + cell.getPathCost()))
                        // needed to add the comparisons below, because TreeSets cannot contain duplicate values
                            // and cells with the same costs would be identified as duplicates
                        .thenComparing((MazeCell cell) -> mazeCellPositions.get(cell).getCol())
                        .thenComparing((MazeCell cell) -> mazeCellPositions.get(cell).getRow()));

        Position start = maze.getStart();
        MazeCell startingCell = maze.getCell(start);
        startingCell.setPathCost(0);
        mazeCellPositions.put(startingCell, start);

        Position goal = maze.getGoal();
        MazeCell goalCell = maze.getCell(goal);
        mazeCellPositions.put(goalCell, goal);

        openCells.add(startingCell);


        do {
            MazeCell currentMazeCell = openCells.first();
            Position currentPosition = mazeCellPositions.get(currentMazeCell);

            closedCells.add(currentMazeCell);
            openCells.remove(currentMazeCell);

            if (closedCells.contains(goalCell)) {
                mazeSolved = true;
                break;
            }

            List<Position> availablePositions = maze.getPathCandidates(currentPosition);
            List<Position> potentialMoves = maze.getMoves(currentPosition);
            availablePositions.addAll(potentialMoves);

            for (Position position : availablePositions) {
                MazeCell cell = maze.getCell(position);
                mazeCellPositions.put(cell, position);

                if (closedCells.contains(cell)) {
                    continue;
                }
                if (!openCells.contains(cell)) {
                    cell.setHeuristicCost(position.getDistance(goal));
                    cell.setPathCost(currentMazeCell.getPathCost() + MOVE_COST);
                    openCells.add(cell);
                    mazeCellToParent.put(cell, currentMazeCell);
                } else {
                    // check to see if using the current cell would give a better path
                        // if so, update the g and h scores
                    if ((currentMazeCell.getPathCost() + MOVE_COST)
                            < (cell.getPathCost())) {
                        openCells.remove(cell);
                        cell.setHeuristicCost(position.getDistance(goal));
                        cell.setPathCost(currentMazeCell.getPathCost() + MOVE_COST);
                        openCells.add(cell);
                        mazeCellToParent.remove(cell);
                        mazeCellToParent.put(cell, currentMazeCell);
                    }
                }
            }
        }
        while (!openCells.isEmpty());

        return maze;
    }
 }
	package Maze;

	import java.util.*;

	/*
	Learned about the A* algorithm from many sources including
	https://www.raywenderlich.com/3016-introduction-to-a-pathfinding - strategy adopted from this post
	http://csis.pace.edu/~benjamin/teaching/cs627/webfiles/Astar.pdf
	*/


	public class MazeSolver{

	private static final int MOVE_COST = 1;
	private static boolean mazeSolved = false;
	private static Map<MazeCell, MazeCell> mazeCellToParent = new HashMap<MazeCell, MazeCell>();

	private MazeSolver() {
	}

	private static Maze drawPath(final Maze maze) {
	Position goal = maze.getGoal();
	MazeCell goalCell = maze.getCell(goal);

	Position start = maze.getStart();
	MazeCell startingCell = maze.getCell(start);

	// update the maze to show the path, if the maze is solve-able
	if (mazeSolved) {
	int movesFromStartToGoal = 1;
	MazeCell currentCell = mazeCellToParent.get(goalCell);
	currentCell.setCellInfo(CellInfo.PATH);
	MazeCell previousCell = currentCell;

	while (currentCell != startingCell) {
	movesFromStartToGoal +=1;
	currentCell = mazeCellToParent.get(previousCell);

	// mark the cell with character representing the path
	currentCell.setCellInfo(CellInfo.PATH);
	previousCell = currentCell;
	}

	System.out.println("Moves from start to goal: " + movesFromStartToGoal);
	}
	return maze;
	}

	public static Maze solve(final Maze maze) {

	Set<MazeCell> closedCells = new HashSet<MazeCell>();
	Map<MazeCell, Position> mazeCellPositions = new HashMap<MazeCell, Position>();

	// h = best guess cost from current node to the destination - using Manhattan distance
	// g = cost from the start to the current node
	// calculate g by taking g of its parent and add movement cost to it
	// f cost = g + h

	TreeSet<MazeCell> openCells = new TreeSet<MazeCell>(
	Comparator.comparingDouble((MazeCell cell) -> (cell.getHeuristicCost() + cell.getPathCost()))
	// needed to add the comparisons below, because TreeSets cannot contain duplicate values
	// and cells with the same costs would be identified as duplicates
	.thenComparing((MazeCell cell) -> mazeCellPositions.get(cell).getCol())
	.thenComparing((MazeCell cell) -> mazeCellPositions.get(cell).getRow()));

	Position start = maze.getStart();
	MazeCell startingCell = maze.getCell(start);
	startingCell.setPathCost(0);
	mazeCellPositions.put(startingCell, start);

	Position goal = maze.getGoal();
	MazeCell goalCell = maze.getCell(goal);
	mazeCellPositions.put(goalCell, goal);

	openCells.add(startingCell);


	do {
	MazeCell currentMazeCell = openCells.first();
	Position currentPosition = mazeCellPositions.get(currentMazeCell);

	closedCells.add(currentMazeCell);
	openCells.remove(currentMazeCell);

	if (closedCells.contains(goalCell)) {
	mazeSolved = true;
	break;
	}

	List<Position> availablePositions = maze.getPathCandidates(currentPosition);
	List<Position> potentialMoves = maze.getMoves(currentPosition);
	availablePositions.addAll(potentialMoves);

	for (Position position : availablePositions) {
	MazeCell cell = maze.getCell(position);
	mazeCellPositions.put(cell, position);

	if (closedCells.contains(cell)) {
	continue;
	}
	if (!openCells.contains(cell)) {
	cell.setHeuristicCost(position.getDistance(goal));
	cell.setPathCost(currentMazeCell.getPathCost() + MOVE_COST);
	openCells.add(cell);
	mazeCellToParent.put(cell, currentMazeCell);
	} else {
	// check to see if using the current cell would give a better path
	// if so, update the g and h scores
	if ((currentMazeCell.getPathCost() + MOVE_COST)
	< (cell.getPathCost())) {
	openCells.remove(cell);
	cell.setHeuristicCost(position.getDistance(goal));
	cell.setPathCost(currentMazeCell.getPathCost() + MOVE_COST);
	openCells.add(cell);
	mazeCellToParent.remove(cell);
	mazeCellToParent.put(cell, currentMazeCell);
	}
	}
	}
	}
	while (!openCells.isEmpty());

	return maze;
	}
	}