Jump to content

Search the Community

Showing results for tags 'maze'.

  • Search By Tags

    Type tags separated by commas.
  • Search By Author

Content Type


Forums

  • General
    • Announcements and Site News
    • Administration
  • AutoIt v3
    • AutoIt Help and Support
    • AutoIt Technical Discussion
    • AutoIt Example Scripts
  • Scripting and Development
    • Developer General Discussion
    • Language Specific Discussion
  • IT Administration
    • Operating System Deployment
    • Windows Client
    • Windows Server
    • Office

Categories

  • AutoIt Team
    • Beta
    • MVP
  • AutoIt
    • Automation
    • Databases and web connections
    • Data compression
    • Encryption and hash
    • Games
    • GUI Additions
    • Hardware
    • Information gathering
    • Internet protocol suite
    • Maths
    • Media
    • PDF
    • Security
    • Social Media and other Website API
    • Windows
  • Scripting and Development
  • IT Administration
    • Operating System Deployment
    • Windows Client
    • Windows Server
    • Office

Find results in...

Find results that contain...


Date Created

  • Start

    End


Last Updated

  • Start

    End


Filter by number of...

Joined

  • Start

    End


Group


Member Title


Location


WWW


Interests

Found 2 results

  1. Hi folks! First off, yeah this may be the lamest title. But it made you look anyway! Edit: Now updated! With step-counter, reset button and a few GUI-tweaks. (the step-counter is cheating! It's calculated in advance...) I recently thought a screenshot of a finished maze may be smart to show, instead of only my long story and code. o=path, x=wall. Here it is: I started making my own implementation of the A* pathing script in a larger project, inspired by Toady's work. (But made one from scratch myself anyway ) After the A* pathing script was working (not cleaned up yet) I wanted to test it. Unfortunately I got no good, randomized, maze lying around that also had the format I needed. So I made my own maze generator! I did a few hours of research on the matter and then a few evenings of scripting. For the people who are interested, one of my problems was that I needed 'one-cell' thick walls. Most maze generation have 1 pixel thick walls drawn by a line, that could be opened if a path is needed. The solution is so simple, I needed this guy to tell me. Click here for my inspiration source. This generator can be used with different sizes maze, even uneven ones! Just set the width and height settings. FYI, it must be odd numbers for this maze to work with it's containment walls. It's the 'simple' Depth-First Search, with backtracking. And without further ado; my a-maze-ing generator!: #cs ---------------------------------------------------------------------------- AutoIt Version: 3.3.12.0 Author: A-maze-ing generator Script Function: Generates a maze. In the $xy[$i][4] is the maze in array form. Don't forget to take the size with it, else it's just a string of o's and x's It does not generate an entrance or exit! #ce ---------------------------------------------------------------------------- ; Script Start - Add your code below here #include <Array.au3> #include <GUIConstantsEx.au3> #include <StaticConstants.au3> ; Set various variables ; width and height must be odd numbers to have a closed, functioning maze. Global $height = 27 ; demo height = 27 Global $width = 43; demo width = 43 ; Check if width & height are an odd number (to get the outer edge an odd number is required) If mod($height, 2) = 0 Or $height < 5 Then msgbox(0,"","Height is not an odd number or a minimum of 5 tall !") Exit ElseIf mod($width, 2) = 0 Or $width < 5 Then msgbox(0,"","Width is not an odd number of a minimum of 5 wide !") Exit EndIf ; Set various variables when script is not exited Global $grid_size = $height * $width Global $numberofsteps = (Ceiling(($height-2) / 2) * (($width-2) - Ceiling(($width-2) / 2))) + (($height-2) - Ceiling(($height-2) / 2)) ; long formula to check the number of steps this maze will take, this is a mathematical given with a fixed number of cells. And yes, I am aware I'm taking a shortcut in this formula. ;) Global $curpos Global $backtrack[1] Global $bt = 0 Local $grid_pixel = 20 ;How many pixels per square ; Initialize main array with all grid data Global $xy[$grid_size + 1][5] Global $reset_xy = $xy ; set the reset array $xy[0][0] = $grid_size ; first entry is the total number of nodes, rest is set with a header name for easy reference in _ArrayDisplay if needed. $xy[0][1] = "ID" $xy[0][2] = "Row" $xy[0][3] = "Column" $xy[0][4] = "Type" ; Fill the grid array with 'walls' For $i = 1 To $xy[0][0] $xy[$i][4] = "x" Next ; Start GUI and create standard buttons Local $gui = GUICreate("A-maze-ing generator", 180 + ($width * $grid_pixel), 80 + ($height * $grid_pixel)) ; Set the main window to the minimum width (IF) needed for the msgbox Local $aPos = WinGetPos($gui) If $aPos[2] < 696 Then $aPos[2] = 696 WinMove($gui, "", $aPos[0], $aPos[1], $aPos[2], $aPos[3]) EndIf GUICtrlCreateLabel("This is a-maze-ing!", 30, 19) Global $progress = GUICtrlCreateLabel("Standing by... " & $numberofsteps & " steps to go.", 150, 15, 550, 30) Local $iOKButton = GUICtrlCreateButton("Start", 45, 50, 60) Local $iResetButton = GUICtrlCreateButton("Reset", 45, 90, 60) Local $iExitButton = GUICtrlCreateButton("Exit", 45, 130, 60) GUICtrlSetFont($progress, 15) GUICtrlSetColor($progress, 0x00AA00) GUICtrlSetState($iResetButton, $GUI_DISABLE) ; Create label-grid and fill the xy array with the positions Local $squarenr = 0 For $i = 0 To ($height * $grid_pixel) - $grid_pixel Step $grid_pixel ; Row For $j = 0 To ($width * $grid_pixel) - $grid_pixel Step $grid_pixel ; Column $squarenr = $squarenr + 1 $xy[$squarenr][0] = GUICtrlCreateLabel('x', 150 + $j, 50 + $i, $grid_pixel, $grid_pixel, BitOr($SS_SUNKEN, $SS_CENTER)) ; if you want debugging numbers, replace 'x' with $squarenr GUICtrlSetBkColor($xy[$squarenr][0], 0x5E87C9) ; lightblue-ish $xy[$squarenr][1] = $squarenr $xy[$squarenr][2] = ($i / $grid_pixel) + 1 $xy[$squarenr][3] = ($j / $grid_pixel) + 1 Next Next $reset_xy = $xy ; Show GUI GUISwitch($gui) GUISetState(@SW_SHOW) ; Start looping and waiting for input Local $aMsg = 0 While 1 $aMsg = GUIGetMsg(1) Select Case $aMsg[0] = $iOKButton GUICtrlSetState($iOKButton, $GUI_DISABLE) GUICtrlSetState($iResetButton, $GUI_DISABLE) GUICtrlSetState($iExitButton, $GUI_DISABLE) GUICtrlSetColor($progress, 0xFF8C00) ; orange GUICtrlSetData($progress, "Running - Creating maze. Please stand by... " & $numberofsteps & " steps to go.") make_maze() GUICtrlSetColor($progress, 0xFF0000) ; red GUICtrlSetData($progress, "Maze complete!") Sleep(1000) ; Just a small sleep for dramatic effect GUICtrlSetColor($progress, 0x00AA00) ; green-ish GUICtrlSetData($progress, "Maze completed in " & $numberofsteps & " steps.") GUICtrlSetState($iResetButton, $GUI_ENABLE) GUICtrlSetState($iExitButton, $GUI_ENABLE) Case $aMsg[0] = $iResetButton GUICtrlSetData($progress, "Resetting maze...") reset_maze() GUICtrlSetState($iResetButton, $GUI_DISABLE) GUICtrlSetState($iOKButton, $GUI_ENABLE) GUICtrlSetData($progress, "Maze reset!") Sleep(1000) ; Just a small sleep for dramatic effect GUICtrlSetData($progress, "Standing by...") Case $aMsg[0] = $GUI_EVENT_CLOSE Or $aMsg[0] = $iExitButton ExitLoop EndSelect WEnd Exit ; Resetting the maze to default state Func reset_maze() $xy = $reset_xy ; Set the $xy array back to it first-run values For $i = 1 To $xy[0][0] $xy[$i][4] = "x" ; set everything to 'x' GUICtrlSetBkColor($xy[$i][0], 0x5E87C9) ; reset the background color GUICtrlSetData($xy[$i][0], "x") ; (re)set the label to 'x' Next EndFunc ; Main function Func make_maze() Local $heading Local $stepcount = $numberofsteps ; Reset the step counter. Local $timed = TimerInit() ; Start the timer to see how long the maze generation took. $backtrack[0] = 0 $curpos = $width + 2 ; This is the starting position, second row, second column - aka top-left, one in from the sides. open_maze($curpos) ; Set the starter cell to 'open / white' ; Main maze generation loop While 1 Do $heading = direction($curpos) Until $heading <> 0 If $bt = 1 Then $bt = 0 ; reset backtracking-tracker, else the backtracking array keeps adding the current position GUICtrlSetData($progress, "Running - Creating maze. Please stand by... " & $stepcount & " steps to go.") Sleep(50) ; Slow maze creation down to look at it - relax! (or don't and comment out the sleep) If $heading = -1 Then ExitLoop $stepcount -= 1 ; Count down the steps to finish. ; We got the heading - now which way do we go? After that, set the current position to the last known heading. Switch $heading Case 1 ; north open_maze($curpos - $width) open_maze($curpos - ($width * 2)) $curpos = $curpos - ($width * 2) Case 2 ; east open_maze($curpos + 1) open_maze($curpos + 2) $curpos = $curpos + 2 Case 3 ; south open_maze($curpos + $width) open_maze($curpos + ($width * 2)) $curpos = $curpos + ($width * 2) Case 4 ; west open_maze($curpos - 1) open_maze($curpos - 2) $curpos = $curpos - 2 EndSwitch ;msgbox(0,"","Turn pause") ; for debugging, click every turn. WEnd ConsoleWrite("Maze completed in " & Round(TimerDiff($timed) / 1000, 1) & " seconds." & @CRLF) ; Show the generation time in seconds, rounded up with one decimal Return EndFunc Func open_maze($dest) ; Function set inputted cells to 'open' instead of being an uncool wall. $xy[$dest][4] = "o" GUICtrlSetData($xy[$dest][0], 'o') ; If you want debugging numbers, replace 'o' with $dest GUICtrlSetBkColor($xy[$dest][0], 0xEEEEEE) EndFunc Func direction(ByRef $curpos) ; Insert current position, output next heading for path generation. Local $nesw Local $open_directions[5][2] $open_directions[0][0] = 0 $nesw = $curpos - ($width * 2) ; north side checking If $nesw > $width + 1 Then fill_open_dir($nesw, 1, $open_directions) $nesw = $curpos + 2 ; east side checking If mod($nesw - 1, $width) <> 0 Then fill_open_dir($nesw, 2, $open_directions) $nesw = $curpos + ($width * 2) ; south side checking If $nesw < $grid_size - $width Then fill_open_dir($nesw, 3, $open_directions) $nesw = $curpos - 2 ; west side checking If mod($nesw, $width) <> 0 Then fill_open_dir($nesw, 4, $open_directions) ; Check which (if any) direction(s) are already opened, if so, discard them from the results-array For $i = $open_directions[0][0] To 1 Step -1 If $xy[$open_directions[$i][1]][4] = "o" Then $open_directions[0][0] -= 1 _ArrayDelete($open_directions, $i) EndIf Next ; If there are any results left... If $open_directions[0][0] > 0 Then If $open_directions[0][0] = 1 Then Return $open_directions[1][0] ; Random does not work with min 1 and max 1 (output = 0), so in this case, return only with the only one result. Else If $bt = 0 Then ; If there is not backtracking active, add this crossroad to the backtrack-array. This is only needed if there are two or three possible sides. $backtrack[0] += 1 _ArrayAdd($backtrack, $curpos) EndIf Return $open_directions[Random(1, $open_directions[0][0], 1)][0] ; Random choose between all possible directions and return with the outcome direction. EndIf ElseIf $backtrack[0] > 0 Then ; If there are no results ánd there are entries in the backtrack list, then visit those entries to see if there still is a path possible. $curpos = $backtrack[$backtrack[0]] _ArrayDelete($backtrack, $backtrack[0]) $backtrack[0] -= 1 $bt = 1 Return 0 ; Return with a new current direction ($curpos), from the backtrack array. Else Return -1 ; If there are no paths to explorer, in the pathing, or backtracking, then return with the message that we are finished. EndIf EndFunc Func fill_open_dir($nesw, $direction, ByRef $open_directions) ; Fill the $open_directions array with a new possible way $open_directions[0][0] += 1 $open_directions[$open_directions[0][0]][1] = $nesw $open_directions[$open_directions[0][0]][0] = $direction Return EndFunc P.S. The 'slow' generation is intended because it looks cool. Comment out the Sleep line on line 157 for a fast generation.
  2. This is my maze generator. It creates a maze useing the Recursive backtracker witch i found here: http://en.wikipedia.org/wiki/Maze_generation_algorithm#Recursive_backtracker It'll save the finished maze in the a folder with the name Mazes in @scriptdir as Maze (Seed).bmp where Seed is the seed of the maze and size is the size. It usees the Bitmap Libray by evelertoaster find it here: Thanks to MvGulik for cleaning the code. Here's a picture of a finished 25*25 maze: The green dot is the start and the red dot is the end. It can also solve the maze. Here's the solution for the above 25*25 maze. So here's the code: ;~ #AutoIt3Wrapper_Au3Check_Stop_OnWarning=y ;~ #AutoIt3Wrapper_AU3Check_Parameters=-q -d -w 1 -w 2 -w 3 -w 4 -w 5 -w 6 -w 7 ;Thanks to MvGulik (http://www.autoitscript.com/forum/user/14111-mvgulik/) for cleaning up the code. And for RND_SeedTimed function #region Decleres and includes ;Add the needed includes #include <Array.au3> #include <ButtonConstants.au3> #include <EditConstants.au3> #include <GUIConstantsEx.au3> #include <StaticConstants.au3> #include <WindowsConstants.au3> #include "BMP3.au3" ; Downloaded from http://www.autoitscript.com/forum/topic/27362-bitmap-library/ #endregion Decleres and includes #Region ### START Koda GUI section ### Form=*** $Gui = GUICreate("Maze Generator", 673, 728, 299, 77) $GenerateButton = GUICtrlCreateButton("Generate!", 528, 8, 137, 49) GUICtrlSetFont(-1, 17, 400, 0, "MS Sans Serif") $SizeXLabel = GUICtrlCreateLabel("X:", 8, 24, 19, 24) GUICtrlSetFont(-1, 12, 400, 0, "MS Sans Serif") $SizeYLabel = GUICtrlCreateLabel("Y:", 112, 24, 19, 24) GUICtrlSetFont(-1, 12, 400, 0, "MS Sans Serif") $SolveCheck = GUICtrlCreateCheckbox("Solve maze?", 384, 24, 137, 20) GUICtrlSetFont(-1, 15, 400, 0, "MS Sans Serif") $MazeYInput = GUICtrlCreateInput("", 136, 24, 57, 21, BitOR($GUI_SS_DEFAULT_INPUT,$ES_NUMBER)) $MazeXInput = GUICtrlCreateInput("", 32, 24, 57, 21, BitOR($GUI_SS_DEFAULT_INPUT,$ES_NUMBER)) $SizeLabel = GUICtrlCreateLabel("Size:", 80, 0, 39, 24) GUICtrlSetFont(-1, 13, 400, 0, "MS Sans Serif") $SeedLabel = GUICtrlCreateLabel("Seed:", 216, 24, 46, 24) GUICtrlSetFont(-1, 12, 400, 0, "MS Sans Serif") $SeedInput = GUICtrlCreateInput("", 264, 24, 97, 21) GUICtrlSetLimit(-1, 10) GUICtrlSetTip(-1, "Leave blank for a random seed.") $MazeTempPic = GUICtrlCreateGraphic(5,72, 663, 651) GUICtrlSetBkColor(-1, 0x000000) $MazeShowPic = GUICtrlCreatePic("", 5, 72, 663, 651) ;this is where the maze will be shown GUISetState(@SW_SHOW) #EndRegion ### END Koda GUI section ### While 1 $nMsg = GUIGetMsg() Switch $nMsg Case $GUI_EVENT_CLOSE Exit Case $GenerateButton Generate(Int(GUICtrlRead($MazeXInput)), Int(GUICtrlRead($MazeYInput)), GUICtrlRead($SeedInput), Int(GUICtrlRead($SolveCheck))) EndSwitch WEnd Func Generate($iMazeX, $iMazeY, $sSeed, $iSolve) ProgressOn("Generating maze", "Generating maze. Please Wait", "", -1, -1 , 16) $iSeed = UseSeed($sSeed) If $sSeed = "" Then $sSeed = String($iSeed) ProgressSet(1, "1 Percent.") Local $sBaseName = 'MazesMaze [' & String($iMazeX) & ', ' & String($iMazeY) & '] (' & $sSeed & ')' ; Now saves mazes in a separate folder DirCreate(@ScriptDir&"Mazes") Local $aiSize[2] = [$iMazeX, $iMazeY] ;$aiSize[0] Equals Number of Rows in each colum and $aiSize[1] equals number of Colums Local $aCells = _;This is where the maze will be stored ; It will store witch walls are intact Generate_Maze($aiSize, $iSolve) ; 25.5% of progress or 51% if not being solved Draw_Maze_Image($aiSize, $aCells, $sBaseName, $iSolve) ; 24.5% of progress or 48% if not being so)ved ;Show image if maze should not be solved If $iSolve = 49 Then GUICtrlSetImage($MazeShowPic, @ScriptDir & "" & $sBaseName & ".bmp") If $iSolve <> 49 Then Local $aCurrentPath = Solve_Maze($aiSize, $aCells) ; 25.5% of progress Solve_Maze_ImgDraw($aiSize, $aCurrentPath, $sBaseName) ; 23.5% of progress GUICtrlSetImage($MazeShowPic, @ScriptDir & "" & $sBaseName & "_Solved.bmp") EndIf ProgressOff() EndFunc Func Generate_Maze(Const ByRef $aiSize, ByRef $iSolve) Local Const $iTotalCells = $aiSize[0] * $aiSize[1] Local $iMoveToCell ; What cell to move to Local $aCellstack[$iTotalCells][2];This stores with sequnce the cell got generated in. used for backtracing. First dimension is Row. Second is Colum Local $iCurrentCellStackNumber = 0 ; Current subscript number to write to in $aCellstack Local $aCurrentCellStack[2] ; USed as a temp storage of a bit of cellstack. First dimension is Row. Second is Colum Local $iUnvisitedCells = $iTotalCells ; Number of cell that are unvisited Local $sNeighbours = '' Local $sNeighbourOk Local $iRndDirection Local $aCurrentCellRowColum $iSolve -= 1 If $iSolve = 3 Then $iSolve = 25.5 ;; setup cell array. Local $aCells[$iTotalCells];This is where the maze will be stored ; It will store witch walls are intact Local $iCurrentCell = Random(0, $iTotalCells - 1, 1) ;; set random start point/cell ;Make all walls be intact by filling the cells array with 1111 array_filler($aCells, '1111') Local $aVisitedCells[$iTotalCells] array_filler($aVisitedCells, False) While 1 ;Mark as visited and add to the cell stack $aCurrentCellRowColum = AddToCellStack($iCurrentCell, $iCurrentCellStackNumber, $aCellstack, $aiSize) ;; $iCurrentCell not used in function. ;Check to see if it sould stop createing the maze If $iUnvisitedCells <> 0 Then ;Check to see if the current cell has any neighbours there are unvisited $sNeighbours = _Neighbours($aCurrentCellRowColum, $iCurrentCell, $aVisitedCells, $aiSize) If $sNeighbours <> "0000" Then ;Choose a random unvisited Neighbour Do $iRndDirection = Random(0, 3, 1) $sNeighbourOk = StringMid($sNeighbours, $iRndDirection + 1, 1) Until $sNeighbourOk = "1" Switch $iRndDirection ;Witch side to move to Case 0 ; Move Up $iMoveToCell = $iCurrentCell - $aiSize[1] Case 1 ; Move Right $iMoveToCell = $iCurrentCell + 1 Case 2 ; Move Down $iMoveToCell = $iCurrentCell + $aiSize[1] Case 3 ; Move Left $iMoveToCell = $iCurrentCell - 1 EndSwitch BustWall($iCurrentCell, $iMoveToCell, $iRndDirection, $aCells) $iCurrentCell = $iMoveToCell ;Make the current cell visited $aVisitedCells[$iCurrentCell] = True $iUnvisitedCells -= 1 Else $aCurrentCellStack[0] = $aCellstack[$iCurrentCellStackNumber - 2][0] ; Get row of last item in cellstack $aCurrentCellStack[1] = $aCellstack[$iCurrentCellStackNumber - 2][1] ; Get colum of last item in cellstack $iCurrentCell = _GetCellPos($aiSize, $aCurrentCellStack) ; Combine row and colum to get pos $iCurrentCellStackNumber -= 2 ; This will ensure that the used cell from the cellstack will be overwritten EndIf Else ExitLoop EndIf ;Update the progress ProgressSet(Int(Map($iUnvisitedCells, $iTotalCells, 0, 0, 25.5) + 1 + $iSolve), String(Int(Map($iUnvisitedCells, $iTotalCells, 0, 0, 25.5) + 1 + $iSolve))&" Percent.") WEnd ProgressSet(Int(25.5 + $iSolve), String(Int(25.5 + $iSolve))&" Percent.") ; Update progress Return $aCells EndFunc ;==>Generate_Maze Func Draw_Maze_Image(Const ByRef $aiSize, ByRef Const $aCells, ByRef Const $sFilename, ByRef $iSolve) Local Const $iTotalCells = $aiSize[0] * $aiSize[1] Local $aImageRowColum Local $tBMP = _BMPCreate($aiSize[1] * 9, $aiSize[0] * 9) ;Define the size of the maze (in bmp) If $iSolve = 25.5 Then $iSolve = 25.5 + 23.5 ;Draw the maze with no walls For $i = 0 To $iTotalCells - 1 $aImageRowColum = _GetCellPos($aiSize, $i) Draw3By3($tBMP, $aImageRowColum[0] * 9, $aImageRowColum[1] * 9) Draw3By3($tBMP, 6 + $aImageRowColum[0] * 9, $aImageRowColum[1] * 9) Draw3By3($tBMP, $aImageRowColum[0] * 9, 6 + $aImageRowColum[1] * 9) Draw3By3($tBMP, 6 + $aImageRowColum[0] * 9, 6 + $aImageRowColum[1] * 9) ProgressSet(Int(Map($i, 0, $iTotalCells-1, 0, 10) + 26.5 + $iSolve), String(Int(Map($i, 0, $iTotalCells-1, 0, 10) + 26.5 + $iSolve))&" Percent."); Update progress Next ;Then Draw the wall on the cells For $i = 0 To $iTotalCells - 1 $aImageRowColum = _GetCellPos($aiSize, $i) If StringMid($aCells[$i], 1, 1) = "1" Then Draw3By3($tBMP, 3 + $aImageRowColum[1] * 9, $aImageRowColum[0] * 9) EndIf If StringMid($aCells[$i], 2, 1) = "1" Then Draw3By3($tBMP, 6 + $aImageRowColum[1] * 9, 3 + $aImageRowColum[0] * 9) EndIf If StringMid($aCells[$i], 3, 1) = "1" Then Draw3By3($tBMP, 3 + $aImageRowColum[1] * 9, 6 + $aImageRowColum[0] * 9) EndIf If StringMid($aCells[$i], 4, 1) = "1" Then Draw3By3($tBMP, $aImageRowColum[1] * 9, 3 + $aImageRowColum[0] * 9) EndIf ProgressSet(Int(Map($i, 0, $iTotalCells-1, 0, 10) + 36.5 + $iSolve), String(Int(Map($i, 0, $iTotalCells-1, 0, 10) + 36.5 + $iSolve))&" Percent."); Update progress Next ;Draw start and exit. ;Start will be green and exit will be red Draw3By3($tBMP, 3, 3, '00FF00') ; Draw a green cube in the first cell(Top Left Corner) $aImageRowColum = _GetCellPos($aiSize, $iTotalCells - 1);Get row and colum of the last cell in the maze Draw3By3($tBMP, 3 + + $aImageRowColum[1] * 9, 3 + $aImageRowColum[0] * 9, 'FF0000') ; Draw a red cube in the last cell (Buttom right corner) ;And finaly save the bmp _BMPWrite($tBMP, @ScriptDir & "" & $sFilename & ".bmp") ProgressSet(Int(51 + $iSolve), String(Int(51 + $iSolve))&" Percent.") ; Update progress EndFunc ;==>Draw_Maze_Image Func Solve_Maze(Const ByRef $aiSize, ByRef $aCells) Local Const $iTotalCells = $aiSize[0] * $aiSize[1] Local $aCurrentPath[$iTotalCells+1000] ; Will store the current solved path Local $aSolveVisitedCells[$iTotalCells] ;This will store if the solver has been to a cell yet or not Local $iCurrentPathSubscriptNumber = -1 ; Current subscript number to write to in $aCurrentPath Local $iCurrentCell = 0 AddToCurrentPath($iCurrentCell, $iCurrentPathSubscriptNumber, $aCurrentPath) ; Add the cell the the path $aSolveVisitedCells[$iCurrentCell] = 1;Mark cell as visited ;Loop until the path has been found Local $CanGoOrNot Local $aYX[2] ; Store Y and X in an array ; used in solveing the maze While 1 ;Find a direction to go For $iDirection = 0 To 3 ;;If $iDirection = 4 Then ExitLoop $aYX = _GetCellPos($aiSize, $iCurrentCell); Convert it to rows and colums $CanGoOrNot = CanGo($aYX[0], $aYX[1], $iDirection, $aCells, $aSolveVisitedCells, $aiSize) ; Check if it can go there If $CanGoOrNot = 1 Then ExitLoop Next If $iDirection <> 4 Then Switch $iDirection Case 0 ; Up $iCurrentCell -= $aiSize[0] Case 1 ; Right $iCurrentCell += 1 Case 2 ; Down $iCurrentCell += $aiSize[0] Case 3 ; Left $iCurrentCell -= 1 EndSwitch AddToCurrentPath($iCurrentCell, $iCurrentPathSubscriptNumber, $aCurrentPath) ; Add the cell the the path $aSolveVisitedCells[$iCurrentCell] = True;Mark cell as visited Else If $iCurrentPathSubscriptNumber > 0 Then $iCurrentCell = $aCurrentPath[$iCurrentPathSubscriptNumber - 1] $iCurrentPathSubscriptNumber -= 1 ;Else ; $iCurrentPathSubscriptNumber -= 1 EndIf EndIf If $iCurrentCell = $iTotalCells - 1 Then ExitLoop WEnd ProgressSet(Int(76.5), "75 Percent"); Update progress Return $aCurrentPath EndFunc ;==>Solve_Maze Func Solve_Maze_ImgDraw(Const ByRef $aiSize, ByRef $aCurrentPath, Const ByRef $sFilename) Local Const $iTotalCells = $aiSize[0] * $aiSize[1] ;This function will use functions from the Drawing Functions region ;Open The Generated maze as a bmp handle Local $tBMP = _BMPOpen(@ScriptDir & "" & $sFilename & ".bmp") Local $aCurrentRowAndColum ;Go thoug all the cells one by one For $i = 0 To UBound($aCurrentPath) - 1 If $aCurrentPath[$i] = $iTotalCells - 1 Then ExitLoop If $aCurrentPath[$i] <> "" Then $aCurrentRowAndColum = _GetCellPos($aiSize, $aCurrentPath[$i]) Draw3By3($tBMP, 9 * $aCurrentRowAndColum[1] + 3, 9 * $aCurrentRowAndColum[0] + 3, 'FFFF00') If $aCurrentPath[$i] - $aiSize[0] = $aCurrentPath[$i + 1] Then ; Up Draw3By3($tBMP, 9 * $aCurrentRowAndColum[1] + 3, 9 * $aCurrentRowAndColum[0], 'FFFF00') Draw3By3($tBMP, 9 * $aCurrentRowAndColum[1] + 3, 9 * $aCurrentRowAndColum[0] - 3, 'FFFF00') ElseIf $aCurrentPath[$i] + 1 = $aCurrentPath[$i + 1] Then ;Right Draw3By3($tBMP, 9 * $aCurrentRowAndColum[1] + 6, 9 * $aCurrentRowAndColum[0] + 3, 'FFFF00') Draw3By3($tBMP, 9 * $aCurrentRowAndColum[1] + 9, 9 * $aCurrentRowAndColum[0] + 3, 'FFFF00') ElseIf $aCurrentPath[$i] + $aiSize[0] = $aCurrentPath[$i + 1] Then ; Down Draw3By3($tBMP, 9 * $aCurrentRowAndColum[1] + 3, 9 * $aCurrentRowAndColum[0] + 6, 'FFFF00') Draw3By3($tBMP, 9 * $aCurrentRowAndColum[1] + 3, 9 * $aCurrentRowAndColum[0] + 9, 'FFFF00') ElseIf $aCurrentPath[$i] - 1 = $aCurrentPath[$i + 1] Then ;LEft Draw3By3($tBMP, 9 * $aCurrentRowAndColum[1], 9 * $aCurrentRowAndColum[0] + 3, 'FFFF00') Draw3By3($tBMP, 9 * $aCurrentRowAndColum[1] - 3, 9 * $aCurrentRowAndColum[0] + 3, 'FFFF00') EndIf EndIf ProgressSet(Int(Map($i, 0, UBound($aCurrentPath) - 1, 0, 22.5) + 76.5), String(Int(Map($i, 0, UBound($aCurrentPath) - 1, 0, 22.5) + 76.5))&" Percent") ; Update progress Next ;reDraw start and exit. ;Start will be green and exit will be red Draw3By3($tBMP, 3, 3, '00FF00') ; Draw a green cube in the first cell(Top Left Corner) Local $aImageRowColum = _GetCellPos($aiSize, $iTotalCells - 1);Get row and colum of the last cell in the maze Draw3By3($tBMP, 3 + + $aImageRowColum[1] * 9, 3 + $aImageRowColum[0] * 9, 'FF0000') ; Draw a red cube in the last cell (Buttom right corner) ;And finaly save th bmp as Maze.bmp _BMPWrite($tBMP, @ScriptDir & "" & $sFilename & "_Solved.bmp") ProgressSet(100, "100 Percent") ; Update progress EndFunc ;==>Solve_Maze_ImgDraw #region Maze generation functions Func BustWall($Cell1, $Cell2, $iDirection, ByRef $aCells) ; This function will remove the walls in two adjacent cells. Direction is from first cell to second. Direction can be from 0 - 3. 0 = Up, 1 = Right, 2 = Down, 3 = Left $aCells[$Cell1] = StringReplace($aCells[$Cell1], $iDirection + 1, "0", 1, 2) ; Bust the wall between cell1 and cell2 in cell1 FlipDirection_br($iDirection) $aCells[$Cell2] = StringReplace($aCells[$Cell2], $iDirection + 1, "0", 1, 2) ; Bust the wall between cell1 and cell2 in cell2 EndFunc ;==>BustWall Func AddToCellStack($iCurrentCell, ByRef $iCurrentCellStackNumber, ByRef $aCellstack, Const ByRef $aiSize); This function will add the $Cell to the $aCellstack at the subscript of $CurretCellStackNumber ;Convert to Rows and colums Local $aCurrentCellRowColum = _GetCellPos($aiSize, $iCurrentCell) ;Add cell to the cell stack $aCellstack[$iCurrentCellStackNumber][0] = $aCurrentCellRowColum[0] $aCellstack[$iCurrentCellStackNumber][1] = $aCurrentCellRowColum[1] ;Add one to $iCurrentCellStackNumber $iCurrentCellStackNumber += 1 Return $aCurrentCellRowColum EndFunc ;==>AddToCellStack Func _Neighbours(Const ByRef $aCurrentCellRowColum, $Cell, ByRef Const $aVisitedCells, Const ByRef $aiSize) ; Check for Neighbours and store them in a string an 1 means that the neighbour has not been visited and an 0 means the neighbour has been visited it also checks for the edge of the maze. Local $NeighbourRowColum, $sNeighbours = '' Local Const $iTotalCells = $aiSize[0] * $aiSize[1] ;Check Clockwise ;Check Above cell If ($Cell - $aiSize[1] >= 0) And ($aVisitedCells[$Cell - $aiSize[1]] = False) Then $sNeighbours &= "1" Else $sNeighbours &= "0" EndIf ;Check Right Cell $NeighbourRowColum = _GetCellPos($aiSize, $Cell + 1) If ($aCurrentCellRowColum[0] >= $NeighbourRowColum[0]) And ($Cell + 1 < $iTotalCells) And ($aVisitedCells[$Cell + 1] = False) Then $sNeighbours &= "1" Else $sNeighbours &= "0" EndIf ;Check Buttom Cell If ($Cell + $aiSize[1] < $iTotalCells) And ($aVisitedCells[$Cell + $aiSize[1]] = False) Then $sNeighbours &= "1" Else $sNeighbours &= "0" EndIf ;Check Left Cell $NeighbourRowColum = _GetCellPos($aiSize, $Cell - 1) If ($aCurrentCellRowColum[0] <= $NeighbourRowColum[0]) And ($Cell - 1 >= 0) And ($aVisitedCells[$Cell - 1] = False) Then $sNeighbours &= "1" Else $sNeighbours &= "0" EndIf Return $sNeighbours EndFunc ;==>_Neighbours #endregion Maze generation functions #region Drawing Functions Func Draw3By3(ByRef $tBMP, $x, $y, $Colur = '000000') ; This function will draw a 3*3 Cube at a given x and y on the $tBMP _PixelWrite($tBMP, $x, $y, $Colur) _PixelWrite($tBMP, $x + 1, $y, $Colur) _PixelWrite($tBMP, $x + 2, $y, $Colur) _PixelWrite($tBMP, $x, $y + 1, $Colur) _PixelWrite($tBMP, $x + 1, $y + 1, $Colur) _PixelWrite($tBMP, $x + 2, $y + 1, $Colur) _PixelWrite($tBMP, $x, $y + 2, $Colur) _PixelWrite($tBMP, $x + 1, $y + 2, $Colur) _PixelWrite($tBMP, $x + 2, $y + 2, $Colur) EndFunc ;==>Draw3By3 #endregion Drawing Functions #region Maze solveing Functions Func CanGo($y, $x, ByRef Const $iDirection, ByRef Const $aCells, ByRef Const $aSolveVisitedCells, Const ByRef $aiSize);Returns 1 if the direction can the traveled and if not it will return 0. $Y = Row, $x = Colum, $iDirection = Direction Local $aYX[2] = [$y, $x] If StringMid($aCells[_GetCellPos($aiSize, $aYX)], $iDirection + 1, 1) = "0" Then Switch $iDirection Case 0 ; Up $aYX[0] -= 1 Case 1 ; Right $aYX[1] += 1 Case 2 ; Down $aYX[0] += 1 Case 3 ; Left $aYX[1] -= 1 EndSwitch If ($aSolveVisitedCells[_GetCellPos($aiSize, $aYX)] <> True) Then Return 1 ; IF cell has not been seen before by the solver EndIf Return 0 EndFunc ;==>CanGo Func AddToCurrentPath(ByRef Const $Cell, ByRef $iCurrentPathSubscriptNumber, ByRef $aCurrentPath) $iCurrentPathSubscriptNumber += 1 $aCurrentPath[$iCurrentPathSubscriptNumber] = $Cell EndFunc ;==>AddToCurrentPath #endregion Maze solveing Functions #region Seed Functions Func UseSeed($sRawSeed) Local Const $INT31u = Int('0x0080000000') ;; (2^31), int64. (2147483648) Local Const $INT32u = Int('0x0100000000') ;; (2^32), int64. (4294967296) If $sRawSeed = "" Then Return SetError(0, 1, RND_SeedTimed()) If StringLen($sRawSeed) > 10 Then Return SetError(1, 0, -1) $s = StringSplit($sRawSeed, "") $iSeed = 0 For $i = 1 To $s[0] $iSeed += (Asc($s[$i])*31^($s[0]-$i)) Next $iSeed = Int(Mod(Int($iSeed), $INT32u) - ($INT31u), 1) SRandom($iSeed) Return SetError(0, 0, $iSeed) EndFunc Func RND_SeedTimed($iSeed = Default) ;; Set seed base on current timer value. Returns used seed value. Local Const $INT31u = Int('0x0080000000') ;; (2^31), int64. (2147483648) Local Const $INT32u = Int('0x0100000000') ;; (2^32), int64. (4294967296) If Not IsNumber($iSeed) Then $iSeed = Int(Mod(Int(TimerInit()), $INT32u) - ($INT31u), 1) ;; wraps to [-2^31 and 2^31-1]. (has value shift) EndIf SRandom($iSeed) Return SetError(@error, @extended, $iSeed) EndFunc ;==>RND_SeedTimed #endregion Seed Functions #region Global Functions Func _GetCellPos(Const ByRef $aiSize, $vFind) ; This function will make a row and a colum into a Pos to be used with $aCells or $aCellstack, Or it will Make a Pos into an array with row and colum If IsArray($vFind) Then Local $CellPos = $vFind[0] * $aiSize[1] + $vFind[1] Return $CellPos Else Local $aCellRowColum[2] ; Will be used in the _GetCellPos function to temp.. store an array $aCellRowColum[0] = Int($vFind / $aiSize[1]) $aCellRowColum[1] = $vFind - ($aCellRowColum[0] * $aiSize[1]) Return $aCellRowColum EndIf EndFunc ;==>_GetCellPos Func FlipDirection_br(ByRef $iDirection) ; Flips the direction If $iDirection > 1 Then $iDirection -= 2 Else $iDirection += 2 EndIf EndFunc ;==>FlipDirection_br Func FlipDirection($iDirection) ; Flips the direction If $iDirection > 1 Then Return $iDirection - 2 Return $iDirection + 2 EndFunc ;==>FlipDirection Func array_filler(ByRef $aArray, $vFiller) ; Fills $aArray with $vFiller For $i = 0 To UBound($aArray) - 1 $aArray[$i] = $vFiller Next EndFunc ;==>array_filler Func Map($iValue, $iFromLow, $iFromHigh, $iToLow, $iToHigh) Return ($iValue - $iFromLow) * ($iToHigh - $iToLow) / ($iFromHigh - $iFromLow) + $iTolow EndFunc #endregion Global Functions Also be VERY carefull when generating very big mazes, my computer crashed when i was trying to generate a 500*500 maze. -FIXED Please post comments and/or any bug or problems. Sorry for any bad spelling that there may be.
×
×
  • Create New...