Code covered by the BSD License  

Highlights from
Genetic Packman

image thumbnail

Genetic Packman

by

 

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

[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
packmanPic=imread('packman__05594.jpg');
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

Contact us