7th Saga Pathing RNG

--Nitrodon's 7th Saga A* algorithm to walk between towns and avoid encounters, modified by Kirkq to choose varying paths and tend towards the extremes more often and record RNG values to force more or less incrementing.

local xdest = 170
local ydest = 52
local savestateinterval

--Melenam: 156,252
--Palsu: 120,234
--Gorfun: 170,52
--Guanas: 100,88

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

--

local randomnum

local RNGTable = {}
local RNGStart = 256*memory.readbyte(0x7e006E) + memory.readbyte(0x7e006C)
local RNGValue = RNGStart
local TableLength = 3500 -- Length of RNG Table, make larger for longer distances.
local TableLoopCount = 0

local TableBreak
local RNGEnd
local BestRNGAmt = 6000  --Amount of RNGs passed  (set high/low for initial comparison)

local tempstate = {}
local value

local scriptloop = 0
local scriptlooplimit = 10 -- how many times to run to completion

local xtotal
local ytotal
local distotal
local xtendency

local CurrAttemptLoads
local MaxAttemptLoads = 160 -- how many times to try a certain attempt

moviefile = "MemDump.vbm"
dumpfile = moviefile..".dump"
io.output(dumpfile)

value = 5   -- Call optimal state as State5
tempstate[value] = savestate.create()
savestate.save(tempstate[value])
value = 0  --  Call base state as state 0
tempstate[value] = savestate.create()
savestate.save(tempstate[value])


while TableLoopCount < TableLength do   ---makes a table of RNG values 0 to table length
    RNGTable[TableLoopCount] = RNGValue
    RNGValue = RNGValue*899 - 65536*(math.floor(RNGValue*899/65536))
    TableLoopCount = TableLoopCount + 1
end
--RNG*899 mod 65536



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()
    gui.text(0,0,"RNG1: " .. memory.readbyte(0x7E006C))
    gui.text(0,10,"RNG2: " .. memory.readbyte(0x7E006E))
    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 scriptloop < scriptlooplimit do
    CurrAttemptLoads = 0
    savestateinterval = math.random(20)
    if savestateinterval < 6 then
    savestateinterval = savestateinterval + 5
    end

    value = 0
    savestate.load(tempstate[value])

    nextframe()

    value = 0
    savestate.load(tempstate[value])

    randomnum = math.random(100)
    xtendency = randomnum
    if xtendency < 5 then   ---prev 5
    xtendency = xtendency + 5  ---prev 5
    elseif xtendency > 95 then  ----prev 95
    xtendency = xtendency - 5    ---prev 5
    end

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


        xcoord = math.floor((memory.readword(0x7e07a8) + memory.readword(0x7e0a91)+16)/32)
        ycoord = math.floor((memory.readword(0x7e07b0) + memory.readword(0x7e0a94)+16)/32)
    xtotal = xdest - xcoord
    ytotal = ydest - ycoord

    if xtotal < 0 then
    xtotal = -1*xtotal
    end
    if ytotal < 0 then
    ytotal = -1*xtotal
    end
    distotal = xtotal + ytotal

    xtotal = xdest - xcoord  --recalc
    ytotal = ydest - ycoord



    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 replay then
    dir = pathdir[step]

    else



        randomnum = math.random(100)
        --xtotal positive = walk right
        --ytotal positive = walk up
        -- xtendency = 75%

        if randomnum < xtendency then
            if xtotal >= 0 then
            randomnum = 4
            else
            randomnum = 3
            end
        else  -- if ytendency
            if ytotal <=0 then   ---should be less than
            randomnum = 1
            else
            randomnum = 2
            end
        end




        --determines directions below
        --1=up 2=down 3=left 4=right--------------------------------------

        --Would do well to associate weighted probabilities based on how many
        --steps are being taken in each direction.  I can implement this later.

        if randomnum == 1 then
            if optimalpaths[step][1] then
            dir=1
            elseif optimalpaths[step][2] then
            dir=2
            elseif optimalpaths[step][3] then
            dir=3
            elseif optimalpaths[step][4] then
            dir=4
            end

        elseif randomnum == 2 then
            if optimalpaths[step][2] then
            dir=2
            elseif optimalpaths[step][1] then
            dir=1
            elseif optimalpaths[step][4] then
            dir=4
            elseif optimalpaths[step][3] then
            dir=3
            end

        elseif randomnum == 3 then
            if optimalpaths[step][3] then
            dir=3
            elseif optimalpaths[step][4] then
            dir=4
            elseif optimalpaths[step][1] then
            dir=1
            elseif optimalpaths[step][2] then
            dir=2
            end

        elseif randomnum == 4 then
            if optimalpaths[step][4] then
            dir=4
            elseif optimalpaths[step][3] then
            dir=3
            elseif optimalpaths[step][2] then
            dir=2
            elseif optimalpaths[step][1] then
            dir=1
            end
        end



        end





        pathdir[step] = dir
        keys = {[directions[dir]]=true}
        for i=1,16 do
        gui.text(0,20,"X Tendency" .. xtendency)
        gui.text(0,30,"CurrAttemptLoads" .. CurrAttemptLoads)
        gui.text(0,40,"Trial Number" .. scriptloop)
        gui.text(0,50,"savestateinterval" .. savestateinterval)
            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
        CurrAttemptLoads = CurrAttemptLoads + 1
        else
            stopped[step] = false
        end
    until ((xcoord == xdest and ycoord == ydest) or (CurrAttemptLoads>=MaxAttemptLoads))


    for i =1,3 do
    nextframe()
    end

    RNGEnd = 256*memory.readbyte(0x7e006E) + memory.readbyte(0x7e006C)

    TableLoopCount = 0   --  Can be edited to later
    TableBreak = 0
    while TableLoopCount < TableLength and TableBreak == 0 do
        TableLoopCount = TableLoopCount+1
        if RNGEnd == RNGTable[TableLoopCount] then
            TableBreak = 1
        end
    end

    if CurrAttemptLoads < MaxAttemptLoads then
    if BestRNGAmt > TableLoopCount then  ---change sign depending on whether you want more or less, and change value of TableLoopCount to large or 0.
        BestRNGAmt = TableLoopCount  --Note: if this gives back the initial TableLoopCount, it is off the chart.
        value = 5
        savestate.save(tempstate[value])

        ----pathdir[step] contain all steps 0 to n
        while step > 0 do
            io.write(pathdir[step]," ")   --writes in steps backwards**
            step = step-1
        end
        io.write(BestRNGAmt)
        io.write("\n")

    end
    end


scriptloop = scriptloop + 1

end

    value = 5
    savestate.load(tempstate[value])

    snes9x.speedmode("normal")
    snes9x.pause()

    for i =1,3 do
    nextframe()
    end

while true do nextframe() end