Beetle Mania bot

--x position of ith shell (0<=i<=69)
function shellx(i)
    x=memory.readbyte(0x404088+22*i)
    return x
end

--y position of ith shell
function shelly(i)
    y=memory.readbyte(0x40408B+22*i)
    return y
end

--Finds the middle of the path, given the desired position j
function findmiddle(cango,i,j)
    local k=j
    while cango[i][k-2] do
        k=k-2
    end
    min = k

    k=j
    while cango[i][k+2] do
        k=k+2
    end
    max = k

    middle=(min+max)/2
    middle=2*math.floor(middle/2)
    return middle
end

function sign(x)
    if x>0 then
        return 1
    elseif x<0 then
        return -1
    else
        return 0
    end
end

function autorecover()
    local lastpress=1
    while memory.readbyte(0x8030e6)>0 do
        if lastpress==1 then
            joypad.set(1,{A=true})
            emu.frameadvance()
            lastpress=0
        else
            joypad.set(1,{B=true})
            emu.frameadvance()
            lastpress=1
        end
    end
end

function lookahead()
    emu.speedmode("maximum")
    local state1=savestate.create()
    savestate.save(state1)
    local startframe=emu.framecount()
    local dodge={{}}
    local lastvals={{}}     --Last x and y coordinates of all shells
    for i=0,69 do
        lastvals[i]={-1,-1}
    end
    for i=1,1200 do     --Look 20 seconds into the future
        for j=0,69 do       --Check all 70 shells
            moved=not(shellx(j)==lastvals[j][1] and shelly(j)==lastvals

[j][2])     --Must check if shell moved since dead shells don't refresh
            if moved and shelly(j)>195 and shelly(j)<250 then

--If the shell hits the ground
                if not(dodge[i]) then
                    dodge[i]={}
                end
                for k=shellx(j)-17,shellx(j)+17 do
                    dodge[i][k]=true
                end
            end
            lastvals[j]={shellx(j),shelly(j)}
        end
        memory.writebyte(0x404000,1)
        memory.writebyte(0x8030e6,0)        --invincibility
        emu.frameadvance()
    end
    savestate.load(state1)
    emu.speedmode("normal")
    return dodge, startframe
end


function showpercolation(dodge,cango,x)
    local i=next(dodge)
    while dodge[i] do
        local j=next(dodge[i])
        while dodge[i][j] do
            gui.pixel(j+7,200-i,"white")
            j=next(dodge[i],j)
        end
        i=next(dodge,i)
    end

    for i = 1,#cango-1 do
        local j=next(cango[i])
        for j=0,table.maxn(cango[i]) do
            if cango[i][j] then
                gui.pixel(j+7,200-i,"magenta")
            end
        end
    end

    for i = 1,#x do
        gui.pixel(x[i]+7,200-i,"blue")
    end

    emu.pause()
end

function percolate(dodge)
    cango={{}}
    cango[1][memory.readbyte(0x404004)]=true

    i=2
    while cango[i-1] and not(i>table.maxn(dodge)) do
        for j=0,238 do      --Playing field is 238 units wide.  The

beetle can access odd values by going to 239, but these are excluded for simplicity.
            --if not(dodge[i]) or not(dodge[i][j]) and cango[i-1][j]

then
            if cango[i-1][j] then
                if not(cango[i]) then
                    cango[i]={}
                end

                cango[i][j-2]=not(dodge[i]) or not(dodge[i][j-2])

    --Go left
                cango[i][j]=not(dodge[i]) or not(dodge[i][j])

--Stay still
                cango[i][j+2]=not(dodge[i]) or not(dodge[i][j+2])

    --Go right
            end
        end
        i=i+1
    end

    local j=0
    local x={}
    while not(cango[#cango-1][j]) do        --Exclude both nil and false
        j=j+2
    end
    x[#cango-1]=findmiddle(cango,#cango-1,j)

    local xx=0
    for i=2,#cango-1 do
        if cango[#cango-i][x[#cango-i+1]-2] then
            xx=x[#cango-i+1]-2
        elseif cango[#cango-i][x[#cango-i+1]] then
            xx=x[#cango-i+1]
        elseif cango[#cango-i][x[#cango-i+1]+2] then
            xx=x[#cango-i+1]+2
        end
        middle=findmiddle(cango,#cango-i,xx)
        x[#cango-i]=x[#cango-i+1]+2*sign(middle-x[#cango-i+1])
    end

    --showpercolation(dodge,cango,x)

    return x
end

--Moves beetle according to x acquired from percolation
function move(x,start,depth)
    local press={}
    for i=start,depth do
        if x[i] and x[i+1] then
            press={}
            if x[i]<x[i+1] then
                press={right=true}
            elseif x[i]>x[i+1] then
                press={left=true}
            end
            joypad.set(1,press)
            emu.frameadvance()
        end
    end
    --emu.pause()
end

function copyvector(vector)
    local vectorcopy={}
    for k, v in pairs(vector) do
        vectorcopy[k]=v
    end
    return vectorcopy
end

function hdectodec(number)
    local place={[0]=0}
    local i=0
    while not(number==0) do
        place[i]=number%16
        number = number-place[i]
        number = number/16
        i=i+1
    end

    local output=0
    for i=0,#place do
        output=output+place[i]*10^i
    end
    return output
end

--Flips the endianness and turns a vector of bytes into a single, large hexadecimal

value
function flipendian(hexvector)
    local L=#hexvector
    local output=0
    for i = 1,L do
        output = output+hexvector[i]*256^(i-1)
    end
    return output
end

function getscore()
    score=memory.readbyterange(0x8030f0,4)
    score=flipendian(score)
    score=hdectodec(score)
    return score
end

function getinputs()
    state2 = savestate.create()
    savestate.save(state2)
    local buttons={}
    local i=1
    while memory.readbyte(0x8030e6)==0 do
        buttons[i]=joypad.get(1)
        i=i+1
        emu.frameadvance()
    end
    savestate.load(state2)
    return buttons, state2
end

function findbest2(buttons, state)
    --emu.speedmode("maximum")
    local scorestart=getscore()
    local framestart=emu.framecount()
    local bestrate=0
    local besti=1
    for i = 1,#buttons do
        for j = 1,i do
            local press=copyvector(buttons[j])
            if i==j then
                press["B"]=true
            end
            joypad.set(1,press)
            emu.frameadvance()
        end
        framecountdown=120      --120 frames (2 seconds) for the

first star to leave the field
        score = getscore()
        while framecountdown>0 do
            memory.writebyte(0x8030e6,0)
            if getscore()>score then        --If the score

increased
                framecountdown=60       --Reset the counter
                score=getscore()
            else
                framecountdown=framecountdown-1
            end
            emu.frameadvance()
        end

        local deltascore=score-scorestart
        local time = emu.framecount()-framestart
        local rate=deltascore/time
        print(i, rate)
        if rate>bestrate then
            bestrate=rate
            besti=i
        end
        savestate.load(state)
    end
    print(besti, bestrate)
    --emu.speedmode("normal")
    return besti
end

function findbest(x)
    emu.speedmode("maximum")
    local state1=savestate.create()     --Return to this state after finding

the best
    local state2=savestate.create()     --Save and load this state for

efficiency when checking depth
    savestate.save(state1)
    savestate.save(state2)
    local scorestart=getscore()
    local framestart=emu.framecount()
    local bestrate=0
    local besti=0
    local doneflag=false

    for depth=1,#x-1 do
        savestate.load(state2)
        move(x,depth,depth)
        savestate.save(state2)
        joypad.set(1,{B=true})

        local framecountdown=120
        local score=getscore()
        while framecountdown>0 do
            memory.writebyte(0x404000,1)        --Invincibility,

just for the purposes of checking score efficiently
            if getscore()>score then        --If the score

increased
                framecountdown=60       --Reset the counter
                score=getscore()
            else
                framecountdown=framecountdown-1
            end
            emu.frameadvance()
        end

        if score==99999999 then     --If the score is maxed out
            doneflag=true
        end

        local deltascore=score-scorestart
        local time = emu.framecount()-framestart
        local rate=deltascore/time
        print(depth, rate)
        if rate>bestrate then
            bestrate=rate
            bestdepth=depth
        end
    end

    savestate.load(state1)
    emu.speedmode("normal")

    return bestdepth, doneflag
end

function makeitso(x,bestdepth,doneflag)
    move(x,1,bestdepth)
    joypad.set(1,{B=true})

    if not(doneflag) then
        local framecountdown=120
        local score=getscore()
        while framecountdown>0 do
            if getscore()>score then        --If the score

increased
                framecountdown=60       --Reset the counter
                score=getscore()
            else
                framecountdown=framecountdown-1
            end
            emu.frameadvance()
            if memory.readbyte(0x404000)==5 then
                autorecover()
            end
        end
    end
    if doneflag then
        emu.frameadvance()
        emu.pause()
    end
end

while true do
    dodge=lookahead()
    x=percolate(dodge)
    bestdepth,doneflag=findbest(x)
    makeitso(x,bestdepth,doneflag)
end

--Byte i030E5 is the "damage" byte.  This is the number of times you have to press

A/B to recover.
--If this byte exceeds 146 you will lose (can't recover in time).
--Byte i030E6 is the "recovery" byte.  When this byte reaches 0, the beetle

recovers.
--Byte s04088: shell 1's horizontal position.
--Byte s0408B: shell 1's vertical position.
--Byte s0409E: shell 2's horizontal position.
--Byte s040A1: shell 2's vertical position.
--Byte s04004: Beetle position.