# Java Pathfinding Lee Algorithm

For my Pacman game i need to implement a pathfinding algorithm. I decide to do it with the Lee Algorithm, because in my opinion it's easier to understand than e.g. A* Star algorithm.
I tried to implement it as explained on Wikipedia(https://en.wikipedia.org/wiki/Lee_algorithm)

My output looks like this, O stands for Obstacle and 0 are the path:

Path exists
Shortest Path:
5 4
4 4
3 4
3 3
3 2
2 2
2 1
2 0
1 0
0 0

0 O 1 1 1 1 1
0 1 1 O 1 1 1
0 0 0 O 1 1 1
1 O 0 0 0 1 1
1 O 1 O 0 1 1
1 1 1 O 0 1 1
1 1 1 1 1 1 1


Node.java

class Node {

private int x;
private int y;
private int value;

public Node(int x, int y) {
this.x = x;
this.y = y;
}

public Node(int x, int y, int value) {
this.x = x;
this.y = y;
this.value = value;
}

public int getX() {
return this.x;
}

public int getY() {
return this.y;
}

public int getValue() {
return this.value;
}

public void setValue(int value) {
this.value = value;
}

public boolean equals(Node n) {
if (this.x == n.x && this.y == n.y) {
return true;
}
return false;
}

public String toString() {
return this.x + " " + this.y;
}
}


LeeAlgorithm.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class LeeAlgorithm {

private final int matrixWidth = 7, matrixHeight = 7;
private int matrix[][] = new int[matrixWidth][matrixHeight];
private boolean matrixVisited[][] = new boolean[matrixWidth][matrixHeight];
private ArrayList<Node> nodeList = new ArrayList<Node>();
private final int MAXITERATIONS = 1000;
private final int OBSTACLE = -1;

/*
find the shortest path between start and goal

*/

public LeeAlgorithm() {
matrix[4][1]=OBSTACLE; matrixVisited[4][1]=true;
matrix[3][1]=OBSTACLE; matrixVisited[3][1]=true;
matrix[2][3]=OBSTACLE; matrixVisited[2][3]=true;
matrix[4][3]=OBSTACLE; matrixVisited[4][3]=true;
matrix[5][3]=OBSTACLE; matrixVisited[5][3]=true;
//matrix[1][0]=OBSTACLE; matrixVisited[1][0]=true; no path
matrix[0][1]=OBSTACLE; matrixVisited[0][1]=true;
}

private ArrayList<Node> findPath(Node start, Node goal) {

if (nodeList.isEmpty()) {
matrixVisited[start.getX()][start.getY()] = true;
}

for (int i = 1; i < MAXITERATIONS; i++) {

nodeList = markNeighbors(nodeList, i);

if (matrix[goal.getX()][goal.getY()] != 0) {
System.out.println("Path exists");
break;
}

if (i == MAXITERATIONS - 1) {
System.out.println("No Path exists");
System.exit(0);
}
}

ArrayList<Node> pathList = backtraceFromGoal(goal, start);

return pathList;
}

/*
First step

mark all unlabeled neighbors of points which are marked with i, with i+1
*/

private ArrayList<Node> markNeighbors(ArrayList<Node> neighborList, int iteration) {

ArrayList<Node> neighbors = new ArrayList<Node>();

for (Node node : neighborList) {

if (node.getY() + 1 < matrix.length && matrixVisited[node.getX()][node.getY() + 1] == false) {

Node node1 = new Node(node.getX(), node.getY() + 1);
matrix[node.getX()][node.getY() + 1] = iteration;
matrixVisited[node.getX()][node.getY() + 1] = true;
}

if (node.getY() >= 1 && matrixVisited[node.getX()][node.getY() - 1] == false) {

Node node2 = new Node(node.getX(), node.getY() - 1);
matrix[node.getX()][node.getY() - 1] = iteration;
matrixVisited[node.getX()][node.getY() - 1] = true;
}

if (node.getX() + 1 < matrix.length && matrixVisited[node.getX() + 1][node.getY()] == false) {

Node node3 = new Node(node.getX() + 1, node.getY());
matrix[node.getX() + 1][node.getY()] = iteration;
matrixVisited[node.getX() + 1][node.getY()] = true;
}

if (node.getX() >= 1 && matrixVisited[node.getX() - 1][node.getY()] == false) {

Node node4 = new Node(node.getX()-1, node.getY() );
matrix[node.getX() - 1][node.getY()] = iteration;
matrixVisited[node.getX() - 1][node.getY()] = true;
}
}
return neighbors;
}

/*
Second step

from goal Node go to next node that has a lower mark than the current node
add this node to path until start Node is reached
*/

private ArrayList<Node> backtraceFromGoal(Node fromGoal, Node toStart) {

ArrayList<Node> pathList = new ArrayList<Node>();

Node currentNode = null;

while (!pathList.get(pathList.size() - 1).equals(toStart)) {

currentNode = pathList.get(pathList.size() - 1);
Node n = getNeighbor(currentNode);
n = currentNode;
}
return pathList;
}

/*
get Neighbor of node with smallest matrix value, todo shuffle
*/

private Node getNeighbor(Node node) {

ArrayList<Node> possibleNeighbors = new ArrayList<Node>();

if (node.getY() + 1 < matrix.length && matrixVisited[node.getX()][node.getY() + 1] == true &&
matrix[node.getX()][node.getY() + 1]!=OBSTACLE) {

Node n = new Node(node.getX(), node.getY() + 1, matrix[node.getX()][node.getY() + 1]);
}

if (node.getY() >= 1 && matrixVisited[node.getX()][node.getY() - 1] == true &&
matrix[node.getX()][node.getY() -1 ]!=OBSTACLE) {

Node n = new Node(node.getX(), node.getY() - 1, matrix[node.getX()][node.getY() - 1]);
}

if (node.getX() + 1 < matrix.length && matrixVisited[node.getX() + 1][node.getY()] == true &&
matrix[node.getX() + 1][node.getY()]!=OBSTACLE) {

Node n = new Node(node.getX() + 1, node.getY(), matrix[node.getX() + 1][node.getY()]);
}

if (node.getX() >= 1 && matrixVisited[node.getX() - 1][node.getY()] == true &&
matrix[node.getX() - 1][node.getY()]!=OBSTACLE) {

Node n = new Node(node.getX() - 1, node.getY(), matrix[node.getX() - 1][node.getY()]);
}

Collections.sort(possibleNeighbors, new Comparator<Node>() {
@Override
public int compare(Node first, Node second) {
return first.getValue() - second.getValue();
}
});

Node n = possibleNeighbors.remove(0);

return n;
}

private void printSolution(ArrayList<Node> output) {

System.out.println("Shortest Path:");
for (Node n : output) {
int x=n.getX();
int y=n.getY();
System.out.println(n.toString());
matrix[x][y]=0;
}

System.out.println("");

for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {

if(matrix[i][j]!=0 && matrix[i][j]!=OBSTACLE) {
matrix[i][j]=1;
}

if(matrixVisited[i][j]==false) {
matrix[i][j]=1;
}

if(matrix[i][j]==OBSTACLE) {
System.out.print("O ");
}

else {

System.out.print(matrix[i][j]+" ");
}
}
System.out.println("");
}
}

public static void main(String[] args) {
LeeAlgorithm l = new LeeAlgorithm();
ArrayList<Node> output = l.findPath(new Node(0, 0), new Node(5, 4));

l.printSolution(output);

}
}


Any Suggestions and improvements would be appreciated.

• A standard trick to avoid testing for node.getY() + 1 < matrix.length etc is to add a border to your matrix, and initialize all nodes on the border to visited. The test reduces to just matrixVisited[node.getX()][node.getY() + 1] == false. This can also be shortened to !matrixVisited[node.getX()][node.getY() + 1].

• The Node's public getters and setters only add clutter to the code. Rather make the fields themselves public.

Correct me if I am wrong, setValue is never called.

• DRY. Instead of spelling out all four neighbors, create a helper delta array of nodes [(-1, 0), (0, -1), (0, 1), (1, 0)], and iterate over it, computing the neighbor as

        neighbor.x = node.x + delta[i].x;
neighbor.y = node.y + delta[i].y;
etc;

• MAX_ITERATION looks artificial. The loop shall end (with failure) if there is no more nodes to mark. In other words, fail when the nodeList.size() become zero.

• The semantics of nodeList, markNeighbors(), neighborList, neighbors is very unclear. I recommend to stick with the Lee algorithm's metaphor, and use names like waveFront, propagateWave() etc.

• Thanks a lot for your tips. I have improved my program. Jul 8, 2018 at 17:29