Exercise 12, Task 5

The results for the given case are:


distmap =


3.41   3.00      0      0      0      0      0       0      0   0
3.00   2.00      0  14.82  15.23  15.64  16.05 16.46  16.87   0
   0   3.00      0  13.82  14.23  14.64  15.05   15.46  16.46   0
   0   4.00      0  12.82  13.23  13.64  14.05   15.05  16.05   0
   0   5.00      0  11.82  12.23  12.64  13.64   14.64  15.64   0
   0   6.00      0  10.82  11.23  12.23  13.23   14.23  15.23   0
   0   7.00      0   9.82  10.82  11.82  12.82   13.82  14.82   0
   0   8.00   8.41   9.41  10.41  11.41  12.41   13.41  14.41   0
   0   9.00   9.41   9.82  10.82  11.82  12.82   13.82  14.82   0
   0  10.00  10.41  10.82  11.23  12.23  13.23   14.23      0   0


route =


     9  9
     8  8
     8  7
     8  6
     8  5
     8  4
     8  3
     7  2
     6  2
     5  2
     4  2
     3  2
     2  2



map =


     0  0  1  0  0  0  0  0  0  0
     0  2  1  0  0  0  0  0  0  0
     1  2  1  0  0  0  0  0  0  0
     1  2  1  0  0  0  0  0  0  0
     1  2  1  0  0  0  0  0  0  0
     1  2  1  0  0  0  0  0  0  0
     1  2  1  0  0  0  0  0  0  0
     1  0  2  2  2  2  2  2  0  0
     1  0  0  0  0  0  0  0  2  0
     1  0  0  0  0  0  0  0  0  0

Exercise 12, Task 4

After computing the distance map with the previous function, the following one finds the minimum distance route from the start point to the final one.


function route = findroute(startcell,finalcell,distmap)
global map;
q = startcell;
cell = startcell;
d = 100000;


while(cell(1)~=finalcell(1) || cell(2)~=finalcell(2))
    n = neighbours(cell);
    for i=1:size(n,1)
        if(map(n(i,1),n(i,2))==0 && distmap(n(i,1),n(i,2))~=0 && distmap(n(i,1),n(i,2))<d)
            d = distmap(n(i,1),n(i,2));
            next = n(i,:)
        end
    end
    q = insert(next,q);
    cell = next;
end


for i=1:size(q,1)
    map(q(i,1),q(i,2))=2;
end 
map
route = q
end


The function returns the list of cells that form the route as well as the map which shows the route (represented by values of 2)

Exercise 12, Task 3

The function starts in the final point and calculates the minimum distances of the cells until it reaches the start point.

function matr = makewave(startcell,finalcell)

global map;

distmap = zeros(size(map,1),size(map,2));

distmap(finalcell(1),finalcell(2))=2;

queue = finalcell;

reached = 0;

while(size(queue,1) && reached==0)

    [crt,queue] = retrieve(queue);

    n = neighbours(crt);

    for i=1:size(n,1)

        if(map(n(i,1),n(i,2))==0)

           d = distmap(crt(1),crt(2)) + celldist(crt,n(i,:));

           if(distmap(n(i,1),n(i,2))==0) 

                distmap(n(i,1),n(i,2))= d;

                queue = insert(n(i,:),queue);

           elseif(distmap(n(i,1),n(i,2)) > d) 

                distmap(n(i,1),n(i,2)) = d;

           end

        end

        if(n(i,:)==startcell)

            reached = 1;

        end    

    end

end    

if(reached==0)

    fprintf('The wave did not reach the starting point.')

end

matr = distmap;

end

Exercise 12, Task 2

The function to find the neighbours of a cell is:

function list = neighbours(cell)
global map;
x = cell(1);
y = cell(2);


if(x==1 && y==1)
    list = [ x   y+1;
            x+1  y+1;
            x+1   y];
elseif(x==1 && y==size(map,2))
    list = [x+1   y;
             x   y-1;
            x+1  y-1];
elseif(x==1)
    list = [ x   y+1;
            x+1  y+1;
            x+1   y;
             x   y-1;
            x+1  y-1];
elseif(y==1 && x==size(map,1))
    list = [x-1  y+1;
             x   y+1;
            x-1   y];
elseif(y==1)
    list = [x-1  y+1;
             x   y+1;
            x+1  y+1;
            x-1   y;
            x+1   y];
elseif(x==size(map,1) && y==size(map,2))
    list = [x-1   y;
            x-1  y-1;
             x   y-1];
elseif(x==size(map,1))
    list = [x-1  y+1;
             x   y+1;
            x-1   y;
            x-1  y-1;
             x   y-1];
elseif(y==size(map,2))
    list = [x-1   y;
            x+1   y;
            x-1  y-1;
             x   y-1;
            x+1  y-1];
else 
    list = [x-1  y+1;
             x   y+1;
            x+1  y+1;
            x-1   y;
            x+1   y;
            x-1  y-1;
             x   y-1;
            x+1  y-1];   
end    
end


Note: Only the valid neighbours of the cell are taken, i.e. the ones that do not exceed the borders of the matrix.

Exercise 12, Task 1

To add or extract elements from a queue, the functions below were used:

function q = insert(cell,queue)
i=size(queue,1)+1;
queue(i,:)=cell;
q = queue;
end


function [val,q] = retrieve(queue)
val = queue(1,:);
q = queue(2:(size(queue,1)),:);
end