[C] Endless Mazes on the CE - Cemetech | Forum

matkeller19
1
New Member (Posts: 82)

[C] Endless Mazes on the CE
27 Jun 2022 11:04:31 pm

For the past few months or so, I have been somewhat interested in mazes (and not Risk so that project has been on hold although I did get a bit of the attack phase and increased the quality of the map) and looked into many of the various maze algorithms that exist. I explored many of these algorithms and implemented DFS recursion, Aldous-Broder, and Wilson's algorithms on the CE with much help from this series of blog posts. The latter two tend to produce less biased mazes with a variety of short and long corridors so I decided to use them in this project: a zen-like game of endless mazes. Once you finish one, a new one will automatically be generated. There is no timer and no scoring, just completing the mazes. I plan to include maze size selection and color customizations, but have done none of the graphics, only the generating code.

As of right now, the code utilizes Aldous-Broder to generate the first 1/3 of the maze (I saw a comment saying this is roughly the ideal convergence time) before switching and completing the rest with Wilson's. As I mentioned, I do not have any fancy graphics to share as of right now. However, this is a 50x50 maze generation I ran in CEmu that took ~6 seconds to complete. I doubt I would allow mazes that large in the final program due to graphics but I wanted to semi-stress test it.

Code:

######################################################################################################


#         # #   #       # #   #   #           #   # #               #   # # #       #     #     #   #


# # ### # # ### ##### # # ### # ### ##### # # # # # # ####### ##### # ### # ##### # ##### # ##### ###


# #   # #     #   #   # #   # #   # #     # # # # #     #     # #     #     #   # #       #     #   #


### # ### ##### # # ####### # # ##### # # # # # ### ########### ### ### # # # ##### # # ##### # # # #


#   #   #   #   #   #       # #   #   # # # # #   #   # #   #     #   # # # # #     # #       # # # #


### # # ### ##### # # ### ### # ####### ### ##### ### # # ### # ### ### ### # # # ### ####### # # ###


# # # # #       # # # #       #   #   # #   #     #     #     #   #   # #   # # # #   #       # #   #


# # # ### ### # # ### # ##### # ##### ##### # # # ##### # ##### ######### # # # ### ### ######### ###


# # # # # #   #       #     #         # #     # # #     # #   #       # # #   #   #   #   #       # #


# # ### ####### ######### # ### # # ### ### # ####### ####### # # ### # ### # # # ##### # # ### ### #


#     #         # # #     # # # # #     #   # # #     #         #   #   # # #   # # #   #   #   #   #


##### ##### ### # # ### ##### ### # ### # ### # # ### ### ### ### ####### # # ##### # ### ### # # ###


#     # #     #   #       #     # # #   # # # #   # # #   #   # #   #       #     #     # # # #     #


### ### # ##### ####### ##### # # # ### ### # # # # ### ##### # # # ##### # # ### ### ##### # ##### #


#   #     # # #   #           # # #   #       # #   # # # # # #   # #     # # #   #       #       # #


# # # ##### # ##### # # ### ######### # ##### # # ### ### # # # ### # ##### # ####### ##### ####### #


# # #     # #       # # # # #     #   # #   #   #   # # #     #   #       # #     # # #         # # #


######### # ### ##### ### # # ############# ##### ### # # ### ##### ########### ### # ####### ### # #


# #     # #       #   # # # # # #       #     #     #   #   #   #   #     # # # #       #     #     #


# # # ### ### ### ##### # # # # ##### # ##### # ##### ### ########### ##### # # ############# ### ###


#   #   #   # #   # # #   #   # #   # #       #     #     # #   #         #   #             #   # # #


# ########### # ### # # # # # # # ####### ### # # ### ### # # ### ##### ### # ### ### # ### ##### # #


#         #   # #       # # #     #       #     #       # #         # #   # #     #   # # #   #     #


# ########### ### ##### ######### ### ### # # ### ##### ####### # ### # ######### ##### # # # # ### #


#   # #     # #   # #       # #     #   # # # #     # # #       # # # # #   #   #   #     # # #   # #


# # # # ####### ### ### # ### ### ####### # ######### ##### ### ### # # # ### ######### ##### ##### #


# #   #       # #     # # # # # # #   # # #   #   # #       #   # # #   #     # # #   #   #       # #


# ### # ##### ### ### # ### # # ### ### # ### # # # # ### # ##### # ##### # ### # ### ##### ##### # #


# #   #     #   #   #         #   #         # # #   # # # #       #     # #     # # #   # # #   # # #


# ### # ######### ##### ##### ### ### ########### ##### ######### ### # ##### # # # # ### # ### #####


#   #   #     #   #   # #         # #       #     # #     # # # #     # #     #     # #   # #       #


####### # ### ##### ### # ######### ##### # # ### # ### # # # # # ### ##### ### # # # ### # # ##### #


#   #       # # #   #   # #     # #     # # # # #   # # # #       #     # #   # # #   # #   # #     #


### # ##### ### # ####### # # # # # ##### ### # # ### # ####### ######### ### # ### ### # # # ### # #


# #   #     #             # # #         #   # #               #       # # #   #   #     # #   #   # #


# ### ##### # ######### # ####### # # ### ### ### ##### # ### ### ### # # # # ####### ##### ##### # #


#   #   #     #   #   # #     #   # # #   #   # # #   # # #   #     # #     #   # # #   #       # # #


### # ##### # ### # ### # ####### # # ##### ### # # ### # ##### ### # # ### # ### # # ##### # ### # #


#   # # #   #   #   # # #   #     # #     #   # #   #   #       #   # # #   # #   # #       # # # # #


### # # ### # ##### # # ##### # # ### # ####### ### ### ### ##### ####### # ### ### # # ### ### # ###


#   # #   # # #       # # #   # # # # # #       # # #   #     # #       # #     # #   # # # # #     #


# # # ### ##### ### ##### ######### ### # ####### ##### ##### # # ##### # ### ### # # ### ### # # ###


# # # #       # #   # # #   #   # #   #         #     #   #   # #   #       #   #   #     #     #   #


# ### ### # ### # ### # # ##### # ### # ##### # ### ########### ######### # # # ######### ####### # #


# #   # # # #   #   #   #   #             #   # #   #   #   #   # # #     # # # #           # # # # #


# # # # ### # ######### ### # ### ########### ### # ### ### # # # # ####### ################# # #####


#   #           # #             # #   #     #     #   #   #   #   #       #   #           #   # # # #


# ### ########### ##### ### ### # ### ##### # # ### # # # ### # ##### # # # # ######### # # # # # # #


# # #   #   #     #     #     # #   #     #   #   # # # #     #     # # #   #     #     # # #       #


# # # # # ### ### # # # ### ### ####### ### ### ### ######### # ##### # # ### ######### ##### # # ###


# #   #   #   #     # # # # #   #     #   #   # # #   # #   # # #     # # #   #   #         # # #   #


# ### ########### # ### # ##### ##### # # # ### # ##### # ### ### # ##### ### ### ##### ### ##### ###


#   #         #   # # # #     #     #   # #   # # #   # #       # # #       #   # #   # #   # # #   #


# ########### ####### # # ### ### # ##### ##### # # ### ####### ### ### ##### ### # # # # # # # # # #


# # #       #     # #       # # # # #       # #   #     # #     #     #     #   #   #   # # #     # #


# # ##### # ### ### # ### ##### ####### # ### ##### ##### ### # ##### ########### ### ####### # # # #


#     #   # # #         # #     #       # #     #   #       # # # # #         #   #           # # # #


# # ### ##### # # ### ######### ### ### ### ### ### # ##### # ### # # ##### ### ################# # #


# #       #   # #   #         # #     #   # # #       #         # #   #   # #     #     #   # # # # #


##### # ##### ##### # ####### # # ####### ### # ### ##### ### ### # ### ### ##### ##### ### # # ### #


# # # #   # #     # # #     #   #   #   # #       #     # #     # # #               #   # #     #   #


# # # ### # # ### # # ##### ### ### ### ############# ####### # # # ##### ### # # ##### # ### # #####


#     #     # #     #       # #   #     #     #     #     #   #   # # #     # # #   #   #   # #   # #


### ### ######### ### ### ### ######### # # ### # # # ####### ####### # # ##### ##### # # ##### # # #


# # #           # #   #     #     #     # #     # #   #   #   #     #   #     #     # #         #   #


# ### ########### ### ### ### ####### # ### ### # ### # # ### ##### ### ##### ########### ### # ### #


#     #   # #   #   # # # #   #       #   #   # #   #   # # #       #     #   #           #   # # # #


# # ##### # # ### ### # # # ### ####### ### ### # ######### # ### # ### ##### ### ### # ##### ### ###


# #   # # #   #   #     #     #     # # #     # # # # # #   # #   #   #   #     # #   # #   #       #


##### # # ### ####### ### # ##### ### ####### ##### # # # ### ### ####### # # ##### ### # ###########


#   #   #   #       #   # #         # #       # # # #       # #           # # # #     #             #


# # ### # ##### ### # # # ########### ####### # ### # ##### ### # ### ### ### # ######### ### ### ###


# # #   #     # #   # # #   #   # # # #       #   #   # #     # #   # #   #     #       #   #   # # #


# ##### # # ### ### ### ##### # # # # # ######### ##### ##### ######### ####### ##### # ######### # #


#   #   # #     #       #   # #   #     #             #     #   #   #   # #           # #   # #     #


# # ####### ########### ### # # # # ### # ### # ### ### ####### # ### # # ####### ### # ### # ##### #


# # #   #           #         # # #   #     # # # # #             #   # #   #   #   # # #         # #


# ### ####### # # ### ### ########### # # # # ### ### ##### # ##### ##### ### # # ####### # ####### #


#     #       # # # # # # #   #       # # # #   #     #   # # #   # #         #           # # #   # #


# ######### ### ### # # # # # ### # ##### ### ### ### # # ####### ### ##### ##### ##### ### # # ### #


#     #   # #           # # #     # # #   #         #   #   #     #   # #     #     # # # #   # #   #


# ### # ##### # ### ### ### ####### # # ######### ######### # ######### ### ##### # # ### # # # # ###


# #         # # # #   #   # # # # #   #   #       #               #       # # #   #     # # #       #


# ### ##### # ### ########### # # # ##### ##### # ### # # ##### ### ######### ######### # ##### # ###


#   #     # #   #     #   #   #   #     #     # # # # # # #     #   # #   # # #   # #   #       # # #


# ########### # # ##### # # ### ### ##### ####### # ######### # # ### ### # # # ### # ### ### ### # #


#   # #   #   # #     # # # #       # #   # #     # #         #   #   #       # #     # # # # #     #


### # ### # ####### ### ### ####### # ##### ### # # ### ##### ### ### ### ##### # ##### ### # #######


# #     #     #                 #   # #   #   # # #         #   #   #   # #         #   #       # # #


# ### ####### ### ### ### ##### ### # # ### ######### # ########### # ### # # ####### # ######### # #


#         #     # #   # #   #       #           #     # # #       # # #     #         #           # #


# ### ### ### ### ### # ### ############# ### # # # ### # ##### ##### # ##### # ### # ### ######### #


# # #   #           #   #   #               # # # # #       # #   #     #   # #   # #   #           #


# # ### ##### # ##### ##### # ##### # ##### ### ### # ##### # # ######### ### ############### # #####


# #     #   # #   # # #     #   #   # # # #   # #   # #     # # # # #     #   #   #       # # #   # #


# ######### ##### # # ##### # ##### # # # ### # ### ######### # # # # # # ### # ####### ### # ##### #


#   #     #       #   # # #     # # # # #     # # #             #     # #         #       #         #


### ### # ### ######### # # # # # ### # ### ### # ### ##### # ### # ### ####### ##### # ### # ### ###


#       # #             #   # #     #     # #       #   #   #   # #   #     #   #     #     # #     #


#####################################################################################################

The algorithms provide only one path for any start and end cell in the maze and uses every cell in the grid.

tr1p1ea
1
Cemetech Expert (Posts: 1742)

28 Jun 2022 12:00:50 am

That's very cool and for a start that is a pretty good speed for a maze that size I imagine.

When you do look to use graphics, what are you thinking of doing?

matkeller19
1
New Member (Posts: 82)

29 Jun 2022 10:01:22 pm

Sat down and worked on graphics a bit today. Each cell only requires 2 walls so I am simply iterating through each cell and printing the walls for each one. I am using variables for background color, wall color, player color, and finish color (though the latter two haven't been implemented yet) so players can customize their game. I have it set so the cells are automatically scaled to a maximum x and y so the mazes are always as large as they can be. I'm not sure what I want to use for maximum maze size, but I'm thinking of tracing the user's path with a line through each cell so I could technically go as small as 3 pixels per cell:

This is what the auto-scaling looks like. It currently tries to get as close to being 300x220px without going over but those can very easily be adjusted depending on how I design the UI.

matkeller19
1
New Member (Posts: 82)

19 Aug 2022 12:03:43 am

Long time, no post.

Over the past two days I have been getting into this project once again. I decided to tackle the movement of the character first. For this, I am using two timers: one to track key repeats and one to track the framerate. I plan to allow the key repeat to be modifiable so users can adjust how quickly key presses are repeated. Likewise, by limiting the framerate, I can easily adjust the length of movement animations. In the screen recording below, I used an animation length of 3 frames at 60fps but I could see it being beneficial to allow users to adjust this animation length as well.

The second major accomplishment I completed was a small little option I wanted to make: allowing users to watch as the maze is generated. Right now, this is being implemented using small buffer blitting and a delay but hopefully I will be able to add an option to adjust the time between cell generation as well. The recording highlights the algorithms used to generate the mazes (Aldous-Broder followed by Wilson's). Each cell is being delayed by 10ms because running it without a delay is practically impossible to watch - it generates too quickly. This recording is using the program's fixed maximum maze dimensions which are, in my opinion, unplayable, so I plan to adjust these in the future (or let users just mess around and use whatever they prefer).

Let me know any suggestions for settings or features you would like to see. The current options planned are:

Lai
Newbie (Posts: 9)

27 Sep 2023 01:42:17 pm

Probably a dead post, but wanted to see if it was finished. If it is, could I maybe get my hands on a copy?

matkeller19
1
New Member (Posts: 82)

28 Sep 2023 11:19:38 pm

Lai wrote:

Probably a dead post, but wanted to see if it was finished. If it is, could I maybe get my hands on a copy?

Hey Lai. I haven't done much work with any of this ever since that last update. However, I have been wanting to get back into some programming and figured I'd update this so that it is at least playable. I threw together a VERY prototype menu just so you have some customization over the mazes. Note that the "Show" option is true/false to determine if the maze generation should be shown as the algorithms run. Having this set to true can slow down generation for large mazes (due to how often it has to draw to the buffer) but I find very reasonable and satisfying for most medium sized mazes.

I threw this menu together in about an hour or so. I haven't bug tested or anything, don't expect everything to be perfect. I am aware of the graphic glitches when moving right or down.

Feel free to download this alpha version here