Shortest path navigation across a grid using Best First Search

The code below is an implementation of the Best First Search algorithm for navigation of the shortest path across a 2D NxN matrix. As a heuristic for the search I use the standard distance formula. The matrix is generated from a text file passed in as a command line argument,where the first line is the size N of and each subsequent line represents a row. For example,

5
.+..g
.....
.....
.+...
i+...

The walls are represented as + and both i and g represent the start and goal positions respectively. Navigation can only be done in four directions, up, down, left, and right. I first parse the file and create a matrix of Node objects

import java.util.*;

public class Node {

    double cost;
    int type;
    int x;
    int y;
    ArrayList neighbors = new ArrayList<>();
    Node parent = null;
    boolean inPath = false;

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

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

    public void setX(int n) { this.x = n; }

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

    public void setY(int n) { this.y = n; }

    public double getCost() { return this.cost; }

    public void setCost(double n) { this.cost= n; }

    public void setType(int n) { this.type = n; }

    public int getType() { return this.type; }

    public void addNeighbor(Node n) {
        if(n.getType() != 3) {//check for not adding walls as neighbor=
            neighbors.add(n);
        }
    }
    public boolean isEqual(Node n2)
    {
        if(this.type == n2.getType()) { return true; }

        else return false;
    }
    public ArrayList getNeighbors() { return neighbors; }

    public Node getParent(){ return parent; }

    public void setParent(Node n) { parent = n; }

    public boolean getPath(){ return inPath; }
    public void setPath(){ inPath = true; }

}

to represent the + walls, i the initial position, g the goal position, and . the open spots.

```
i

High-level reusable or purpose-built?

You wrote Strategy like a high-level, all purpose Dijkstra Pathfinder (works on nodes, which can be arbitrarily far, but your grid only allows 4-connected neighbours), which even uses an external Comparator for increased versatility.

You wrote Node like generic graph representation (it has a List of neighbours etc. but your grid only allows 4).

However Strategy uses intimate knowledge of Node: it knows it's in a grid. But Strategy does not need the grid to solve the problem (it uses getNeighbours()), it only needs it for printing the map... Which a Strategy shouldn't know how to do!

In the other hand you allow arbitrary distance in evaluate() function, but it only ever return 1...

Right now it's all entangled.

You need to decide what you want:

• Make a more integrated and efficient solution which leverages the knowlegdge of the grid structure

• Make a more high-level solver which offloads intimate logic to its Node function. With the right hooks, this can stil be made quite efficient (leaving the door open for high-level optimization like switching to A-start without even altering the underlying application at all), but above all, reusable

Since this is Code Review, I can weigh in and say: you will want the latter, and split Strategy further away from Node class. I think you need a Node abstract class for the Strategy, and GridNode class for your grid application.

Tip: Use Java's package. Put Strategy in its own package like algo.pathfinding. Add an abstract Node class to that package, make it completely unaware of its grid structure. Then gather the grid-related stuff in its own separate package like game.grid. Using this, it'll be much easier to pull off a well-designed API.

Remove the printing from the Strategy

It has nothing to do there. Let Strategy return a List as path, then pass that path with the grid to a PathPrinter class.

Performance

• Drop the sqrt. If you override Node's distance function using GridNode, you can (and should) use manahttan. If you know the ceels are adjasent, return always 1.

• Use switch when checking cell contents: this is faster, and less error-prone.

Ease of use

• Store the grid as a 2d array of enums. USing enums is more powerful than String, char or ints, and the switch is more powerful (IDE auto-checks missing cases etc.)

StackExchange Code Review Q#122525, answer score: 2