algorithm - Understanding a* for Java / processing -
i trying learn a* algorithm, dijkstra 1 too. yesterday found working example processing, thought coded. looked @ content of project didn't see method steps or save way target in array... here questions:
to implement such pathfinding system game pacman, there needs array, steps or way saved right?
because don't know yet how pathfinding used... how possible enemy (ghost) moves target looking @ array?
if 1 wants see code of algorithm:
int[][] findpath () { int[][]done=asarray(); done[fr][fc] = 0;int counter = 0;while (true) { boolean foundone = false; (int = 0; < copyarray.length; i++) { (int j = 0; j < copyarray[0].length; j++) { if (done[i][j] == counter) { foundone = true; if (isvalid(done, i-1, j, counter+1)) done[i-1][j] = counter + 1; if (isvalid(done, i+1, j, counter+1)) done[i+1][j] = counter + 1; if (isvalid(done, i, j-1, counter+1)) done[i][j-1] = counter + 1; if (isvalid(done, i, j+1, counter+1)) done[i][j+1] = counter + 1; } } } counter ++; if (!foundone) break; } (int = 0; < copyarray.length; i++) { (int j = 0; j < copyarray[0].length; j++) { //print ( done[i][j] + "\t" ); } println (); } return done; } arraylist getpath(int[][] flood) { if (flood[sr][sc] == -1) return null; arraylist path = new arraylist(); int cr = sr, cc = sc; while (true) { if (cr == fr && cc == fc) { return path; } if (isvalid(flood, cr-1, cc)) { if (flood[cr-1][cc] < flood[cr][cc]) { cr = cr-1; cc = cc; pvector spot = new pvector (cr, cc); path.add (spot); continue; } } if (isvalid(flood, cr+1, cc)) { if (flood[cr+1][cc] < flood[cr][cc]) { cr = cr+1; cc = cc; pvector spot = new pvector (cr, cc); path.add (spot); continue; } } if (isvalid(flood, cr, cc-1)) { if (flood[cr][cc-1] < flood[cr][cc]) { cr = cr; cc = cc-1; pvector spot = new pvector (cr, cc); path.add (spot); continue; } } if (isvalid(flood, cr, cc+1)) { if (flood[cr][cc+1] < flood[cr][cc]) { cr = cr; cc = cc+1; pvector spot = new pvector (cr, cc); path.add (spot); continue; } } } } boolean isvalid (int[][] arr, int r, int c, int count) { if (r < 0 || r >= rows) return false; if (c < 0 || c >= cols) return false; if (arr[r][c] == -2) return false; if (arr[r][c] <= count && arr[r][c] != -1) return false; return true; } boolean isvalid (int[][] arr, int r, int c) { if (r < 0 || r >= rows) return false; if (c < 0 || c >= cols) return false; if (arr[r][c] == -2) return false; return true; } int[][] asarray () { int[][] res = new int[rows][cols]; (int = 0; < rows; i++) { (int j = 0; j < cols; j++) { if (maze[i][j].type != 1) res[i][j] = -1; else res[i][j] = -2; } } return res; } int maxvalin2d (int[][] look) { int mx = 0; (int = 0; < look.length; i++) { (int j = 0; j < look[i].length; j++) { mx = look[i][j] > mx ? look[i][j] : mx; } } return mx; } int wraparound (int low, int high, int data) { return (data >= low && data <= high) ? data : (data < low ? high - (low - data - 1) : low + (data - high - 1)); //lol } main file :
int[][] testarray2 = {{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}};int[][] copyarray = new int[testarray2.length][testarray2[0].length];tile[][] maze; int rows; int cols; int lastmilli = 0; int[][] mapdata; arraylist path; int state; boolean found; boolean isneeded = false; int sr, sc, fr, fc; void setup() { size (600, 600); background (255); arraycopy(testarray2,copyarray); path = new arraylist<integer>(); maze = new tile[copyarray.length][copyarray[0].length]; (int = 0; < copyarray.length; i++) { (int j = 0; j < copyarray[0].length; j++) { // bedeuted 0 ?? if(copyarray[i][j] == 0 || copyarray[i][j] == 2) { maze[i][j] = new tile(i, j, 0); } if(copyarray[i][j] == 1 ) { maze[i][j] = new tile(i, j, 1); } } rows = copyarray.length; cols = copyarray[0].length; } state = 0; // sind die koordinaten des startes, im array sr = 4; sc = 5; // sind die koordinaten des zieles, im array fr = 8; fc = 8; found = true; nostroke(); } void draw() { background (255); if (!found && sr != -1 && sc != -1 && fr != 1 && fc != -1) { found = true; mapdata = findpath(); path = getpath(mapdata); } nostroke (); // mahlt nur das array (int = 0; < copyarray.length; i++) { (int j = 0; j < copyarray[0].length; j++) { switch(maze[i][j].type) { case 0:if (mapdata != null) { if (mapdata[i][j]==-1) { fill (255); } else { colormode (hsb); fill (160, map(mapdata[i][j], 0, maxvalin2d(mapdata), 0, 255), 255); colormode (rgb); } } else { fill (255); } break; case 1: fill (0); break; case 2: fill (0, 255, 0); break; case 3: fill (255, 0, 0); break; case 4: fill (64, 64, 255); break; } if (path != null) { (object o : path) { pvector p = (pvector)o; // zeigt den gelben weg if (p.x == && p.y == j && !(p.x == fr && p.y == fc)) { fill (255, 255, 0); println(p.x+" "+p.y); } } } rect ((width/cols) * j, (height/rows) * i, width/cols, height/rows); } } switch (state) { case 0: stroke (128); break; case 1: stroke (0, 255, 0); break; case 2: stroke (255, 0, 0); break; } nofill (); int row = (int) map (mousey, 0, height, 0, rows); int col = (int) map (mousex, 0, width, 0, cols); rect ((width/cols) * col, (height/rows) * row, width/cols, height/rows); maze[sr][sc].type = 2; maze[fr][fc].type = 3; milli(2500); found = false; for(int = 0; i< path.size();i++) { print(path.get(i)); } } void milli(int intervall) { if(millis()>lastmilli+intervall)//been @ least 200 millis { lastmilli=millis(); //wpdate last time did //println("millis running"); } } i know maybe it's lot , there 2 questions.
you're trying, , applaud that.
but you're approaching bit backwards: don't understand algorithm looking @ code first. understand algorithm starting plain old english, , last step @ (or write) code.
if want understand these algorithms, first thing need read them- wikipedia place start. when think you've understood you've read, next step write them out in own words set of steps. in english- not in code; not in pseudocode.
pretend have dumb friend has no idea a* or dijkstra is. write out list of steps friend follow in order accomplish 1 of algorithms. remember how dumb friend is, make sure each step small possible! break steps down smaller sub-steps whenever can.
seriously, in real life. use graph paper draw maze, , give maze else along list of steps you've written out. have them follow steps out of maze.
when have steps written out, that's algorithm can start thinking turning code.
if stuck on specific step, that's stack overflow for. right question still way broad give specific answer.
Comments
Post a Comment