3
\$\begingroup\$

I implemented A* Search with Array Lists following the pseudocode here.

I have been working with different algorithms on my own, and now, I am trying to optimize them so that I can run them with less code. The actual algorithm I wrote does not use a lot of code, but the setup does (creating the grid and setting the values for each successor).

Is there a more efficient way to create the grid and set the successor values? If you have any other suggestions regarding regarding refactoring, I'd be happy to hear those as well.

package AStar;

import java.util.ArrayList;

public class AStar {

    private static int[][] grid = new int[3][3];

    public static void main(String[] args) {
        ArrayList<AStarNode> path = new ArrayList<>();
        path = runAStar(6);
        printPath(path);

    }

    private static void printPath(ArrayList<AStarNode> path) {

            for (AStarNode node : path) {
                System.out.print(node.value + " ");
            }

            System.out.println();

    }

    public static ArrayList runAStar(int goal) {
        ArrayList<AStarNode> path = new ArrayList<>();

        //2 3 4
        //5 0 9
        //0 8 6
        //Test #2
        grid[0][0] = 2;
        grid[0][1] = 3;
        grid[0][2] = 4;

        //row #2
        grid[1][0] = 5;
        grid[1][1] = 0;
        grid[1][2] = 9;

        //row #3
        grid[2][0] = 0;
        grid[2][1] = 8;
        grid[2][2] = 6;


        //initilialize the open list
        ArrayList<AStarNode> openList = new ArrayList<>();
        //initialize the closed list
        ArrayList<AStarNode> closedList = new ArrayList<>();

        //put the starting node on the open list
        AStarNode startingNode = new AStarNode();
        startingNode.parent = null;
        startingNode.x = 0;
        startingNode.y = 0;
        startingNode.f = 0;
        startingNode.value = grid[0][0];

        openList.add(startingNode);

        //while the open list is not empty
        AStarNode q = new AStarNode();
        AStarNode nextQ = new AStarNode();
        ArrayList<AStarNode> openListTemp = new ArrayList();
        while (!openList.isEmpty()) {
            openListTemp = new ArrayList();
            //find the node with the least f on the open list, call it "q"
            float smallestF = Float.MAX_VALUE;
            for (AStarNode node : openList) {
                if (node.f < smallestF) {
                    smallestF = node.f;
                    q = node;
                }
            }
            //pop q off of the open list
            for (AStarNode node : openList) {
                if (node != q) {
                    openListTemp.add(node);
                }
            }
            openList = openListTemp;

            //generate q's 4 successors and set their parents to q
            ArrayList<AStarNode> successors = new ArrayList<>();

            //North Node - node above the current one
            AStarNode north = new AStarNode();
            north.x = q.x - 1;
            north.y = q.y;
            north.parent = q;
            successors.add(north);

            //South Node - node below the current one
            AStarNode south = new AStarNode();
            south.x = q.x + 1;
            south.y = q.y;
            south.parent = q;
            successors.add(south);

            //East Node - node to the right of the current one
            AStarNode east = new AStarNode();
            east.x = q.x;
            east.y = q.y - 1;
            east.parent = q;
            successors.add(east);

            //West Node - node to the left of the current one
            AStarNode west = new AStarNode();
            west.x = q.x;
            west.y = q.y + 1;
            west.parent = q;
            successors.add(west);

            int min = 0;
            int max = 2;

            //remove nodes that are outside of the grid
            ArrayList<AStarNode> temp = new ArrayList<>();
            for (AStarNode node : successors) {
                int x = node.x;
                int y = node.y;
                if (node.x < min || node.x > max || node.y < min || node.y > max || grid[x][y] == 0) {
                    //do nothing
                } else {
                    node.value = grid[x][y];
                    temp.add(node); //add all items except the invalid one to a new temp list
                }
            }
            System.out.println("Q: " + q.value);
            for (AStarNode inTemp : temp) {
                System.out.println("Successor Node: " + grid[inTemp.x][inTemp.y]);

            }
            System.out.println("___________________________");

            ArrayList<AStarNode> tempFinal1 = new ArrayList<>();
            ArrayList<AStarNode> tempFinal2 = new ArrayList<>();
            //for each successor
            for (AStarNode successor : temp) {
                //if successor is the goal, stop the search
                int x = successor.x;
                int y = successor.y;
                //if successor is the goal, stop the search
                if (grid[x][y] == goal) {
                    path.add(q);
                    path.add(successor);

                    return path;
                }
                //successor.g = q.g + distance between successor and q
                successor.g = q.g + 1;

                //successor.h = distance from goal to successor
                successor.h = 1;

                //successor.f = successor.g + successor.h
                successor.f = successor.g + successor.h;

                //if a node with the same position as successor is in the OPEN list
                //which has a lower f than successor, skip this successor
                for (AStarNode checkOpenList : openList) {
                    if ((checkOpenList.x == x && checkOpenList.y == y) && checkOpenList.f < successor.f) {
                    } else {
                        tempFinal1.add(checkOpenList);
                    }
                }

                //if a node with the same position as successor is in the CLOSED list
                //which has a lower f than successor, skip this successor
                for (AStarNode checkClosedList : closedList) {
                    if ((checkClosedList.x == x && checkClosedList.y == y) && checkClosedList.f < successor.f) {
                    } else {
                        tempFinal2.add(checkClosedList);
                    }
                }
                //otherwise, add the node to the open list
                if (successors.contains(successor)) {//if the current successor has not been removed
                    nextQ = successor;
                    openList.add(successor);
                }
            }
            //add the node and its parent to the path if the parent is not null
            if (q.parent != null) {
                path.add(q.parent);
                path.add(q);
            }
           //add q to the closed list
            closedList.add(q);
            q = nextQ;
        }
        return path;
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ For the record, it's generally written out as A-star, but A* is preferred. Your title reads as "A (Star Search)…" rather than "(A Star) Search…" \$\endgroup\$ – Nic Hartley Apr 27 '16 at 13:41
  • \$\begingroup\$ I wonder why it is so popular to limit the graph based algorithm to operate on a grid. \$\endgroup\$ – I'll add comments tomorrow Apr 27 '16 at 19:00
  • \$\begingroup\$ @I'll add comments tomorrow I guess when people think of algorithms like this, they think of games. I know I do. And many of the games function on grids...and they're easy to implement. Maybe there are others though. I personally don't know of any other ways to implement such algorithms. \$\endgroup\$ – JustBlossom Apr 28 '16 at 12:36
  • \$\begingroup\$ There was a nice article about this Fixing Pathfinding Once and For All that's now offline, but a pdf version can be found here. It not only suggests the use of graphs to do the pathplanning, but also the use of polygons as nodes, not just points. Now think about how many points on your grid could be grouped into one big quadrangle for example and treated as one node. \$\endgroup\$ – I'll add comments tomorrow Apr 28 '16 at 13:32
2
\$\begingroup\$

Declare with an interface

        ArrayList<AStarNode> path = new ArrayList<>();
        path = runAStar(6);

You don't need the new ArrayList.

    ArrayList<AStarNode> path;
    path = runAStar(6);

This would work fine and saves an unnecessary object creation.

    List<AStarNode> path = runAStar(6);

This is even better though. It declares and initializes path in the same statement.

It also changes the type of path from a rigid implementation to the flexible interface. Currently if you wanted to change from ArrayList to a different implementation, you'd have to change it in many places. If we instead make the change to use the interface, future changes to the implementation can change just one place.

Another advantage is that it makes the methods more reusable. If you have two methods that take a List, you can use them with any kind of list. If they take a specific implementation, then you have to rewrite them for each implementation.

As a general rule, it is often easier if you use the interface anywhere you can. Only specify the implementation if you have to do so. Either because the implementation has functionality that is not accessible through the interface or because you are producing a new object (e.g. new ArrayList).

Shorter initialization

        //2 3 4
        //5 0 9
        //0 8 6
        //Test #2
        grid[0][0] = 2;
        grid[0][1] = 3;
        grid[0][2] = 4;

        //row #2
        grid[1][0] = 5;
        grid[1][1] = 0;
        grid[1][2] = 9;

        //row #3
        grid[2][0] = 0;
        grid[2][1] = 8;
        grid[2][2] = 6;

You can replace this with

        grid = new int[][] {{2, 3, 4}, {5, 0, 9}, {0, 8, 6}};

More discussion.

Avoid static

    private static int[][] grid = new int[3][3];

Why is this static? That means that you can only have one AStar.

    private int[][] grid = new int[3][3];

This way we can search multiple grids.

Of course that wouldn't work if the grid is hardcoded into the runAStar method. Either pass it into the method or set it prior to the method.

Pick your data type

        //initilialize the open list
        ArrayList<AStarNode> openList = new ArrayList<>();

You put the currently open nodes in a list. As a result, insertion is quick (constant time) but finding is slow (linear time). It is often quicker to keep something in order than to put it in order. You're putting things in order on the fly. Consider using a data structure that maintains order, e.g. a TreeSet.

        NavigableSet<AStarNode> openNodes = new TreeSet<>(new AStarNodeComparator());

Personally, I'd prefer openNodes to openList as I find it more descriptive. It also works regardless of the underlying type.

Note that TreeSet may not be the best data structure either. I like it because it supports quick inserts and lookups. Maybe there's a better one though. You might have to try several to find the best one. Compare runtimes based on real data sets. Repeat the search on the same data with different data structures.

Note that you need to implement AStarNodeComparator to make this work.

        //initialize the closed list
        ArrayList<AStarNode> closedList = new ArrayList<>();

Here you do a lot of searches for particular nodes. Each node should only appear once. So we want a Set with a quick lookup. HashSet has a constant time lookup.

        Set<AStarNode> closedNodes = new HashSet<>();

Use the data structure

            openListTemp = new ArrayList();
            //find the node with the least f on the open list, call it "q"
            float smallestF = Float.MAX_VALUE;
            for (AStarNode node : openList) {
                if (node.f < smallestF) {
                    smallestF = node.f;
                    q = node;
                }
            }
            //pop q off of the open list
            for (AStarNode node : openList) {
                if (node != q) {
                    openListTemp.add(node);
                }
            }
            openList = openListTemp;

But we changed to a NavigableSet.

            q = openNodes.pollFirst();

We don't need the rest of the code. That's the power of using the right data structure.

Use helper methods

    private void addIfValid(List<AStarNode> validNodes, AStarNode node) {
        if (node.x >= min && node.x <= max && node.y >= min && node.y <= max && grid[node.x][node.y] != 0) {
            node.value = grid[node.x][node.y];
            validNodes.add(node);
        }
    }

Now rather than saying

            successors.add(north);

You could say

            addIfValid(successors, node);

Or perhaps even better

    private void addIfValid(List<AStarNode> validNodes, int x, int y, AStarNode parent) {
        if (x < 0 || x >= grid.length || y < 0 || y > grid[x].length || grid[x][y] == 0) {
            return;
        }

        AStarNode node = new AStarNode();

        node.x = x;
        node.y = y;
        node.parent = parent;
        node.value = grid[x][y];

        validNodes.add(node);
    }

Which would allow you to replace

            //West Node - node to the left of the current one
            AStarNode west = new AStarNode();
            west.x = q.x;
            west.y = q.y + 1;
            west.parent = q;
            successors.add(west);

with

            addIfValid(successors, q.x, q.y + 1, q);

and would eliminate

            int min = 0;
            int max = 2;

            //remove nodes that are outside of the grid
            ArrayList<AStarNode> temp = new ArrayList<>();
            for (AStarNode node : successors) {
                int x = node.x;
                int y = node.y;
                if (node.x < min || node.x > max || node.y < min || node.y > max || grid[x][y] == 0) {
                    //do nothing
                } else {
                    node.value = grid[x][y];
                    temp.add(node); //add all items except the invalid one to a new temp list
                }
            }
\$\endgroup\$
  • \$\begingroup\$ Wow! Thank you so much for taking the time to give such a thorough answer. Everything makes a lot of sense. It seems like I especially have a lot of work to do regarding handling data structures. \$\endgroup\$ – JustBlossom Apr 28 '16 at 12:32

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.