Batch Maze Game:(Another Major speed improvement)

Discussion forum for all Windows batch related topics.

Moderator: DosItHelp

Post Reply
Message
Author
Sounak@9434
Posts: 100
Joined: 16 Dec 2016 22:31

Batch Maze Game:(Another Major speed improvement)

#1 Post by Sounak@9434 » 10 Mar 2017 05:54

Hello, everyone. This time I'm not here for a problem but for a little batch game. :D
I call it Maze_Game.bat

Code: Select all

::Changelog

::V:2.0 HOTFIX
Fixed a bug where Congratulation is not being displayed after finishing a level

V:2.0 (Another Major Speed Improvement+bugfix)
Optimized input and analysis process for best performance on higher levels
Edited Logo
Fixed bugs

V:1.2 (Major speed improvement+bugfix)
Updated lilgui.bat for speed improvement. Now it only recreates two/one lines for your each movement
Updated Align.bat for a slight speed improvement
Fixed some small bugs where "!" sign was not appearing
Added input check in "Defined specific window"

V:1.1.2(bugfix)
Fixed a bug where the main game would continue even if you lost(due to the timeout)
Fixed a very small bug where :options is written as :option mistakenly

V:1.1.1(bugfix)
Fixed a small bug where the timeout would go to negative if output is slow

V:1.1
Added Timeout Feature
Added changing of code page

V:1.0
Released The Game

Get V:2.0
MAZEGAME.zip
(9.09 KiB) Downloaded 220 times

Get V:1.2
MAZEGAME.zip
Maze_game V1.2
(9.06 KiB) Downloaded 119 times

Get V:1.1.2
MAZE112.zip
Maze_game V1.1.2
(8.96 KiB) Downloaded 133 times


Added A timeout feature and code page changing to support most of the PCs.
I would work on the implantation of the Neorobin's code.
For people like me who still enjoy classic games this is something they would like.
This is an almost pure batch Game. Only the maze generator uses a compiled application called amaze.exe
All files needed are provided under the zip_archive.
Try the game if you like.

//EDIT: I have finally optimized the game for best performance. It now gives almost smooth performance even in 51x51 grid level.

Any suggestion, bug report will be highly appreciated.

Code: Select all

::Special Thanks to
einstein1969
   For Neorobin's code
   For Suggestion to add timeout
   For finding a bug



Sounak
Last edited by Sounak@9434 on 13 Apr 2017 00:21, edited 9 times in total.

einstein1969
Expert
Posts: 763
Joined: 15 Jun 2012 13:16
Location: Italy, Rome

Re: Batch Maze Game

#2 Post by einstein1969 » 10 Mar 2017 10:53

Hi,

good work Sounak@9434!

can you add a timeout for completing a maze ? (this is very difficult)

For pure batch game you can use neorobin's maze generator:

Code: Select all

@echo off & setlocal enabledelayedexpansion & color f0 & chcp 437
set /a "wid=60,hei=40,wid|=1,hei|=1,iMax=wid*hei,cols=wid,row=hei+1"
title maze !wid! col X !hei! row
mode con cols=!cols! lines=!row!

set "maze="
for /l %%y in (1 1 !hei!) do for /l %%x in (1 1 !wid!) do set "maze=!maze!#"
REM {1,2,4,8} -> {17,18,20,24} <-> {Up,Left,Right,Down}
set "d17=y-=2" & set "d18=x-=2" & set "d20=x+=2" & set "d24=y+=2" & set "d=0"
set "w17=y+=1" & set "w18=x+=1" & set "w20=x-=1" & set "w24=y-=1" & set "w=0"
set "dirs=" & set "cells=." & set /a "x=2, y=2"

for /l %%* in () do (
  if defined n!x!_!y! ( rem backtrack point
    if !dirs:~-2! equ 0x1f ( rem all dirs be searched at backtrack point
      set "dirs=!dirs:~0,-2!"
      set "cells=!cells:~1!" & set "cells=!cells:*.=.!"
      if "!cells!"=="." (
        <nul set /p "=" & title Maze generation completed, any key to exit...
        >nul pause & exit
      )
      for /f "tokens=1-2 delims=.#" %%x in ("!cells!") do (set x=%%x&set y=%%y)
    ) else ( rem exist some dirs not searched at backtrack point
      for /f "tokens=1-2 delims=.#" %%x in ("!cells!") do (set x=%%x&set y=%%y)
      set "dir=!dirs:~-2!"

      set /a "visit=1, randS=!random! & 3, randE=randS | 4"
      for /l %%d in (!randS! 1 !randE!) do if !visit! neq 0 (
        set /a "dc=1<<(%%d &3), visit=dir&dc,dir|=dc, dc|=0x10"
        if !visit! equ 0 (
          for %%r in (d!dc!) do set /a "!%%r!"
          set "dirs=!dirs:~0,-2!!dir!"
    ) ) )
  ) else ( rem can pass point
    set /a "xin=x-2^x-wid,yin=y-2^y-hei,in=(xin&yin)>>31"
    if !in! equ 0 ( rem out of the region
      for /f "tokens=1-2 delims=.#" %%x in ("!cells!") do (set x=%%x&set y=%%y)
    ) else ( rem In the region
      set "cells=.!x!#!y!!cells!"
      set "n!x!_!y!=1"

      for %%r in (w!dc!) do for %%i in (1 2) do (
        set /a "ind=(x-1)+(y-1)*wid+1, lL=ind-1, lR=iMax-ind"
        for /f "tokens=1-3" %%a in ("!lL! !ind! !lR!") do (set maze=!maze:~0,%%a!+!maze:~%%b,%%c!)
        set /a "!%%r!"
      )
      for %%r in (d!dc!) do set /a "!%%r!"
      cls & <nul set /p "=!maze:+= !"

      set /a "dc=(1<<(!random!&3))|0x10"
      set "dirs=!dirs!!dc!"
      for %%r in (d!dc!) do set /a "!%%r!"
) ) )
exit


einstein1969.

Sounak@9434
Posts: 100
Joined: 16 Dec 2016 22:31

Re: Batch Maze Game

#3 Post by Sounak@9434 » 10 Mar 2017 23:24

Hi, einstein1969
einstein1969 wrote:can you add a timeout for completing a maze ? (this is very difficult)

After brainstorming for ideas for Half an hour I finally made it.
I updated the archive to version 1.1
Hope you would like it.

einstein1969 wrote:For pure batch game you can use neorobin's maze generator

I would be working on it. But That code may be kind of Slower than this whole thing already is.

Maybe setting blocks of all lines to different variables would fasten up the script a lot.
I would check that.

Thanks for your review after all.

Sounak

Sounak@9434
Posts: 100
Joined: 16 Dec 2016 22:31

Re: Batch Maze Game

#4 Post by Sounak@9434 » 11 Mar 2017 03:29

Fixed a few bugs.
The latest version now works fine.

And I checked generating display and echoing is taking 75% of time and getting input and processing is taking 25% of time on average on high width and length.

Have to work more on speeding up the script.
Till then, Enjoy :mrgreen:

Sounak

Sounak@9434
Posts: 100
Joined: 16 Dec 2016 22:31

Re: Batch Maze Game:(Major speed improvement)

#5 Post by Sounak@9434 » 10 Apr 2017 23:55

Updated lilgui.bat with new algorithm for display.
It now sets all lines at the beginning and only recreates two lines each turn for vertical movement and one line each turn for horizontal movement.
In simple words this version is 3X faster than the last one.
I also updated Align.bat with new code for a slight faster output
Some bugfixes are also done

Thanks everyone for 30+ downloads.

Enjoy :mrgreen:
And don't forget to give suggestions and inform me about bugs.

Sincerely,
Sounak

Sounak@9434
Posts: 100
Joined: 16 Dec 2016 22:31

Re: Batch Maze Game:(Another Major speed improvement)

#6 Post by Sounak@9434 » 12 Apr 2017 00:39

I have finally updated lilgui.bat with a optimized analysis which is another boost to speed improvement. Now this game runs smoothly on higher levels.
Hope you all would like the new updates.

I think I will leave this game as it is till any other suggestion as I am out of Ideas for improvements.

Anyway, Enjoy :mrgreen:

Sincerely,
Sounak

einstein1969
Expert
Posts: 763
Joined: 15 Jun 2012 13:16
Location: Italy, Rome

Re: Batch Maze Game:(Another Major speed improvement)

#7 Post by einstein1969 » 12 Apr 2017 15:39

Hi,

I have probed the V 2.0. and when i finish the game in time, the game change windows size and reinit a new maze without show the "congratulation" message.

einstein1969

Sounak@9434
Posts: 100
Joined: 16 Dec 2016 22:31

Re: Batch Maze Game:(Another Major speed improvement)

#8 Post by Sounak@9434 » 13 Apr 2017 00:29

einstein1969 wrote:the game change windows size and reinit a new maze without show the "congratulation" message.


Thanks again einstein1969 for finding a bug.
I actually planned to display the congratulation after the player finishes all the levels(64 in total), But that's a pretty long wait for a congratulation :D
So I edited the code. Now it shows congratulation each time you finish a level

Thanks for the suggestion/bug report.

And unfortunately I am still unable to implant neorobin's_maze_generator code. But I'll kepp on trying.

Anyway thanks.

Sincerely,
Sounak

CirothUngol
Posts: 46
Joined: 13 Sep 2017 18:37

Re: Batch Maze Game:(Another Major speed improvement)

#9 Post by CirothUngol » 28 Sep 2017 20:19

Thanks for the fun little batch game. I played it for awhile (looks great, quick and fun to play, challenging when the mazes get big) and was checking out neorobin's code... so now I've got mazes on my mind! I've been examining the different algorithms and decided to attempt the easiest depth-first maze generator I could muster. It's super simple, finitely iterative, totally stack-less, can produce mazes of any dimensions up to a maximum of ~2096 cells, and I've designed it as a direct replacement for amaze.exe. Simply substitute amaze.bat and make the following change to line# 14 of the file mazeit.bat:

Code: Select all

>%_filename% CALL amaze %lines% %cols% #

I was able to increase the maximum number of cells from ~1992 to ~2096 by removing the exterior walls from the maze string (adding them back during output). I eliminated the stack by storing the back-tracking information in the maze itself... leaving bread crumbs, Hansel und Gretel style! It was already checking in each direction for closed cells, so I added a check for crumbs. Bingo, no stack. I've added some other stuff to the version I'm currently playing with (retention of longest path, animated display) but I'm posting this version now since it's a ready-to-go command-line replacement (I've also posted it at Rosetta Code).

Code: Select all

:amaze Rows Cols [wall char]
:: A stack-less, iterative, depth-first maze generator in native WinNT batch.
:: Rows and Cols must each be >1 and Rows*Cols cannot exceed 2096.
:: Default wall character is #, [wall char] is used if provided.
:: 2017/09/27 v0.1 by CirothUngol

@ECHO OFF
SETLOCAL EnableDelayedExpansion

:: check for valid input, else GOTO :help
IF /I "%~2" EQU "" GOTO :amaze_help
FOR /F "tokens=* delims=0123456789" %%A IN ("%~1%~2") DO IF "%%~A" NEQ "" GOTO :amaze_help
SET /A "rows=%~1, cols=%~2, mTmp=rows*cols"
IF !rows! LSS 2    GOTO :amaze_help
IF !cols! LSS 2    GOTO :amaze_help
IF !mTmp! GTR 2096 GOTO :amaze_help

:: set map characters and use 1st character of %3 for wall, if defined
SET "wall=#"
SET "hall= "
SET "crumb=."
IF "%~3" NEQ "" SET "wall=%~3"
SET "wall=!wall:~0,1!"

:: assign width, height, cursor position, loop count, and offsets for NSEW
SET /A "cnt=0, wide=cols*2-1, high=rows*2-1, size=wide*high, N=wide*-2, S=wide*2, E=2, W=-2"

:: different random entrance points
:: ...on top
:: SET /A "start=(!RANDOM! %% cols)*2"
:: ...on bottom
:: SET /A "start=size-(!RANDOM! %% cols)*2-1"
:: ...on top or bottom
:: SET /A ch=cols*2, ch=!RANDOM! %% ch
:: IF !ch! GEQ !cols! ( SET /A "start=size-(ch-cols)*2-1"
:: ) ELSE SET /A start=ch*2
:: random entrance inside maze
SET /A "start=(!RANDOM! %% cols*2)+(!RANDOM! %% rows*2)*wide"
SET /A "curPos=start, cTmp=curPos+1, loops=cols*rows*2+1"

:: fill the maze with 8186 wall characters, clip to size, and open 1st cell
SET "mz=!wall!"
FOR /L %%A IN (1,1,6) DO SET mz=!mz!!mz!!mz!!mz!
SET bdr=!mz:~-%wide%!
SET mz=!mz:~3!!mz:~3!
SET mz=!mz:~-%size%!
SET mz=!mz:~0,%curPos%!!hall!!mz:~%cTmp%!

:: iterate #cells*2+1 steps of random depth-first search
FOR /L %%@ IN (1,1,%loops%) DO (
   SET "rand=" & SET "crmPos="
   REM set values for NSEW cell and wall positions
   SET /A "rCnt=rTmp=0, cTmp=curPos+1, np=curPos+N, sp=curPos+S, ep=curPos+E, wp=curPos+W"
   SET /A "wChk=curPos/wide*wide, eChk=wChk+wide, nw=curPos-wide, sw=curPos+wide, ew=curPos+1, ww=curPos-1"
   REM examine adjacent cells, build direction list, and find last crumb position
   FOR /F "tokens=1-8" %%A IN ("!np! !sp! !ep! !wp! !nw! !sw! !ew! !ww!") DO (
      IF !np! GEQ 0 IF "!mz:~%%A,1!" EQU "!wall!" ( SET /A rCnt+=1 & SET "rand=n !rand!"
      ) ELSE IF "!mz:~%%E,1!" EQU "!crumb!" SET /A crmPos=np, cw=nw
      IF !sp! LEQ !size! IF "!mz:~%%B,1!" EQU "!wall!" ( SET /A rCnt+=1 & SET "rand=s !rand!"
      ) ELSE IF "!mz:~%%F,1!" EQU "!crumb!" SET /A crmPos=sp, cw=sw
      IF !ep! LEQ !eChk! IF "!mz:~%%C,1!" EQU "!wall!" ( SET /A rCnt+=1 & SET "rand=e !rand!"
      ) ELSE IF "!mz:~%%G,1!" EQU "!crumb!" SET /A crmPos=ep, cw=ew
      IF !wp! GEQ !wChk! IF "!mz:~%%D,1!" EQU "!wall!" ( SET /A rCnt+=1 & SET "rand=w !rand!"
      ) ELSE IF "!mz:~%%H,1!" EQU "!crumb!" SET /A crmPos=wp, cw=ww
   )
   IF DEFINED rand ( REM adjacent unvisited cell is available
      SET /A rCnt=!RANDOM! %% rCnt
      FOR %%A IN (!rand!) DO ( REM pick random cell + wall
         IF !rTmp! EQU !rCnt! SET /A "curPos=!%%Ap!, cTmp=curPos+1, mw=!%%Aw!, mTmp=mw+1"
         SET /A rTmp+=1
      )
      REM write the 2 new characters into the maze
      FOR /F "tokens=1-4" %%A IN ("!mw! !mTmp! !curPos! !cTmp!") DO (
         SET "mz=!mz:~0,%%A!!crumb!!mz:~%%B!"
         SET "mz=!mz:~0,%%C!!hall!!mz:~%%D!"
      )
   ) ELSE IF DEFINED crmPos ( REM follow the crumbs backward
      SET /A mTmp=cw+1
      REM erase the crumb character and set new cursor position
      FOR /F "tokens=1-2" %%A IN ("!cw! !mTmp!") DO SET "mz=!mz:~0,%%A!!hall!!mz:~%%B!"
      SET "curPos=!crmPos!"
   )
)
SET /A open=cols/2*2, mTmp=open+1
ECHO !wall!!bdr:~0,%open%!!hall!!bdr:~%mTmp%!!wall!
FOR /L %%A IN (0,!wide!,!size!) DO IF %%A LSS !size! ECHO !wall!!mz:~%%A,%wide%!!wall!
ECHO !wall!!bdr:~0,%open%!!hall!!bdr:~%mTmp%!!wall!
ENDLOCAL
EXIT /B 0

:amaze_help
ECHO Usage:   %~0 Rows Cols [wall char]
ECHO          Rows^>1, Cols^>1, and Rows*Cols^<=2096
ECHO Example: %~0 11 39 @
ENDLOCAL
EXIT /B 0

Next up is a maze-solving algorithm (simple depth-first search) and then I want to try to implement a couple more (Hunt and Kill, Growing Tree, recursive division, and Eller's especially) before I attempt to do anything useful with them. Check out Think Labyrinth if mazes interest you at all, it's the Grand PooBah of maze algorithm sites!

Edit 1: fixed link to Rosetta Code.

pieh-ejdsch
Posts: 198
Joined: 04 Mar 2014 11:14
Location: germany

Re: Batch Maze Game:(Another Major speed improvement)

#10 Post by pieh-ejdsch » 01 Oct 2017 08:30

Hello,
i think your maze is not really a maze.
every cell of this big area is (wall - field to go - wall).
your algoritm go not throw the wall because it will go on a Wall.
when it go on a Wall, it must check the corners too.
if it goes throw a Wall it will only Check the field behind this one.
This are not the same things.
If you have a place 2x2 fields this is forbidden at on the wall - as same as a place of 3x3 fields at throw a wall.
Phil

CirothUngol
Posts: 46
Joined: 13 Sep 2017 18:37

Re: Batch Maze Game:(Another Major speed improvement)

#11 Post by CirothUngol » 02 Oct 2017 10:57

pieh-ejdsch wrote:Hello,
i think your maze is not really a maze.

Hmm, perhaps we have different definitions of what a maze is? It produces output fairly identical to amaze.exe (so perhaps it doesn't produce mazes either?). It also produces output fairly identical to many of the code samples on Rosetta Code (for non-graphic languages) and is directly solvable with a right or left-handed Wall Follow algorithm.
your algoritm go not throw the wall because it will go on a Wall.
Variables !np!, !sp!, !ep!, and !wp! hold the NSEW positions for adjacent cells (they are always 2 characters away in any direction). Variables !nw!, !sw!, !ew!, and !ww! hold the NSEW positions of adjacent walls (which are always 1 character away in any direction). Perhaps you're seeing the placement and removal of crumb characters that are placed in newly-vacated wall positions? These are used for back-tracking, alleviating the need for a stack.

...you have run the code to see that it produces a 1-character wide multiply interlinked passage with only one solution, right?

Code: Select all

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@       @     @         @   @       @   @         @     @         @           @
@@@@@ @ @@@ @ @@@@@ @ @ @ @ @@@ @@@ @ @ @ @@@@@ @ @@@ @@@ @@@ @@@ @ @@@ @@@@@ @
@     @     @     @ @ @ @ @   @ @   @ @   @   @ @   @     @   @   @ @   @   @ @
@ @@@@@@@@@@@@@@@ @@@ @ @ @@@ @@@ @@@ @@@@@@@ @ @@@ @ @@@@@ @ @@@@@ @ @@@ @@@ @
@       @ @     @ @   @   @ @   @           @ @ @   @ @   @ @ @     @ @ @     @
@@@@@@@ @ @ @ @@@ @ @@@@@@@ @@@ @ @@@@@@@@@ @ @ @ @@@@@ @ @ @@@ @@@@@ @ @ @@@@@
@   @ @ @   @     @   @ @       @ @   @       @ @     @ @ @ @   @ @   @ @   @ @
@ @ @ @ @@@ @@@@@@@@@ @ @ @@@@@@@@@ @ @@@@@@@@@ @@@@@ @ @ @ @ @@@ @ @@@ @@@ @ @
@ @   @   @   @       @       @     @     @     @   @   @ @   @   @ @     @ @ @
@ @@@ @@@ @@@ @@@ @@@@@@@@@@@ @@@ @@@@@@@ @ @@@@@@@ @@@@@ @@@ @ @@@ @@@ @@@ @ @
@   @   @ @     @ @       @ @   @ @     @   @ @         @   @   @   @   @   @ @
@@@ @@@ @ @@@@@ @ @ @@@@@ @ @@@ @ @@@ @@@@@@@ @ @ @@@@@ @@@ @@@@@ @@@ @@@ @@@ @
@   @   @   @     @ @     @     @   @     @     @     @   @   @   @   @   @   @
@ @@@@@ @@@ @@@@@@@ @ @@@@@ @@@@@@@ @ @ @@@ @@@@@@@@@ @@@ @@@ @ @@@ @@@ @@@ @ @
@ @   @ @   @       @ @ @   @       @ @     @   @   @ @   @   @ @       @   @ @
@ @ @ @@@ @@@ @@@@@@@ @ @ @@@ @@@ @@@@@@@@@@@ @ @ @ @ @ @@@ @@@ @ @@@@@@@ @@@ @
@ @ @   @     @     @ @ @ @     @             @   @ @ @   @   @ @ @       @   @
@ @ @@@ @@@@@@@ @@@ @ @ @ @ @@@@@@@@@@@@@@@@@ @@@@@ @ @@@@@@@ @ @ @@@@@ @@@ @@@
@   @     @   @ @ @ @   @ @ @       @       @ @     @   @   @   @   @   @ @ @ @
@ @@@ @@@@@ @ @ @ @ @@@@@ @@@ @@@@@ @ @@@@@ @@@ @@@@@ @ @ @ @@@@@@@ @ @@@ @ @ @
@   @       @     @           @       @         @     @   @           @       @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

The entrance and exit are arbitrarily placed to match the output of amaze.exe, my current code always places the exit at the end of the longest single path. I've used this same method to implement Growing Tree and Hunt & Kill algorithms, both of with seem to work fine (albeit rather slowly ^_^)
I implemented the algorithms myself from the explanations on Think Labyrinth, so if you still feel the algorithm and it's output is incorrect, I would truly like to know why it seems to behave appropriately so that I could correct them.

PS. I'm currently wasting plenty of time on a little animated batch maze generator/solver. So far, Depth-1st Backtracker (this), Growing Tree, and Hunt & Kill are working, but the only solver I've written is a simple Left or Right-handed Wall Follow. Totally useless, but fun to watch and a bunch of fun to create!

pieh-ejdsch
Posts: 198
Joined: 04 Mar 2014 11:14
Location: germany

Re: Batch Maze Game:(Another Major speed improvement)

#12 Post by pieh-ejdsch » 04 Oct 2017 14:18

ok your program goes.
I just think the ALGORITHM was made a bit cumbersome. It would be easier to put all fields in an array and to process this one after the other. a non-processed field may have no connection. that is to say, if no connection takes place from this field, it should at least create one. If there is already a connection, however, it should be able to select it again by chance.
Thus, connecting would only take a full array. In addition, the compound a> b should be the same as b> a. In a second array you pack only the connections and by reading the fields the length of the path can see.
one horizontal and one vertical
this is shorter

Code: Select all

for /f "delims=1234567890" %%H in ("%~1%~2") do goto :help
...
set "wall=%~3#"
set "wall=!wall:~0,1!"

Phil

Post Reply