ÎÌÌÌ̈ˆˆ¬ªªª¬ˆˆˆ¬ÌÌ̬ÌÀ̬ÌÀ̬ÌÀÌÌÌìÌÀÀî̬ÀÌÀ¬ÀÀÀ¬ÀÀÀ¬ÀÀÎÌÌÌ̈ˆˆ¬ªªª¬ˆˆˆ¬ÌÌ̬ÌÌ̬ÌÀ̬ÌÀÌÌÌìÌÀÀî̬ÀÌ̬ÀÀÀ¬ÀÀÀ¬ÀÀ¬ÌÌ̬ªªª¬ª¬ª¬ªÊ̬ªªªŒˆˆˆÌÀÌÎÌÌÎ̬̪ªÀ쬪ÀÀÀÌîÀìîÌÌîî¬ÌÌ̬ªªª¬ª¬ª¬ªÊ̬ªªªŒˆˆˆÌÀÌÎÌÌÎ̬̪ªÀ쬪ÀÀÀÌîÀìîÌÌîî >H? ÌÌÌÌÌÌÌÌ ÌÌÌÌÌÌÌÌÌ Ì ÌÌ ÌÌÌÌÌ ÌÌÌÌÌÌÌÌ Ì ÌÌÌÌÌÌÌÌÌ ÌÌ<ÃÌÌ Ì3ÌÌÌÌÌÌ ÌÌÌÌÌ îîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîî 33 3<3 <33 ÌÌÌÌ Ì Ì Ì Ì îîîîÌ ÌÌ Ì ÌÌÌ Ì Ì ÌÌ ÌÌ Ì ÌÌ<3Ì<<<Ì3Ì3<Ã<<Ì3ÌÌ ÌÌ îîîîîîîîîîîîîîîîîîîîîîî  030<0 03300<3303 îîÌ ÌÌ Ì ÌÌÌÌ ÌÌ ÌÌ Ì ÌÌ Ì Ì Ì ÌÌ Ì <3ÃÌ3à 3ÌÃÌ3<< Ì3<Ã3 îîîÌÌ îîîîîîîîîîîîîîîî  3  îÌ ÌÌÌ Ì ÌÌ îî Ì Ì Ì ÌÌ ÌÌÌÌ Ì ÌÌ Ì Ì ÌÌ ÌÌÌ Ì Ì ÌÌ Ì îîîîî Ì ÌÌ îîîîîîîîîîîîîî   îîÌ Ì Ì Ì Ì îÌÌ Ì Ì Ì ÌÌ Ì Ì Ì Ì ÌÌÌ ÌÌ ÌÌ Ì ÌÌ ÌÌ îîîîîÌ ÌÌ îîîîîîîîîîîîîîîîî   îîîÌÌ Ì Ì ÌÌ îîîîÌÌ Ì Ì ÌÌ Ì ÌÌÌ ÌÌ ÌÌÌ ÌÌÌ ÌÌ Ì Ì îîîîÌÌ ÌÌ îîîîîîîîîîîîîîîîî   îîîîî ÌÌÌÌ Ì Ì îîîîî ÌÌ Ì Ì Ì ÌÌ ÌÌÌÌ Ì Ì ÌÌ Ì Ì Ì ÌÌ Ì îîîîîîÌ Ì Ì Ì îîîîîîîîîîîîî   îîîÌÌ Ì ÌÌ îîîîîîÌ ÌÌÌ Ì ÌÌÌ ÌÌ ÌÌ Ì Ì ÌÌ Ì Ì ÌÌ Ì Ì îîîîîî Ì ÌÌ Ì îîîîîîîîîîîîîîîî    îîîî Ì Ì îîîîÌ îîîîîÌ Ì ÌÌ Ì Ì Ì ÌÌ ÌÌÌÌÌÌ ÌÌ Ì îîîîîîÌ ÌÌÌÌ Ì îîîîîîîîîîîîîî    îîîîî Ì Ì îîîî Ì ÌÌ îîÌ ÌÌÌÌ ÌÌ ÌÌ ÌÌ ÌÌÌ ÌÌ îîîîîîîî ÌÌÌÌ Ì Ì îîîîîîîîîîîîîîîî    îÌ ÌÌ Ì Ì Ì Ì îîîÌÌÌÌ îîîîÌ ÌÌÌ Ì Ì Ì ÌÌÌÌ Ì Ì Ì îîîîîîîÌ ÌÌÌ Ì îîîîîîîîîîîîîîî    îî Ì ÌÌ îÌ îîîîîîîÌ Ì îîîÌ Ì Ì Ì ÌÌÌ ÌÌ ÌÌ Ì îîîÌ Ì Ì Ì îîîîîîîîîîî    îîÌÌÌ ÌÌÌÌ îîîîîîîî ÌÌ îîÌ ÌÌÌ Ì  Ì Ì Ì ÌÌ Ì îîîîî Ì Ì îîîîîîîîîîîîîî     îîÌÌÌ ÌÌ îîîîîîîîîîÌ ÌÌ îîîÌ îîîîî Ì Ì Ì Ì Ì Ì îîîîîÌ ÌÌ Ì ÌÌ îîîîîîîîîîîîîîîî    îîÌ ÌÌÌÌÌ Ì îîîîîîîîîîîîÌ ÌÌ îîîîÌÌ Ì ÌÌÌÌÌ Ì Ì îîîîî Ì Ì Ì îîîîîîîîîîîîîîîîîî   îîîÌÌÌÌ ÌÌ îîîîîîîîîîî ÌÌ Ì îîÌÌ ÌÌ Ì Ì ÌÌÌÌ Ì ÌÌ ÌÌÌÌÌÌÌ ÌÌ Ì Ì îîîîîîîîîîîîîîîî   îîîîîîÌÌ îîîîîîîîîîÌÌ îî Ì ÌÌ ÌÌ Ì ÌÌ Ì Ì Ì ÌÌ ÌÌ ÌÌ Ì Ì îîîîîîîîîîîîîî  îîîîîîîîîîîîîîî Ì îîÌ Ì ÌÌÌÌ ÌÌ ÌÌ Ì Ì Ì ÌÌÌ Ì Ì îîîîîîîîîîîîîîîîî  îîîîîîîîîîîîîîîîîîîîîî Ì îîîîîîÌÌÌ îî Ì Ì Ì Ì Ì ÌÌ ÌÌÌÌ ÌÌ ÌÌ Ì ÌÌÌÌ îîîîîîîîîîîîîî  îîîîîîîîîîîîîîîîîîîÌ Ì îîîîîîîîîîÌ Ì ÌÌÌ Ì ÌÌ ÌÌÌÌ ÌÌÌ Ì Ì îîîîîîîîîîî  îîîîîîîîîîîîîîîîÌ îîîîîîîîÌÌ Ì Ì ÌÌÌ Ì ÌÌÌ Ì ÌÌÌ ÌÌ Ì îîîîîîîîîîîîîîîîî  îîîîîîîîîîîîîîîîÌÌ Ì îîîîîîîîîîîî ÌÌ ÌÌÌ ÌÌ Ì Ì Ì ÌÌ ÌÌ îîîîîîîîîîîîîîî  îîîîîîîîîîîîîîîîîÌÌ îîîîîîîîîîîîî Ì Ì Ì ÌÌÌ Ì Ì ÌÌ Ì îîîîîîîîîîîîîîîîî  îîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîÌ ÌÌÌÌ Ì îÌ Ì  Ì ÌÌ Ì Ì Ì îîîîîîîîîîîîîîîîî   îîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîî îîîÌ îÌ Ì Ì ÌÌÌ Ì îîîîîîîîîîîîîîîî  îîîîîîîîîîîîîîîîîîîîîîîîîîîîîî îîîîîîî ÌÌ ÌÌÌÌÌ ÌÌ îîîîîîîîîîîîîîî   îîîîîîîîîîîîîîîîîîîîîîîîîîîîîÌ îîîîÌ îîîîîîîÌÌ îîîîîîîîîîîîîîîîî îîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîÌ îîîîîîîîîîîîîîîîîîî îîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîÌ îîîîîîîîîîîîîîîîîîî îîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîÎ îîîÌÌ Ì îîîîîîîîîîîîîî  îîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîÌÌÌ îîîî ÌÌ îîîîîîîîîîîîîîîîîî  îîîîîîîîîîîîîîîîîîîîîîîîîîîÌ îÌ Ì îîîÌ îîîîîîîîîîîîîîîîîîîî   îîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîî Ì ÌÌ îîÌ Ì îîîîîîîîîîîîîî   îîîîîîîîîîîîîîîîîîîîîîîîîîîîîîî ÌÌÌÌ Ì îÌ îîîîîîîîîîîîîîîî  îîîîîîîîîîîîîîîîîîîîîîîîîîîÌ Ì ÌÌ Ì Ì îÌÌ îîîîîîîîîîîîîîîîîî  îîîîîîîîîîîîîîîîîîîîîîîîîîîîîî ÌÌÌ Ì Ì îÌ îîîîîîîîîîîîîîîîîî îîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîÌÌÌÌ ÌÌÌ ÌÌÌ îîîîîîîîîîîîîîîîîîî îîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîî ÌÌÌ Ì îîîîîîîîîîîîîîîîîîîîî îîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîî ÌÌ Ì Ì îîîîîîîîîîîîîîîîîîîîîî îîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîÌÌÌÌ Ì îîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîîX-- title: DFS maze generator and A* solver -- author: Sava -- desc: simple DFS maze generator and A* solver -- version: 0.1 -- script: lua w=240 h=136 gen = true gx, gy = 1, 1 stack = {} visited = {} dirs = {} find = true opened = {} costs = {} finx, finy = w/2, h/2 finish = {} function BOOT() for i=1, w/2 do visited[i]={} dirs[i]={} costs[i]={} opened[i]={} finish[i]={} for j=1, h/2 do visited[i][j]=false dirs[i][j]={false, false, false, false} costs[i][j]={nil, nil, nil} opened[i][j]=false finish[i][j]=false end end visited[gx][gy]=true stack[#stack+1]={x=gx, y=gy} end function TIC() if gen then make(25) elseif find then Astar(10) end cls(0) for i=1, w/2 do for j=1, h/2 do local col = 14 if opened[i][j] then col = 12 end if finish[i][j] then col = 10 end pix(i*2-2, j*2-2, col) for i1=1, 4 do cx, cy = idxToPos(i1) cx, cy = cx+i*2, cy+j*2 if dirs[i][j][i1] then pix(cx-2, cy-2, col) end end end end local dots = (math.floor(time()/250)%3)+1 local dotTable = {".", "..", "..."} local dotStr = dotTable[dots] if gen then print("generating"..dotStr, w/2-30, 0, 3) elseif find then print("solving"..dotStr, w/2-21, 0, 3) else print("done!", w/2-15, 0, 3) end end function make(c) for i=1, c do if #stack > 0 then gx, gy = stack[#stack].x, stack[#stack].y stack[#stack] = nil local neigh = {} neigh[1]=(gx+1 <= w/2 and not visited[gx+1][gy]) neigh[2]=(gx-1 > 0 and not visited[gx-1][gy]) neigh[3]=(gy+1 <= h/2 and not visited[gx][gy+1]) neigh[4]=(gy-1 > 0 and not visited[gx][gy-1]) local nNeigh = {} for i=1, 4 do if neigh[i] then nNeigh[#nNeigh+1]=i end end if #nNeigh > 0 then stack[#stack+1]={x=gx, y=gy} local choose=math.random(1, #nNeigh) local cx, cy = idxToPos(nNeigh[choose]) cx, cy = cx+gx, cy+gy dirs[gx][gy][nNeigh[choose]]=true visited[cx][cy] = true stack[#stack+1]={x=cx, y=cy} end else gen = false gx, gy = 1, 1 open(1, 1) break end end end function idxToPos(idx) if idx == 1 then return 1, 0 elseif idx == 2 then return -1, 0 elseif idx == 3 then return 0, 1 else return 0, -1 end end function Astar(c) for i=1, c do AstarIter() end end function AstarIter() if not find then finishS(finx, finy) return end local minFc = 999999 local minFcx, minFcy = 0, 0 for i=1, w/2 do for j=1, h/2 do if not opened[i][j] then if costs[i][j].fc ~= nil then if costs[i][j].fc < minFc then minFc = costs[i][j].fc minFcx, minFcy = i, j end end end end end open(minFcx, minFcy) if minFcx == finx and minFcy == finy then find = false end end function finishS(sx, sy) local x, y = sx, sy while x ~= 1 or y ~= 1 do finish[x][y]=true x1, y1 = costs[x][y].fromx, costs[x][y].fromy x, y = x1, y1 end finish[1][1]=true end function open(x, y) opened[x][y]=true local neigh={} neigh[1]=(x+1 <= w/2 and dirs[x][y][1]) neigh[2]=(x-1 > 0 and dirs[x][y][2]) neigh[3]=(y+1 <= h/2 and dirs[x][y][3]) neigh[4]=(y-1 > 0 and dirs[x][y][4]) for i=1, 4 do if neigh[i] then local cx, cy = idxToPos(i) cx, cy = cx+x, cy+y local gc = 0 if costs[x][y].gc ~= nil then gc = costs[x][y].gc+dist(x, y, cx, cy) else gc = dist(x, y, cx, cy) end local hc = dist(cx, cy, finx, finy) local fc = gc+hc if costs[cx][cy].fc == nil or costs[cx][cy].fc > fc then costs[cx][cy]={gc=gc, hc=hc, fc=fc, fromx=x, fromy=y} end end end end function dist(x1, y1, x2, y2) return math.floor(math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))*10) end