Code covered by the BSD License

# Genetic Packman

### Hanan Kavitz (view profile)

A simple demonstration of Genetic Algorithm using all times favorite game.

### Editor's Notes:

This file was selected as MATLAB Central Pick of the Week

[x,fval,exitFlag]=geneticPackman(cubeSize,numOfMoves,packmanVis,greedyAndSimple)
```function [x,fval,exitFlag]=geneticPackman(cubeSize,numOfMoves,packmanVis,greedyAndSimple)
% The purpose of this demo is to 'teach' packman to find path through as many
% green tiles as posible, using a given number of moves.
% I'm using Genetic Algorithm to find the optimal path.
%
% The broader goal can be of finding an optimal path by gaining points
% from going through certain high yield tiles.
%
% As reference to how well the genetic packman can find the optimal path
% one can compare this to greedy algorithm, which usualy will be much faster but get a
% lower score, or using some other simple strategy for looking for green tiles (I used
% a simple strategy of going up and down through the coloms).
%
% inputs:
%
% cubeSize- size of the cube for the packman to move on.
%
% numOfMoves- number of allowed moves.
%
% packmanVis- if set to true will visualize the packman movements.
%
% greedyAndSimple- if set to true will compare a greedy algorithm to the
% genetic solution
%
% outputs:
%
% x- packman solution movements, at each move there are four posibilities,
%   1- packman goes up
%   2- packman goes left
%   3- packman goes down
%   4- packman goes right
%
% fval-number of collected green tiles
%
% exitFlag- the usual GA exitFlag (see 'ga' function in global optimization toolbox)
%
% example:
%
% [x,fval,exitFlag]=geneticPackman(30,100,true,false);
%
% [x,fval,exitFlag]=geneticPackman(30,150,false,false);
%
% made by Hanan Kavitz, free to use and distribute

global cubeSide
cubeSide=cubeSize;
field=(rand(cubeSize)<0.3);

if greedyAndSimple
val=greedyPackman(field,numOfMoves);
disp(['Greedy Packman finds ' num2str(val) ' green tiles'])

val=simpleMoves(field,numOfMoves);
disp(['Simply moving Packman finds ' num2str(val) ' green tiles'])
end

gaoptions=gaoptimset('CreationFcn',@createFcn,'CrossoverFcn',@crossoversinglepoint,...
'CrossoverFraction',0.8,'Generations',700,'MutationFcn',{@mutate_permutation,0.01},...
'PopulationSize',300,'PopulationType','doubleVector',...
'SelectionFcn',@selectionroulette,'StallGenLimit',700,...
'FitnessLimit',-sum(field(:)),'Vectorized','off');
if packmanVis
gaoptions=gaoptimset(gaoptions,'PlotFcn',{@gaplotbestf,@feedingPlot},'PlotInterval',10);
end
[x,fval,exitFlag]=ga(@(x)objFnc(x,cubeSize,field),numOfMoves,[],[],[],[],[],[],...
[],gaoptions);
fval=-fval;
disp(['Genetic Packman finds ',num2str(fval) ' green tiles']);

% Creation function

function pop=createFcn(NVARS,~,options)
pop=randi(4,options.PopulationSize,NVARS);

function val=objFnc(x,cubeSize,field)
global changingField
changingField=field;
xi=floor(cubeSize/2);
yi=floor(cubeSize/2);
val=0;
for i=1:size(x,2)

if x(i)==1 && yi+1<cubeSize
yi=yi+1;
end

if x(i)==2 && xi>1
xi=xi-1;
end

if x(i)==3 && yi>1
yi=yi-1;
end

if x(i)==4 && xi+1<cubeSize
xi=xi+1;
end

if field(xi,yi)
val=val-1;
field(xi,yi)=false;% food eaten!
end

end

function state = feedingPlot(~,state,flag)
global cubeSide changingField
persistent patchHandles
[~,idx]=min(state.Score);
bestSolution=state.Population(idx,:);

switch flag

case 'init'

set(gcf,'toolbar','figure');
set(gca,'xTickMode','auto','yTickMode','auto','xTick',[],'yTick',[],...
'XLimMode','manual','YLimMode','manual');
end
patchHandles=zeros(cubeSide);
for j=0:cubeSide-1
for i=0:cubeSide-1
if changingField(i+1,j+1)
patchHandles(i+1,j+1)=patch([i i i+1 i+1]/cubeSide,[j j+1 j+1 j]/cubeSide,...
[0 1 0],'EdgeColor',[1 1 1]);
else
patchHandles(i+1,j+1)=patch([i i i+1 i+1]/cubeSide,[j j+1 j+1 j]/cubeSide,...
[0 0 0],'EdgeColor',[1 1 1]);
end
end
end

plotBestPath(bestSolution,patchHandles);

function plotBestPath(bestSolution,patchHandles)
global cubeSide
hold on
if mod(cubeSide,2)==0
X=[0.5-1/cubeSide 0.5];
Y=[0.5-1/cubeSide 0.5];
else
X=[0.5-1/(2*cubeSide) 0.5+1/(2*cubeSide)];
Y=[0.5-1/(2*cubeSide) 0.5+1/(2*cubeSide)];
end
imHandle=image(packmanPic,'XData',X,'YData',Y);
i=floor(cubeSide/2);
j=i;
for ii=1:length(bestSolution)
if bestSolution(ii)==1 && j<cubeSide
Y=Y+1/cubeSide;
j=j+1;
end

if bestSolution(ii)==2 && i>1
X=X-1/cubeSide;
i=i-1;
end

if bestSolution(ii)==3 && j>1
Y=Y-1/cubeSide;
j=j-1;
end

if bestSolution(ii)==4 && i<cubeSide
X=X+1/cubeSide;
i=i+1;
end
set(imHandle,'XData',X,'YData',Y);
if mod(cubeSide,2)==0
set(patchHandles(i,j),'FaceColor',[1 0 0]);
else
set(patchHandles(i+1,j+1),'FaceColor',[1 0 0]);
end
pause(0.005);
end
delete(imHandle)
hold off
```