12 ms·
The dumbest way to solve a maze [video]
- jonatron 4y agoThere is unfortunately a dumber way to solve a maze: https://youtu.be/v2uAipnt2nw https://youtu.be/v2uAipnt2nw
- opless 4y agoOMG, that brief clip was more painful than a whole episode of scorpion. Thanks for introducing me to something that sets such a low bar on TV technobabble!
- zimpenfish 4y agoI watched the first episode of Numb3rs and, IIRC, he found the likely home of the criminal by drawing an analogy from the pattern of crimes to a garden sprinkler. I did not watch any more episodes.
- lelanthran 4y agoThis I gotta see :-)
- bad416f1f5a2 4y agoThis analogy is likely based on a pair of complimentary theories in criminology. The first is that criminals commit crimes in an area they know, so their activity is distributed close to home. The second theory essentially says “yeah, but not /too close/“ - and that criminals will leave a buffer zone around their home. So, plot a torus with the center on the offenders home, and most crimes will occur on the disk. This would also work with the pattern a radial lawn sprinkler would make. Unfortunately, while neat theories, the reproduction crisis is happening in criminology as well and I can’t find a good systemic review that says either theory is particularly good. But criminologists believe them, so the show isn’t that far off in those regards.
- ModernMech 4y agoThat’s a shame, it’s a fun show. I mean, using math to fight crime and solve mysteries is a great concept, and the whole point of Charlie using ridiculous metaphors and analogies is to try and make the concepts accessible to his FBI brother and colleagues (and by proxy the audience). Who cares if they are a stretch or not accurate? It’s math on prime time TV, how else do you get it there?
- mistrial9 4y agowait - you just gave a "who cares, relax" green light to a theory of incrimination, in the burgeoning age of surveillance, and specifically so "my male family member who is legally paid to incriminate" can understand the concept? in the same breath as saying it cant be real ? Do you get why this is really, really a bad idea?
- ModernMech 4y agoIt's a tv show. The criminals and cops aren't real. The episode in question they were just trying to narrow a search space. Anyway, I don't think the real FBI is using TV mathemagic to solve crimes, so I think it's okay to have fun watching a TV show.
- zimpenfish 4y ago> I don't think the real FBI is using TV mathemagic to solve crimes I dunno, they use a whole swathe of dodgy nonsense already.
- drrotmos 4y agoI think this clip might have given me brain damage.
- Oarch 4y agoThis is so bad it makes me think the writer knew exactly what they were writing and they made nonsensical dialogue on purpose.
- ccrush 4y agoIt may actually be the dumbest way to solve any problem. It's not a bad way to create a maze though.
- carlmr 4y agoJust leave the maze in a humid, warm environment: https://www.youtube.com/watch?v=7YWbY7kWesI https://www.youtube.com/watch?v=7YWbY7kWesI
- matt-attack 4y agoIt’s funny that he first described his method of random atoms bounding around until they found the exit. He then suggested adding a “fan” to the start to hell blow the atoms in the right direction. The thing is, that’s exactly what his first solution was. A fan. His first solution is literally how air blows through the maze. (I suppose it’s technically when happens when you release air into an evacuated mass but still). Also he suggests that collisions are needed to add “pressure”. Not true. He had pressure in his first modeling and no collisions are necessarily to model.
- jamesrom 4y agoI took his idea of a "fan" blowing air to be like a sort of bias applied to the vector in a certain direction, perhaps a small bias for not going "backward".
- JKCalhoun 4y agoStill sounds like, with the wrong maze, they would tend to pile up in certain nooks.
- taeric 4y agoI think that is an idea behind many air filters. You will get build up in areas of the "maze", but ideally the lighter portions of the air will be able to basically bounce out and through. Some bigger particles will get lucky and find an exit.
- Retr0id 4y ago> Also he suggests that collisions are needed to add “pressure”. Not true. If there are no inter-molecule collisions, there is effectively 0 pressure. (Ignoring the pressure that the walls of the container "feel", which is presumably not being modeled)
- octopolus 4y ago
- RandomWorker 4y agoGenerating the maze was the best step. Love this guy, math created art. Some one that mastered two tools to make something cool.
- anderskaseorg 4y agoHis maze generation algorithm is the well-known randomized Kruskal’s algorithm. What seems to be less well-known is that this algorithm is subtly biased toward producing mazes with many short dead ends. Unbiased algorithms that produce a sample from the uniform distribution over all loop-free mazes include Wilson’s algorithm and the Aldous-Broder algorithm. https://en.wikipedia.org/wiki/Maze_generation_algorithm https://en.wikipedia.org/wiki/Maze_generation_algorithm
- CobrastanJorji 4y agoMaze generation is one of those hobby areas of computer programming that just keeps going. It's really cool how many ways there are and how different the resulting mazes look. Here's an old blog post with visualizations for several popular ones: https://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap https://weblog.jamisbuck.org/2011/2/7/maze-generation-algori...
- patates 4y agoAs a tangent to hobby programming, it very possible to lose your mind when trying to develop a solution that can pass all levels of elevator saga without a second try: https://play.elevatorsaga.com/ https://play.elevatorsaga.com/
- ghusbands 4y agoI don't think there's a solution/behavior that you'd want from a real-world lift that can pass all of the levels. I think some of the levels require you to encode an unfair/odd strategy that just happens to work well for the case they provide, and I think the randomisation makes runs occasionally impossible. You can try all of the solutions on the wiki, and they don't consistently succeed, even where they're claimed to solve all levels.
- tromp 4y agoThe author actually says: it's not the dumbest way, because it does find a solution. Here's the most obfuscated way to generate a maze. Compile char*M,A,Z,E=40,J[40],T[40];main(C){for(*J=A=scanf(M="%d",&C); -- E; J[ E] =T [E ]= E) printf("._"); for(;(A-=Z=!Z) || (printf("\n|" ) , A = 39 ,C -- ) ; Z || printf (M ))M[Z]=Z[A-(E =A[J-Z])&&!C & A == T[ A] |6<<27<rand()||!C&!Z?J[T[E]=T[A]]=E,J[T[A]=A-Z]=A,"_.":" |"];} with clang -fwritable-strings -Wno-implicit-function-declaration and enter a desired height. Gcc no longer accepts the -fwritable-strings option, so we can alternatively avoid writable strings by making the top line one character longer: char M[3],A,Z,E=40,J[40],T[40];main(C){for(*J=A=scanf("%d",&C);
- aaron695 4y ago
- andsens 4y agoMade me think of the good ‘ole Pessimal Algorithms paper: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.116.9158&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11... Always a hoot to read ^^ > However, suppose the maze is actually quite agreeable, so much so that we wouldn’t mind spending a few extra cycles in the search for v; in fact we vaguely hope, nay, decidedly wish, that the search will take as long as possible,
- pkrumins 4y agoThis method is super fun for mazes of size 10x10 but the odds a particle reaches exit decrease exponentially with the size of the maze. Make the maze 20x20 and you will have to wait for the solution for a day, and make it 30x30 and you will have to wait for a year.
- thriftwy 4y agoI would assume it should be possible to craft relatively small mazes which will be practically unsolvable by this algorithm. Which is DoS vulnerability.
- planede 4y agoNote that there are two variables for running the simulation: t - duration of simulation for each individual particle N - number of simulated particles I believe if you leave t fixed, and then increase the size of the grid, then yeah, the number of simulated particles you need probably increase exponentially (or worse) for finding one that reaches the exit. But you probably want to increase t with the grid size as well, and I think that would mitigate this to be less bad than exponential. This is basically diffusion, and characteristic distance travelled by diffusion is proportional to sqrt(t).
- danwee 4y agoIf you make the hallways' maze "thinner", I imagine you don't need as many particles in the simulation? I guess as well that the "thinnest" hallway is of length: 1 pixel. If the particle is also 1 pixel in size, then wouldn't the simulation be the path finding (backtracking?) algorithm? I don't remember the details, maybe I misunderstood something (last time I saw this was at university)
- TomGullen 4y agoOr make the particles bigger
- Someone 4y agoNo. It would be a random walk on a graph. It could (and likely would) revisit the starting position more often than the number of each of its neighboring cells. Another way to see why that can’t be like backtracking is that it is memoryless, while backtracking keeps track of what was visited.
- mackman 4y agoBack when I worked in the video game industry I built a tool to find places in the collision mesh where objects could fall out of the map. It worked by just doing millions of ball simulations. Distributed the job with one sector per core to every developer machine at night. Worked great!
- patates 4y agoNeither have I ever worked in game industry nor developed games in any capacity, but as a very casual player, I'm always amazed in how many games even in these days, falling off the map is still not very hard. Is it easy to fix but nobody cares (like the most SQL injection vuln.s in web apps) or is it really genuinely hard to prevent?
- nauful 4y agoDepending on the technology used it may be trivial to extremely difficult. For most additive geometry constructed maps, cracks can form to create collision holes which otherwise look solid, or the map may not be entirely closed and have a gaping hole into the void. This is very difficult to get right. For maps which carve out empty space from solid space and then add geometry back (subtractive, such as Unreal), there may be cracks caused by numerical imprecision but collision errors here are relatively rare.
- Dalewyn 4y agoIt's the latter. The first problem is that it's not immediately obvious. Hitboxes aren't tied to what is visible, so just looking over a map won't tell you anything. Playtesting the map also isn't foolproof, because sometimes the lack of a hitbox where there should be only manifests under very specific conditions which may or may not be in the realm of developer expectations. The second problem is that it's just very complex, and complex things are hard to build right the first time, find any problems, and fix them. Are these two overlapping polygons a bug or intended? Should this polygon have a hitbox? What about this particular face on the polygon, should it have a hitbox or not? How accurately should we be calculating collisions? The third problem is that game developers, and especially programmers, are paid bad and work in bad conditions. Any programmer worth their salt wants to jump ship over to the enterprise side of things ASAP, where both the pay and the conditions are much better. So you're left with not necessarily skilled/motivated programmers left to deal with complex programs (games) rife with the potential for bugs.
- zfxfr 4y agoI don't think his solution is that "dumb" except if by "dumb" he means over-complicated. A "dumber" solution would probably be to follow a side of a "wall". Imagine if you're in a real maze if you put your finger on a wall and follow that wall (your finger is always in contact with the wall) then you'll eventually get to the exit if there's one or you get back to the entrance.
- hypertele-Xii 4y agoNot if there's a loop in the maze.
- mrweasel 4y agoIf you always keep your right hand on the wall, how exactly would you ever get stuck in a loop? The only case I can think of is if the exit isn't on the outer wall, but through a hole in the middle or something. Sure you can have bits of wall pieces in the maze, but you'll never get into contact with those, as that would require you to remove your hand from the wall.
- taneq 4y agoOr if the exit is on the outer wall, but the wall you pick to follow is not.
- simcop2387 4y agoThis does a reasonable job of explaining it, and uses the terms you'll want to look up for more information too. https://www.inverse.com/article/21386-corn-maze-lost-wall-follower https://www.inverse.com/article/21386-corn-maze-lost-wall-fo...
- jallen_dot_dev 4y agoI don't think this is correct. > Imagine, for example, deciding to put your right hand on the wall of Taylor Swift’s pupil. You’d literally get lost in her eyes! You would have to first take your hand off the wall in order to put it on the pupil. The idea is you put your hand on the wall at the entrance and never take it off, not put it on arbitrary walls.
- brianshaler 4y agoI was hoping this would be a new Tom7 project, akin to the bad chess algorithms. http://tom7.org/chess/ http://tom7.org/chess/
- jastr 4y agoSimilarly, watch a random walk solving a maze https://stripenight.com/random_walk.html https://stripenight.com/random_walk.html