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.

Hill-climbing vLLM and SGLang configs on a single A100

https://twitter.com/johnsonshi86/status/2124250717963932121
1•johnsonshi•23s ago•0 comments

Progress and Poverty

https://en.wikipedia.org/wiki/Progress_and_Poverty
1•teleforce•1m ago•0 comments

Anthropic mathematician proves Riemann hypothesis

https://www.scientificamerican.com/article/anthropic-mathematician-claims-to-prove-riemann-hypoth...
1•twilight-code•1m ago•1 comments

Api.live – Point it at a repo, get every endpoint as a runnable request

https://api.live/
1•varuncee•2m ago•1 comments

A CPU benchmark you can't fake

https://primecrunch.com/blog/8/a-cpu-benchmark-you-can-t-fake
1•andyhedges•3m ago•0 comments

Chinese-Born Neuroscientist Is Detained by ICE While Traveling from Conference

https://www.nytimes.com/2026/11/20/science/chinese-scientist-detained-ice-princeton-eva-yi-xie-.html
2•yubblegum•4m ago•0 comments

Fley AI Update 1.2v a voice AI assistant

https://fileknot.io/1f4410ab016d2e4d/FLEY_AI_Setup1.2.exe
1•Drfoxi•7m ago•1 comments

Show HN: Security Watch – alerts when a new vulnerability affects your stack

https://github.com/ShieldaAI/security-watch
1•VDudaG-A•9m ago•0 comments

Show HN: Reviving a 2012 open-source password manager for modern Android

https://jurakovic.github.io/passdroid/
1•jurakovic•10m ago•0 comments

Ask HN: How many of you have replaced your everyday apps with something custom?

1•JCattheATM•11m ago•1 comments

Open-source harness and MCP dataset for options trading with AI agents

https://github.com/DevDizzle/gammarips-harness
1•gammarips•13m ago•0 comments

Duha – All-in-one software for masjids and Islamic centers

https://duha.app
1•moesaid007•19m ago•0 comments

Riemann Hypothesis: The AI generated a 61GB, obfuscated code dump

https://twitter.com/Crashoverride_X/status/2123900241258955223
1•doener•20m ago•3 comments

International UN talks on controlling use of autonomous weapons collapse

https://www.theguardian.com/technology/2026/nov/21/international-talks-control-ai-autonomous-weap...
4•nephihaha•23m ago•0 comments

Show HN: Hearthen, an app for building and keeping strong relationships

https://hearthenapp.com
2•mamorales•26m ago•1 comments

Older people with religious or spiritual beliefs enjoy better quality of life

https://www.cnn.com/2026/11/20/health/religious-spiritual-older-adults-intl-scli-wellness
4•teleforce•27m ago•2 comments

MHUB – install and update 28 open source Mac utilities from the menu bar

https://github.com/starbudweiser/mHUB
2•Starbudweiser•28m ago•0 comments

Grok Bot Symbiosis

https://timeline.place/guides/grok-bot-symbiosis
3•marcelmarais•30m ago•0 comments

Studio Wetware

https://studiowetware.com/
2•Beachkilla•33m ago•0 comments

Say which AI wrote it: AI transparency for Open Source projects

https://www.saywhichai.org
2•cedricbonhomme•34m ago•0 comments

Code was my second mother tongue. Now everyone speaks it. What could go wrong?

https://blog.ngxson.com/going-deaf-in-my-own-language
1•ngxson•36m ago•0 comments

Plv8: V8 Engine JavaScript Procedural Language Add-On for PostgreSQL

https://github.com/plv8/plv8
1•thunderbong•40m ago•1 comments

Show HN: Git blame for AI code, down to the agent session

https://keepplain.com/blame
1•keepplain•42m ago•0 comments

Cappz – AI agents sell work to each other, paid per stage on XRPL

https://github.com/CAPPZ-ai/cappz-sdk
1•fastflair•44m ago•0 comments

Trump vows to work with Democrats to cap credit card interest rates at 10%

https://apnews.com/article/trump-credit-cards-interest-rates-warren-banks-098a69b520e520e535eebe5...
1•petethomas•49m ago•1 comments

Macaron – Turn customer messages into fixes ready for review

https://macaron.sh
1•garagemanda•51m ago•0 comments

Americas Mexico detains top cartel boss 'El Chapo Isidro,' setting off violence

https://www.npr.org/2026/11/21/nx-s1-6049672/cartel-boss-el-chapo-isidro-detained
1•blinding-streak•51m ago•0 comments

Bayer reaches Roundup settlement that could cost the company billions

https://www.npr.org/2026/11/21/nx-s1-6049684/roundup-bayer-hodgkins-settlement
1•blinding-streak•53m ago•0 comments

Measuring nanometers by looking at your reflection [video]

https://www.youtube.com/watch?v=k4AEZ35VklM
1•ivanjermakov•53m ago•0 comments

Field Guide: Running Qwen3.8 Locally

https://igorstechnoclub.com/field-guide-running-qwen38-locally/
1•Igor_Wiwi•54m ago•0 comments