HN Theater @HNTheaterMonth

⬐ tromp

The 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);

⬐ matt-attack

It’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.

⬐ Retr0id

> 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)

⬐ contravariant

An ideal gas still exerts pressure, even though in theory it has no interactions between particles.

Roughly speaking if you put a bunch of bouncing particles in a box then even if they don't hit each other they're going to hit the walls of the box more often if you decrease the volume. This means pressure is proportional to density so inversely proportional to volume i.e. pV is constant.

⬐ Arnavion

The simulated molecules move in a random walk instead of straight lines. That is already an approximation of collisions.

⬐ octopolus

What?

⬐ CorrectHorseBat

>Ignoring the pressure that the walls of the container "feel", which is presumably not being modeled

But that is exactly what pressure (of an ideal gas) is? No intermolecule collisions are required to model the behavior of a gas as we know it.

⬐ rcxdude

If you assume the gas is spread evenly throughout the space, you can model the pressure the gas exerts on the container it is in without intermolecule collisions. You (somewhat obviously) cannot model the pressure the gas exerts on itself this way, which is important if you're looking at the dynamics of how the gas will respond to a non-uniform distribution (the steady-state will still be uniformly distributed, but a gas with intermolecular collisions will spread out faster than one without: this is actually extremely relevant to achieving an ultra-high vacuum: when pressures are low enough you can't easily pump a volume out through a small hose, you need the pump to occupy a large enough part of the surface area of the volume you're pumping for the molecules flying around to actually hit it).

⬐ contravariant

The thermodynamic definition of pressure is just how much work it takes to compress the system. This definition still works locally, you can just imagine compressing a small volume of gas.

I'm not 100% sure if fluid dynamics uses a subtly different definition (though how hard the medium is to compress is a fairly universal definition).

Obviously thermodynamics does break down if you've only got a small number of particles, but then 'pressure' also kind of stops working as a concept when you've got mostly vacuum.

⬐ Retr0id

An ideal gas does not exist, at the molecular level.

⬐ eutectic

No, free molecular flow is a very different regime with very different behavior.

⬐ supernova87a

I don't think that's quite right actually. The first solution is like releasing gas molecules into a vacuum. They random walk and collide their way gradually diffusing out. That is taking a long time, as you can observe.

If the maze were already filled with a gas, and a fan were pressurizing the whole thing from one end, a pressure wave would be traveling through the maze towards the exit, sending the first particle out the door much faster.

⬐ taeric

Notably, they are not colliding with each other, I don't think. That is what he meant by adding pressure. If you made it more like a "flood fill" of the maze, where new particles are pushing into the maze, that would be similar. Though, I would guess that the earlier particles added would be higher probability to get out first. (Which would fit the intuition.)

⬐ taeric

Is it? Without pressure forcing molecules in an average direction, it isn't a fan. Right?

Notably, a fan would first saturate all dead ends closest to it. Basically turning deadends into walls at their entrance. But, again, this only works if you have pressure. Right?

⬐ Double_a_92

I assume he meant pressure as, if there are already a bunch of particles stuck in a dead-end branch lower the chance of going there.

⬐ jamesrom

I 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

Still sounds like, with the wrong maze, they would tend to pile up in certain nooks.

⬐ taeric

I 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.

⬐ ghusbands

You're mistaken about the simulation they're actually running. They are doing simple Brownian motion rather than a gas/fluid simulation, so there's no pressure differential anywhere and the particles don't interact with each other but rather with a theoretical other gas of consistent pressure.

You can see it by noting that the molecules that are very far apart are still bouncing around as though hitting other molecules (and they also mention it at 3m19s or so).

So there isn't a fan and they couldn't realistically add one. If they did, they'd essentially have to bias particles towards a prior-knowledge correct path through the maze (which is solving a maze by already having a solution), or actually run a gas simulation.

⬐ mackman

Back 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

Neither 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

Depending 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

It'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.

⬐ mminer237

It sounds like they should just have a rendering mode where you do just see hitboxes to test.

⬐ muststopmyths

> 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

I read ignorant shit about the game industry all the time on HN, but this is so beautifully ignorant, arrogant and demonstrative of what is wrong with software developers that if wish HN had gold to give.

I suppose John carmack, George Romero and jonathon blow would be sad to learn they’re not worth their salt.

Lest someone argue that I’m picking outliers, you’ll just have to take my word that in my years at Microsoft and then in games I have seen brilliant programmers (and bad ones) in both environments. And many of the best in games tried to stick it out at “enterprise software” (google, msft, SV unicorns) but always left within a year despite bags of money being hurled at them.

Sorry if this sounds harsh but I am so tired of people who’ve never walked a mile in the shoes, telling a walker how they must suck at walking. It’s endemic on HN, for all kinds of things, not just games.

⬐ UncleMeat

Carmack did leave gaming and is now working on AI and VR. George Romero is a filmmaker so I think you are thinking of John Romero, who was never a stunningly good programmer but instead was focused on game design and level design. Jonathon Blow made two games, neither of which are known for particularly impressive engines, and is now spending most of his time developing a language and compiler.

Odd examples to choose.

⬐ muststopmyths

Yeah, I meant John Romero, sorry. And Carmack didn't leave gaming for enterprise "ASAP". He had a long and storied career in games. I would say Romero was "worth his salt" as a programmer, whatever that vague metric means.

Jonathan Blow made two games with engines developed from scratch. I don't know how you think that's "not particularly impressive" for a solo person, unless you have never tried to actually ship a game. With or without a custom engine.

I was just trying to pick programmer examples that people would know. Probably didn't make my point very well, which was that there are plenty of programmers "worth their salt" in the gaming industry, and who chose to stay in it. To state otherwise is just fucking idiotic.

⬐ pkrumins

This 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

I would assume it should be possible to craft relatively small mazes which will be practically unsolvable by this algorithm. Which is DoS vulnerability.

⬐ planede

Note 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).

⬐ zfxfr

I 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.

⬐ pier25

This always reminds of the Name of the Rose by Umberto Eco. I think Willian of Baskerville, the protagonist, mentions this at some point?

⬐ hypertele-Xii

Not if there's a loop in the maze.

⬐ mrweasel

If 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

Or if the exit is on the outer wall, but the wall you pick to follow is not.

⬐ simcop2387

This 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-fo...

⬐ jallen_dot_dev

I 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.

⬐ andsens

Made me think of the good ‘ole Pessimal Algorithms paper: 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,

⬐ danwee

If 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

Or make the particles bigger

⬐ Someone

No. 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.

⬐ RandomWorker

Generating the maze was the best step. Love this guy, math created art. Some one that mastered two tools to make something cool.

⬐ CobrastanJorji

Maze 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-algori...

⬐ patates

As 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/

⬐ ghusbands

I 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.

⬐ patates

I mean, the constant frustration of getting very close but having to optimize for even one more thing and that breaking all other levels...

It really forces you to be really creative, even if you'll never succeed. I'm enjoying the process much more than the results.

⬐ anderskaseorg

His 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

⬐ jastr

Similarly, watch a random walk solving a maze https://stripenight.com/random_walk.html

⬐ brianshaler

I was hoping this would be a new Tom7 project, akin to the bad chess algorithms.

http://tom7.org/chess/

⬐ aaron695

None

⬐ jonatron

There is unfortunately a dumber way to solve a maze: https://youtu.be/v2uAipnt2nw

⬐ drrotmos

I think this clip might have given me brain damage.

⬐ Oarch

This is so bad it makes me think the writer knew exactly what they were writing and they made nonsensical dialogue on purpose.

⬐ ccrush

It may actually be the dumbest way to solve any problem. It's not a bad way to create a maze though.

⬐ opless

OMG, 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

I 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.

⬐ ModernMech

That’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

wait - 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

It'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

> 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.

⬐ lelanthran

This I gotta see :-)

⬐ bad416f1f5a2

This 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.

⬐ carlmr

Just leave the maze in a humid, warm environment: https://www.youtube.com/watch?v=7YWbY7kWesI