2
\$\begingroup\$

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()) {
        nodeList.add(start);
        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);
            neighbors.add(node1);
            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);
            neighbors.add(node2);
            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());
            neighbors.add(node3);
            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() );
            neighbors.add(node4);
            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>();

    pathList.add(fromGoal);
    Node currentNode = null;

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

        currentNode = pathList.get(pathList.size() - 1);
        Node n = getNeighbor(currentNode);
        pathList.add(n);
        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]);
        possibleNeighbors.add(n);
    }

    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]);
        possibleNeighbors.add(n);
    }

    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()]);
        possibleNeighbors.add(n);
    }

    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()]);
        possibleNeighbors.add(n);
    }

    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.

\$\endgroup\$
2
\$\begingroup\$
  • 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.

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot for your tips. I have improved my program. \$\endgroup\$ – Marten Jul 8 '18 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.