Maze AI

--By xXxMoNkEyMaNxXx (Whitemambaa)
--annoying autocomplete fixers: doz

--[[
    ********************************************
    **BUILD A MAZE AND PLACE THE TURTLE INSIDE**
    ********************************************

    The finish should be marked by a block in
    the floor that is different from the rest of
    the maze, and that same block type should be
    placed in slot 1.  You can put fuel in any
    other slots.  The turtle will explore the
    maze completely, then go back to the start
    to do a SPEED RUN!  It will then wander to
    random nodes.

    *************
    **HAVE FUN!**
    *************
--]]

---[[
if not turtle then
    math.randomseed(os.time())
    math.random()

    local fuel=0
    turtle={
        getFuelLevel=function() return math.random()*1000 end,
        compareDown=function() return math.random()<0.001 end,
        detect=function() return math.random()<0.51 end,
        up=function() fuel=fuel-1 return true end,
        down=function() fuel=fuel-1 return true end,
        forward=function() fuel=fuel-1 return true end,
        back=function() fuel=fuel-1 return true end,
        turnLeft=function() return true end,
        turnRight=function() return true end,
        refuel=function(n) fuel=fuel+n return true end,
        select=function() return true end,
        getItemCount=function(s) return 64 end,
    }

    sleep=function() end
end
--]]

local tick=os.clock

local next=next
local abs=math.abs
local max=math.max
local min=math.min

local insert=table.insert
local remove=table.remove

--Stolen from my vec.lua--
local vec={}
function vec.add(a,b)
    local new={}
    for d=1,max(#a,#b) do
        new[d]=(a[d] or 0)+(b[d] or 0)
    end
    return new
end
function vec.sub(a,b)
    local new={}
    for d=1,max(#a,#b) do
        new[d]=(a[d] or 0)-(b[d] or 0)
    end
    return new
end
function vec.tostring(a)
    local new=tostring(a[1])
    for d=2,#a do
        new=new..", "..tostring(a[d])
    end
    return new
end
--------------------------
local function distance(v3a,v3b)
    local dx,dy,dz=v3b[1]-v3a[1],v3b[2]-v3a[2],v3b[3]-v3a[3]
    return abs(dx*dx)+abs(dy*dy)+abs(dz*dz)
end

local start=1
local finish

local nodes={{0,0,0}}
local links={{}}--Adjacent nodes indexed by direction
local state={}--Exploring state of the node
local known=0--Number of nodes that have no unexplored adjacent nodes

local pos=1
local dir=1

local units={{0,0,1},{-1,0,0},{0,0,-1},{1,0,0}}
local unitNames={"N","W","S","E"}

local function getDir(a,b)
    local d=vec.sub(b,a)
    if d[1]==1 then
        return 4
    elseif d[3]==1 then
        return 1
    elseif d[1]==-1 then
        return 2
    elseif d[3]==-1 then
        return 3
    end
end

local function getRealFuel()
    local f=turtle.getFuelLevel()
    return type(f)=="number" and f or math.huge
end

local function refuel(req)
    while getRealFuel()<req do
        for s=2,16 do
            if turtle.getItemCount(s)>0 then
                turtle.select(s)
                turtle.refuel(1)
            end
        end
        sleep(1)
    end
    turtle.select(1)
end

local function update(jumps,nodeId)
    local dis=jumps[nodeId]+1
    local addToQueue={}
    for _,i in next,links[nodeId] do
        if not jumps[i] or jumps[i]>dis then
            jumps[i]=dis
            addToQueue[#addToQueue+1]=i
        end
    end
    return addToQueue
end

local function jumpMap(pos,nodeId)--Non-recursive pathfinding ;)
    local point=nodes[pos]
    local jumps={[nodeId]=0}
    local queue={nodeId}
    local best=math.huge
    repeat
        local b,q=math.huge
        for i=1,#queue do
            local j=queue[i]
            local dis=distance(nodes[j],point)+jumps[j]
            if jumps[pos] then
                if dis<best then
                    best,q=dis,i
                end
            elseif dis<b then
                b,q=dis,i
                if b<best then
                    best=b
                end
            end
        end
        if q then
            local addToQueue=update(jumps,remove(queue,q))
            for i=1,#addToQueue do
                queue[#queue+1]=addToQueue[i]
            end
        else
            break
        end
    until #queue==0
    return jumps
end

local function register(node,parent)
    local p=nodes[parent]
    for i=1,#nodes do
        local n=nodes[i]
        if n[1]==node[1] and n[2]==node[2] and n[3]==node[3] then
            links[i][getDir(n,p)]=parent
            links[parent][getDir(p,n)]=i
            return not state[i]
        end
    end
    local i=#nodes+1
    nodes[i]=node
    links[i]={}
    links[i][getDir(node,p)]=parent
    links[parent][getDir(p,node)]=i
    return true
end

local function turn(turns)-- + is Left
    while turns>0 do
        if turtle.turnLeft() then
            turns=turns-1
            dir=dir%4+1
        end
    end
    while turns<0 do
        if turtle.turnRight() then
            turns=turns+1
            dir=(dir-2)%4+1
        end
    end
end

local function f(d)
    turn((d-dir+2)%4-2)
    repeat refuel(1) until turtle.forward()
    pos=links[pos][(d-1)%4+1]
end

local function b(d)
    turn((d-dir+2)%4-2)
    repeat refuel(1) until turtle.back()
    pos=links[pos][(d+1)%4+1]
end

print'There is a finish... right?'

print"I'll start exploring. Brb"
do
    local t0=tick()
    while known<#nodes do--Even though known will not be filled in in ascending order, this will only be true when the whole maze has been explored.
        if not state[pos] then
            turn(1)
            state[pos]=-1
            if not turtle.detect() and register(vec.add(nodes[pos],units[dir]),pos) then--Could be logically simpler, but the program would register walls.
                f(dir)
            end
        elseif state[pos]==-1 then
            turn(-1)
            state[pos]=0
            if not turtle.detect() and register(vec.add(nodes[pos],units[dir]),pos) then
                f(dir)
            end
        elseif state[pos]==0 then
            turn(-1)
            state[pos]=1
            if not turtle.detect() and register(vec.add(nodes[pos],units[dir]),pos) then
                f(dir)
            end
        elseif state[pos]==1 then
            if turtle.compareDown() then
                if finish then
                    print'I found the... other finish'
                else
                    finish=pos
                    print'I found the finish!'
                end
            end
            turn(1)
            state[pos]=true
            known=known+1
            if pos~=start then
                b(dir)
            end
        else
            print'Uh, what am I doing here?'
            print"Whatever, I'll throw some crazy error."
            error"[SEVERE] YO MAMA's SO FAT THAT SHE ACQUIRED PRIORITY OVER ALL OTHER PROCESSES."
        end
    end
    local dt=tick()-t0
    if finish then
        print("Exploring took "..dt.." second"..(dt==1 and "" or "s")..".")
    else
        print"There's no finish you bastard!"
        error'No finish'
    end
end

sleep(2)
print'Time for a speed-run!'
sleep(1.5)
for i=3,1,-1 do
    print(i)
    sleep(1)
end
print'Go!'

do
    local t0=tick()
    print'Calculating...'
    local jumps=jumpMap(pos,finish)
    local t1=tick()
    if jumps[pos] then
        print("Optimal path found. ("..t1-t0.."s)  Lol, umad?")
        while pos~=finish do
            local best,v
            for d,i in next,links[pos] do
                if jumps[i] and (not best or jumps[i]<best) then
                    best,v=jumps[i],d
                end
            end
            f(v)-- :D
        end
        local dt=tick()-t1
        print("WINNER!  "..dt.." SECOND"..(dt==1 and "" or "S")..", A NEW RECORD!  THE CROWD GOES WIIIIILD!")
    else
        print("No path found... ummm, this shouldn't happen.")
    end
end

turtle.up()
turtle.up()
turtle.turnLeft()
turtle.turnRight()
turtle.up()
turtle.down()
turtle.turnRight()
turtle.turnLeft()
sleep(10)
turtle.down()
turtle.down()

print'Wandering.'

repeat
    local target=math.random(#nodes)
    print("Moving to node "..target..".")
    local jumps=jumpMap(pos,target)
    if jumps[pos] and pos~=target then
        repeat
            local best,v
            for d,i in next,links[pos] do
                if jumps[i] and (not best or jumps[i]<best) then
                    best,v=jumps[i],d
                end
            end
            f(v)-- :D
        until pos==target
    end
until nil