Block user from moving anywhere

Question

I have made a game which is nearly identical to Popcap's Atomica. (http://www.popcap.com/gamepopup.php?theGame=atomica)

It's almost finished, except for one important function; blocking the user from moving spheres anywhere. Like, if there is a wall of other spheres in between the sphere the user is trying to move, and the field it is trying to move it to, the user should not be able to move it.

I have stored all the fields and spheres in a multidimensional array[x-loc, y-loc] where "e" equals empty, "s" sphere, etc. I've tried running a loop through it to find out if there is a clear road between the two fields, but nothing has worked.

Can anyone please give me a hint of how I can solve this problem?

Answer 1

You need to run a path algorithm like Floyd-Warshall ... omit invalid notes and edges from your matrix (i.e. the graph you look at would be the sub graph of all nodes without a sphere) such that you create a graph of only legal moves. Then, a path algorithm like Floyd-Warshall will give you all "legal" moves.