3
\$\begingroup\$

Just for fun I have written a Conway's Game of Life in cmd batch file. I like writing in batch - its restrictions and limits are its appeal.

However - it is slow, very slow on a large grid. Any tips to speed it up?

I think the slowest part is the function GETNCOUNT - this gets the count of the neighbouring 'live' cells so it is called once per cell.

@ECHO OFF
SETLOCAL ENABLEDELAYEDEXPANSION

IF "%3"=="" GOTO HELP
SET WIDTH=%1
SET HEIGHT=%2
SET DENSITY=%3
SET LIFECYCLE=0

::::::::::::::::::::
:: Generate Grid 'A'
:: Also for safety, delete any Grid 'B' cells that might be in memory
FOR /L %%h IN (1, 1, %HEIGHT%) DO (
        FOR /L %%w IN (1, 1, %WIDTH%) DO (

            SET /A RAND=!RANDOM!*100/32768
            SET /A RAND=!RAND!+1

            IF !DENSITY! GEQ !RAND! (
                SET A[%%w][%%h]=@
            ) ELSE (
                SET "A[%%w][%%h]= "
            )

            SET B[%%w][%%h]=
        )   
)


::::::::::::::::::::::::::::::
:: TOP OF MAIN PROCESSING LOOP
::
:: Loop through all the Grid 'A' cells
::  - Count number of neighbours
::  - Check if alive or not
::  - If required assign new alive/dead status in Grid 'B'
::
:PROCESS
SET /A LIFECYCLE=%LIFECYCLE%+1

CLS
ECHO Conway's Game of Life. 
CALL :DISPLAY
ECHO Current lifecycle: %LIFECYCLE%

FOR /L %%h IN (1, 1, %HEIGHT%) DO (
        FOR /L %%w IN (1, 1, %WIDTH%) DO (

            CALL :GETNCOUNT %%w %%h
            IF "!A[%%w][%%h]!"=="@" (SET ALIVE=Y) ELSE (SET ALIVE=N)

            IF "!ALIVE!"=="Y" (
                IF !NCOUNT! LSS 2 (
                    SET "B[%%w][%%h]= "
                )
                IF !NCOUNT! EQU 2 (
                    SET B[%%w][%%h]=@
                )
                IF !NCOUNT! EQU 3 (
                    SET B[%%w][%%h]=@
                )
                IF !NCOUNT! GTR 3 (
                    SET "B[%%w][%%h]= "
                )
            )

            IF "!ALIVE!"=="N" (
                IF !NCOUNT! EQU 3 (
                    SET B[%%w][%%h]=@
                )
            )           
        )   
)

:: Now check if we have any Grid 'B' cells 
:: If so, assign these to Grid 'A' cells
FOR /L %%h IN (1, 1, %HEIGHT%) DO (
        FOR /L %%w IN (1, 1, %WIDTH%) DO (

            IF DEFINED B[%%w][%%h] (
                IF "!B[%%w][%%h]!"==" " (
                    SET "A[%%w][%%h]= "
                )
                IF "!B[%%w][%%h]!"=="@" (
                    SET A[%%w][%%h]=@
                )
            )       
        )   
)

:: loop back to the top of process to start again
GOTO PROCESS
::::::::::::::::::::::::::
:: BOTTOM OF PROCESS LOOP
::::::::::::::::::::::::::


:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:: THIS FUNCTION COUNTS THE NUMBER OF NEIGHBOURS FOR THE GIVEN X AND Y CO-ORDINATES
:: THE COUNT IS STORED IN VARIABLE 'NCOUNT'
::
:: TL | TM | TR
:: ML |    | MR
:: BL | BM | BR
::
:: %1=x %2=y
::
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:GETNCOUNT
SET NCOUNT=0

::::::
:: TOP
IF %2 EQU 1 (SET Y=%HEIGHT%) ELSE (SET /A Y=%2-1)
:: TOP-LEFT
IF %1 EQU 1 (SET X=%WIDTH%) ELSE (SET /A X=%1-1)
IF !A[%X%][%Y%]! EQU @ (SET /A NCOUNT=!NCOUNT!+1)
:: TOP-MIDDLE
SET X=%1
IF !A[%X%][%Y%]! EQU @ (SET /A NCOUNT=!NCOUNT!+1)
:: TOP-RIGHT
IF %1 EQU %WIDTH% (SET X=1) ELSE (SET /A X=%1+1)
IF !A[%X%][%Y%]! EQU @ (SET /A NCOUNT=!NCOUNT!+1)

:::::::::
:: MIDDLE
SET Y=%2
:: MIDDLE-LEFT
IF %1 EQU 1 (SET X=%WIDTH%) ELSE (SET /A X=%1-1)
IF !A[%X%][%Y%]! EQU @ (SET /A NCOUNT=!NCOUNT!+1)
:: MIDDLE-RIGHT
IF %1 EQU %WIDTH% (SET X=1) ELSE (SET /A X=%1+1)
IF !A[%X%][%Y%]! EQU @ (SET /A NCOUNT=!NCOUNT!+1)

:::::::::
:: BOTTOM
IF %2 EQU %HEIGHT% (SET Y=1) ELSE (SET /A Y=%2+1)
:: BOTTOM-LEFT
IF %1 EQU 1 (SET X=%WIDTH%) ELSE (SET /A X=%1-1)
IF !A[%X%][%Y%]! EQU @ (SET /A NCOUNT=!NCOUNT!+1)
:: BOTTOM-MIDDLE
SET X=%1
IF !A[%X%][%Y%]! EQU @ (SET /A NCOUNT=!NCOUNT!+1)
:: BOTTOM-RIGHT
IF %1 EQU %WIDTH% (SET X=1) ELSE (SET /A X=%1+1)
IF !A[%X%][%Y%]! EQU @ (SET /A NCOUNT=!NCOUNT!+1)
::ECHO BR=X:%X% Y:%Y%

GOTO EOF


::::::::::::::::::::::::::::::::::::::::::::
:: THIS FUNCTION DISPLAYS GRID 'A' ON SCREEN 
::::::::::::::::::::::::::::::::::::::::::::
:DISPLAY
SET TOP=
SET BOT=
FOR /L %%h IN (1, 1, %height%) DO (

    IF %%h EQU 1 (FOR /L %%w IN (1, 1, %width%) DO (SET TOP=_!TOP!))
    IF %%h EQU 1 ECHO .!TOP!.

    SET ROW=
    FOR /L %%w IN (1, 1, %WIDTH%) DO (
            SET ROW=!ROW!!A[%%w][%%h]!
    )

    ECHO ^|!ROW!^|

    IF %%h EQU %height% (FOR /L %%w IN (1, 1, %width%) DO (SET BOT=~!BOT!))
    IF %%h EQU %height% ECHO `!BOT!'    
)
GOTO EOF


:HELP
ECHO/
ECHO 'Conway's Game of Life' - Batch Edition - Chazjn 25/02/2017
ECHO ===========================================================
ECHO Usage is as follows:
ECHO    life [width] [height] [%%density]
ECHO E.g.
ECHO    life 8 5 25
ECHO/
ECHO For more infomation visit: https://en.wikipedia.org/wiki/Conway's_Game_of_Life

GOTO EOF


:EOF
\$\endgroup\$
1
\$\begingroup\$

Ok so it turns out that the using CALL in a batch script is very slow. So calling a function once per cell was very expensive time-wise.

So I knew I had to move the logic from the function GETNCOUNT into the main processing loop. However the main issue I ran into here was variable expansion.

I am storing each cell value in a variable named A[x][y] e.g. A[1][1], A[1][2], A[1][3] etc. So after I had calculated the x and y value of the neighbouring cell that I wanted to check, I had to get the value of that variable somehow.

I tried all kinds of double-expansion-nested syntax, e.g. !A[!X!][!Y!]! but this just resulted in XY because the script was trying to expand variables !A[! !][! !]!.

In the end I tried a FOR loop and this worked very nicely. E.g.:

FOR /F "tokens=1,2" %%a IN ("!X! !Y!") DO (ECHO !A[%%a][%%b]!)

So what this is doing is expanding and assigning !X! and !Y! to variables local to the FOR loop %%a and %%b. Thus I can inject them into my cell variable and expand this to get the value its assigned.

So here is the 'final' code, it works much much faster than before. I am pretty satisfied with the performance now, I don't think I can get much more speed out of it.

What I would like to do next is figure out a way to exit gracefully as the only way currently is to press CTRL+C. But that's for another time...

@ECHO OFF
SETLOCAL ENABLEDELAYEDEXPANSION

IF "%3"=="" GOTO HELP
SET WIDTH=%1
SET HEIGHT=%2
SET DENSITY=%3
SET GENERATION=0
SET /A CELLCOUNT=%WIDTH%*%HEIGHT%
SET ALIVECOUNT=0

::::::::::::::::::::
:: Generate grid 'A'. This grid holds the cell layout for display
:: Also for safety, delete any grid 'B' cells that might be in memory
:: Grid 'B' used to store temporary cell values before they are assigned to grid 'A' 
FOR /L %%h IN (1, 1, %HEIGHT%) DO (
        FOR /L %%w IN (1, 1, %WIDTH%) DO (

            SET /A RAND=!RANDOM!*100/32768

            IF !DENSITY! GEQ !RAND! (
                SET A[%%w][%%h]=@
                SET /A ALIVECOUNT=!ALIVECOUNT!+1
            ) ELSE (
                SET "A[%%w][%%h]= "
            )

            SET B[%%w][%%h]=
        )   
)

::::::::::::::::::::::::::::::
:: TOP OF MAIN PROCESSING LOOP
::
:: Display grid 'A'
:: Loop through all the Grid 'A' cells:
::  - Get values neighbouring cells
::  - Get count of alive neighbours 
::  - Apply 'Game of Life' rules and store resulting value in grid 'b' cell
:: Assign grid 'b' cell values to grid 'a' cell values
:: Loop back to start process again
:PROCESS
SET /A GENERATION=%GENERATION%+1
CLS
ECHO Conway's Game of Life. 
ECHO Generation: %GENERATION%
ECHO Live Cells: %ALIVECOUNT%/%CELLCOUNT%
CALL :DISPLAY

IF "%ALIVECOUNT%"=="0" (GOTO EOF)

SET ALIVECOUNT=0
SET COUNTER=0
FOR /L %%h IN (1, 1, %HEIGHT%) DO (
    FOR /L %%w IN (1, 1, %WIDTH%) DO (

        SET /A COUNTER=!COUNTER!+1
        TITLE Calculating Cell !COUNTER!/%CELLCOUNT%

        SET X=0
        SET Y=0
        SET NCOUNT=0

        REM Find the 3 cells above this cell
        IF %%h EQU 1 (SET Y=%HEIGHT%) ELSE (SET /A Y=%%h-1)
        IF %%w EQU 1 (SET X=%WIDTH%) ELSE (SET /A X=%%w-1)
        FOR /F "tokens=1,2" %%a IN ("!X! !Y!") DO (IF "!A[%%a][%%b]!"=="@" (SET /A NCOUNT=!NCOUNT!+1))  
        SET X=%%w
        FOR /F "tokens=1,2" %%a IN ("!X! !Y!") DO (IF "!A[%%a][%%b]!"=="@" (SET /A NCOUNT=!NCOUNT!+1))
        IF %%w EQU %WIDTH% (SET X=1) ELSE (SET /A X=%%w+1)
        FOR /F "tokens=1,2" %%a IN ("!X! !Y!") DO (IF "!A[%%a][%%b]!"=="@" (SET /A NCOUNT=!NCOUNT!+1))

        REM Find the 2 cells left and right of this cell
        SET Y=%%h
        IF %%w EQU 1 (SET X=%WIDTH%) ELSE (SET /A X=%%w-1)
        FOR /F "tokens=1,2" %%a IN ("!X! !Y!") DO (IF "!A[%%a][%%b]!"=="@" (SET /A NCOUNT=!NCOUNT!+1))
        IF %%w EQU %WIDTH% (SET X=1) ELSE (SET /A X=%%w+1)
        FOR /F "tokens=1,2" %%a IN ("!X! !Y!") DO (IF "!A[%%a][%%b]!"=="@" (SET /A NCOUNT=!NCOUNT!+1))

        REM Find the 3 cells below this cell
        IF %%h EQU %HEIGHT% (SET Y=1) ELSE (SET /A Y=%%h+1)
        IF %%w EQU 1 (SET X=%WIDTH%) ELSE (SET /A X=%%w-1)
        FOR /F "tokens=1,2" %%a IN ("!X! !Y!") DO (IF "!A[%%a][%%b]!"=="@" (SET /A NCOUNT=!NCOUNT!+1))
        SET X=%%w
        FOR /F "tokens=1,2" %%a IN ("!X! !Y!") DO (IF "!A[%%a][%%b]!"=="@" (SET /A NCOUNT=!NCOUNT!+1))
        IF %%w EQU %WIDTH% (SET X=1) ELSE (SET /A X=%%w+1)
        FOR /F "tokens=1,2" %%a IN ("!X! !Y!") DO (IF "!A[%%a][%%b]!"=="@" (SET /A NCOUNT=!NCOUNT!+1))  

        REM Check if this cell is alive or not
        IF "!A[%%w][%%h]!"=="@" (
            SET ALIVE=Y
            SET /A ALIVECOUNT=!ALIVECOUNT!+1
        ) ELSE (
            SET ALIVE=N
        )

        REM Assign live status to grid 'B' based on rules
        IF "!ALIVE!"=="Y" (
            IF !NCOUNT! LSS 2 (
                SET "B[%%w][%%h]= "
            )
            IF !NCOUNT! EQU 2 (
                SET B[%%w][%%h]=@
            )
            IF !NCOUNT! EQU 3 (
                SET B[%%w][%%h]=@
            )
            IF !NCOUNT! GTR 3 (
                SET "B[%%w][%%h]= "
            )
        )

        REM Assign dead status to grid 'B' based on rules
        IF "!ALIVE!"=="N" (
            IF !NCOUNT! EQU 3 (
                SET B[%%w][%%h]=@
            )
        )   
    )   
)

:: Now check if we have set any Grid 'B' cells 
:: If so, assign these cell values to Grid 'A' cells
FOR /L %%h IN (1, 1, %HEIGHT%) DO (
        FOR /L %%w IN (1, 1, %WIDTH%) DO (

            IF DEFINED B[%%w][%%h] (
                IF "!B[%%w][%%h]!"==" " (
                    SET "A[%%w][%%h]= "
                )
                IF "!B[%%w][%%h]!"=="@" (
                    SET A[%%w][%%h]=@
                )
            )       
        )   
)

:: Loop back to the top of process to start again
GOTO PROCESS


::::::::::::::::::::::::::::::::::::::::::::
:: THIS FUNCTION DISPLAYS GRID 'A' ON SCREEN 
::::::::::::::::::::::::::::::::::::::::::::
:DISPLAY
SET TOP=
SET BOT=
FOR /L %%h IN (1, 1, %height%) DO (

    IF %%h EQU 1 (FOR /L %%w IN (1, 1, %width%) DO (SET TOP=_!TOP!))
    IF %%h EQU 1 ECHO .!TOP!.

    SET ROW=
    FOR /L %%w IN (1, 1, %WIDTH%) DO (
            SET ROW=!ROW!!A[%%w][%%h]!
    )

    ECHO ^|!ROW!^|

    IF %%h EQU %height% (FOR /L %%w IN (1, 1, %width%) DO (SET BOT=~!BOT!))
    IF %%h EQU %height% ECHO `!BOT!'    
)
GOTO EOF

:HELP
ECHO/
ECHO 'Conway's Game of Life' - Batch Edition - Chazjn 01/03/2017
ECHO ===========================================================
ECHO Usage is as follows:
ECHO    life [width] [height] [%%density]
ECHO E.g.
ECHO    life 15 10 25
ECHO/
ECHO For more infomation visit: https://en.wikipedia.org/wiki/Conway's_Game_of_Life
GOTO EOF

:EOF
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.