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.

How the European Commission rolled out Matrix to more than 40k staff

https://element.io/blog/how-the-european-commission-rolled-out-matrix-to-more-than-40-000-staff/
451•liotier•5h ago•229 comments

Everything you need to survive and rebuild society

https://lastbook.org/
59•tejohnso•1h ago•29 comments

Why AI Wants to Be Local – With Pete Warden (Creator of Moonshine Voice)

https://thedataexchange.media/pete-warden-moonshine/
19•datascientist•32m ago•7 comments

Garage Door Spam

https://blog.harrison.page/garage-door-spam/
379•harrisonpage•2d ago•161 comments

Cooling buildings is overtaking heating them as an energy need, IEA says

https://maccus.fr/en/cooling-overtaking-heating/
27•robtherobber•1h ago•9 comments

Making 8-page foldable zines from a single A4 sheet in the browser

https://krthr.co/paper-folds-and-whats-new-in-fanzines-app/
90•krthr•2h ago•26 comments

Nintendo takes Picofly firmware down from GitHub [video]

https://www.youtube.com/watch?v=-TLCGUpoD6c
143•cowlevel•1d ago•43 comments

Show HN: Foolscap – a writing app that reads your book and never writes for you

https://foolscap.works/
77•atugard•2h ago•41 comments

Someone reported java4shell bug in September 2026

https://github.com/openjdk/jdk/pull/32781
112•notmine1337•4h ago•27 comments

How to Make the Ink Used to Write Hamlet and the Declaration of Independence

https://lithub.com/how-to-make-the-ink-used-to-write-hamlet-the-declaration-of-independence-and-b...
9•ohjeez•57m ago•0 comments

Ruby2ßhell: Pre-authentication RCE on stock Rails

https://verialabs.com/ruby2shell/
285•jdns•11h ago•116 comments

What's New in PHP 8.6

https://www.php.net/releases/8.6/en.php
187•netol•6h ago•97 comments

Germany and Austria Call for European Control of TikTok

https://www.techcentral.ie/germany-and-austria-call-for-european-control-of-tiktok/
60•thm•1h ago•35 comments

Gemini 4 Neon

https://blog.google/innovation-and-ai/models-and-research/gemini-models/introducing-gemini-4-neon/
953•yigitdemirag•18h ago•734 comments

Distributed, high-performance blob storage on SQLite

https://zerodha.tech/blog/high-performance-distributed-blob-storage/
169•ghostfoxgod•7h ago•40 comments

Oregon library dropped Dewey Decimal system, adopted bookstore-like arrangement

https://www.fastcompany.com/91597520/oregon-library-ditched-dewey-decimal-wayfinding-system
80•bookofjoe•1d ago•62 comments

Do not buy RAM, compress

https://curiousbits.nl/blog/do-not-buy-ram-compress/
85•Ecno92•7h ago•82 comments

We taught robots to carve marble sculptures

https://eleanorwiesler.com/blog/robotic-stone-carving/
85•ewiesler•23h ago•64 comments

Unblockable communication with gravity – Science Advances

https://www.science.org/doi/10.1126/sciadv.aee0802
44•rbanffy•3h ago•15 comments

SSD prices will start going down the second half of next year

https://www.drivevault.io/blog/when-will-hard-drive-prices-come-down.html
214•illidan1000•7h ago•181 comments

C's designated initializers give us named arguments

https://quuxplusone.github.io/blog/2026/11/16/named-arguments-in-c/
36•joshcsimmons•1d ago•30 comments

15M web servers on one VM – smoltcp, DPDK, AF_XDP

https://kapteko.com/15-million-webservers/
280•fessguid•10h ago•32 comments

Exponential Behavior in Magic: The Gathering

https://levineuwirth.org/essays/exponential-magic/
48•neuwirth•1d ago•23 comments

I built Cornhole News. A Hacker News inspired site for news across the Midwest

https://cornholenews.news
11•cornholemedia•32m ago•4 comments

Show HN: Watch weight-space programming in action with WebGPU

https://tabbyml.github.io/weight-space-playground/
3•wsxiaoys•38m ago•0 comments

It's All about the Allocator

https://aarol.dev/posts/zig-allocator/
12•ibobev•4d ago•1 comments

Multiple vulnerabilities in Regexp and String case conversion

https://www.ruby-lang.org/en/news/2026/11/18/multiple-vulnerabilities-in-regexp-and-string/
314•runesoerensen•16h ago•120 comments

Anthropic prices initial public offering

https://www.anthropic.com/news/anthropic-prices-initial-public-offering
365•surprisetalk•16h ago•675 comments

Seven new models at scalable price-performance

https://microsoft.ai/news/microsoft-ignite-2026/
584•gmays•1d ago•365 comments

Inside Deutsche Bank

https://www.inside-db.com/
753•gyre007•1d ago•251 comments