186 lines
6.5 KiB
AutoHotkey
186 lines
6.5 KiB
AutoHotkey
Width := 10, Height := 10 ; set grid size
|
|
SleepTime := 0
|
|
|
|
gosub, Startup
|
|
|
|
Gui, +AlwaysOnTop
|
|
Gui, font, s12, consolas
|
|
Gui, add, edit, vEditGrid x10, % maze
|
|
Gui, add, button, xs gStartup Default, Generate maze
|
|
Gui, add, button, x+10 gSolve, Solve
|
|
Gui, show,, maze
|
|
GuiControl,, EditGrid, % maze ; show maze
|
|
return
|
|
|
|
;-----------------------------------------------------------------------
|
|
^Esc::
|
|
GuiEscape:
|
|
GuiClose:
|
|
ExitApp
|
|
return
|
|
|
|
;-----------------------------------------------------------------------
|
|
Startup:
|
|
oMaze := [] ; initialize
|
|
Solved := false
|
|
loop, % Height
|
|
{
|
|
row := A_Index
|
|
loop, % Width ; create oMaze[row,column] borders
|
|
col := A_Index, oMaze[row,col] := "LRTB" ; i.e. oMaze[2,5] := LRTB (add all borders)
|
|
}
|
|
Random, row, 1, % Height ; random row
|
|
Random, col, 1, % Width ; random col
|
|
grid := maze2text(oMaze) ; object to text
|
|
GuiControl,, EditGrid, % Grid ; show Grid
|
|
row := col := 1 ; reset to 1,1
|
|
oMaze := Generate_maze(row, col, oMaze) ; generate maze starting from random row/column
|
|
oMaze[1,1] .= "X" ; start from 1,1
|
|
maze := maze2text(oMaze) ; object to text
|
|
GuiControl,, EditGrid, % maze ; show maze
|
|
GuiControl,, EditRoute ; clear route
|
|
GuiControl, Enable, Solve
|
|
return
|
|
|
|
;-----------------------------------------------------------------------
|
|
Solve:
|
|
GuiControl, Disable, Generate maze
|
|
GuiControl, Disable, Solve
|
|
loop % oRoute.MaxIndex()
|
|
oRoute.pop()
|
|
|
|
oSolution := Solve(1, 1, oMaze) ; solve starting from 1,1
|
|
oMaze := oSolution.1
|
|
oRoute := oSolution.2
|
|
Update(oMaze, oRoute)
|
|
Solved := true
|
|
GuiControl, Enable, Generate maze
|
|
return
|
|
|
|
;-----------------------------------------------------------------------
|
|
Update(oMaze, oRoute){
|
|
global SleepTime
|
|
GuiControl,, EditGrid, % maze2text(oMaze)
|
|
Sleep, % SleepTime
|
|
}
|
|
|
|
;-----------------------------------------------------------------------
|
|
maze2text(oMaze){
|
|
width := oMaze.1.MaxIndex()
|
|
BLK := "█"
|
|
for row, objRow in oMaze
|
|
{
|
|
for col, val in objRow ; add ceiling
|
|
{
|
|
ceiling := InStr(oMaze[row, col] , "x") && InStr(oMaze[row-1, col] , "x") ? "+ " BLK " " : "+ "
|
|
grid .= (InStr(val, "T") ? "+---" : ceiling) (col = Width ? "+`n" : "")
|
|
}
|
|
for col, val in objRow ; add left wall
|
|
{
|
|
wall := SubStr(val, 0) = "X" ? BLK : " "
|
|
grid .= (InStr(val, "L") ? "| " : " ") wall " " (col = Width ? "|`n" : "") ; add left wall if needed then outer right border
|
|
}
|
|
}
|
|
Loop % Width
|
|
Grid .= "+---" ; add bottom floor
|
|
Grid .= "+" ; add right bottom corner
|
|
return RegExReplace(grid , BLK " (?=" BLK ")" , BLK BLK BLK BLK) ; fill gaps
|
|
}
|
|
|
|
;-----------------------------------------------------------------------
|
|
Generate_maze(row, col, oMaze) {
|
|
neighbors := row+1 "," col "`n" row-1 "," col "`n" row "," col+1 "`n" row "," col-1
|
|
Sort, neighbors, random ; randomize neighbors list
|
|
Loop, parse, neighbors, `n ; for each neighbor
|
|
{
|
|
rowX := StrSplit(A_LoopField, ",").1 ; this neighbor row
|
|
colX := StrSplit(A_LoopField, ",").2 ; this neighbor column
|
|
if !instr(oMaze[rowX,colX], "LRTB") || !oMaze[rowX, colX] ; if visited (has a missing border) or out of bounds
|
|
continue ; skip
|
|
|
|
; remove borders
|
|
if (row > rowX) ; Cell is below this neighbor
|
|
oMaze[row,col] := StrReplace(oMaze[row,col], "T") , oMaze[rowX,colX] := StrReplace(oMaze[rowX,colX], "B")
|
|
else if (row < rowX) ; Cell is above this neighbor
|
|
oMaze[row,col] := StrReplace(oMaze[row,col], "B") , oMaze[rowX,colX] := StrReplace(oMaze[rowX,colX], "T")
|
|
else if (col > colX) ; Cell is right of this neighbor
|
|
oMaze[row,col] := StrReplace(oMaze[row,col], "L") , oMaze[rowX,colX] := StrReplace(oMaze[rowX,colX], "R")
|
|
else if (col < colX) ; Cell is left of this neighbor
|
|
oMaze[row,col] := StrReplace(oMaze[row,col], "R") , oMaze[rowX,colX] := StrReplace(oMaze[rowX,colX], "L")
|
|
|
|
Generate_maze(rowX, colX, oMaze) ; recurse for this neighbor
|
|
}
|
|
return, oMaze
|
|
}
|
|
|
|
;-----------------------------------------------------------------------
|
|
Solve(row, col, oMaze){
|
|
static oRoute := []
|
|
oNeighbor := [], targetrow := oMaze.MaxIndex(), targetCol := oMaze.1.MaxIndex()
|
|
|
|
;~ Update(oMaze, oRoute)
|
|
oRoute.push(row ":" col) ; push current cell address to oRoute
|
|
oMaze[row, col] .= "X" ; mark it visited "X"
|
|
|
|
if (row = targetrow) && (Col = targetCol) ; if solved
|
|
return true ; return ture
|
|
|
|
; create list of Neighbors
|
|
oNeighbor[row, col] := []
|
|
if !InStr(oMaze[row, col], "R") ; if no Right border
|
|
oNeighbor[row, col].push(row "," col+1) ; add neighbor
|
|
if !InStr(oMaze[row, col], "B") ; if no Bottom border
|
|
oNeighbor[row, col].push(row+1 "," col) ; add neighbor
|
|
if !InStr(oMaze[row, col], "T") ; if no Top border
|
|
oNeighbor[row, col].push(row-1 "," col) ; add neighbor
|
|
if !InStr(oMaze[row, col], "L") ; if no Left border
|
|
oNeighbor[row, col].push(row "," col-1) ; add neighbor
|
|
|
|
; recurese for each oNeighbor
|
|
for each, neighbor in oNeighbor[row, col] ; for each neighbor
|
|
{
|
|
Update(oMaze, oRoute)
|
|
startrow := StrSplit(neighbor, ",").1 ; this neighbor
|
|
startCol := StrSplit(neighbor, ",").2 ; becomes starting point
|
|
|
|
if !InStr(oMaze[startrow, startCol], "X") ; if it was not visited
|
|
if Solve(startrow, startCol, oMaze) ; recurse for current neighbor
|
|
return [oMaze, oRoute] ; return solution if solved
|
|
}
|
|
oRoute.pop() ; no solution found, back track
|
|
oMaze[row, Col] := StrReplace(oMaze[row, Col], "X") ; no solution found, back track
|
|
;~ Update(oMaze, oRoute)
|
|
}
|
|
|
|
;-----------------------------------------------------------------------
|
|
#IfWinActive, maze
|
|
Right::
|
|
Left::
|
|
Up::
|
|
Down::
|
|
if Solved
|
|
return
|
|
|
|
if (A_ThisHotkey="Right") && (!InStr(oMaze[row,col], "R"))
|
|
oMaze[row, col] := StrReplace(oMaze[row, col], "X") , col++
|
|
if (A_ThisHotkey="Left") && (!InStr(oMaze[row,col], "L"))
|
|
oMaze[row, col] := StrReplace(oMaze[row, col], "X") , col--
|
|
if (A_ThisHotkey="Up") && (!InStr(oMaze[row,col], "T"))
|
|
oMaze[row, col] := StrReplace(oMaze[row, col], "X") , row--
|
|
if (A_ThisHotkey="Down") && (!InStr(oMaze[row,col], "B"))
|
|
oMaze[row, col] := StrReplace(oMaze[row, col], "X") , row++
|
|
|
|
oMaze[row, col] .= "X"
|
|
GuiControl,, EditGrid, % maze2text(oMaze)
|
|
|
|
if (col = Width) && (row = Height)
|
|
{
|
|
Solved := true
|
|
oMaze[height, width] := StrReplace(oMaze[height, width], "X")
|
|
SleepTime := 0
|
|
gosub, solve
|
|
return
|
|
}
|
|
return
|
|
#IfWinActive
|