frontpage.
newsnewestaskshowjobs

Open Source @Github

fp.

Open in hackernews

Generating Mazes with Inductive Graphs (2017)

https://jelv.is/blog/Generating-Mazes-with-Inductive-Graphs/
20•todsacerdoti•1y ago

Comments

tomfly•1y ago
where is the entrance and exit?
Jaxan•1y ago
Doesn’t matter, because all positions are reachable. So just pick any two positions at the border and remove a wall.
kazinator•1y ago
Here is a maze that was generated recursively starting at the upper left cell.

  +    +----+----+----+----+----+----+----+----+----+
  |    |                        |                   |
  |    |                        |                   |
  +    +----+----+    +----+    +----+    +----+    +
  |              |         |                   |    |
  |              |         |                   |    |
  +----+----+    +    +----+----+----+----+----+    +
  |              |    |                        |    |
  |              |    |                        |    |
  +    +----+----+    +    +----+----+----+    +    +
  |         |              |              |    |    |
  |         |              |              |    |    |
  +    +----+    +    +----+----+----+    +    +----+
  |              |    |                   |    |    |
  |              |    |                   |    |    |
  +----+----+----+    +    +----+----+----+    +    +
  |                        |                   |    |
  |                        |                   |    |
  +    +----+----+----+    +    +----+----+----+    +
  |    |    |              |    |              |    |
  |    |    |              |    |              |    |
  +    +    +    +    +----+    +    +----+    +    +
  |    |    |    |    |         |    |         |    |
  |    |    |    |    |         |    |         |    |
  +    +    +    +    +----+----+----+    +    +    +
  |    |    |    |    |                   |         |
  |    |    |    |    |                   |         |
  +    +    +----+    +    +----+----+    +----+----+
  |              |         |                        |
  |              |         |                        |
  +----+----+----+----+----+----+----+----+----+    +

It matters to start there because it will be easier if you go backwards.

The maze has 100 cells. For each cell, we can calculate which exit goes back toward the entrance, assigning the letters U, D, L, R:

  U R R D L L R D L L
  U L L D L U L L L U
  R R U D D L L L L U
  U L D L L R R D U U
  U L L U D L L L U D
  R R R U L R R R U D
  U D R R U U R R D D
  U D U U R U U D L D
  U D U U D L L L U L
  U L L U L R R U L L
Stats:

  L - 33
  U - 29
  R - 20
  D - 18
Left and Up are more frequent back-to-entrance escapes than Right or Down. This is because of the way the maze was generated.

To check the hypothesis, we should analyze it in the other direction. For each cell, determine the exit which heads in the direction of the exit:

  D R R D L L R D L L
  D R D D L U L L L U
  D L L D D L L L L U
  D L R D L R R D D U
  R R U D D L L L U D
  R R R R D R R R U D
  U D R D L U R R D D
  U D U D R U U D L D
  U D U D R R R D U L
  U L L R U R R R R D
Stats:

  D - 30
  R - 28
  L - 24
  U - 18
There is a weaker bias for the D-R axis toward the exit, compared to the L-U axis toward the entrance. I suspect if we study larger numbers of larger mazes, we will find similar findings.

So that is to say, it is easier to navigate the maze in the reverse direction: the heuristic to try left/up exits will work more often than the right/down in the proper direction.

smartmic•1y ago
From the book "Mazes for Programmers" by Jamis Buck, 2015, The Pragmatic Programmers (a must-read for any maze/programming enthusiast!):

> Aren't mazes supposed to have starting points and end points? […] honestly, […] it's entirely up to you. […] The maze […] is a perfect maze, and one of the attributes of a perfect maze is that there exists exactly one path between any two cells in it. […] You pick them, and there's guaranteed to be a path between them.

You do not need to choose an entrance or exit only on the sides, but you can also choose "Pacman-style" where the goal is to reach points inside the maze.

"Perfect" refers to the mathematical/logical properties of a maze (i.e. no loops), not the aesthetical aspect. I have not checked though if the mazes in the source here are all perfect.

kazinator•1y ago
While you can put the entrance and exit wherever you want, if you know that the maze was generated by a recursive branching process which had a starting point somewhere, it probably behooves you to put the start at that point corresponding to the root of the tree, so that the maze wanderer faces the most branching choices.

Laying out the abstract maze tree into the rectilinear grid of cells obfuscates the tree somewhat, but not entirely. A process that generates from upper left to lower right, for instance, will tend to generate cells whose parent-headed exits going left and up more often than not, making the reverse direction a bit easier.

(Again, it depends on the maze generation process.)

kazinator•1y ago
Making random mazes in a rectilinear grid is a good exercise for one big reason: mazes are not all the same. Mazes have style can be very knotty and twisty, or have long passages. You can add hacks into a given algorithm to vary the style, but there are certain things it won't necessarily do.

What the fuck is w2rt6byl5nf1opmc-a.com?

https://jack.cab/blog/siterate
197•dverlaeckt80•1h ago•59 comments

Amazon's Discount Illusion: 1 in 3 "Deals" Offered No Savings– 1 in 10 Cost More

http://groundworkcollaborative.org/news/amazons-decoy-deals-groundwork-investigation-reveals-near...
119•DeepLogin•1h ago•76 comments

The Secret ThinkPad Powerbutton Code to Bring Dead Laptops Back to Life (2007)

https://masnick.com/posts/the-secret-thinkpad-powerbutton-code-to-bring-dead-laptops-back-to-life/
128•sammatilda•3h ago•58 comments

Soldier files whistleblower complaint over Iran strike that killed 6 U.S. troops

https://www.cnn.com/2026/11/15/politics/army-soldier-whistleblower-complaint
79•firefax•1h ago•10 comments

How to make almost anything

https://pub.cba.mit.edu/863.26/site/
551•o4c•9h ago•98 comments

Show HN: Coral – Open-source gateway where agents write their own tools

https://github.com/withcoral/coral
35•jcs•1h ago•10 comments

Universal XSS in uBlock Origin from website-driven element picker

https://iter.ca/post/ubo-uxss/
499•zaik•13h ago•143 comments

Researchers track whole body movement with just a smartwatch

https://news.cornell.edu/stories/2026/11/researchers-track-whole-body-movement-just-smartwatch
123•PaulHoule•2d ago•37 comments

“…and the proof is checked in Lean”

https://xenaproject.wordpress.com/2026/11/12/and-the-proof-is-checked-in-lean/
131•matt_d•7h ago•54 comments

OOS – an open operating system for the Rigol Scopes

https://www.eevblog.com/forum/testgear/oos-an-open-operating-system-for-the-rigol-scopes/
56•qwezxcrty•2d ago•16 comments

Qwen4-Max

https://qwen.ai/blog?id=qwen4-max
715•ilreb•13h ago•351 comments

What's Next for Nvidia?

https://steveblank.com/2026/11/15/whats-next-for-nvidia/
368•zdw•15h ago•465 comments

Old Bitly links are being hijacked

https://ransomnews.com/burger-king-tweet-bitly-link-hijack-2026/
339•hspeiser•17h ago•170 comments

It's always DNS, so why are we running our own?

https://s2.dev/blog/dns-server
49•misker1•6h ago•29 comments

Winudf – DVD / BluRay driver for DOS, Windows 1.x – 3x / 95 / 98 / ME

https://github.com/ages2001/WINUDF
48•Oxodao•7h ago•5 comments

Coffeehouses and the Rise of Science [pdf]

https://www.monirbounadi.com/Bounadi_JMP.pdf
119•Michelangelo11•4h ago•75 comments

Tor Project Issues Rapid-Response DoS-Defense Fix Amid Sustained DDoS Attack

https://forum.torproject.org/t/security-release-0-4-9-17/22454
203•aillia•15h ago•55 comments

Protomaps: Self-hosting map tiles has gotten cheap and easy

https://bruceroettgers.eu/blog/protomaps/
412•bcye•20h ago•72 comments

Show HN: ThingStudio, Node-RED style programming for microcontrollers

https://thingstudio.net/
17•mkarliner•5d ago•2 comments

Exact Gradients Through a BRep Kernel

https://muni.works/research/vcad
32•ecto•2d ago•12 comments

Handwriting, as a Font

https://ductus.sorenblank.com
384•coinfused•19h ago•66 comments

The Opportunivore's Dilemma

https://www.vqronline.org/essays/opportunivores-dilemma
6•NaOH•2d ago•4 comments

A short explainer on how El Niño works [video]

https://www.youtube.com/watch?v=7_JF3etiAv8
271•nharada•21h ago•155 comments

Preserving 30 years of Salon journalism

https://blog.archive.org/2026/11/12/preserving-30-years-of-salon-journalism/
183•CharlesW•16h ago•49 comments

The Lasting Influence of John Berger

https://www.newyorker.com/magazine/2026/11/16/john-berger-a-life-tom-overton-book-review
44•prismatic•4d ago•4 comments

Microsoft blames monster email outage on software defect introduced in July fix

https://www.theregister.com/saas/2026/11/16/microsoft-blames-monster-email-outage-on-software-def...
27•Bender•2h ago•27 comments

Crows make decisions faster than we can

https://www.nytimes.com/2026/11/15/science/birdbrain-crows-birds-research-decision.html
275•gumby•21h ago•182 comments

Do we still have to denormalize? Have your schema and search it too

https://www.paradedb.com/blog/joins
99•philippemnoel•2d ago•31 comments

Mayor Zohran Kwame Mamdani: We Are Disbanding the SRG

https://twitter.com/NYCMayor/status/2122298477816504328
4•doener•2m ago•0 comments

WebGL Flight Simulator with seed generated terrain

https://baron.by.dai.studio/
205•ranger_danger•19h ago•49 comments