Algorithm to find positions in a game board i can move to

Question

The problem i have goes as follows (simplified):

• I have a board, represented as a matrix of n x m squares (n might equal m)
  
• In it, there are p game pieces
  
• Each game piece has a pre-defined speed, which is how many steps it can take in it's turn
  
• Pieces can't overlap
  
• 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)
  

So, given a game piece in a certain [i,j] position in my game board, i want to find out:
a) All the places it can move to, with it's speed
b) The path to a certain [k,l] position in the board

Having a) solved, b) is almost trivial. Currently the algorithm i'm using goes as follows, assuming a language where arrays of size n go from 0 to n-1:

• 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])
  
• 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])
  
• 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])
  
• 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.

An example:
P are pieces, W are walls, E are empty cells which require no extra movement, X are cells which require 1 extra movement to be crossed.

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

The first matrix:

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 

The second matrix:

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

The sum:

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  

Since [0,0] is not 2+1+1, i correct it: The sum:

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  

Since [0,1] is not 2+1+0, i correct it: The sum:

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

Since [0,2] is not 2+1+1, i correct it: The sum:

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

Which one is the correct answer?
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 a).

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.

Answer 1

A-star is a standard algorithm to determine shortest path give obstacles on a 2d board and cost per square of moving. You can also use it to test if a specific move is valid, but to actually generate all valid moves I would simply start ay the start position, move in each direction by one square mark which squares are valid and then repeat from each of your new places making sure not to visit the same square again. It will be a recursive algorithm calling itself at most 4 times on each call and will generate you valid moves efficiently. If there are constraints like how many squares you can move at once with different costs just pass the running total of how far you've come for each square.