title: Understanding a* for Java / processing
body: <p>I am trying to learn the a* algorithm, the Dijkstra one too. Yesterday I found a working example for processing, which I thought was easily coded. I looked at the content of the project but i didn't see any method to get the steps or to save the way to the target in an Array... 
  So here finally are my questions:</p>
  
  <ol>
  <li><p>To implement such a pathfinding system into a game like pacman, there needs to be a Array, where the steps or the way will be saved right? </p></li>
  <li><p>Because I don't really know yet how pathfinding is used... How is it possible that the enemy (ghost) moves to the target by looking at the Array? </p></li>
  </ol>
  
  <p>If some one wants to see the code of the algorithm:</p>
  
  <pre><code>int[][] findPath () { int[][]done=asArray(); done[fR][fC] = 0;int counter = 0;while (true) { boolean foundOne = false; for (int i = 0; i &lt; copyArray.length; i++) { for (int j = 0; j &lt; 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; } for (int i = 0; i &lt; copyArray.length; i++) { for (int j = 0; j &lt; 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 &amp;&amp; cC == fC) { return path; } if (isValid(flood, cR-1, cC)) { if (flood[cR-1][cC] &lt; 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] &lt; 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] &lt; 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] &lt; 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 &lt; 0 || r &gt;= rows) return false; if (c &lt; 0 || c &gt;= cols) return false; if (arr[r][c] == -2) return false; if (arr[r][c] &lt;= count &amp;&amp; arr[r][c] != -1) return false; return true; } boolean isValid (int[][] arr, int r, int c) { if (r &lt; 0 || r &gt;= rows) return false; if (c &lt; 0 || c &gt;= cols) return false; if (arr[r][c] == -2) return false; return true; } int[][] asArray () { int[][] res = new int[rows][cols]; for (int i = 0; i &lt; rows; i++) { for (int j = 0; j &lt; 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; for (int i = 0; i &lt; look.length; i++) { for (int j = 0; j &lt; look[i].length; j++) { mx = look[i][j] &gt; mx ? look[i][j] : mx; } } return mx; } int wrapAround (int low, int high, int data) { return (data &gt;= low &amp;&amp; data &lt;= high) ? data : (data &lt; low ? high - (low - data - 1) : low + (data - high - 1)); //LOL } 
  </code></pre>
  
  <p>Main File :</p>
  
  <pre><code>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&lt;Integer&gt;(); maze = new Tile[copyArray.length][copyArray[0].length]; for (int i = 0; i &lt; copyArray.length; i++) { for (int j = 0; j &lt; copyArray[0].length; j++) { // was 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 &amp;&amp; sR != -1 &amp;&amp; sC != -1 &amp;&amp; fR != 1 &amp;&amp; fC != -1) { found = true; mapData = findPath(); path = getPath(mapData); } noStroke (); // mahlt nur das array for (int i = 0; i &lt; copyArray.length; i++) { for (int j = 0; j &lt; 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) { for (Object o : path) { PVector p = (PVector)o; // zeigt den gelben weg an if (p.x == i &amp;&amp; p.y == j &amp;&amp; !(p.x == fR &amp;&amp; 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 i = 0; i&lt; path.size();i++) { print(path.get(i)); } } void milli(int intervall) { if(millis()&gt;lastMilli+intervall)//been at least 200 millis { lastMilli=millis(); //wpdate the last time we did anything //println("Millis is Running"); } }
  </code></pre>
  
  <p>I know maybe it's a lot and that there are 2 questions.</p>