NearestEvolve.lua

if gameinfo.getromname() == "Super Mario World (USA)" then
	filename = "DP1.state"
	buttonNames = {
		"A",
		"B",
		"X",
		"Y",
		"Up",
		"Down",
		"Left",
		"Right",
	}
elseif gameinfo.getromname() == "Super Mario Bros." then
	filename = "SMB1-1.state"
	buttonNames = {
		"A",
		"B",
		"Up",
		"Down",
		"Left",
		"Right",
	}
end

boxRadius = 6
inputSize = (boxRadius*2+1)*(boxRadius*2+1)
snapshotSize = inputSize + #buttonNames

function getPositions()
	if gameinfo.getromname() == "Super Mario World (USA)" then
		marioX = memory.read_s16_le(0x94)
		marioY = memory.read_s16_le(0x96)

		local layer1x = memory.read_s16_le(0x1A);
		local layer1y = memory.read_s16_le(0x1C);

		screenX = marioX-layer1x
		screenY = marioY-layer1y
	elseif gameinfo.getromname() == "Super Mario Bros." then
		marioX = memory.readbyte(0x6D) * 0x100 + memory.readbyte(0x86)
		marioY = memory.readbyte(0x03B8)+16

		screenX = memory.readbyte(0x03AD)
		screenY = memory.readbyte(0x03B8)
	end
end

function getTile(dx, dy)
	if gameinfo.getromname() == "Super Mario World (USA)" then
		x = math.floor((marioX+dx+8)/16)
		y = math.floor((marioY+dy)/16)

		return memory.readbyte(0x1C800 + math.floor(x/0x10)*0x1B0 + y*0x10 + x%0x10)
	elseif gameinfo.getromname() == "Super Mario Bros." then
		local x = marioX + dx + 8
		local y = marioY + dy - 16
		local page = math.floor(x/256)%2

		local subx = math.floor((x%256)/16)
		local suby = math.floor((y - 32)/16)
		local addr = 0x500 + page*13*16+suby*16+subx

		if suby >= 13 or suby < 0 then
			return 0
		end

		if memory.readbyte(addr) ~= 0 then
			return 1
		else
			return 0
		end
	end
end

function getSprites()
	if gameinfo.getromname() == "Super Mario World (USA)" then
		local sprites = {}
		for slot=0,11 do
			local status = memory.readbyte(0x14C8+slot)
			if status ~= 0 then
				spritex = memory.readbyte(0xE4+slot) + memory.readbyte(0x14E0+slot)*256
				spritey = memory.readbyte(0xD8+slot) + memory.readbyte(0x14D4+slot)*256
				sprites[#sprites+1] = {["x"]=spritex, ["y"]=spritey}
			end
		end

		return sprites
	elseif gameinfo.getromname() == "Super Mario Bros." then
		local sprites = {}
		for slot=0,4 do
			local enemy = memory.readbyte(0xF+slot)
			if enemy ~= 0 then
				local ex = memory.readbyte(0x6E + slot)*0x100 + memory.readbyte(0x87+slot)
				local ey = memory.readbyte(0xCF + slot)+24
				sprites[#sprites+1] = {["x"]=ex,["y"]=ey}
			end
		end

		return sprites
	end
end

function getExtendedSprites()
	if gameinfo.getromname() == "Super Mario World (USA)" then
		local extended = {}
		for slot=0,11 do
			local number = memory.readbyte(0x170B+slot)
			if number ~= 0 then
				spritex = memory.readbyte(0x171F+slot) + memory.readbyte(0x1733+slot)*256
				spritey = memory.readbyte(0x1715+slot) + memory.readbyte(0x1729+slot)*256
				extended[#extended+1] = {["x"]=spritex, ["y"]=spritey}
			end
		end

		return extended
	elseif gameinfo.getromname() == "Super Mario Bros." then
		return {}
	end
end

function getInputs()
	getPositions()

	sprites = getSprites()
	extended = getExtendedSprites()

	local inputs = {}

	for dy=-boxRadius*16,boxRadius*16,16 do
		for dx=-boxRadius*16,boxRadius*16,16 do
			inputs[#inputs+1] = 0

			tile = getTile(dx, dy)
			if tile == 1 and marioY+dy < 0x1B0 then
				inputs[#inputs] = 1
			end

			for i = 1,#sprites do
				distx = math.abs(sprites[i]["x"] - (marioX+dx))
				disty = math.abs(sprites[i]["y"] - (marioY+dy))
				if distx <= 8 and disty <= 8 then
					inputs[#inputs] = -1
				end
			end

			for i = 1,#extended do
				distx = math.abs(extended[i]["x"] - (marioX+dx))
				disty = math.abs(extended[i]["y"] - (marioY+dy))
				if distx < 8 and disty < 8 then
					inputs[#inputs] = -1
				end
			end
		end
	end

	--mariovx = memory.read_s8(0x7B)
	--mariovy = memory.read_s8(0x7D)

	return inputs
end


function evaluate(inputs, chromosome)
	local outputs = {}
	local minDist = 4*inputSize

	for i=0,(math.floor(#chromosome/snapshotSize)-1) do
		local total = 0
		for j=1,inputSize do
			d = inputs[j] - chromosome[i*snapshotSize + j]
			total = total + d*d
		end
		if total < minDist then
			minDist = total
			for j=1,#buttonNames do
				outputs[j] = chromosome[i*snapshotSize+inputSize+j]
			end
			nearest = i*snapshotSize
		end
	end

	return outputs
end

function randomChromosome()
	local c = {}

	for i=1,snapshotSize*100 do
		c[i] = math.random(-1, 1)
	end

	return c
end

function initializeRun()
	savestate.load(filename);
	rightmost = 0
	frame = 0
	timeout = 20
	clearJoypad()
end

function crossover(c1, c2)
	local c = {["chromosome"] = {}, ["fitness"] = 0}
	local pick = true
	for i=1,#c1["chromosome"] do
		if math.random(#c1["chromosome"]/2) == 1 then
			pick = not pick
		end
		if pick then
			c["chromosome"][i] = c1["chromosome"][i]
		else
			c["chromosome"][i] = c2["chromosome"][i]
		end
	end

	return c
end

function mutate(c, rate)
	for i=1,#c["chromosome"] do
		if math.random(rate) == 1 then
			c["chromosome"][i] = math.random(-1, 1)
		end
	end
end

function difference(c1, c2)
	total = 0
	for i=1,#c1 do
		d = c1[i] - c2[i]
		total = total + d*d
	end

	return total / (#c1*4)
end

function clone(c)
	cl = {["chromosome"] = {}, ["fitness"] = 0}
	for i=1,#c["chromosome"] do
		cl["chromosome"][i] = c["chromosome"][i]
	end
	return cl
end

function createNewGeneration()
	local shock = (generation % 60 == 59)

	local top = pool[1]["fitness"]
	if not shock then
		pool[1]["fitness"] = 1000000
	end

	table.sort(pool, function (a,b)
		return (a["fitness"] > b["fitness"])
	end)

	pool[1]["fitness"] = top

	if shock then
		for i=2,(#pool) do
			pool[i] = clone(pool[1])
			mutate(pool[i], 20)
		end
	else
		for i=((#pool)/2+1),(#pool) do
			c1 = pool[math.random(2, #pool/2)]
			c2 = pool[math.random(2, #pool/2)]
			pool[i] = crossover(c1, c2)
			mutate(pool[i], 400)
		end
		forms.settext(localFitness, "Local Fitness: " .. math.floor(pool[2]["fitness"]))
	end

	generation = generation + 1
end

function clearJoypad()
	controller = {}
	for b = 1,#buttonNames do
		controller["P1 " .. buttonNames[b]] = false
	end
	joypad.set(controller)
end

function showTop()
	clearJoypad()
	currentChromosome = 0
	initializeRun()
end

function onExit()
	forms.destroy(form)
end
event.onexit(onExit)

function connectionCost(chromosome)
	local total = 0
	for i=1,#chromosome["chromosome"] do
		c = chromosome["chromosome"][i]
		total = total + c*c
	end

	return total
end

function outputChromosomes()
	local filename = forms.gettext(saveLoadFile)
        local file = io.open(filename, "w")
	file:write(generation .. "\n")
	file:write(maxfitness .. "\n")
        file:write(#pool .. "\n")
        for c=1,#pool do
                local size = #pool[c]["chromosome"]
                file:write(size .. "\n")
                for n=1,size do
                        file:write(pool[c]["chromosome"][n] .. "\n")
                end
        end
        file:close()
end

function inputChromosomes()
	initializeSimulation()
	currentChromosome=0
	local filename = forms.gettext(saveLoadFile)
        local file = io.open(filename, "r")
	generation = tonumber(file:read())
	maxfitness = tonumber(file:read())
	forms.settext(maxFitnessLabel, "Top Fitness: " .. math.floor(maxfitness))
        local poolsize = tonumber(file:read())
        for c=1,poolsize do
                local size = tonumber(file:read())
                for n=1,size do
                        pool[c]["chromosome"][n] = tonumber(file:read())
                end
        end
        file:close()
end

function initializeSimulation()
	pool = {}
	for i=1,20 do
		pool[i] = {["chromosome"] = randomChromosome(), ["fitness"] = 0}
	end
	currentChromosome = 1
	generation = 0
	maxfitness = -1000000
	initializeRun()
end

form = forms.newform(200, 275, "Fitness")
maxFitnessLabel = forms.label(form, "Top Fitness: ", 5, 8)
goButton = forms.button(form, "Show Top", showTop, 5, 30)
goButton = forms.button(form, "Restart", initializeSimulation, 80, 30)
localFitness = forms.label(form, "Local Fitness: ", 5, 55)
showUI = forms.checkbox(form, "Show Inputs", 5, 74)
inputsLabel = forms.label(form, "Inputs", 5, 96)
showChromosomes = forms.checkbox(form, "Show Map", 5, 118)
saveButton = forms.button(form, "Save", outputChromosomes, 5, 142)
loadButton = forms.button(form, "Load", inputChromosomes, 80, 142)
saveLoadFile = forms.textbox(form, "nearest_chromosomes.txt", 170, 25, nil, 5, 188)
saveLoadLabel = forms.label(form, "Save/Load:", 5, 169)
showNearest = forms.checkbox(form, "Show Nearest", 5, 215)

if pool == nil then
	initializeSimulation()
else
	forms.settext(maxFitnessLabel, "Top Fitness: " .. math.floor(maxfitness))
end

while true do
	getPositions()

	timeoutBonus = frame / 4
	if timeout + timeoutBonus <= 0 then
		local fitness = 0
		fitness = rightmost - frame / 2

		if currentChromosome >= 1 then
			pool[currentChromosome]["fitness"] = fitness
		end

		if fitness > maxfitness then
			forms.settext(maxFitnessLabel, "Top Fitness: " .. math.floor(fitness))
			maxfitness = fitness
		end

		console.writeline("Generation " .. generation .. " chromosome " .. currentChromosome .. " fitness: " .. math.floor(fitness))
		if currentChromosome == #pool then
			createNewGeneration()
			currentChromosome = #pool/2+1
		else
			if currentChromosome == 2 and pool[currentChromosome+1]["fitness"] ~= 0 then
				currentChromosome = (#pool)/2+1
			else
				currentChromosome = currentChromosome + 1
			end
		end
		initializeRun()
	end

	if timeout + timeoutBonus > 2 and frame % 5 == 0 and currentChromosome >= 1 then
		inputs = getInputs()
		outputs = evaluate(inputs, pool[currentChromosome]["chromosome"])

		controller = {}
		inputsString = ""
		for n = 1,#buttonNames do
			if outputs[n] > 0 then
				controller["P1 " .. buttonNames[n]] = true
				inputsString = inputsString .. buttonNames[n]

			else
				controller["P1 " .. buttonNames[n]] = false
			end
			if controller["P1 Left"] and controller["P1 Right"] then
				controller["P1 Left"] = false
				controller["P1 Right"] = false
			end
			if controller["P1 Up"] and controller["P1 Down"] then
				controller["P1 Up"] = false
				controller["P1 Down"] = false
			end
		end

		forms.settext(inputsLabel, inputsString)
	end
	joypad.set(controller)

	if timeout + timeoutBonus <= 2 then
		clearJoypad()
	end

	if marioX > rightmost then
		timeout = 20
		rightmost = marioX
	end

	timeout = timeout - 1
	frame = frame + 1


	if forms.ischecked(showUI) and inputs ~= nil then
		for dy = 0,boxRadius*2 do
			for dx = 0,boxRadius*2 do
				input = inputs[dy*(boxRadius*2+1)+dx+1]
				local x = screenX+(dx-boxRadius)*16
				local y = screenY+(dy-boxRadius)*16
				if input == -1 then
					gui.drawBox(x, y, x+16, y+16, 0xFFFF0000, 0xA0FF0000)
				elseif input == 1 then
					gui.drawBox(x, y, x+16, y+16, 0xFF00FF00, 0xA000FF00)
				else
					gui.drawBox(x, y, x+16, y+16, 0xFFFFFF00, 0xA0FFFF00)
				end
				--gui.drawText(,,string.format("%i", input),0x80FFFFFF, 11)
			end
		end

		gui.drawBox(screenX, screenY, screenX+16, screenY+32, 0xFF000000)
	end

	if forms.ischecked(showNearest) and nearest ~= nil and currentChromosome >= 1 then

		for dy = 0,boxRadius*2 do
			for dx = 0,boxRadius*2 do
				input = pool[currentChromosome]["chromosome"][nearest+dy*(boxRadius*2+1)+dx+1]
				local x = screenX+(dx-boxRadius)*16
				local y = screenY+(dy-boxRadius)*16
				if input == -1 then
					gui.drawBox(x, y, x+16, y+16, 0xFFFF0000, 0xA0FF0000)
				elseif input == 1 then
					gui.drawBox(x, y, x+16, y+16, 0xFF00FF00, 0xA000FF00)
				else
					gui.drawBox(x, y, x+16, y+16, 0xFFFFFF00, 0xA0FFFF00)
				end
			end
		end

		gui.drawBox(screenX, screenY, screenX+16, screenY+32, 0xFF000000)
	end

	if forms.ischecked(showChromosomes) then
		gui.drawBox(0, 3, 201, 3+#pool*3, 0xFFFFFFFF, 0xFFFFFFFF)
		for c=1,#pool do
			local y = 1+c*3
			local size = #pool[c]["chromosome"]
			for n=1,size do
				if n%math.floor(size/200) == 0 then
					local x = 1+n*200/#pool[c]["chromosome"]
					v = pool[c]["chromosome"][n]
					r = (1-v)/2
					g = (1+v)/2
					gui.drawLine(x, y, x, y+1, 0xFF000000 + math.floor(r*0xFF)*0x10000 + math.floor(g*0xFF)*0x100)
				end
			end
		end
	end

	emu.frameadvance();
end