аоооооооооооооооооооооооооооооооо""""""""""""""""""""""""""""""""™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™ЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄffffffffffffffffffffffffffffffff33333333333333333333333333333333 >А?оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо""""ЄЄЄЄоооооооооооо""""ЄЄЄЄоооооооооооо""""ЄЄЄЄоооооооооооо""""ЄЄЄЄоооооооооооо""""ЄЄЄЄоооооооооооо""""ЄЄЄЄоооооооооооо""""ЄЄЄЄоооооооооооо""""ЄЄЄЄоооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооо™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооо™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооо™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооо™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооо™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооо™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооо™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооо™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооо™™™™оооо™™™™ЄЄЄЄоооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооо™™™™оооо™™™™ЄЄЄЄоооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооо™™™™оооо™™™™ЄЄЄЄоооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооо™™™™оооо™™™™ЄЄЄЄоооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооо™™™™оооо™™™™ЄЄЄЄоооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооо™™™™оооо™™™™ЄЄЄЄоооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооо™™™™оооо™™™™ЄЄЄЄоооооооооооооооооооооооо™™™™ЄЄЄЄоооооооооооооооооооооооо™™™™оооо™™™™ЄЄЄЄоооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™ЄЄЄЄооооffffоооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™ЄЄЄЄооооffffоооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™ЄЄЄЄооооffffоооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™ЄЄЄЄооооffffоооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™ЄЄЄЄооооffffоооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™ЄЄЄЄооооffffоооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™ЄЄЄЄооооffffоооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™ЄЄЄЄооооffffоооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо^ -- title: Greedy Best-First Search -- author: Jeremy Miller -- desc: Greedy best-first search visualized -- script: lua -- sprites FLOOR=0 WALL=1 START=2 VISITED=3 QUEUED=4 GOAL=5 PATH=6 -- buttons A=4 MAP_WIDTH=30 MAP_HEIGHT=17 function init() queue={} visited={} goal={ x=28, y=15, } start={ x=1, y=1, visited=false, parent=nil, score=0, } start.score=getScore(start) push(start) current=nil done=false end function input() if btnp(A) then -- restart resetMap() init() end end -- Clear map of any existing sprites function resetMap() for y=1,MAP_HEIGHT-2 do for x=1,MAP_WIDTH-2 do if mget(x,y)~=WALL then mset(x,y,FLOOR) end end end end function update() if not done then if #queue>0 then current=pop() if current.x==goal.x and current.y==goal.y then -- found goal done=true else -- no goal yet, keep looking addAdjacentCells(current) end else -- no more edges, didn't find goal end end end -- Remove first cell from queue and -- return it function pop() local cell=queue[1] table.remove(queue,1) cell.visited=true table.insert(visited,cell) return cell end -- Add adjacent cells of given cell -- to queue if they aren't already in -- queue, haven't been visited, and -- are not walls function addAdjacentCells(cell) local adjacents={ {x=cell.x,y=cell.y-1}, {x=cell.x,y=cell.y+1}, {x=cell.x-1,y=cell.y}, {x=cell.x+1,y=cell.y}, } for _,c in ipairs(adjacents) do if not contains(queue,c.x,c.y) and not contains(visited,c.x,c.y) and mget(c.x,c.y)~=WALL then local adjacentCell={ x=c.x, y=c.y, visited=false, parent=cell, score=getScore(cell), } push(adjacentCell) end end end -- Calculate Manhattan distance from -- given cell to goal function getScore(cell) return math.abs( (cell.x-goal.x)+ (cell.y-goal.y) ) end -- Add given cell to queue, then sort -- queue based on "score" function push(cell) table.insert(queue, cell) table.sort( queue, function(a,b) return a.score