The main purpose of this project was to create a submission for the 1kB Challenge. It turns out that 1kB is way more than I needed for this project, so I made it my goal to make this program as small as I possibly could.

Hardware

At the heart of the project is an Intel 8048 Microcontroller, which has some limitations compared to today's high end microcontrollers, but that should be expected considering it is 40 years old. It has only 64 bytes of RAM and although its maximum clock speed of 11MHz seems decent, it is divided by 15 internally (I used a 11.0592MHz crystal because I like to live dangerously).

Normally, the program for the microcontroller would be stored on the microcontroller's 1kB of ROM, but because it is one-time-programmable, I can't overwrite what is already on it. Instead, I used external EEPROM. The microcontroller will skip the program in the internal ROM and instead access external memory with the help of a 74ls373 latch if the EA pin is pulled high.

The maze is displayed on a memory LCD. These types of displays are known for their low power consumption because they do not require the display to constantly be refreshed - not that it matters here with the large amount of power consumed by the microcontroller. For most modern applications of these displays, a frame buffer is used to store image data before writing to the display, but that would require 240*400/8 = 12,000 bytes of RAM. Instead, the program writes to the LCD as the maze is being generated.

The LCD needs a square wave signal to invert the polarity a few times every second. Instead of using software to do this, I used a 7555 CMOS timer.

Software

Software was written in assembly using the ASM48 assembler. A few tricks were used to minimize code size.

The algorithm used to generate the maze is the binary tree algorithm. This algorithm has some limitations such as having a strong diagonal bias and having straight lines along at least two edges, but it is relatively easy to implement with a small amount of RAM and code space.

Random-ish numbers based on the row and column are generated for each grid square in the maze to determine if that square will have an opening downwards to to the right. The formula used is: rr(row + column) ^ row (where rr is the rotate right assembly instruction). The parity of that result is calculated. If it is 0, the square will have an opening to the right. If it is a 1, the square will have an opening on the bottom. This method isn't perfect, but it works good enough for my purpose.

Data is written to the LCD one line at a time. Each command to write a line needs to contain the row number, but the row numbers are backwards for some reason (ie 0b10000000 = row 1 and 0b01000000 = row 2). Instead of incrementing the row and then reversing the number, I made it so that my SPI write function writes all data backwards (LSB first). Then I just had to make sure that all other data using that SPI write function is backwards.

The time from when power is applied to when the maze is finished being drawn is about 2.5 seconds.

The whole program uses only 9 bytes of RAM. 4 bytes are used for the stack, and 5 bytes of general purpose registers are used. By not needing to address any RAM, I saved some program space, but it makes it difficult to keep track of which functions are using which general purpose registers. Therefore, expanding this program would be difficult.

The total program size is 117 bytes.