Implementing A Star algorithm on 2d array

Question

I am required to code a snake game with AI for a project. I am having trouble coding a shortest path algorithm implemented on a 50x50 2d array. I have written code for the AStar pathfinding algorithm (see code below) but it doesn't seem to work. Can someone please help me correct my code, and also can someone help me to code the Dijktra's algorithm as I am struggling to code it for a 2d array. It is worthwhile mentioning that the shortest path algorithm is for my snake to find the shortest path to get to an apple on the 2d board. Hope someone can help. Just to make my question more clear: my problem is that I need to find the shortest path between two points on a 2d array, as I am a beginner in coding I need help to code an algorithm to find the shortest path between the initial point and end point, such as Dijktra's or AStar.

        //implementing a*
public int manhattenDistance(Point current, Point goal){
    return Math.abs(current.getX()-goal.getX())+Math.abs(current.getY()-goal.getY());
}
public ArrayList<Point> aStar(Point myHead, Point apple){
    ArrayList<Point> closedSer=new ArrayList<>();
    ArrayList<Point> openSet=new ArrayList<>();
    openSet.add(myHead);
    ArrayList<Point> cameFrom=new ArrayList<>();

    int[][] gscore=new int[50][50];
    for(int i=0;i<gscore.length;i++){
        for(int j=0;j<gscore.length;j++)
            gscore[i][j]=Integer.MAX_VALUE;
    }
    gscore[myHead.getX()][myHead.getY()]=0;

    int[][] fscore=new int[50][50];
    for(int i=0;i<fscore.length;i++){
        for(int j=0;j<fscore.length;j++)
            fscore[i][j]=Integer.MAX_VALUE;
    }
    fscore[myHead.getX()][myHead.getY()]=manhattenDistance(myHead,apple);

    while(!openSet.isEmpty()){
        Point current; int[] fscores=new int[openSet.size()];
        for (int i=0;i<openSet.size();i++){
            Point p=openSet.get(i);
            fscores[i]=manhattenDistance(p,apple);
        }int min=fscores[0], index=openSet.size();
        for(int i=0;i<fscores.length-1;i++){
            if(fscores[i]<fscores[i+1]) {
                min = fscores[i];
                index = i;
            }if(fscores[i+1]<min){
                min=fscores[i+1]; index=i+1;
            }
        }
        current=openSet.get(index-1);
        if(current==apple) return cameFrom;//.toArray(new Point[cameFrom.size()]);// reconstructpath(cameFrom,current);
        openSet.remove(index-1);
        closedSer.add(current);

        Point[] currentNeighbourstemp=current.getNeighbours();
        ArrayList<Point> currentNeighbours=new ArrayList<>();
        for(Point n:currentNeighbourstemp)
                if(isOnBoard(n)) currentNeighbours.add(n);
        /*for(int i=0;i<currentNeighbours.length;i++){
            for(int j=0; j<openSet.size();j++)
                if(currentNeighbours[i]==openSet.get(j)) continue;;
        }*/

        for (Point neighbour:currentNeighbours){
            Double tentative_gscore=gscore[neighbour.getX()][neighbour.getY()]+distanceBetween(neighbour,current);
            boolean in=false;
            for(int i=0;i<openSet.size();i++){//checking if in oppenset
                if(neighbour==openSet.get(i)) in=true;
            }
            if(!in) openSet.add(neighbour);
            else if(tentative_gscore>=gscore[neighbour.getX()][neighbour.getY()]) continue;
            gscore[neighbour.getX()][neighbour.getY()]=tentative_gscore.intValue();
            fscore[neighbour.getX()][neighbour.getY()]=gscore[neighbour.getX()][neighbour.getY()]+manhattenDistance(neighbour,apple);
        }
    }
    return cameFrom;//.toArray(new Point[cameFrom.size()]);
}

public Double distanceBetween(Point a,Point b){
    return Math.sqrt((b.getX()-a.getX())*(b.getX()-a.getX())+(b.getY()-a.getY())*(b.getY()-a.getY()));
}
public static float invSqrt(float x) {
    float xhalf=0.5f*x;
    int i=Float.floatToIntBits(x);
    i=0x5f3759df-(i>>1);
    x=Float.intBitsToFloat(i);
    x=x*(1.5f-xhalf*x*x);
    return x;
}
public float gravityDistance(Point that,Point th){
    if(this.equals(that)) return Float.MAX_VALUE;
    return 20.0f*invSqrt(Math.abs(th.x-that.x)+Math.abs(th.y-that.y));
}

You should leave a space before and after every symbol (`+-=/*...`) — Bálint, Sep 29 '16 at 15:31
You need to make your question much clearer in order to get a good answer. Provide a clear question and your answers will be much more helpful to you. — SuperHanz98, Sep 29 '16 at 15:43
Possible duplicate of [Shortest Path Dijkstra Java](http://stackoverflow.com/questions/35733833/shortest-path-dijkstra-java) — Aditya Varma, Sep 29 '16 at 16:30
here something to compare with (but it is in C++) [How to speed up A* algorithm at large spatial scales?](http://stackoverflow.com/a/23779490/2521214) — Spektre, Sep 30 '16 at 07:20
Hi I am a beginner to coding shortest paths, I have added a bit more explanation to my question — amine, Sep 30 '16 at 07:39
1. Define trouble. What is your current output, where is the algorithm failing? Don't just ask for us to do your work, show what you've done already and where specifically you are getting stuck. 2. Solve a simple use case on paper, so you understand how A* works, and then write a simple test-case to debug your current implementation, both A* and Dijkstra are well-documented, you should be able to trnaslate the pseudocode yourself, seeing as you've done most of that already. 3. As for Dijkstra, it can be seen as a special case of A* with the heuristic function returning zero for every node. — Samuel Huylebroeck, Sep 30 '16 at 07:53
The current output is blank. I tried to run the code on a set array giving it a start point and end point, and it returns nothing. Also as the return value should be an array I tried getting the size of the array but it still returns nothing. — amine, Sep 30 '16 at 08:01

Bakhtiar Hasan · Accepted Answer · 2016-09-30T16:00:38.080

Here's a JAVA implementation of Dijkstra’s shortest path algorithm:

// A Java program for Dijkstra's single source shortest path algorithm.
// The program is for adjacency matrix representation of the graph.

class ShortestPath
{
    /* A utility function to find the vertex with minimum distance value,
       from the set of vertexes not yet included in shortest path tree */
    static final int V = 9;
    int minDistance(int dist[], boolean sptSet[])
    {
        // Initialize min value
        int min = Integer.MAX_VALUE, min_index = -1;

        for(int v = 0; v < V; v++)
        {
            if(sptSet[v] == false && dist[v] <= min)
            {
                min = dist[v];
                min_index = v;
            }
        }
        return min_index;
    }

    // A utility function to print the constructed distance array
    void printSolution(int dist[], int n)
    {
        System.out.println("Vertex    Distance from Source");
        for(int i = 0; i < V; i++)
            System.out.println(i+" \t\t "+dist[i]);
    }

    /* Function that implements Dijkstra's single source shortest path
       algorithm for a graph represented using adjacency matrix
       representation */
    void dijkstra(int graph[][], int src)
    {
        int dist[] = new int[V];  /* The output array, dist[i] will hold
                                     the shortest distance from src to i */
        /* sptSet[i] will be true if vertex i is included in shortest
           path tree or shortest distance from src to i is finalized */
        Boolean sptSet[] = new Boolean[V];

        for(int i = 0; i < V; i++)
        {
            dist[i] = Integer.MAX_VALUE;
            sptSet[i] = false;
        }

        // Distance of source vertex from itself is always 0
        dist[src] = 0;

        //Find shortest path for all vertexes
        for(int count = 0; count < V-1; count++)
        {
            /* Pick the minimum distance vertex from the set of vertexes
               not yet processed. u is always equal to src in first
               iteration. */
            int u = minDistance(dist, sptSet);

            // Mark the picked vertex as processed
            sptSet[u] = true;

            /* Update dist value of the adjacent vertexes of the
               picked vertex. */
            for(int v = 0; v < V; v++)
            {
                /* Update dist[v] only if it is not in sptSet, there is an
                   edge from u to v, and total weight of path from src to
                   v through u is smaller than current value of dist[v] */
                   if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX 
                                   && dist[u]+graph[u][v] < dist[v])
                        dist[v] = dist[u] + graph[u][v];
            }
        }

        // print the constructed distance array
        printSolution(dist, V);
    }
    public static void main(String[] args)
    {
        // Create an example graph
        int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0},
                                    {4, 0, 8, 0, 0, 0, 0, 11, 0},
                                    {0, 0, 7, 0, 9, 14, 0, 0, 0},
                                    {0, 0, 0, 9, 0, 10, 0, 0, 0},
                                    {0, 0, 0, 9, 0, 10, 0, 0, 0},
                                    {0, 0, 4, 14, 10, 0, 2, 0, 0},
                                    {0, 0, 0, 0, 0, 2, 0, 1, 6},
                                    {8, 11, 0, 0, 0, 0, 1, 0, 7},
                                    {0, 0, 2, 0, 0, 0, 6, 7, 0}};
        ShortestPath t = new ShortestPath();
        t.dijkstra(graph, 0);
    }
}

The code is pretty self explanatory. Some points to be noted:

Here I have taken a 9X9 2D array. The 9 rows represent 9 nodes in the graph. Each column represents the connection between other nodes with the respective node.
A non-zero value in graph[i][j] position represents that there is a connection between i and j. And the value represents the cost of going from i to j.
A zero in graph[i][j] position means i and j are not connected.
src represents the source from where distances to all the other points will be calculated.
Remember that, your grid represents a graph, where the vertexes/nodes are the cells and edges are the adjacent cells.

Hope this helps! Let me know if you face any problem understanding the algorithm. Good luck!

Thank you very much for your help. I only don't understand two things in your implementation. the first is the second parameter of the dijkstra function, I know you explained it above, but does it represent the node I am starting at in graph[i][j]? The second thing is the inner for loop (in dijkstra function), should i get all the neighbors of the current cell and add them to dist[v]? Thank you for your help — amine, Sep 30 '16 at 15:22
The second parameter represents the source node from where we will find out the distance of all other nodes. Let's say, I have nodes (1, 2, 3, 4, 5) and I want to find out the distance of 2, 3, 4, 5 from node 1. Then 1 is the source node. V represents the number of nodes. For your case, it will be 50. There was a small mistake in my code, now it's corrected. Thank you for pointing it out! — Bakhtiar Hasan, Sep 30 '16 at 15:59

Implementing A Star algorithm on 2d array

1 Answers1