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.

CipherAML: Advanced Mobile Location for emergency services without Google

https://github.com/CipherOS/CipherAML
1•lucgommans•54s ago•0 comments

Hostile Hospitality

https://blog.vasi.li/hostile-hospitality/
1•vsviridov•57s ago•0 comments

Framework Wireless Touchpad Keyboard [video]

https://www.youtube.com/watch?v=qUsU5KxT4Vs
1•ajs1998•1m ago•0 comments

Mistral: We're making Vibe free in Europe for the first 3 months

https://twitter.com/MistralAI/status/2122713540666806397
1•doener•1m ago•0 comments

Jensen Huang was building an open AI ecosystem that threatened Anthropic

https://www.businessinsider.com/jensen-huang-nvidia-ouster-removes-major-threat-to-anthropic-ipo-...
2•vinyl7•2m ago•0 comments

Show HN: SGNE-CC – 3.13 MiB Qwen3.5-0.8B edit beats MIT-p50c 8.6x at T=0

https://github.com/Nondual-Observer/dna-weight-editing
1•NondualObserver•2m ago•0 comments

Show HN: Flappy Mail, digital letters sent by 8-bit carrier pigeons

https://flappymail.net/
1•kgold333•4m ago•0 comments

AI Tamagotchi Turns Everyday Objects into Needy Virtual Pets

https://www.wired.com/story/this-ai-tamagotchi-oats-turns-everyday-objects-into-needy-virtual-pets/
1•PaulHoule•6m ago•0 comments

Optimizely hack infected CNN, Fox News, BBC, Salesforce sites with malware

https://www.bleepingcomputer.com/news/security/optimizely-supply-chain-attack-delivers-malware-to...
4•balderdash•7m ago•0 comments

Nvidia stopped disclosing Singapore sales as revenues hit $104B

https://www.ft.com/content/dbde7a30-548c-4f9d-a4be-7898a0c24dcf
2•louiereederson•8m ago•0 comments

Show HN: Hue MD – Markdown that shows status at a glance and stays plain text

https://spingras.github.io/hue-md/
2•spingras•8m ago•0 comments

PyScript is entering maintenance mode

https://gist.github.com/WebReflection/37cd8ff649ffa336782fec9d28646fae
1•lumpa•8m ago•0 comments

Tirazain.com

https://tirazain.com
1•trkaky•9m ago•0 comments

Show HN: Machine Internet: turn a site's hidden JSON API into MCP tools

https://github.com/chetanty/machine_internet
1•ChetanTy•11m ago•0 comments

Show HN: LLM cost calculator for agent runs (45 models, prompt caching included)

https://llmcost.pitropatro.com/
1•pitropatro•11m ago•0 comments

Google Embraces Geothermal Technology to Vaporize Rock for Clean Power

https://www.wsj.com/business/energy-oil/google-embraces-geothermal-technology-to-vaporize-rock-fo...
1•bookofjoe•12m ago•1 comments

Show HN: Introduction to GPU Inference, a short course with Interactive diagrams

https://athrael.net/courses/gpu-inference/
2•athrael-soju•12m ago•0 comments

Stacked Diffs with Maiao

https://entropicthoughts.com/stacked-diffs-with-maiao
1•aray07•12m ago•0 comments

Show HN: Solarian – Open-source Python framework for AI robots

https://solarian.dev
1•rgarreta•12m ago•0 comments

Show HN: Postcode map colouring tool for sales territories and delivery zones

https://www.gbmaps.com/mcs/map4-ui-test5.php?mapRegion=uk&mapType=district
1•mrmascott10•13m ago•0 comments

Show HN: HabitStats – a free habit tracker with heatmaps and real stats

https://habitstats.app/
2•gthompson1•14m ago•1 comments

Appatchy – paste a website or App Store link and get a UGC-style promo video

https://appatchy.com
1•pixerizer•14m ago•0 comments

Google Wallet is now available on iOS in the U.S.

https://blog.google/products-and-platforms/platforms/google-pay/wallet-available-ios-united-states/
2•acossta•15m ago•0 comments

U.S. Loses Its Measles Elimination Status

https://www.nytimes.com/2026/11/17/well/us-measles-elimination-status.html
5•cdrnsf•16m ago•0 comments

Do Apple M-Series Processors Enforce the Compound Memory Model?

https://arxiv.org/abs/2611.21406
1•titusblair•18m ago•0 comments

A Town's Forgotten History Helped Protect Its Drinking Water

https://blog.archive.org/2026/11/17/the-falmouth-story/
1•raybb•19m ago•0 comments

What Failure Looks Like

https://www.alignmentforum.org/posts/HBxe6wdjxK239zajf/what-failure-looks-like
1•cududa•20m ago•0 comments

Show HN: A dashboard my wife is finally interested in

https://github.com/sourpatchdad/patchboard
1•sourpatchdad•21m ago•0 comments

Widthipedia: A different Wiki page for every browser window size

https://vole.wtf/widthipedia/
1•gaws•21m ago•0 comments

Valkey kills the skiplist, cuts sorted set overhead by up to 43%

https://valkey.io/blog/from-skiplist-to-b+tree/
3•reconditerose•22m ago•1 comments