Maze Generator

Add instructions to instructions page🤦. Hopefully don’t get rejected again! tho lwk rejection an old friend(that was tuff and you can’t convince me otherwise)

Fixed colors, and made it realy obvious that there is a simulaition. Last devlog, see u in the next project :)

Added simulation page. Support for origin shift, dfs, and hunt kill. I’m gonna abandon dsu. Gonna ship soon, need to clean up code and maybe css. Also I’m really proud of this part, i added a global. flag to make sure only one simulation can run at a time, and it waits for others to abort before starting current.

I made better colors for the maze so it actually kinda looks lit up now. I also just made the base of the info page but haven’t made sims yet.

Bro Ts is so annyoing. I tried DSU, but then i realised i have to somehow generate randomly between 2 nodes, and i have to choose both in a connected region and it’s gonna be hella hard so just abbandoning it for now. Gonna work on the sims first. Vid is kinda ass ik

I ADDED A TIMER! The math is hella chopped but it shows seconds(up to hundereths place) then minutes, then hours. If more than 24 hours, cry about it. I’m not bouta do extra stuff to make it say days cause u had a skill issue(though lwk full sized dfs map could take that long). I also added the blind mode resetting correctly, ti reveals the maze after it is solved, then again blinds after generatikng new. I don’t think yall understand how dumb i am. I kept making changes and was like “why can’t i see the changes”. I WAS LOOKING AT THE GITHUB PAGE, NOT TEH FILE. Next might add the dsu method But definitely the info pages, maybe with a simulation for each type. Ig i would just have to draw maze after each step. It might work for small size. Also dfs is gonna be annoying cause i gota show the solution path then the generation.

I added a timer, it’s not working right now completely though. The problem is after full minute, the resetting thing is wierd. I don’t really get it. I also fixed blind mode first load, problem was edge length and offset are null first time, and lastly, I fixed user pos. Before, since i was clearing the circle BEFORE setting new pos, it didn’t look centered. OHH and also i made ti scale, so now u see abt 3 intersections at all times, no matter size of maze. Diabolical for full sized dfs maze. Also gonna now add the last things which is Simulations, prob no 4th maze gen method

Added downloading and blind mode. Problem with blind mode rn is that on the first one, it goes copmletely blind, like you can’t even see the circle around the player.

I Implemented the multiple layers! The order i figured out should be maze, user, blind, solution. Reason is maze is base, maze and user need to be hidden by blind, and solution should always be seen. In reality, maze and user order are interchangable. Right now, the bottom collor of layers degrades top color. I had to use really bright green for it to seem even this green.

I made multiple canvases that overlap. That way I can have the solution, user, and base maze on 3 different canvases. This will allow me to easily hide them without having to redraw anything. Also, I came up with this hella cool idea during math class cause i was bored. Basically, u konw thos retro games that have the guy going through tunenls and he can only see some of his surroundings cause rest is to dark? Basically same idea in here, i’m gonna overlay another canvas which blacks out everything except a circle around user. I don’t have to redraw whole hting each time, just draw rect over the curr circle, then clear circle next to it. Other ideas i had was to add a save mode(like to pdf so people can print easily), a stop watch, an info page explaining how each gen method works, animations of the maze generation on that info page(not 1 time recorded stuff, like dynamically generate simulation), and one more method, which connects nodes randomly and then uses an algorithm kinda like DSU to join the maze. I don’t know how much of these i will get to, but will definitely do the overlay canvases

Fixing the whole logic. Now what we do is dfs the solution path, then STORE the solution path, reset everything NOT on the solution path. After that, you go to each node(in a random order) and check if it has any unvisited neighbors. Unvisited neighbors means parts of the maze that the user cannot currently visit. To fix this, start dfs FROM THIS NODE, to it’s visitable neighbor. This opens up the section. In the video, I’m pointing out where a section got opened up

Ok, I REALLY like this method of dfs, It is fun to play because there are many ways u can go. The method is to dfs generate the solution path and then go back to all the unvisited parts and open those up using dfs. However, for some reason right now there are parts that GET EXPLORED but not connected to main path. This is because of ghost paths. Basically, when i dfs, somehow i leave traces that i visited a node even though i’m not using it. I tried to fix it but debugging is hell

I tried fixing dfs a couple of ways. I tried multi headed bfs and dfs combo(like bfs through seeds but then dfs a tree of len 15 or less from seeds). However, that doesn’t have the cool patterns from dfs(the really long paths). The thing i’m gonna try now is having it generate a dfs path, so it will be really long, then from a random point or smth on either side of the solution path, run dfs and then connect the 3 parts. Right now there’s an infinite loop so the vid isn’t really intersting

SOLVER WORKING! So basically, i release bfs from BOTH the start and the end of the maze. Once they meet, i stop. When showing the solution, I go from the meet point to the start, then from the meet point to the end. This path is stored. DFS was tweaking cause it had an opening at the start before solving. DFS is slowest, but it’s paths are the coolest. I’ma try to optimize it. First using a stack and then storing the open nodes or smth

Can actually find the solution now! Do this by using bfs while going down. If the parent of a child node HASN’T been set, then set it to the current node. Have to check because bidirectional. So if u go from a to b, b detects a as a child. Then when displaying hte solution, just look at parents from the bottom right until you reach 0, 0. Now need to actually draw path on. the canvas.

Converted Path_maze to use booleans because before it was double counting directions. For example a cell might have stored up, left, up and store up twice. This would have made bfs solve slower(i’ma implement that next). Now get_direction_chioces gives list of indices. 0 is left, 1 is up, 2 is right, 3 is down, and 4 is endpoint(previously ‘O’). Then instead of adding direction to end of a string, you set it’s value to true inside the array.

First devlog of the new year!🥳. Hope this one is as good as the last. Ok, now the actual material i did is that i fixed dfs logic(make it use the double arrow format which enables 0,0 detection instead of visited counting) Also lay down basics for the Solver. Use the multiple arrow format to add a start and end to the maze(ran into brief problem with endpoints there). NEXT STEPS. JS doesn’t have priority queues which are needed for djikstra. Ik u can do it using arrays but then time complexity is V^2 and at that point use bellman ford. Also, it’s too slow for us. So gotta implement PQ. 😁(that’s smile is sarcastic btw)

Made the Display able to give bigger mazes. DFS is the slowest because it has to back track every time it gets stuck. Origin Shift is better, but you need to shift a lot to make sure entire maze is properly scrambled. Gen 3 is the best because when it gets stuck it just teleports to a different point. It has to sacrifice memory to do this, but 450^2 isn’t that much memory. If you had enough time, DFS can generate 450 mazes.

Gen 3 working. The problem was that if more than 1 node gets stuck (it has no visitable neighbor) and all other nodes are visited, that means the code will keep looking at the backups, all of which are stuck, making it an infinite loop. Easy fix is to set them to ‘O’ so that it doesn’t consider it a backup anymore and the draw function already handles those. now ‘O’ just means an ‘endpoint’ node. In origin shift, thats the origin, in dfs, thats the leftover node at the end, in gen 3, it’s any stuck node. Next, i want to remove the use of visited variable in dfs. I think you should be able to stop if you go back 0, 0, because if all it’s children are blocked, then it too is blocked. And no, it can’t be that you only explored 1 branch unless that 1 branch ends at 0, 1 or 1, 0 in which case you can just make 0, 0 an endpoint. I’m not sure that will work though

I realized that bfs can’t work because you would have to go through each node in a level before continuing, resulting in a rougly same maze every time. Even if you randomize the order that you go through a level, it still says the same. I am thinking of storing all nodes that can be visited and then randomizing from that, kinda like djikstra, but it wont be called bfs, for now i’m just leaving the name as gen_method_3 and will figure out later. The reason you see bfs doesn’t work is in the diagram, no matter how much you randomize the order of the nodes, they still go in the color coded order, green to red.

Finished DFS. The problem was that It got confused when all neighbors were visited. Also i said != when i ment to say ==. Basically, now it stores which way it came from and if there are no neighbors, go the the parent. Then if that parent had any leftover childs, use those, otherwise go to the grandparent, so on. only don’t consider it as stuck if visited == total number of nodes.

Tried to implement DFS generation but theres an error in the logic so it blocks off and there is no path through the maze. Also i spent a lot of time debugging that i didn’t change the value of the selector to dfs, only the innerHTML.

Origin shift is working! Next im gonna add dfs and bfs generation before djikstra solve and maybe more solve and gen methods

Started with actual origin shift! Made it generate the base maze, which would look like the other file i uploaded(edited in preview, that was painful) shows how the mazes work. The green is what is stored in the code and the blue is the corresponding maze

Basically starter code, creating the base. I made 3 files for the website(html, css, js) and added elements to the html that i knew i wanted. I need a canvas to show the maze, a selector for which method to generate the maze by(I plan to have at least 3 but i’m gona start with origin shift), a range for how big to make the maze and the solve button. In js, i added the listeners so the label for the size changes as you move the slider and it makes the maze as soon as you let go(right now empty matrix). I also made the css dark mode everything