function [dRow,dCol,action,mark] = solver4(mainMap,foodMap,myAntMap,opAntMap, ...
	myScentMap,opScentMap,myDeathMap,opDeathMap, timeStep) %#ok

% Konstanten
nSight             = 5;
myInd              = 13;
actionFight        = -1;
actionIdle         =  0;
actionCarry        =  1;
maxMarkPerAnt      = 100;

indMatrix          = reshape(1:nSight*nSight, nSight, nSight);
otherIndex         = indMatrix ~= myInd;
neighborIndex      = [ 7  8  9 14 19 18 17 12];

% Parameter
maxOwnAntHillScent        = 501;
scentStep                 = 20;
keepScentFactor           = 1.2;
nrOfCarriersPerFood       = 3.0;
nrOfFightersPerOpponent   = 1.5;
randMoveProb              = 0.2;

% Initialisierung
dRow   = NaN;
dCol   = NaN;
ind    = NaN;
action = NaN; % noch keine Aktion gefunden
mark   = NaN; % noch keine Markierung ausgewählt

antsWithoutActionProb = 1; % Anteil der Ameisen ohne Job

% Eingangsdaten modifizieren um nicht auf Hindernisse zu laufen
reachableMap = checkConnections(mainMap);
mainMap   (~reachableMap) = NaN;
foodMap   (~reachableMap) = 0;
myScentMap(~reachableMap) = NaN;
myAntMap  (~reachableMap) = 0;
opAntMap  (~reachableMap) = 0;

%%%%%%%%%%%%%
% Markieren %
%%%%%%%%%%%%%

% Nach eigenem Ameisenhügel sehen
onOwnAntHill      = mainMap(myInd) == 1;
ownAntHillVisible = any(mainMap(otherIndex(:)) == 1);

% maximale Duftmarke suchen
myScentMax = max(myScentMap(:));
wayToOwnAntHillFound = myScentMax > 0;

if onOwnAntHill
	targetScent = maxOwnAntHillScent;
else
	if ownAntHillVisible
		% Abstand zum und Position vom Ameisenhaufen bestimmen
		[indOwnAntHill, distToOwnAntHill, firstStepToOwnAntHill] = findWayToClosestTarget(find(mainMap == 1), mainMap, neighborIndex);
		targetScent = myScentMap(indOwnAntHill) - scentStep * distToOwnAntHill - 2;

	elseif wayToOwnAntHillFound
		% Distanz zu und Position der maximalen Duftmarke berechnen - diese
		% kann auch auf dem eigenen Feld liegen!
		[indMyScentMax, distToMyScentMax, firstStepToMyScentMax] = ...
			findWayToClosestTarget(find(myScentMap == myScentMax), mainMap, neighborIndex);
		targetScent = myScentMax - scentStep * distToMyScentMax - 2;
	else
		targetScent = 0;
	end
end

if targetScent > 0
	% Markierung berechnen

	% mit allen Ameisen auf dem aktuellen Feld zusammen markieren bis Zielwert erreicht, bei nichtganzzahliger
	% Markierung pro Ameise durch Zufallsprozess Ziel zu erreichen versuchen
	targetMarkPerAnt = ( targetScent - myScentMap(myInd) ) / myAntMap(myInd);
	mark = floor(targetMarkPerAnt) + 1*(rand < mod(targetMarkPerAnt, 1));
end

if opAntMap(myInd) > 0 % opponent on own field
	%%%%%%%%%%%%
	% Attacke! %
	%%%%%%%%%%%%
	fightProb = min(1, nrOfFightersPerOpponent * opAntMap(myInd) / (antsWithoutActionProb * myAntMap(myInd)));
	antsWithoutActionProb = antsWithoutActionProb * (1 - fightProb);
	if rand < fightProb
		ind    = myInd;
		action = actionFight;
	end
end

if isnan(action) && any(opAntMap(:) & otherIndex(:)) % opponent visible
	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	% Gegnerische Ameisen verfolgen %
	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	fightersNeededMap = max(0, nrOfFightersPerOpponent * opAntMap - myAntMap);
	fightersNeededMap(myInd) = 0;
	nrOfFightersNeeded = sum(fightersNeededMap(:));
	followProb = min(1, nrOfFightersNeeded / (antsWithoutActionProb * myAntMap(myInd)));
	antsWithoutActionProb = antsWithoutActionProb * (1 - followProb);
	if rand < followProb

		% nicht alle auf dieselben Ameisen
		indOpAntsVec = find(fightersNeededMap & otherIndex);
		if length(indOpAntsVec) > 1
			opAntProbs = fightersNeededMap(indOpAntsVec) / nrOfFightersNeeded;
			indOpAnt = indOpAntsVec(randomstate(opAntProbs));
		else
			indOpAnt = indOpAntsVec;
		end

		% Weg zu nächstem Gegner nehmen
		ind = findWayToTarget(indOpAnt, mainMap, neighborIndex);
		action = actionIdle;
	end
end

if isnan(action)

	%%%%%%%%%%%%%%%%%%%%
	% Friedlicher Teil %
	%%%%%%%%%%%%%%%%%%%%

	onFood      = foodMap(myInd) > 0 && ~onOwnAntHill;
	foodVisible = any( foodMap(:) & mainMap(:) ~= 1 & otherIndex(:) );

	if isnan(action) && antsWithoutActionProb > 0
		%%%%%%%%%%%%%%%%%%%
		% Stellung halten %
		%%%%%%%%%%%%%%%%%%%

		% Einige Ameisen sollen auf markierten Feldern die Stellung halten um
		% die richtige Duftkonzentration herzustellen
		if targetScent > myScentMap(myInd)
			newScent = min(maxMarkPerAnt, targetMarkPerAnt) * myAntMap(myInd) + myScentMap(myInd);
			noMoveProb = min(1, keepScentFactor * ((targetScent - newScent) / maxMarkPerAnt) / ...
				(antsWithoutActionProb * myAntMap(myInd)));
			antsWithoutActionProb = antsWithoutActionProb * (1 - noMoveProb);

			if rand < noMoveProb
				dRow = 0; dCol = 0;

				% nichts machen
				action = actionIdle;
			end
		end
	end

	if isnan(action) && onFood && antsWithoutActionProb > 0 && ...
			(ownAntHillVisible || (wayToOwnAntHillFound && myScentMax > myScentMap(myInd)))
		%%%%%%%%%%%%%%%%%%%%%%%%
		% Zucker weiter tragen %
		%%%%%%%%%%%%%%%%%%%%%%%%

		% Es werden möglicherweise nicht alle Ameisen zum Tragen benötigt
		carryProb = min(1, nrOfCarriersPerFood * foodMap(myInd) / (antsWithoutActionProb * myAntMap(myInd)));
		antsWithoutActionProb = antsWithoutActionProb * (1 - carryProb); % Wk dass andere Ameisen bis hierher noch keinen Auftrag haben

		if rand < carryProb
			
			if opAntMap(myInd) > 0 || any(opAntMap(neighborIndex) > 0)
				ind = myInd;
				action = actionFight;
			else
				action = actionCarry;

				if ownAntHillVisible
					% Das Ziel ist in Sichtweite
					ind = firstStepToOwnAntHill;
				else
					% in Richtung maximaler Duftmarke gehen
					ind = firstStepToMyScentMax;
				end
			end
		end
	end
	
	if isnan(action) && foodVisible && antsWithoutActionProb > 0 && ...
			(ownAntHillVisible || (wayToOwnAntHillFound && myScentMax > myScentMap(myInd)))
		%%%%%%%%%%%%%%%
		% Essen holen %
		%%%%%%%%%%%%%%%
		foodMapTmp = foodMap;
		foodMapTmp(mainMap == 1) = 0; % kein Essen von eigenen Ameisenhügel holen
		foodMapTmp(myInd)        = 0; % nicht stehen bleiben

		carriersNeededMap = max(0, nrOfCarriersPerFood * foodMapTmp - myAntMap);
		carriersNeededMap(myInd) = 0;
		nrOfCarriersNeeded = sum(carriersNeededMap(:));
		moveToFoodProb = min(1, nrOfCarriersNeeded / (antsWithoutActionProb * myAntMap(myInd)));
		antsWithoutActionProb = antsWithoutActionProb * (1 - moveToFoodProb);
		if rand < moveToFoodProb
			% nicht alle auf denselben Haufen
			carriersNeededIndex = find(carriersNeededMap);
			if length(carriersNeededIndex) > 1
				carrierProbs = carriersNeededMap(carriersNeededIndex) / nrOfCarriersNeeded;
				indFood = carriersNeededIndex(randomstate(carrierProbs));
			else
				indFood = carriersNeededIndex;
			end

			ind = findWayToTarget(indFood, mainMap, neighborIndex);
			action = actionIdle;
		end
	end
	
	if isnan(action) && antsWithoutActionProb > 0
		if rand < randMoveProb
			%%%%%%%%%%%%%%%%%%
			% Zufallsschritt %
			%%%%%%%%%%%%%%%%%%

			% mit gewisser Wk einfach zufällig weiter (um Blockierungen zu
			% vermeiden)
			ind = getRandomMove(mainMap);
			action = actionIdle;
			if isnan(mark)
				mark = 0;
			end
		end
		%antsWithoutActionProb = antsWithoutActionProb * (1 - randMoveProb);
	end
end

if isnan(action)
		%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
		% Suche nach Essen oder Feinden %
		%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

		% Gewichtung für die Wahl der Laufrichtung berechnen
		penaltyMap = zeros(nSight);
		penaltyMap(~reachableMap) = inf;

		ownAntPenaltyFactor   = 1;
		ownFieldPenalty       = 5;
		nonMarkedFieldPenalty = -10;

		rowIndexMap = repmat((1:5)', 1, nSight);
		colIndexMap = repmat( 1:5,   nSight, 1);

		% möglichst nicht stehen bleiben
		penaltyMap(myInd) = penaltyMap(myInd) + ownFieldPenalty;

		% in Richtung nicht markierter Felder suchen
		nonMarkedFieldIndex = find(myScentMap == 0 & otherIndex);
		penaltyMap(nonMarkedFieldIndex) = penaltyMap(nonMarkedFieldIndex) + nonMarkedFieldPenalty;

		% von anderen nicht beschäftigten Ameisen fernhalten um möglichst
		% viel Gebiet zu erkunden
		myAntMapTmp = myAntMap;
		myAntMapTmp(myInd) = myAntMapTmp(myInd) - 1; % alle Ameisen außer der aktuellen betrachten
		myAntMapTmp(foodMap  > 0) = 0;               % Essen tragende Ameisen hier nicht berücksichtigen
		myAntMapTmp(opAntMap > 0) = 0;               % Kämpfende Ameisen hier nicht berücksichtigen
		nrOfOwnAnts = sum(myAntMapTmp(:));
		if nrOfOwnAnts > 0
			[ownAntRows, ownAntCols] = find(myAntMapTmp > 0 & otherIndex);
			distAdd = 1;
			for k = 1:length(ownAntRows)
				penaltyMap = penaltyMap + ownAntPenaltyFactor * myAntMapTmp(ownAntRows(k), ownAntCols(k)) / nrOfOwnAnts * ...
					1 ./ (distAdd + abs(ownAntRows(k) - rowIndexMap) + abs(ownAntCols(k) - colIndexMap));
			end
		end

		% in Richtung kleinster Penalty laufen
		if myAntMap(myInd) == 1
			% aktuelle Ameise ist allein auf ihrem Feld
			[minPenalty, indMinPenalty] = min(penaltyMap(:));
		else
			% mehrere Ameisen auf dem aktuellen Feld, zufällig eines der Felder
			% mit minimalem Penalty auswählen
			[ignore, sortIndex] = sort(penaltyMap(:));
			nrOfFiniteValues = length(find(isfinite(penaltyMap)));
			indMinPenalty = sortIndex(ceil(rand * min(myAntMap(myInd), nrOfFiniteValues)));
		end

		ind = findWayToTarget(indMinPenalty, mainMap, neighborIndex);
		action = actionIdle;
end

if (isnan(dRow) || isnan(dCol)) && ~isnan(ind)
	% Index gegeben, in dRow, dCol umrechnen
	[dRow, dCol] = ind_2_dRow_dCol(ind, nSight);
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [ind, dist, firstStep] = findWayToClosestTarget(indCandidates, allowedMap, neighborIndex)

myInd = 13;
if any(indCandidates == myInd)
	ind       = myInd;
	dist      = 0;
	firstStep = myInd;
	return
end

% Erstmal in der direkten Nachbarschaft nachsehen
indCandNeighbors = intersect(indCandidates, neighborIndex);
if ~isempty(indCandNeighbors)
	indCandidates = indCandNeighbors;
end

% Nächstes Ziel finden
dist = inf;
for k = 1:length(indCandidates)
	[curFirstStep, curDist] = findWayToTarget(indCandidates(k), allowedMap, neighborIndex); %#ok
	curDist = curDist + (rand-0.5) * 0.2; % bei gleichen Distanzen zufällig auswählen
	if curDist < dist 
		dist      = curDist;
		firstStep = curFirstStep;
		ind       = indCandidates(k);
	end
end
dist = round(dist); % Zufallsanteil wieder wegwerfen

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function path = traceback(z,PZ,t)

path = zeros(t+1,1);
path(1) = z;
for j = 1:t
	z = PZ(z);
	path(j+1) = z;
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [indOut, dist] = findWayToTarget(ind, B, neighborIndex)

indOut = NaN;
dist   = NaN;

if ~isfinite(B(ind))
	% Ziel nicht erreichbar
	return
end

% check neighborhood first
if any(neighborIndex == ind)
	indOut = ind;
	dist   = 1;
	return
end

nSight = size(B, 1);
nSightPad = nSight + 2;
[row, col] = ind_2_row_col(ind, nSight);

% padding
B = [nan(nSightPad,1), [nan(1,nSight); B; nan(1,nSight)], nan(nSightPad,1)];
row = row + 1;
col = col + 1;

PZ = zeros(nSightPad);
C  = -ones(nSightPad);
C(4,4) = 0; % source
C(row,col) = -2; % tag the target

znext = zeros(nSightPad*nSightPad,1);
znext(1) = 25;
dZ = [-6 -8 6 8 -1 1 -7 7];

count = 1;
for step = 0:nSightPad*nSightPad
	if count < 1
		break
	end
	N = count;
	z = znext;
	count = 0;
	for i = 1:N
		zi = z(i);
		for s=1:8
			Z = zi + dZ(s);
			tag = C(Z);
			if tag == -2
				% way to target found
				PZ(Z) = zi;
				path = traceback(Z,PZ,step+1);
				dist = length(path) - 1;

				% undo padding
				[row, col] = ind_2_row_col(path(end-1), nSight + 2);
				indOut = row_col_2_ind(row-1, col-1, nSight);
				return

			end
			if tag == -1 && isfinite(B(Z))
				C(Z) = step+1;
				PZ(Z) = zi;
				count = count + 1;
				znext(count) = Z;
			end
		end
	end
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function reachableMap = checkConnections(allowedMap)

%                       N  NO  O  SO  S  SW   W  NW
dRowVector         = [ -1  -1  0   1  1   1   0  -1 ];
dColVector         = [  0   1  1   1  0  -1  -1  -1 ];

% padding
allowedMapTmp = [nan(7,1), [nan(1,5); allowedMap; nan(1,5)], nan(7,1)];

% Alle erreichbaren Felder in 7x7-Matrix finden
reachableMap = zeros(7);
reachableMap(4,4) = 1;

rowIndex = zeros(1,49);
colIndex = zeros(1,49);
rowIndex(1) = 4;
colIndex(1) = 4;
memIndex = 2;
for n = 1:length(rowIndex)
	row = rowIndex(n);
	col = colIndex(n);
	if row == 0
		break
	end
	for k = 1:length(dRowVector)
		rowTmp = row + dRowVector(k);
		colTmp = col + dColVector(k);
		if ~reachableMap(rowTmp, colTmp) && isfinite(allowedMapTmp(rowTmp, colTmp))
			% Punkt erreichbar
			reachableMap(rowTmp, colTmp) = 1;
			rowIndex(memIndex) = rowTmp;
			colIndex(memIndex) = colTmp;
			memIndex = memIndex + 1;
		end
	end
end

reachableMap = reachableMap(2:6, 2:6); % padding

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [dRow, dCol] = ind_2_dRow_dCol(ind, nSight)
[row, col] = ind_2_row_col(ind, nSight);
dRow = row - (nSight+1) / 2;
dCol = col - (nSight+1) / 2;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [row, col] = ind_2_row_col(ind, nSight)
row = mod(ind - 1, nSight) + 1;
col = ceil(ind / nSight - eps);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function ind = row_col_2_ind(row, col, nSight)
ind = row + nSight * (col - 1);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function ind = getRandomMove(mainMap)

indVector = [7 8 9 14 19 18 17 12];
indVector = indVector(isfinite(mainMap(indVector)));
ind = indVector(ceil(rand*length(indVector)));

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function states = randomstate(probs)

nrOfStates = length(probs);
sumProbs = sum(probs);
number = rand * sumProbs;
threshold = 0;
for k = 1:nrOfStates
	threshold = threshold + probs(k);
	if number <= threshold
		states = k;
		return
	end
end
states = nrOfStates;