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.
Advertisement
Answer
I just looked at the wikipedia article on Dijkstra’s Algorithm.
- Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
- 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.
- 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.
- 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.
- If the unvisited set is empty, then stop. The algorithm has finished.
- 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.