Java Maze shortest path 2d int array

Question

I am currently stuck on a project. My aim is to use Dijkstra's algorithm.

I understand that I start at point (0,0) I look at the two nodes next to the start point and then I move to the smallest first and look at the surrounding nodes. My maze is random but to make it easy to start lets say the following is my maze.

I will start at (0,0) and want to end at (9,9) the numbers are the DANGER level and we aim for the safest path not really the shortest.

I need a push to understand how to set this up. I know I need a list or a path to keep where I am and where I want to look. but I don't know how to do that in java.

import java.awt.Point;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;


public class solver {

    /**
     * @param args
     */
    public static int[][]maze;
    public static int[][]openlist;
    public static int[][]closed;
    public static int[][]copy;
    public static int danger;
    public static int size=100;
    static int Max=9;
    static int Min=0;
    public static List path = new ArrayList();
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        maze = new int[size][size];
        openlist = new int[size][size];
        closed = new int[size][size];
        copy = new int[size][size];
        filler(maze);
        copy=dijstkra();
        printer(maze);
        //printer(copy);
        EDSfAO(maze,0,0);
        printer(openlist);
        printer(copy);
    }
    private static Boolean notwall(int i, int j){

        if((i>maze.length-1)||(j>maze.length-1)||(i<0)||(j<0))
        {return false;}

        return true;}
    private static int[][] dijstkra(){


        for(int i=0;i<maze.length;i++){
            for(int j=0;j<maze.length;j++){
                copy[i][j]=100000000;
            }}
        copy[0][0]=0;
        return copy;
        }

    private static void EDSfAO(int[][] maze,int i,int j){
        int min=100000000;
        int holdx = 0;  
        int holdy = 0;
        openlist[i][j]=1;
        danger=copy[i][j];
        if(i==maze.length-1&&j==maze.length-1){

            printer(copy);
            for(holdx=0;holdx<path.size();holdx++){

                System.out.print(path.get(holdx));

            }


        }
        else{
        if(notwall(i+1,j)&&openlist[i+1][j]!=1){
            copy[i+1][j]=danger+maze[i+1][j];
        } if(notwall(i,j+1)&&openlist[i][j+1]!=1){
            copy[i][j+1]=danger+maze[i][j+1];
        } if(notwall(i,j-1)&&openlist[i][j-1]!=1){
            copy[i][j-1]=danger+maze[i][j-1];
        } if(notwall(i-1,j)&&openlist[i-1][j]!=1){
            copy[i-1][j]=danger+maze[i-1][j];
        }
        for(int x=0;x<maze.length;x++){
            for(int y=0;y<maze.length;y++){

            if(openlist[x][y]!=1){

                if(min>copy[x][y]){
                min=copy[x][y];
                holdx=x;    
                holdy=y;
                }

            }


        }}
        moveToPosition(holdx,holdy);
        }
    }


    private static void moveToPosition(int x, int y) {

            openlist[x][y]=1;
            path.add("("+x+","+y+")");
            openlist[x][y]=1;
            EDSfAO(maze,x,y);
    }

private static void printer(int[][] maze) {
        // TODO Auto-generated method stub
    for(int i=0;i<maze.length;i++){
        for(int j=0;j<maze.length;j++){
        System.out.print("["+maze[i][j]+"]");                       
        }
        System.out.println();
        }

    }

public static void filler(int[][] maze){

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

            for(int j=0;j<maze.length;j++){
            //If i=0 AND j=0 then maze[0][0]= 0(start) OR i= maze.length-1 AND j= maze.length-1 then maze[maze.length][maze.length]=0
            if((i==0 && j==0) || (i==maze.length-1 && j==maze.length-1)){

                maze[i][j]=0;   

            }else{
                maze[i][j]=Min + (int)(Math.random() * ((Max - Min) + 1));
            }
            }
            }
    }
}

The maze is connected with no walls all the boxes are rooms. I have been trying to work on this for time and I could really use a push. I have watched a lot of videos about dijstkra's algorithm I am just currently really lost.

I added a array that i keep the danger in it starts by making ever node 100000000 but the starting node (0,0) is 0.

CAN someone help me with the next steps I understand it's homework but I am running out of time and really need some pointers.

UPDATE:

OK so I have it workingish. It prints the path it takes but if it finds a better path it prints both can someone help me fix this.

Also it breaks if i do 100X100 element can someone tell me why? This is the last of the real "programming assignments". As you may expect, this will involve graphs (with a twist); but of course, there will be some problem solving involved as well. Instruction

---

Imagine a “dungeon game” where all the rooms are laid out in a perfect grid with in a square environment. Each room has a creature posing some degree of danger ranging from 0 (harmless) to 9 (avoidance would be prudent). The object is to find a path through the dungeon from start to end which minimizes the overall amount of danger.

Each room, unless at boundary, only has exists in the up, down, left, right directions (no diagonals). The entrance is at the upper-left (0,0) and the exit is at the lower right (n-1, n-1).

List all of the “rooms” which must be traversed, in the form of a path of room coordinates, from the start to finish.

For example:

(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (3,3) (4,3) (4,4)

Total danger = 11 Input

The input file will consist of 100 rows of 100 digits, 0-9. (Yes, 10,000 is be a lot of rooms, but luckily, our intrepid traveler never leaves home without a portable computer and a collection of Electronic Data-Sets for All Occasions received in last year's holiday gift exchange; it was probably re-gifted.)*

*For this assignment, you'll have to generate your own test data. This is why I don't go to these kinds of parties... Output

The program should write the output to a file (in the format illustrated above, including the "total danger" output). Thanks.

UPDATE2: i found an error in my coding I have

if(min>copy[x][y]){
                min=copy[x][y];
                holdx=x;    
                holdy=y;
                }

This will make it test every path that is there at a given point my shortest path is bigger then the other path how do I fix this?

What I am I missing? UPDATE I finished this thanks for the VERY LITTLE help.

Answer 1

You can base your solution on algorithms found in "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein, 2nd Edition. In chapter 24 they analyze "single-source shortest paths" algorithm and in 24.3 you have Dijkstra.

I will use pseudo-code here. You could replace the min-priority queue below with another data structure like a map in Java. It won't be fast but it will work and that could be a satisfactory first try. I also have a Java implementation of a min-priority queue if you want.

Say you have the maze represented by a 2D array like in your code: int[M][N] maze. The first index is the row index and the second is the column index, zero-based. Thus going from 0 to M-1 for the rows and from 0 to N-1 for the columns. The value maze[row][column] represent the danger associated with the room at (row, column). We need a convenient representation to get the weight between two rooms in the maze and to know which rooms are adjacent to a specific room.

The idea is to flatten the array and put every row side by side: row1, row2, ..., rowM. Then we can give an index i to each room. To be able to use this idea we need to convert between different type of coordinates: (row, column) -> i and i -> (row, column).

convert_to_index(row, column) ::= row * N + column
convert_to_pair(i) ::= (i div N, i modulo N)

Say SIZE is M*N, the total number of rooms in the maze.

Now we can make an adjacency matrix representing the maze with the danger values: int[SIZE][SIZE] adjacency_matrix, the first index is the FROM, the second is the TO. In a cell we find the cost or weight to go from one room to another. Note that given a specific room, there are only a few room that are adjacent to that room. The other rooms in the maze are not reachable from that room. By convention, we will use the biggest integer to indicate that and use the constant INFINITY. The other values represent danger and range from 0 to 9. The matrix will be sparse and there are techniques to optimize that.

When we have a room located at (r, c), what are the rooms adjacent to it ? We want to have a vector of indices to be used directly in our algorithm. If we don't take the maze borders into account, we have: (r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), (r+1, c) and (r+1,c+1). We could then apply convert_to_index to each of them, check they are in the range 0..SIZE-1 and initialize the matrix with that. Thus, e.g., going from (r, c) to (r-1, c-1) has a cost or danger of maze[r-1, c-1] and going from (r-1, c-1) to (r, c) has a cost of maze[r, c]. But going from (r, c) to another distant room has a cost of 10, it is unreachable and the inverse is true.

adjacent_rooms(r, c) ::=
    Given the vector [(r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), (r+1, c), (r+1,c+1)]
    Filter it by deleting pairs whose row is not in 0..M-1 or whose column is not in 0..N-1
    Then apply the function convert_to_index to each resulting pair (map operation)
    Return the result

for i in 0..SIZE-1 loop
    for j in 0..SIZE-1 loop
        adjacency_matrix[i, j] := -1
    end loop
end loop

for i in 0..SIZE-1 loop
    (current_r, current_c) := convert_to_pair(i)
    adjacent_room_indexes := adjacent_rooms(current_r, current_c)
    for j in 0..SIZE-1 loop
        if adjacency_matrix[i, j] == -1 then
            (r, c) := convert_to_pair(j)
            if i == j then adjacency_matrix[i, j] := 0
            elsif j in adjacent_room_indexes then adjacency_matrix[i, j] := maze[r, c]; adjacency_matrix[j, i] := maze[current_r, current_c]
            else adjacency_matrix[i, j] := INFINITY
        end if
    end loop
end loop

Next we need a vector estimates of shortest-path estimates (Cfr. book page 585) and a predecessors vector (Cfr. book page 584).

for i in 0..SIZE-1 loop
    predecessors[i] := NONE
    estimates[i] := INFINITY
end loop

Going from the start to the start costs 0.

estimates[0] := 0

Initialize set of vertices that belong to the MST (minimum spanning tree)

mst := empty set

The min-priority queue q is initialized

for i in 0..SIZE-1 loop
    q.add(i, estimates[i])
end loop

until q.empty? loop
    u, u_d = q.delete_min
    mst.add(u)
    (current_r, current_c) := convert_to_pair(i)
    adjacent_room_indexes := adjacent_rooms(current_r, current_c)
    for i in 0..adjacent_room_indexes.length-1 loop
        v := adjacent_room_indexes[i]
        cost = adjacency_matrix[u, v]
        if cost < q[v]
          predecessors[v] = u
          estimates[v] = c
          q[v] = c
        end
    end loop
end loop

Job is done. We have our path in predecessors with the costs in estimates.

This might be overkill and A* might be better. But I guess that using Dijkstra was a requirement of your homework. If you want to explore A*, I suggest you take a look at A* Pathfinding for Beginners and Amit’s A* Pages.

Answer 2

I went ahead and implemented the algorithm as mentioned by ccoakley. Find below the partial code to help you in the right direction:

import java.util.HashSet;
import java.util.Set;

// 1. Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
// 2. Mark all nodes unvisited. Set the initial node as current. Create a set of the unvisited nodes called the unvisited set consisting of all the nodes except the initial node.
// 3. For the current node, consider all of its unvisited neighbors and calculate their tentative distances. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6+2=8. If this distance is less than the previously recorded distance, then overwrite that distance. Even though a neighbor has been examined, it is not marked as visited at this time, and it remains in the unvisited set.
// 4. When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again; its distance recorded now is final and minimal.
// 5. If the unvisited set is empty, then stop. The algorithm has finished.
// 6. Set the unvisited node marked with the smallest tentative distance as the next "current node" and go back to step 3.
public class Dijkstra {

    class Node {
        String name;
        Integer distance = Integer.MAX_VALUE;
        boolean visited;
        Set<Edge> edges = new HashSet<Edge>();

        Node(String name) {
            this.name = name;
        }

        Edge connect(Node destination, int length) {
            Edge edge = new Edge();
            edge.length = length;
            edge.from = this;
            edge.to = destination;
            edges.add(edge);
            destination.edges.add(edge);
            return edge;
        }

        @Override
        public String toString() {
            return name;
        }
    }

    class Edge {
        int length;
        Node from;
        Node to;

        Node getNeighbor(Node origin) {
            if (from == origin) {
                return to;
            }
            else if (to == origin) {
                return from;
            }
            else {
                throw new IllegalArgumentException("This edge is not connected to node " + origin);
            }

        }

        @Override
        public String toString() {
            return String.format("%s-%s", from, to);
        }
    }

    /**
     * <pre>
     * a - b - c
     * |   |   
     * d - e   |
     * |
     * f - g - h
     * </pre>
     * 
     * @return
     */
    private Set<Node> initialize() {
        Node a = new Node("a");
        Node b = new Node("b");
        Node c = new Node("c");
        Node d = new Node("d");
        Node e = new Node("e");
        Node f = new Node("f");
        Node g = new Node("g");
        Node h = new Node("h");

        a.connect(b, 4);
        a.connect(d, 8);
        b.connect(c, 6);
        b.connect(e, 1);
        c.connect(h, 7);
        d.connect(e, 2);
        d.connect(f, 5);
        f.connect(g, 3);
        g.connect(h, 1);

        a.distance = 0;

        Set<Node> unvisited = new HashSet<Dijkstra.Node>();
        unvisited.add(a);
        unvisited.add(b);
        unvisited.add(c);
        unvisited.add(d);
        unvisited.add(e);
        unvisited.add(f);
        unvisited.add(g);
        unvisited.add(h);

        return unvisited;
    }

    private Set<Node> solve(Set<Node> unvisited) {

        Set<Node> visited = new HashSet<Node>();

        while (!unvisited.isEmpty()) {

            System.out.println(String.format("Unvisited nodes:%s", unvisited.size()));
            print(unvisited);
            Node current = findNodeWithSmallestDistance(unvisited);
            System.out.println(String.format("Current node:%s", current));
            updateNeighbors(current);
            current.visited = true;
            unvisited.remove(current);
            visited.add(current);
        }

        return visited;
    }   

    private void updateNeighbors(Node current) {

        for (Edge edge : current.edges) {    
            Node neighbor = edge.getNeighbor(current);
            if (!neighbor.visited) {
                int tentativeNeighborDistance = current.distance + edge.length;
                if (tentativeNeighborDistance < neighbor.distance) {
                    neighbor.distance = tentativeNeighborDistance;
                    System.out.println(String.format("Neighbor:%s distance:%s", neighbor, neighbor.distance));
                }
                else {
                    System.out.println(String.format("Neighbor:%s no shorter path     found", neighbor));
                }
            }
            else {
                System.out.println(String.format("Neighbor:%s already visited",     neighbor));
            }
        }
    }

    private Node findNodeWithSmallestDistance(Set<Node> nodes) {
        Node smallest = null;
        for (Node node : nodes) {
            if (smallest == null || node.distance < smallest.distance) {
                smallest = node;
            }
        }
        return smallest;
    }

    private void print(Set<Node> visited) {
        for (Node node : visited) {
            System.out.println(String.format("Node:%s has distance:%s", node, node.distance));
        }
    }

    public static void main(String[] args) {
        Dijkstra edsger = new Dijkstra();
        Set<Node> unvisited = edsger.initialize();
        Set<Node> visited = edsger.solve(unvisited);
        edsger.print(visited);
    }
}

EDIT: added the missing bits

Answer 3

I just looked at the wikipedia article on Dijkstra's Algorithm.

1. Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
2. Mark all nodes unvisited. Set the initial node as current. Create a set of the unvisited nodes called the unvisited set consisting of all the nodes except the initial node.
3. For the current node, consider all of its unvisited neighbors and calculate their tentative distances. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6+2=8. If this distance is less than the previously recorded distance, then overwrite that distance. Even though a neighbor has been examined, it is not marked as visited at this time, and it remains in the unvisited set.
4. When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again; its distance recorded now is final and minimal.
5. If the unvisited set is empty, then stop. The algorithm has finished.
6. Set the unvisited node marked with the smallest tentative distance as the next "current node" and go back to step 3.

Just approach it naively at first. Heck, treat it as "programmer's reading comprehension." In this case, the trick is mapping your 2 dimensional array to a set of graph nodes. Every node needs "a tentative distance value". Ok, your nodes are defined by their i,j value. Make something so you can get/set a tentative_distance_value given an i and j.

You need to mark if a node is visited. Same idea.

You need a "current node." Same idea, but simpler.

I know I need a list or a path to keep were. I am and were I want to look. but I don't know how to do that in java.

Technically, you don't need to maintain a path to run the algorithm. You'll have to figure out how to construct it from the results of the algorithm if you don't, but it's certainly possible.

Answer 4

Once you understand how to use Dijkstra's algorithm, you can use an ArrayList containing pairs of numbers that indicate your previous positions:

List<Point> path = new ArrayList<Point>();

You can then write a Point class that simply wraps two int primitives, x and y.

So when you move, you can use:

private void moveToPosition(int x, int y) {
    path.add(new Point(x, y));

    // Move yourself to this point
    ...
}

As for learning how to actually employ the algorithm, I think that's somewhat the point of your homework, and we don't want to spoil your fun!

The Wikipedia article on the algorithm is fairly useful, though I have a feeling your class notes will also help.

Dijkstra's algorithm on Wikipedia