MAZIST - keep turning left!

[goksteroo]

MAZIST

A maze generation programme for the Amstrad CPC

By Geoff Camp, 2020

Maze generation routine based on 'MAZE' as published in 'More Basic Computer Games', edited by David H Ahl, published by Creative Computer Press. All other solving routines, grahics interface, sound, etc by myself.

History:

I originally wrote a maze generation programme (also called Mazist) on the Atari ST. It was also based on David Ahl's routines but modified to be graphically based and mouse controlled. I used STOS - a beautiful Basic language with easy music & sprite routines built in - to write that and it was released as shareware under the Undersoft label.

Before I had the Atari I had an Amstrad 464, and later a 6128. Loved these machines and programmed quite a bit in basic and taught myself some z80 machine code as well. Alas, once I went to 16bit I gave up using the 8bit CPC.

Today I have much free time and am revisiting my computer roots. I started this journey with a Raspberry Pi running Retropi and discovered the wonderful world of retro gaming. Firstly playing the old Atari and Nintendo games but then my world changed; I rediscovered the joys of those early 8 and 16 bit games. I tried to find some old CPCs and STs but alas their cost and rarity in Austrlia is prohibitive and has made the search a futile one so far. I now use a Raspberry Pi 'suitcase' setup with mouse/keyboard/joysticks to emulate my old CPCs and STs when I'm on the move and have emulators set up on my PC Tower to programme and play games.

But playing games is not always stimulating enough.... so I decided to try my hand at programming again and chose the CPC for this. I hadn't programmed anything in basic for many, many years but PDFs of the CPC manuals and firmware calls helped immensely. I started off with Conway's game of life. It didn't take long to write the programme in Basic and then came the steep learning curve - writing it in z80 machine code. I did release this on an Amstrad Facebook page as an example of speed of basic vs compiled basic vs pure machine code. It was a good learning exercise.

Many months passed and I pondered what to write next. I remembered Mazist I'd written on the Atari ST and thought this would be a good start on the CPC. I knew where to find the basic maze generation code but the fun would be converting it to a graphics interface, adding an on screen solve routine and some sort of user interface. After many weeks of programming, testing, tweeking, testing, changing my mind, rewriting some code, testing, tweeking, having a break, drinking too much coffee, rewriting some code and finally saying "That's enough!" I now present MAZIST for the CPC......

MAZIST - A maze generation programme for Amstrad CPC 464/664/6128

Functions:

Produces a graphics based maze in a selectable size ranging from 10-79 horizontal nodes and 10-49 vertical nodes. Each node is 2x2 squares and each square is 1x2 pixels so a 49x79 maze will fill a mode 0 screen.

The maze can be solved on screen by using the cursor keys to navigate to the exit. A mark can be left to assist in identifying your progress around the maze.

The maze can be saved (and loaded of course) along with any progress in solving the maze.

A solution to the maze can be computed (Mouse solve) if you a really stuck.

Intro Screen:

Press [L] to load a previously saved maze - the disc has one saved maze on it already. The load is in two parts - a screen shot of the maze it self loads first, then the array that describes the maze to the computer is loaded. Once loaded the 'Solve' routine is entered. Error checking is minimal.

Press  to get info and instructions for Mazist. Press [SPACE] at the end of each page to go to the next.

Press [SPACE] to enter the Maze Size routine.

Press [Q] to quit Mazist.

Maze Size:

Use the [CURSOR KEYS] to change the Horizontal and Vertical sizes for the maze.

Press [RETURN] when ready to generate the maze.

Maze Generation:

This page will display a counter for the number of nodes to compute. This is a recursive routine so the last few lines of nodes can take a longer time to compute than the early ones. The counter does not count down every node. I omitted this as the maximum sized maze would mean printing 3871 numbers. Time better spent calculating nodes. A sound cuee will let you know the CPC is still working so be patient with big mazes.

Solve:

Use the [CURSOR KEYS] to navigate around the maze. Pressing [SHIFT] at the same time will mark a spot or line so you can make and routes to try or not try or go back to. Once you have solved the maze you will be prompted to press [SPACE] to continue either by the word SPACE at the bottom of the screen or by a flashing line at the base of the screen if the maze is a large one.

Press 'S' to save the maze. This is a two part process. Firstly a screen shot is saved. Note that a few bytes of data are poked to the last line of the screen. This describes the position in the maze, its size, etc for when the maze if reloaded. Any saved maze will overwrite any previous maze. Error checking is minimal.

Press[Q] to quit the maze and return to the Intro Screen.

Press [M] for a Mouse solve for the maze.

Mouse Solve:

The CPC will computer the solution to that maze. A growing red line at the bottom of the screen will indicate progress and a sound cue will let you know that the CPC is still working. A small maze will be solved quite quickly. Once the mouse solution is displayed you will be prompted to press [SPACE] to continue either by the word SPACE at the bottom of the screen or by a flashing line at the base of the screen if the maze is a large one. The largest maze will take a cup of coffee to mouse solve! Press [SPACE] when you've finished admiring the solution it return to the Intro Screen.

The Future:

I've tried to compile the basic code but I am yet to find a compiler that will handle the large arrays in the CPCs limited memory. I've cut down the programme to the bare minimum and can get a maze generated but the programme soon crashes with memory errors. The only solution I can see is to convert the arrays to blocks of memory that are poked directly. This may be efficient enough on a 464 or I have to use bank switching and use the scren as a buffer. This is to be contemplated on as performance is greatly enhanced with compiled basic. The other option is to write Mazist in z80 machine code - a mildly daunting prospect for me.

Performance:

This table will give you some indication of maze generation times. I have used WinAPE to write Mazist and the Turbo in the following table refers its turbo mode. The times are in seconds and are an average as times depend on the amount of recursion that is needed towards the end on the maze generation process.

-------------------------------------------------------------------------------------------------------
|      Maze Size              |      Basic        |   Basic-Turbo |   Compiled    |Compiled-Turbo|
|-----------------------------------------------------------------------------------------------------|
| 10x10 (100 nodes)    |      6 -  4       |         3 - 1      |                    |                       |
| 20x20 (400 nodes)    |     30 - 11     |       13 - 4      |                    |                       |
| 40x40 (1600 nodes)  |    140 - 42    |       44 - 15    |    28 - 10     |       10 - 4       |
| 79x49 (3871 nodes)  |    380 - 98    |     130 - 36    |    65 - 24     |       25 - 9       |
-------------------------------------------------------------------------------------------------------
                              Times are: to Generate - to Print

Contact:

Any comments, suggestions, offers of assistance, etc can be directed to me at goksteroo@gmail.com

[Sykobee (Briggsy)]

3871 nodes using 16-bit ints should use under 8KB - surely there's enough memory?


And it's unlikely you need 16-bits per node? I haven't checked the code to see if each node is solid/clear or if its walls, but even walls only uses 4-bits, so some packing may work - edit: I see each nodes holds 2x2 squares already, so likely already packed. Do you use a recursive traversal function?

[Mr. DVG]

Great! I love long and impossible challenges (5 minutes to spawn this maze)!

[SRS]

Changing from "DIM w(79,49),v(79,49)" to poked array of bytes would give you 3,8k more free memory (POKEing and PEEKing or use a little RSX Tool).

(Values seem to be 0..3 -> you could get 4 numbers into one byte, which would give you - instead of 15484 Bytes - a memory footprint of 1936 Bytes.)

Also a "SYMBOL AFTER 256" gets you some more space


P.S.: Using "CLEAR INPUT" is a line that makes your program not working on a CPC464. "WHILE INKEY$<>"":WEND" should do the same job on 464 664 6128.

[goksteroo]

Hi all,
I'm converting the Maze generation to Machine Code, but I need some help. The MC mostly works but I've run into a couple of issues that I've spent the last couple of weeks trying to sort. Some are sorted but a couple remain. Any experienced MC programmers willing to look over the code and tell me where my logic/code is completely wrong? I have basically converted straight from the basic code so documentation of what is intended to happen is good, but the code is not as efficient as it could be - but I need to get it to work properly first. My intention is to convert most of the routines (or the whole program) to MC eventually but the code in the generation routine is obviously essential.
Leave a note, message me or email me at goksteroo at gmail dot com

Thanks,Geoff

[goksteroo]

All solved. I knew it'd be something simple that I'd seen so often when looking at the codethat I didn't see it. I was doing 8bit manipulation on a 16bit piece of data.
Maze generation is now phenomenal compared with basic - for the largest maze (79*49) time has been reduced from around 390 seconds to 15 seconds (down to 4.5 seconds in Winape Turbo mode)
Now to do the rest of the routines so other bits run faster - display and mouse solve especially.
Geoff