аоооооооооооооооооооооооооооооооо""""""""""""""""""""""""""""""""™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™ЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄЄffffffffffffffffffffffffffffffff33333333333333333333333333333333 >А?оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо""""™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄоооооооо""""™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄоооооооо""""™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄоооооооо""""™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄоооооооо""""™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄоооооооо""""™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄоооооооо""""™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄоооооооо""""™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄоооооооо™™™™™™™™оооо™™™™™™™™™™™™оооооооооооооооо™™™™оооо™™™™™™™™оооо™™™™оооооооооооооооо™™™™™™™™оооо™™™™™™™™™™™™оооооооооооооооо™™™™оооо™™™™™™™™оооо™™™™оооооооооооооооо™™™™™™™™оооо™™™™™™™™™™™™оооооооооооооооо™™™™оооо™™™™™™™™оооо™™™™оооооооооооооооо™™™™™™™™оооо™™™™™™™™™™™™оооооооооооооооо™™™™оооо™™™™™™™™оооо™™™™оооооооооооооооо™™™™™™™™оооо™™™™™™™™™™™™оооооооооооооооо™™™™оооо™™™™™™™™оооо™™™™оооооооооооооооо™™™™™™™™оооо™™™™™™™™™™™™оооооооооооооооо™™™™оооо™™™™™™™™оооо™™™™оооооооооооооооо™™™™™™™™оооо™™™™™™™™™™™™оооооооооооооооо™™™™оооо™™™™™™™™оооо™™™™оооооооооооооооо™™™™™™™™оооо™™™™™™™™™™™™оооооооооооооооо™™™™оооо™™™™™™™™оооо™™™™оооооооооооооооо™™™™™™™™оооо™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™оооо™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™оооо™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™оооо™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™оооо™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™оооо™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™оооо™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™оооо™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™оооо™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™оооо™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™оооо™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™оооо™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™оооо™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™оооо™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™оооо™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™оооо™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооо™™™™оооо™™™™™™™™™™™™™™™™оооооооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооо™™™™оооо™™™™™™™™™™™™™™™™оооооооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооо™™™™оооо™™™™™™™™™™™™™™™™оооооооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооо™™™™оооо™™™™™™™™™™™™™™™™оооооооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооо™™™™оооо™™™™™™™™™™™™™™™™оооооооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооо™™™™оооо™™™™™™™™™™™™™™™™оооооооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооо™™™™оооо™™™™™™™™™™™™™™™™оооооооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооо™™™™оооо™™™™™™™™™™™™™™™™оооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™™™™™™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™™™™™™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™™™™™™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™™™™™™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™™™™™™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™™™™™™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™™™™™™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™™™™™™™™™ЄЄЄЄоооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™™™™™оооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™ЄЄЄЄоооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™ЄЄЄЄоооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™ЄЄЄЄоооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™ЄЄЄЄоооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™ЄЄЄЄоооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™ЄЄЄЄоооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™ЄЄЄЄоооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооо™™™™™™™™™™™™оооо™™™™ЄЄЄЄоооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄ™™™™™™™™ооооЄЄЄЄоооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄ™™™™™™™™ооооЄЄЄЄоооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄ™™™™™™™™ооооЄЄЄЄоооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄ™™™™™™™™ооооЄЄЄЄоооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄ™™™™™™™™ооооЄЄЄЄоооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄ™™™™™™™™ооооЄЄЄЄоооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄ™™™™™™™™ооооЄЄЄЄоооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™ооооЄЄЄЄ™™™™™™™™ооооЄЄЄЄоооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооо™™™™оооооооооооооооооооооооооооо™™™™ооооооооооооооооооооЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ооооооооооооооооооооЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ооооооооооооооооооооЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ооооооооооооооооооооЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ооооооооооооооооооооЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ооооооооооооооооооооЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ооооооооооооооооооооЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™ооооооооооооооооооооЄЄЄЄоооооооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™оооооооооооооооооооооооооооооооооооооооооооооооооооо™™™™™™™™™™™™™™™™™™™™™™™™ЄЄЄЄооооооооffffоооооооо™™™™™™™™™™™™™™™™™™™™™™™™ЄЄЄЄооооооооffffоооооооо™™™™™™™™™™™™™™™™™™™™™™™™ЄЄЄЄооооооооffffоооооооо™™™™™™™™™™™™™™™™™™™™™™™™ЄЄЄЄооооооооffffоооооооо™™™™™™™™™™™™™™™™™™™™™™™™ЄЄЄЄооооооооffffоооооооо™™™™™™™™™™™™™™™™™™™™™™™™ЄЄЄЄооооооооffffоооооооо™™™™™™™™™™™™™™™™™™™™™™™™ЄЄЄЄооооооооffffоооооооо™™™™™™™™™™™™™™™™™™™™™™™™ЄЄЄЄооооооооffffооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооб -- title: Breadth-First Search -- author: Jeremy Miller -- desc: Breadth-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={} start={ x=1, y=1, visited=false, parent=nil, } table.insert(queue,start) goal={ x=28, y=15, } 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, } table.insert(queue,adjacentCell) end end end -- Check if a cell with given X/Y is -- in given table "t" function contains(t,x,y) for _,item in ipairs(t) do if item.x==x and item.y==y then return true end end return false end function draw() drawMap() drawVisited() drawQueue() drawPath() drawStartEnd() end function drawMap() map(0,0,30,17) end function drawVisited() for _,cell in ipairs(visited) do mset(cell.x,cell.y,VISITED) end end function drawQueue() for _,cell in ipairs(queue) do mset(cell.x,cell.y,QUEUED) end end function drawPath() if done then drawPathCell(current) end end function drawPathCell(cell) mset(cell.x,cell.y,PATH) if cell.parent then drawPathCell(cell.parent) end end function drawStartEnd() mset(start.x,start.y,START) mset(goal.x,goal.y,GOAL) end init() function TIC() cls() input() update() draw() end