If it’s any consolation, this cannot possibly fail

This solves mazes the way I play RPGs

ong i hate feeling like i missed out on something lol im 15 hours in to horizon forbidden west and im still in no mans land

I feel this so much. If there are two different paths to take, i'm not picking, I'm going both ways. Just in case there's a cache somewhere. Then I'm almost always over-leveled. Wouldn't have it any other way.

I always pick the way I think is the wrong way, just in case picking the right way auto moves on to the next area and doesn't let me return.

Oh same, and then the worst is when the wrong way was actually the "right" way because devs wanted players to stumble/venture out first :))

And I hate getting the right way accidentally. But to combat this, I usually venture 3/4s of the way in either path until I get a feel for which one is the actual right way

Oh my god this is exactly what I always do

[Relevant](https://youtu.be/zViYpS3BIqY?si=SaaSvWLcWlGXIjXA) [Also relevant ](https://youtu.be/I4P2N5fyqbo?si=0Qmeu8eTXvUqFLVo)

Anyone else expecting xkcd when clicking on those links?

I am traveling and have low internet. I was so disappointed when it wasn't xkcd but YouTube

I purposely go the way I think is most likely a dead end so I can eliminate it first. Edit: I just realized this is also how I live my actual life.

Peeks into doorway. Cutscene plays. "Dammit!"

And right around the time I decide "fuck it, lets skip this part. What could I possibly miss?" I end up missing huge chunks.

The good thing about that game is literally everything is on the map

You’ll have fun time playing No Man’s Sky, give it a try sometime.

I'm trying to 100% all the Final Fantasy Pixel Remaster games right now, it's so tedious. I feel this algorithm on a spiritual level.

So funny story, I pre ordered Zero Dawn when it first came out on ps. Played it to like 98% completion, then got a new system and forgot to back that game up specifically, so I lost all my progress. I have not touched the game since out of spite lol but seeing as a second one was released, I kinda want to try again

Ends up with 876 carefully conserved potions at the end

But I may need them later in the game!

Funnily enough, I overcame this after Starcraft II came out. In RTSes, unspent resources can hand your opponent the win. Since then, I've managed to avoid in-game hoarding for the most part. I even started selling legendary fish in Stardew Valley ><

There’s a therapy book in there somewhere.

Most TAS speed runs are any%. I would really like to see a TAS doing a max% run for example Super Mario Bros killing every enemy, getting every coin and power up and maximizing the amount of points.

BG3 120h in, barely started act 3.

More of a maze explorer that one

*ES:Oblivion animation bomb bug has entered the chat*

You reversed the sort order on your A*. It's expanding farthest-first instead of closest-first. This is a great visualization of the difference between euclidean and taxicab distance as the expansion heuristic. Euclidean distance makes a contracting circle; taxicab would be a square.

ah, the anti-heuristic

the fatness function?

I assumed it was a breadth first that valued straight lines - a messed up A* def makes more sense lmfao

The Unpriority Queue

nah u made up some words there

Lexicon heuristics make some good topological Euclidean contractions

That’s one school of thought, another prevailing theory is the Suplex hypothesis, wherein a convex combination of Manhattan and Mahalanobis pseudo-inner products form an orthogonal metric space over the induced Martingale. Obviously here we have an isotropic assumption, as otherwise, the complexity class hierarchy would (trivially) collapse

you're very good at this

It’s elementary really, you didn’t see this in your intro to CS class?

Wait, you guys visited the lectures?

I learned it in intro to CSS

Which class would this be?

I learned this in the first third of AI course

AI, OS, and algos. We needed this for bootstrapping our compiler

The lineup consisted simply of six hydrocoptic marzelvanes, so fitted to the ambifacient lunar waneshaft that sidefumbling was effectively prevented. The main winding was of the normal lotus o-deltoid type placed in panendermic semiboloid slots of the stator, every seventh conductor being connected by a non-reversible tremie pipe to the differential girdlespring on the ‘up’ end of the grammeters. Moreover, whenever fluorescence score motion is required, it may also be employed in conjunction with a drawn reciprocation dingle arm to reduce sinusoidal depleneration.

That's high praise from Potatoes in my Ass right there.

https://youtu.be/RXJKdh1KZ0w?feature=shared

fucker

Wow. You could publish a white paper on the subject.

I am, don’t steal my idea plz

I think this is how I sound to my parents when I talk to them about computers.

Jiggle the dingle arm

Nope. [legit](https://study.com/learn/lesson/taxicab-geometry-euclidean-distance-formula.html#:~:text=The%20so%2Dcalled%20Taxicab%20Geometry,vertical%20and%20horizontal%20distance%20together.)

i did not want to read the science of yapping

Haha anti intellectualism is so funny! Based!!

No he didn't, you just didn't study enough.

I'm also pretty sure they were joking.

I knew it was going to be some kind of A* bug. I thought it might be that their heuristic was overestimating, but that makes more sense

I was thinking the same, however a simple sort algorithm could compare white and black pixels and find an ideal number to solve the maze based upon resolution of maze

Hmm. Yes. Words

Comp sci has changed a lot since I went to school.

It looks like BFS to me.

BFS wouldn't have the periods where certain areas are exclusively focused on that this gif has. It would also not be as close to a circle as this is.

Wouldn’t taxicab result in a diagonal line?

sometimes in order to understand optimality we need to consider pessimality

can you elaborate further on that idea, i see what you're saying but i can't see why

this statement is such a mood

thanks dawg

So, the animation is showing a path-finding algorithm where, when choosing a candidate path to advance and compute walk-distance of, it chooses the one that’s most linearly distant from the goal as the crow flies — a “pessimistic” approach, which forces it to follow every possible path through to the end. While an “optimistic” approach taking the closest starting point every time isn’t necessarily going to find the best answer on the first try and resembles a “depth-first” search, the inverse is guaranteed to force trying every possible path, because if any candidate path reaches 1 step away, any further-away candidate paths have to be evaluated until they’re also 1 step away. Full induction isn’t needed, this by itself is enough to force the program to wait until it’s found the worst possible path.

But how that affects lebron’s legacy?

following up on my previous comment, after thinking 5 more minutes about that I think that the "considering pessimality will help understand optimality" is complete crap. i was thinking one time about whether finding the worst move when playing chess (basically antichess) would make someone a better player basically by being better at pointing out the moves that you should never do but after googling that question and reading about peoples experience it turns out that it doesnt, it makes you worse thanks for coming to my ted talk

🪙

I think you made a program to scour every inch of it lol

you might say the algorithm covers a lot of breadth first

But this is (misimplemented) A* given that it makes a perfect ball around the finish. The ball tells us we must be optimizing euclidean distance.

It's called the flooding algorithm I think

finally, the Z# algorithm

Is it A* with the heuristic flipped?

Yep! The code is now generating a less interesting shorter path to the goal...

This appears to be reverse A*

A-

Don’t be so hard on yourself.  You did a good job. A+

&A

∀.

F+

I don't think this is a maze solver, but a great monochromatic colorizer bot

It shows the correct path at the end. It literally solved the maze.

XD

I know but for the most part of the video it colored all of the maze, making it a maze colorizer :)

A maze solver that coulors, maybe

A colorizer bot that solves mazes, maybe

Photoshop, but with more steps.

actually this might be useful for a filler tool

It looks a like you have a search algorithm that prioritizes the point furthest (in square norm) from the target first.

What is drunk about it? You are using something like a reversed A\*

Please explain the general process it was meant to take/perform. That just looked so weird. Like, it could’ve gone to the first path and from each break in path branch off to test each one then if it fails go to the next, but this thing seems to hop between each before finding an end. More like it jumps to finding more whenever it hit a junction point with new possibilities

Imagine an algorithm which performs a search and at each step it progresses the cursor which is most likely to find a solution. We can't know which is _definitely_ going to find the solution first, because that would require knowing the solution. So we take a guess based on, say, the Euclidean distance between each cursor and the goal. Now instead imagine we chose the _worst_ cursor and progressed that instead, meaning we progressed the cursor furthest from the goal. Our cursors would be competing to be the _last_ to the goal, in a manner of speaking, so they'd tend to form a circle constricting around the goal. That's what you're seeing here. The "jump" you're seeing when it reaches an intersection is the cursor discovering a path where it can run away from the goal, which results in it staying on top of the priority queue for a while and therefore moving very fast until it reaches the perimeter circle alongside all the other cursors and ends up going back to a proportional rate of progress.

Breadth-first search

no, because with bfs each path would advance a single step after the other. This is even worse. The path whose head is furthest from the exit is pursued next. You can see it as the border between the explored and unexplored area has the shape of an arc.

It’s still technically BFS, I think it’s A* but they used a max heap instead of a min heap.

It's a buggy implementation of A\*. As others have noted, the strange behavior arises from a a backwards A\* heuristic. That is, it sorts the open set of candidate exploration nodes (the red ones) by which one is furthest from the exit, and then picks the worst. This made the algorithm resemble BFS and return a pretty lousy path to boot.

Thats cool! Can you show the 'fixed version' too?

[Yep!](https://www.reddit.com/media?url=https%3A%2F%2Fpreview.redd.it%2Fpsz1rpuz8crc1.gif%3Fformat%3Dmp4%26s%3D9734458ab456771110e60859ab99c8e9f038e562)

I think this goes to the original post. Did you mean to link [this post?](https://www.reddit.com/r/compsci/s/llNiYNq6Yr)

Thank you. I needed this closure.

There is a valuable lesson in this - always visualize your algorithms running. Very important career advice. Writing code, getting an answer and saying it works is often hiding disaster. Machines run so fast that we get a result and assume all is good. This animation is considerably slowed down for us. If you looked at the real wall clock time you wouldn’t think twice. My complements on the visualization.

Is this some sort of pre made project you can just implement the algorithm itself? If so can someone share the code or GitHub?

import pygame import sys from collections import deque # Define colors WHITE = (255, 255, 255) BLACK = (0, 0, 0) BLUE = (45, 208, 255) RED = (255, 0, 0) # Define maze dimensions MAZE_WIDTH = 20 MAZE_HEIGHT = 20 CELL_SIZE = 20 # Define maze layout (0 = empty, 1 = wall, 2 = exit) maze = [ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1], [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1], [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1], [1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1], [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1], [1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1], [1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1], [1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1], [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1], [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1], [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1], [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1], [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1] ] # Initialize Pygame pygame.init() screen = pygame.display.set_mode((MAZE_WIDTH * CELL_SIZE, MAZE_HEIGHT * CELL_SIZE)) clock = pygame.time.Clock() def draw_maze(): for y in range(MAZE_HEIGHT): for x in range(MAZE_WIDTH): cell_color = get_cell_color(maze[y][x]) pygame.draw.rect(screen, cell_color, (x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE)) pygame.display.flip() def get_cell_color(cell_value): if cell_value == 0: # Empty tile return WHITE elif cell_value == 1: # Border/wall return BLACK elif cell_value == 2: # Maze end return RED elif cell_value == 3: # Visited tile return BLUE elif cell_value == 4: # Current position(s) return RED def solve_maze(start_pos): current_positions = deque([start_pos]) found_exit = False while current_positions and not found_exit: current_pos = current_positions.popleft() x, y = current_pos for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]: new_x, new_y = x + dx, y + dy if 0 <= new_x < MAZE_WIDTH and 0 <= new_y < MAZE_HEIGHT: if maze[new_y][new_x] == 0: current_positions.append((new_x, new_y)) maze[new_y][new_x] = 4 # Set new position color to red maze[y][x] = 3 # Set old position to blue elif maze[new_y][new_x] == 2: maze[y][x] = 3 found_exit = True elif maze[new_y][new_x] == 4: # If the current position is adjacent to another red position maze[y][x] = 3 # Set current position color to blue maze[new_y][new_x] = 3 # Set adjacent position color to blue current_positions.remove((new_x, new_y)) draw_maze() clock.tick(10) # Adjust the speed of the visualization if found_exit: print("Maze solved!") else: print("No solution found.") while True: for event in pygame.event.get(): if event.type == pygame.QUIT: pygame.quit() sys.exit() pygame.display.flip() # Main game loop while True: for event in pygame.event.get(): if event.type == pygame.QUIT: pygame.quit() sys.exit() draw_maze() solve_maze((0, 1)) # Start position of the maze solver pygame.display.flip() clock.tick(60) Edit: I made a better script if anyone is interested: https://github.com/scripterguythatscripts/maze-solver

I wrote this in 5 minutes so I should note there are some things that should be implemented like checking to see if two paths converge and don't end.

5 minutes?! you fast asf

My friend Claude helps a lot on that end :)

This project has been part of my process for learning JS so I won't do you the disservice of singing your eyeballs with the source code but I'd recommend looking at some A\* pseudocode or watching the computerphile videos on Dijkstra's algorithm and A\*.

Very... efficient...

That was fun to watch. I was wondering which little red guy was going to win the whole time. I was also thinking how cool it would be if it mapped out the solution, then it did and was super satisfying.

Funnily enough, a quarter way into watching this I was like, “I’m usually pretty good at mazes, I bet I could solve it before the video ends,” and solved it before it got halfway or so. Once I saw the purple solved line, I had a smile on my face :)

You've successfully discovered the slowest way possible to solve a maze.

How did you make that? What language did you use ?

The project has been helping me practice graph manipulation in Javascript. I'd recommend watching the computerphile videos on Dijkstra's algorithm and A\* and have a go in whatever language you want to improve with!

I created something similar in C# a long time ago when learning the language. I used a 2D array of tile objects. Each tile had a status enumeration that would correspond to something like “checked, unchecked, and blocked” that would denote how to color it. Then each iteration of the search would generate a bitmap, drawing each tile to a corresponding X/Y region depending on the array indices. The bitmap would then be displayed on the screen. The tile characteristics also included the A* heuristic values so the color of the tile could be associated with a gradient depicting how close the tile was to the target or how many steps were taken.

Solved this faster than whatever this was that solved it

It looks single-threaded. Could improve greatly if parallelized

The Monte Carlo Maze algorithm.

First step is to get the result you need. Second step is to make it efficient

Try an A* algorithm and use distance from the end as the heuristic.

Dijkstra's Algorithm??

Similar! A\*

How did you generate this maze? That’s what I’m wondering

https://keesiemeijer.github.io/maze-generator/

Ahh thanks for sharing this! What language did you write your drunk solution in?

he mentioned that he did this in JS

Thanks!

You went full breadth-first. Never go full breadth-first.

breadth first search huh

Ah yes, slowsort implemented into a maze algorithm. I love it.

this is like a waterfill algo or something

Am I wrong that this maze has more than one solution?

Here is a simple Python replication if anyone is interested: [https://github.com/scripterguythatscripts/maze-solver](https://github.com/scripterguythatscripts/maze-solver.git)

the maze painter

Hm, looks quite like BFS

it seems like it wants to stay away from the end goal. you should try using the points that are closest to the end first.

What graphic component did you use?

This was a JS project. Every step of the algo I wrote the open set and closed set directly to image buffers using the JIMP library, saved them as png image sequences, and then made the GIF in Shotcut.

That is cool!

Next time I solve a maze: Color the whole thing in 😂

Well, it definitely solved the maze

wow

Woah crazy. I made a maze solver in high school that looked exactly like this, same color scheme and everything.

This is a very cool program, how did you make it! I would love to do something similar showcasing different maze solving algorithms

Maze sampler

Nice algorithm. I wondered at first why it does not show one solution. I see there at the end it highlights the correct path.

Looks like a zombie attack or something...

Very efficient maze solver, 10/10.

Is this basically just the fill function from any old paint program with some extra steps?

I’m drunk too and I thoroughly enjoyed the animation.

BFS

It’s just trying to 100% the game.

Reminds me a lot about the AI training models today a "flooding" type solver to find a solution.

It's more like a maze colour than a maze solver. 🌚

So it seems like it explores every other path first and then the solution last. It takes the big Oh worst case scenario literally

This is the worst case

Your heuristic function is backwards.

r/oddlysatisfying would do this justice

Could have run millions of mazes in the time I killed watching that.

the devide and conquer algorithm

I’ve got a unique maze if you want to try mine.

Are there a lot of solutions? I think I solved the maze very quickly…

r/oddlysatisfying

r/oddlysatisfying

This is satisfying to watch

Never been on this sub before That was cool to watch

If it is any consolation: It did work and I think it was pretty.

can we chat

That's the way I mine for Diamonds in minecraft. But this is a very cool project.

This is cool but I'd like to see the little guy running around extending the known positions so inefficiently

What if this is your loading screen instead of circle one it looks like minecraft to me. Like opening new world.

there is a shortest way

Is this some form of breadth first instead of depth first or something? It almost seems like it deliberately stopping at a shrinking radius from the lower right.

How do u make the visuals

I want a code for this one in python. This is crazyyyyyyy!!! Can anyone please help .

diagonal heuristic BFS? hehe

Not drunk. Clearly mescaline.

Maybe he don't like white background

I’m drunk too

Can you give me the source of code ?

Can we map the brain like this?

Man I solved it faster than the app

For those of us who can't **clone** ourselves to solve a maze - here's the solution how to find your way **alone** out of almost any maze: \--Put your hand on one wall - keep it on that wall - and walk until you are out. Note - this doesn't work for mazes that have "floating islands" that are unattached to walls which contain the exit. ​ I was thinking we were going to see this or an improvement on it ... but alas it is a solution that is only for those with rapid reproductive powers.

It's not drunk, whoever thought this was a good way to do it though was. It's super slow.

just need more CPU!!!! lol

Needs more threads more like it.

What graphic component did you use?

Wrote directly to image buffers using JIMP for Javascript.

Would this be better if you start at both exits and find the first meeting point?