title: Algorithm to find positions in a game board i can move to
body: <p>The problem i have goes as follows (simplified):<br></p>
  
  <ul>
  <li>I have a board, represented as a matrix of n x m squares (n might equal m)<br></li>
  <li>In it, there are <strong>p</strong> game pieces<br></li>
  <li>Each game piece has a pre-defined speed, which is how many steps it can take in it's turn<br></li>
  <li>Pieces can't overlap<br></li>
  <li>There are three types of cells: those which don't require extra movements to be crossed (you loose 0 extra speed when going through), those which require 1 extra movement to be crossed and some  which you simply can't get through (like a wall)<br></li>
  </ul>
  
  <p>So, given a game piece in a certain <code>[i,j]</code> position in my game board, i want to find out:<br>
  <strong>a)</strong> All the places it can move to, with it's speed<br>
  <strong>b)</strong> The path to a certain <code>[k,l]</code> position in the board<br></p>
  
  <p>Having a) solved, b) is almost trivial.
  Currently the algorithm i'm using goes as follows, assuming a language where arrays of size <code>n</code> go from <code>0</code> to <code>n-1</code>:</p>
  
  <ul>
  <li>Create a sqaure matrix of speed*2+1 size which represents the cost of moving as if all cells had no extra cost to be crossed (the piece is on the position [speed, speed])<br></li>
  <li>Create another square matrix of speed*2+1 size which has the extra costs of each cell (those which can't be crossed because either it's a wall or there is another piece in it has a value of infinite)(the piece is on the position [speed, speed])<br></li>
  <li>Create another square matrix of speed*2+1 size which is the sum of the former two(the piece is on the position [speed, speed])<br></li>
  <li>Correct the latter matrix making sure the value of each cell is: the minimal cost of all the adjacent cells + 1 + the extra cost of the cell. If it isn't, i correct it and start with the matrix all over again.</li>
  </ul>
  
  <p>An example:<br>
  <code>P</code> are pieces, <code>W</code> are walls, <code>E</code> are empty cells which require no extra movement, <code>X</code> are cells which require <strong>1</strong> extra movement to be crossed.<br></p>
  
  <pre><code>X,E,X,X,X
  X,X,X,X,X
  W,E,E,E,W
  W,E,X,E,W
  E,P,P,P,P
  </code></pre>
  
  <p>The first matrix:    </p>
  
  <pre><code>2,2,2,2,2    
  2,1,1,1,2    
  2,1,0,1,2    
  2,1,1,1,2    
  2,2,2,2,2 
  </code></pre>
  
  <p>The second matrix:    </p>
  
  <pre><code>1,0,1,inf,1    
  1,1,1,1,1    
  inf,0,0,0,inf    
  inf,0,1,0,inf    
  0,inf,inf,inf,inf
  </code></pre>
  
  <p>The sum:    </p>
  
  <pre><code>3,2,3,3,3    
  3,2,2,2,3    
  inf,1,0,1,inf    
  inf,1,2,1,inf    
  inf,inf,inf,inf,inf  
  </code></pre>
  
  <p>Since <code>[0,0]</code> is not <code>2+1+1</code>, i correct it:
  The sum:    </p>
  
  <pre><code>4,2,3,3,3    
  3,2,2,2,3    
  inf,1,0,1,inf    
  inf,1,2,1,inf    
  inf,inf,inf,inf,inf  
  </code></pre>
  
  <p>Since <code>[0,1]</code> is not <code>2+1+0</code>, i correct it:
  The sum:    </p>
  
  <pre><code>4,3,3,3,3    
  3,2,2,2,3    
  inf,1,0,1,inf    
  inf,1,2,1,inf    
  inf,inf,inf,inf,inf
  </code></pre>
  
  <p>Since <code>[0,2]</code> is not <code>2+1+1</code>, i correct it:
  The sum:    </p>
  
  <pre><code>4,2,4,3,3    
  3,2,2,2,3    
  inf,1,0,1,inf    
  inf,1,2,1,inf    
  inf,inf,inf,inf,inf
  </code></pre>
  
  <p>Which one is the correct answer?<br>
  What I want to know is if this problem has a name I can search it by (couldn't find anything) or if anybody can tell me how to solve the point <strong>a)</strong>. </p>
  
  <p>Note that I want the optimal solution, so I went with a dynamic programming algorithm. Might random walkers be better? AFAIK, this solution is not failing (yet), but I have no proof of correctness for it, and I want to be sure it works.</p>