losrange = 7
    fielddim = losrange*2

    pillardancing = false

    dance_direction = nil
    dance_direction_num = nil
    next_move = nil
    pillar_center = {nil,nil}
    walk_path = {[-1]={},[1]={}}

    order_diag = { {-1,-1}, {0,-1}, {1,-1}, {1,0}, {1,1}, {0,1}, {-1,1}, {-1,0} }
    moves_diag = { "y", "h", "b", "j", "n", "l", "u", "k" }
    order_adja = { {-1,0}, {0,1}, {1,0}, {0,-1} }

    pseudomonsters = { ["fungus"]=true, ["plant"]=true }

    function rotate_forward(what) table.insert(what,#what,table.remove(what,1)) end
    function rotate_backward(what) table.insert(what,1,table.remove(what,#what)) end
    function contains(t,what)
        for _,f in pairs(t) do if f ~= nil and f == what then return true end end
        return false
    end

    function pv(v) return type(v) == "table" and "("..tostring(v[1])..","..tostring(v[2])..")" or tostring(v) end
    function vector_out_of_bounds(v,range) return math.abs(v[1]) > range or math.abs(v[2]) > range end
    function tile_at_vector(v) return pillar_fov[v[1]][v[2]] end
    function set_tile_at_vector(v,t) pillar_fov[v[1]][v[2]] = t end
    function feature_at_vector(v) return view.feature_at(v[2],v[1]) end
    function monster_at_vector(v) return monster.get_monster_at(v[2],v[1]) end
    function exclude_at_vector(v) travel.set_exclude(v[2],v[1],0) end
    function unexclude_at_vector(v) travel.del_exclude(v[2],v[1]) end

    function vector_field(v1,v2)
        vectorfield = {}
        for y=v1[1],v1[2] do for x=v2[1],v2[2] do vectorfield[#vectorfield+1] = {y,x} end end
        return vectorfield
    end
    los_vectorfield = vector_field({-losrange,losrange},{-losrange,losrange})
    field_vectorfield = vector_field({-fielddim,fielddim},{-fielddim,fielddim})
    function vector_field_offset(field,offset)
        vectorfield_new = {}
        for _,v in pairs(field) do
            vectorfield_new[#vectorfield_new+1] = vector_add(v,offset)
        end
        return vectorfield_new
    end
    function vector_equal(v1,v2) return v1[1] == v2[1] and v1[2] == v2[2] end
    function vector_copy(v) return {v[1],v[2]} end
    function vector_neg(v) return {-v[1],-v[2]} end
    function vector_add(v1,v2) return {v1[1]+v2[1],v1[2]+v2[2]} end
    function vector_sub(v1,v2) return {v1[1]-v2[1],v1[2]-v2[2]} end
    function vector_redir(v,dir) return {v[1]*dir[1],v[2]*dir[2]} end
    function vector_cross(v1,v2) return v1[1] * v2[2] - v1[2] * v2[1] end
    function vector_abs(v) return math.sqrt(v[1]^2+v[2]^2) end
    function vector_coordabs(v) return {math.abs(v[1]),math.abs(v[2])} end
    function vector_angle(v1,v2) return math.atan(vector_cross(v1,v2) / (vector_abs(v1) * vector_abs(v2))) end

    function all_fields_in(vectorfield,what)
        r = {}
        for _,v in pairs(vectorfield) do if what[tile_at_vector(v)] ~= nil then r[#r+1] = v end end
        return r
    end

    function not_fields_in(vectorfield,what)
        r = {}
        for _,v in pairs(vectorfield) do if what[tile_at_vector(v)] == nil then r[#r+1] = v end end
        return r
    end

    function get_dance_direction(move,pillar_offset)
        if pillar_offset == nil then pillar_offset = {0,0} end
        rawdir = vector_cross(vector_sub(pillar_center,pillar_offset),move)
        return rawdir ~= 0 and rawdir / math.abs(rawdir) or 0
    end

    function init_fov()
        pillar_fov = {}
        for _,v in pairs(vector_field({-fielddim,fielddim},{-fielddim,fielddim})) do
            if pillar_fov[v[1]] == nil then pillar_fov[v[1]] = {} end
            set_tile_at_vector(v,"0")
            if not vector_out_of_bounds(v,losrange) then
                f = feature_at_vector(v)
                mon = monster_at_vector(v)
                if f == nil or not travel.feature_traversable(f) or (mon and pseudomonsters[mon:name()] == true) then set_tile_at_vector(v,"1") end
            end
        end
        set_tile_at_vector({0,0},"x")
    end

    function shift_fov(next_move)
        a=crawl.call_dlua("return crawl.millis()")
        set_tile_at_vector({0,0},"p")
        new_fov = {}
        for _,v in pairs(vector_field({-fielddim,fielddim},{-fielddim,fielddim})) do
            vn = vector_sub(v,next_move)
            if not vector_out_of_bounds(vn,fielddim) then
                if new_fov[vn[1]] == nil then new_fov[vn[1]] = {} end
                new_fov[vn[1]][vn[2]] = tile_at_vector(v)
            end
        end
        pillar_fov = new_fov
        for _,v in pairs(vector_field({-fielddim,fielddim},{-fielddim,fielddim})) do
            if pillar_fov[v[1]] == nil then pillar_fov[v[1]] = {} end
            if tile_at_vector(v) == nil then set_tile_at_vector(v,"0") end
        end
        set_tile_at_vector({0,0},"x")
        c=crawl.call_dlua("return crawl.millis()")
        p(c-a)
    end

    function floodfill(v)
        set_tile_at_vector(v,"?")
        for _,move in pairs(order_adja) do
            vn = vector_add(v,move)
            if vector_out_of_bounds(vn,losrange) then
                set_tile_at_vector(v,"!")
                return false
            end
            if tile_at_vector(vn) == "1" and not floodfill(vn) then
                set_tile_at_vector(v,"!")
                return false
            end
        end
        if tile_at_vector(v) == "?" then
            set_tile_at_vector(v,"P")
            return true
        end
    end

    function path_recursion(step,origin,path)
        neworigin = vector_add(origin,step)
        for _,vn in pairs(all_fields_in(vector_field_offset(order_diag,neworigin),{["p"]=true,["x"]=true})) do
            vn = vector_sub(vn,neworigin)
            if not vector_equal(vn,vector_neg(step)) then
                continue = vector_copy(vn)
                dir = get_dance_direction(continue,neworigin)
                continue[3] = dir
            end
        end
        path[#path+1] = continue
        if tile_at_vector(vector_add(neworigin,continue)) == "x" then
            return path
        else
            return path_recursion(continue,neworigin,path)
        end
    end

    function find_dir_of_path(step)
        walk_path = {[-1]={},[1]={}}
        path = path_recursion(step,{0,0},{step})
        dirsum = 0
        for _,step in pairs(path) do dirsum = dirsum + step[3] end
        return dirsum / math.abs(dirsum), path
    end

    function draw_path()
        for _,v in pairs(all_fields_in(los_vectorfield,{["P"]=true})) do
            for _,vn in pairs(not_fields_in(vector_field_offset(order_adja,v),{["P"]=true})) do
                set_tile_at_vector(vn,"p")
            end
        end
        set_tile_at_vector({0,0},"x")
    end

    function calculate_path()
        possible_moves = {}
        for i,v in pairs(all_fields_in(order_diag,{["p"]=true})) do
            dir = get_dance_direction(v)
            possible_moves[#possible_moves+1] = {v[1],v[2],dir}
        end
        d1, p1 = find_dir_of_path(possible_moves[1])
        d2, p2 = find_dir_of_path(possible_moves[2])
        if d1 == d2 then
            crawl.mpr("Couldn't determine path directions, this shouldn't happen!")
            StopPillardancing()
        else
            for _,v in pairs(p1) do walk_path[d1][#walk_path[d1]+1] = {v[1],v[2],d1} end
            for _,v in pairs(p2) do walk_path[d2][#walk_path[d2]+1] = {v[1],v[2],d2} end
        end
    end

    function fill_pillar()
        for _,v in pairs(all_fields_in(los_vectorfield,{["p"]=true})) do
            surrounded = true
            for _ in pairs(not_fields_in(vector_field_offset(order_adja,v),{["p"]=true,["P"]=true,["x"]=true,["!"]=true})) do surrounded = false break end
            if surrounded then set_tile_at_vector(v,"P") end
        end
    end

    function tendril(v,dv)
        for d=1,losrange*2 do
            vn = vector_add(v,vector_redir({d,d},dv))
            if vector_out_of_bounds(vn,losrange-1) then break end
            tile = tile_at_vector(vn)
            if (tile ~= "0" and tile ~= "p") or (tile == "p" and d == 1) then break end
            if tile == "p" then for dn=1,d do
                set_tile_at_vector(vector_add(v,vector_redir({dn,dn},dv)),"p")
                return true
            end end
        end
    end

    function next_to_pillar()
        for _,v in pairs(all_fields_in(order_diag,{["1"]=true})) do
            if floodfill(v) then return v end
            init_fov()
        end
        return nil
    end

    function monsters_at(move)
        ybound = {-losrange,losrange}
        xbound = {-losrange,losrange}

        if move[1] < 0 then ybound[2] = -1
        elseif move[1] > 0 then ybound[1] = 1 end
        if move[2] < 0 then xbound[2] = -1
        elseif move[2] > 0 then xbound[1] = 1 end
        for _,v in pairs(all_fields_in(vector_field(ybound,xbound),{["0"]=true,["p"]=true})) do
            mon = monster_at_vector(v)
            --travel.set_exclude(x,y,0)
            if mon and not mon:is_safe() then
                return true
            end
        end
        return false
    end

    function calculate_next_pillar_step()
        if dance_direction_num ~= nil then
            possible_moves = {walk_path[dance_direction_num][1],walk_path[dance_direction_num*-1][1]}
        else
            possible_moves = {walk_path[-1][1],walk_path[1][1]}
        end
        goodmove = nil
        for _,move in pairs(possible_moves) do
            goodmove = move
            if monsters_at(move) then
                if dance_direction_num ~= nil and move[3] == dance_direction_num then dance_direction_num = dance_direction_num*-1 end
                goodmove = nil
            else
                break
            end
        end
        if goodmove ~= nil then
            travel.del_exclude(goodmove[2], goodmove[1])
            return goodmove
        else
            crawl.mpr("No suitable move found!")
            StopPillardancing()
            return nil
        end
    end

    function next_pillar_step()
        for i,c in pairs(order_diag) do if vector_equal(c,next_move) then
                crawl.sendkeys(moves_diag[i])
                break
        end end
        pillar_center = vector_sub(pillar_center,next_move)
        shift_fov(next_move)
        rotate_forward(walk_path[next_move[3]])
        rotate_backward(walk_path[next_move[3]*-1])
        next_move = nil
    end

    function Pillardance()
        a=crawl.call_dlua("return crawl.millis()")
        if not pillardancing then
            pillardancing = true
            init_fov()
            p(crawl.call_dlua("return crawl.millis()"))
            b=crawl.call_dlua("return crawl.millis()")
            pillar_pos = next_to_pillar()
            if pillar_pos == nil then
                crawl.mpr("No pillar found!")
                pillardancing = false
                return false
            end
            draw_path()
            p(crawl.call_dlua("return crawl.millis()"))
            c=crawl.call_dlua("return crawl.millis()")
            fill_pillar()
            p(crawl.call_dlua("return crawl.millis()"))
            d=crawl.call_dlua("return crawl.millis()")
            --for _,v in pairs(all_fields_in(los_vectorfield,{["p"]=true,["x"]=true})) do for _,dv in pairs(order_diag) do tendril(v,dv) end end
            --fill_pillar()
            p(crawl.call_dlua("return crawl.millis()"))
            e=crawl.call_dlua("return crawl.millis()")
            for _,v in pairs(all_fields_in(los_vectorfield,{["p"]=true,["x"]=true})) do exclude_at_vector(v) end
            p(crawl.call_dlua("return crawl.millis()"))
            f=crawl.call_dlua("return crawl.millis()")
            pillar_center = {0, 0}
            vectorcount = 0
            --for y=-losrange,losrange do for x=-losrange,losrange do if pillar_fov[y][x] == "P" then
            --      pillar_center = {pillar_center[1] + y, pillar_center[2] + x}
            --      vectorcount = vectorcount + 1
            --end end end
            for _,v in pairs(all_fields_in(los_vectorfield,{["P"]=true})) do
                    pillar_center = {pillar_center[1] + v[1], pillar_center[2] + v[2]}
                    vectorcount = vectorcount + 1
            end
            pillar_center = {pillar_center[1] / vectorcount, pillar_center[2] / vectorcount}
            p(crawl.call_dlua("return crawl.millis()"))
            g=crawl.call_dlua("return crawl.millis()")
            calculate_path()
            p(crawl.call_dlua("return crawl.millis()"))
            h=crawl.call_dlua("return crawl.millis()")
            next_move = calculate_next_pillar_step()
            p(crawl.call_dlua("return crawl.millis()"))
            i=crawl.call_dlua("return crawl.millis()")
            if next_move == nil then return false end
            dance_direction_num = get_dance_direction(goodmove)
            dance_direction = dance_direction_num > 0 and "clockwise" or "counterclockwise"
            crawl.mpr("Dancing "..dance_direction.."!")
            p(crawl.call_dlua("return crawl.millis()"))
            j=crawl.call_dlua("return crawl.millis()")
            p("init:"..b-a..",draw:"..c-b..",fill:"..d-c..",tendril:"..e-d..",exclude:"..f-e..",center:"..g-f..",calc:"..h-g..",next:"..i-h..",done:"..j-i..",total:"..j-a)
        else
            if next_move ~= nil then
                next_pillar_step()
            else
                next_move = calculate_next_pillar_step()
                exclude_at_vector({0,0})
                crawl.redraw_screen()
            end
        end
        --for y=-fielddim,fielddim do
        --  ls = ""
        --  for x=-fielddim,fielddim do
        --      ls = ls .. pillar_fov[y][x]
        --  end
        --  dmsg(pad(y,3), ls)
        --end
    end

    function StopPillardancing()
        if pillardancing then
            for _,v in pairs(all_fields_in(field_vectorfield,{["p"]=true,["x"]=true})) do unexclude_at_vector(v) end
            pillardancing = false
            dance_direction = nil
            dance_direction_num = nil
            next_move = nil
            pillar_center = {nil,nil}
            walk_path = {[-1]={},[1]={}}
        end
    end