BFS Pico 8

pico-8 cartridge // http://www.pico-8.com
version 32
__lua__
-- pico-8 bfs search using map flags
-- david mcquillan @geeitsomelaldy
grid = {}
path = nil
cost_values = nil
cycles = 0
cursor_x,cursor_y = 1,1
point = {{0,0},{0,0}}
index = 1
grid_size = {0,0,32,32}
function _init()
    grid = build_pathfinding_grid(unpack(grid_size))
end

function _update60()
    if btnp(0) then
    cursor_x -= 1
    end
    if btnp(1) then
     cursor_x += 1
    end
    if btnp(2) then
    cursor_y -= 1
    end
    if btnp(3) then
    cursor_y += 1
    end
    if(btnp(4)) then
        point[index] = {cursor_x,cursor_y}
        if(index == 1)
        then
            index = 2
        else
            path,cost_values,cycles = grid:get_path_to(point[1],point[2])
            index = 1
        end
    end
    if(btnp(5)) then
        point[2] = {cursor_x,cursor_y}
        path,cost_values,cycles = grid:get_path_to(point[1],point[2])
        index = 1
    end
end
function _draw()
        draw_grid()
    camera(0,0)
    po(stat(7) .. " fps",2,38)
    if(cost_values != nil) then
        po(cycles .. " cycles",2,47)
    end
    if(path != nil) then
        po("#path = " .. #path,2,54,9)
    end
    pset(point[1][1]+1,point[1][2]+1,9)
    pset(point[2][1]+1,point[2][2]+1,9)


    camera(mid(-32,cursor_x*8 -64,128),mid(0,cursor_y*8-64,128))
    spr(3,cursor_x*8,cursor_y*8)
    spr(4,point[1][1]*8,point[1][2]*8)
    spr(5,point[2][1]*8,point[2][2]*8)

end
function po(t,x,y,c1,c2)
    print(t,x+1,y+1,c2 or 0)
    print(t,x+1,y-1,c2 or 0)
    print(t,x-1,y+1,c2 or 0)
    print(t,x-1,y-1,c2 or 0)
    print(t,x+1,y,c2 or 0)
    print(t,x-1,y,c2 or 0)
    print(t,x,y+1,c2 or 0)
    print(t,x,y-1,c2 or 0)
    print(t,x,y,c1 or 7)
end
function draw_grid()
    cls(0)
    camera(mid(-32,cursor_x*8 -64,128),mid(0,cursor_y*8-64,128))
    map(grid_size[1],grid_size[2],0,0,grid_size[3],grid_size[4])
    if(path != nil) then
        for  pi = 2, #path do
            line(path[pi][1]*8 +4,path[pi][2]*8 +4,path[pi-1][1]*8 +4,path[pi-1][2]*8 +4,2)
        end
        for  pi = 1, #path do
            print(cost_values[path[pi]],path[pi][1]*8,path[pi][2]*8,7)
        end
    end
    camera(0,0)
    for ix = 1,#grid do
        for iy = 1,#grid[ix] do
            pset(ix,iy,grid[ix][iy] and 11 or 8)
        end
    end
    if(cost_values != nil) then
        for k,v in pairs(cost_values) do
            pset(k[1]+1,k[2]+1,3)
        end
    end
    if(path != nil) then
        for  pi = 1, #path do
            pset(path[pi][1]+1,path[pi][2]+1,2)
        end
    end

end
-->8
--astar
function build_pathfinding_grid(mx,my,mw,mh)
    local grid = {}
    for ix = mx,mx+mw-1 do
        local row = {}
        for iy = my,my+mh-1 do
            local m = mget(ix,iy)
            local issolid = fget(m,solid)
            add(row,not(issolid))
        end
        add(grid,row)
    end
    local get_path = function(came_from,endnode)
        local path = {}
        add(path,endnode)
        local next = came_from[endnode]
        while(next != nil) do
            add(path,next)
            next = came_from[next]
        end
        return path
    end
    local ref={}
    grid.get_node_reference = function(self,x,y) -- cache references to nodes so we're passing around objects, not strings
        if(ref[x] == nil) ref[x] = {}
        if(ref[x][y] == nil) ref[x][y] = {x,y}
        return ref[x][y]
    end
    grid.is_node = function(self, x,y)
        return self[x+1] and self[x+1][y+1]
    end
    grid.get_neighbours = function(self,point)
        local neighbours = {}
        if(self:is_node(point[1],point[2]+1)) add(neighbours,self:get_node_reference(point[1]  ,point[2]+1))
        if(self:is_node(point[1],point[2]-1)) add(neighbours,self:get_node_reference(point[1]  ,point[2]-1))
        if(self:is_node(point[1]+1,point[2])) add(neighbours,self:get_node_reference(point[1]+1,point[2]  ))
        if(self:is_node(point[1]-1,point[2])) add(neighbours,self:get_node_reference(point[1]-1,point[2]  ))
        return neighbours
    end
    grid.get_path_to = function(self,p1,p2)
        if(self:is_node(p1[1],p1[2]) and self:is_node(p2[1],p2[2])) then
            return self:find_nearest(p1[1],p1[2],{p2})
        end
        return nil
    end
    grid.find_nearest = function(self, sx,sy, destinations)
        local start = self:get_node_reference(sx,sy)
        local frontier = {start}
        local came_from = {}
        local cost_so_far = {}
        local current = nil
        came_from[start] = nil
        cost_so_far[start] = 0
        local f = 0
        while #frontier > 0 do
            current = queue_get(frontier)
            local neighbours = self:get_neighbours(current)
            for ni = 1,#neighbours do
                local n = neighbours[ni]
                if(cost_so_far[n] == nil) then
                    add(frontier,n)
                    came_from[n] = current
                    cost_so_far[n] = cost_so_far[current] + 1
                    f+=1
                    if(f > 1000) then --timeout check
                        return nil
                    end
                    if(contains_comp(destinations, function(v,i,a)
                        return v[1] == n[1] and v[2] == n[2]
                    end)) then
                        return get_path(came_from,n),cost_so_far,f
                    end
                end
            end
        end
        return nil
    end

    return grid
end

function queue_get(q)
    local r = q[1]
    del(q,r)
    return r
end
function contains_comp(arr,comp)
    for ri = 1,#arr do

        if comp(arr[ri],ri,arr) then
            return true
        end
    end
    return false
end
function index_of(arr,item)
    for ri = 1,#arr do

        if arr[ri] == item then
            return ri
        end
    end
    return -1
end
function fully_unpack(table,p)
    local s = ""
    local tabs = p or ""
    for k,v in pairs(table) do
        if( type(k) == "table" ) then
            k = fully_unpack(k)
        end
        if( type(v) == "table" ) then
            s ..= tabs .."["..k.."] = {\n".. fully_unpack(v,tabs .. "\t")..tabs.."\n},\n"
        else
        s ..= tabs .."["..k.."] = "..v..",\n"