function mv = solver(ai,af,w)
nBlocks = length(w);
[m,n] = size(ai);
m2=m+2;
O1=-ones(1,n+2);
O2=-ones(m,1);
A=[O1;O2,ai,O2;O1];
Af=[O1;O2,af,O2;O1];
S=[m+2,n+2];
di=[m2 1 -m2 -1];
P=w;
Pf=w;
R=w;
C=w;
for i=1:nBlocks
P(i)=find(A==i);
Pf(i)=find(Af==i);
[R(i),C(i)]=ind2sub(S,Pf(i));
end
mv = [];
while any(P~=Pf)
% Pick a random block
bid = ceil(rand*nBlocks);
i=P(bid);
% Move it in a random direction
direc = ceil(rand*4);
ni=i+di(direc);
% Is it a legal move? Check for collision
if A(ni)
continue
end
% Check distance
% Get the target location
[r,c]=ind2sub(S,i);
d = (r-R(bid))^2 + (c-C(bid))^2;
[r,c]=ind2sub(S,ni);
dn = (r-R(bid))^2 + (c-C(bid))^2;
% Have we moved closer to the target location?
if (d<dn) && (rand>0.05)
continue
end
A(ni)=bid;
A(i)=0;
P(bid)=ni;
% Record the move
mv(end+1,[1 2]) = [bid direc];
end
|
