7th Saga Pathing

--Nitrodon's 7th Saga A* algorithm to walk between towns and avoid encounters.

local xdest = 482
local ydest = 130
local savestateinterval = 20

local xmin = 0
local xmax = 511
local ymin = 0
local ymax = 511
local map1 = 0xce7134
local map2 = 0xce6154
local map3 = 0xce0000
local map4 = 0xce48e0
local sector1
local sector2
local sector3
local sector4
local xcoord
local ycoord
local distance = {[xdest]={[ydest]=0}}
local paths = {[xdest]={[ydest]=1}}
local dx={0,0,-1,1}
local dy={-1,1,0,0}
local dir
local keys
local directions = {"up", "down", "left", "right"}
local optimalpaths = {}
local npaths = {}
local pathdir = {[0]=1}
local stopped = {}
local step
local replay

function updatevalue(newx, newy, xcoord, ycoord, distance, paths, changed)
    if newx >= xmin and newx <= xmax and newy >= ymin and newy <= ymax then
        sector1 = math.floor(newx/32) + 16*math.floor(newy/32) -- check for map collision
        sector2 = AND(newx, 0x18)/8 + AND(newy, 0x18)/2
        sector3 = AND(newx, 0x6)/2 + 2*AND(newy, 0x6)
        sector4 = math.fmod(newx, 2) + 2*math.fmod(newy, 2)
        if AND(memory.readbyte(memory.readbyte(memory.readword(memory.readbyte(map1+sector1)*32+map2+2*sector2)*16+map3+sector3)*32+map4+1),2^(5-sector4)) == 0 then
            if distance[newx] == nil then
                distance[newx] = {}
                paths[newx] = {}
            end
            if distance[newx][newy] == nil or distance[newx][newy] > distance[xcoord][ycoord]+1 then
                distance[newx][newy] = distance[xcoord][ycoord] + 1
                paths[newx][newy] = paths[xcoord][ycoord]
                table.insert(changed,{x=newx, y=newy})
            elseif distance[newx][newy] == distance[xcoord][ycoord]+1 then
                paths[newx][newy] = paths[newx][newy] + paths[xcoord][ycoord]
            end
        end
    end
end


--checks to see that distance to destination has lowered.
function isoptimal(newx, newy, xcoord, ycoord, distance)
    if distance[newx] ~= nil and distance[newx][newy] ~= nil and distance[newx][newy] == distance[xcoord][ycoord] - 1 then
        return true
    else
        return false
    end
end

--function only runs after cycle is done.
function nextframe()
    if memory.readbyte(0x7e0722) ~= 2 then
        xcoord = math.floor((memory.readword(0x7e07a8) + memory.readword(0x7e0a91)+16)/32)
        ycoord = math.floor((memory.readword(0x7e07b0) + memory.readword(0x7e0a94)+16)/32)
        region = math.floor(xcoord/8) - 64*math.floor(xcoord/512) + 64*math.floor(ycoord/8) - 4096*math.floor(ycoord/512)
        encmap = memory.readword(0x7e07a3) + 0x10000*memory.readbyte(0x7e07a5)
        gui.text(0,180,"Current location: (" .. xcoord .. ", " .. ycoord .. ")")
        if memory.readbyte(0x7e0723) ~= 2 then
            gui.text(0,190,"Encounter region: " .. memory.readbyte(encmap+region))
            if distance[xcoord] ~= nil and distance[xcoord][ycoord] ~= nil then
                gui.text(0,200,"Distance: " .. distance[xcoord][ycoord])
                gui.text(0,210,"Paths: " .. paths[xcoord][ycoord])
            end
        end
    else
        gui.text(0,190,"Enemy HP:")
        if AND(memory.readword(0x7e1e9e),0xa000) == 0 then
            gui.text(96,190,memory.readword(0x7e1e84))
        end
        if AND(memory.readword(0x7e1f1e),0xa000) == 0 then
            gui.text(160,190,memory.readword(0x7e1f04))
        end
        if AND(memory.readword(0x7e1f9e),0xa000) == 0 then
            gui.text(224,190,memory.readword(0x7e1f84))
        end
    end
    snes9x.frameadvance()
end
--

---Begin Cycle
snes9x.speedmode("maximum")

local i = 1
local changed = {{x=xdest,y=ydest}}
while i <= # changed do
    xcoord = changed[i].x
    ycoord = changed[i].y
    updatevalue(xcoord-1, ycoord, xcoord, ycoord, distance, paths, changed)
    updatevalue(xcoord+1, ycoord, xcoord, ycoord, distance, paths, changed)
    updatevalue(xcoord, ycoord-1, xcoord, ycoord, distance, paths, changed)
    updatevalue(xcoord, ycoord+1, xcoord, ycoord, distance, paths, changed)
    i = i + 1
end

while memory.readbyte(0x7e0712) ~= 0 do nextframe() end -- wait until input is accepted

if distance[xcoord] ~= nil and distance[xcoord][ycoord] ~= nil then
    local states = {}
    replay = false
    step = 0
    repeat
        step = step + 1
        if math.mod(step, savestateinterval) == 1 and not replay then
            if states[step] == nil then
                states[step] = savestate.create()
            end
            savestate.save(states[step])
        end
        xcoord = math.floor((memory.readword(0x7e07a8) + memory.readword(0x7e0a91)+16)/32)
        ycoord = math.floor((memory.readword(0x7e07b0) + memory.readword(0x7e0a94)+16)/32)
        if optimalpaths[step] == nil then
            optimalpaths[step] = {}
        end
        if not replay then
            npaths[step] = 0
            for i=1,4 do
                optimalpaths[step][i] = isoptimal(xcoord+dx[i],ycoord+dy[i],xcoord,ycoord,distance)
                npaths[step] = npaths[step] + (optimalpaths[step][i] and 1 or 0)
            end
        end
        if stopped[step] then
            replay = false
        end
        if optimalpaths[step][pathdir[step-1]] then
            dir=pathdir[step-1]
        elseif optimalpaths[step][1+XOR(pathdir[step-1]-1,2)] then
            dir=1+XOR(pathdir[step-1]-1,2)
        elseif optimalpaths[step][1+XOR(pathdir[step-1]-1,3)] then
            dir=1+XOR(pathdir[step-1]-1,3)
        elseif optimalpaths[step][1+XOR(pathdir[step-1]-1,1)] then
            dir=1+XOR(pathdir[step-1]-1,1)
        else
            break
        end
        pathdir[step] = dir
        keys = {[directions[dir]]=true}
        for i=1,16 do
            joypad.set(1,keys)
            nextframe()
        end
        if memory.readbyte(0x7e0722) == 2 then
            repeat
                stopped[step] = true
                optimalpaths[step][pathdir[step]] = false
                npaths[step] = npaths[step] - 1
                step = step - 1
            until step == 0 or npaths[step+1] ~= 0
            step = savestateinterval * math.floor(step/savestateinterval)
            savestate.load(states[step+1])
            replay = true
        else
            stopped[step] = false
        end
    until xcoord == xdest and ycoord == ydest
    snes9x.speedmode("normal")
    snes9x.pause()
end

while true do nextframe() end