frontpage.
newsnewestaskshowjobs

Made with ♥ by @iamnishanth

Open Source @Github

Open in hackernews

Generating Mazes with Inductive Graphs (2017)

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

Comments

tomfly•2mo ago
where is the entrance and exit?
Jaxan•2mo ago
Doesn’t matter, because all positions are reachable. So just pick any two positions at the border and remove a wall.
kazinator•2mo 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•2mo 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•2mo 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•2mo 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.

Show HN: A 50% Undercut

https://www.aiworkphoto.com/
1•alexbradford196•1m ago•0 comments

Chctx – omz plugin for changing context of AWS/Terraform

https://github.com/jmischler72/chctx
1•jmischler72•2m ago•0 comments

ATC/OSDI'25 Technical Sessions

http://muratbuffalo.blogspot.com/2025/07/atcosdi25-technical-sessions.html
2•ArneVogel•4m ago•0 comments

Go Fork

https://github.com/HRHDaniel/go/tree/throwOperator1.24
1•martinskou•5m ago•1 comments

AI Study Assistant – Ask questions from your own notes

1•RajGuruYadav•7m ago•0 comments

Brine new world: technology enhances desalination and lithium mining

https://cosmosmagazine.com/science/chemistry/thermodiffusion-lithium/Brinenewworld:technologyenhancesdesalinationandlithiummining
2•Bluestein•7m ago•0 comments

Climate simulator 'brings weather into the lab'

https://www.bbc.com/news/articles/cqjq2e5gd8wo
3•Bluestein•9m ago•0 comments

Autocoder.cc – The first full stack vibe coding tool

https://www.autocoder.cc/
1•Sharon_Q•10m ago•1 comments

Elon Musk's Tesla to open first India store in Mumbai on July 15

https://www.thehindu.com/business/elon-musks-tesla-to-open-first-india-store-in-mumbai-on-july-15/article69798935.ece
2•Bluestein•10m ago•0 comments

METR's AI productivity study is good

https://www.seangoedecke.com/impact-of-ai-study/
2•ingve•12m ago•0 comments

Transition to using 16 KB page sizes for Android apps and games

https://android-developers.googleblog.com/2025/07/transition-to-16-kb-page-sizes-android-apps-games-android-studio.html
1•ingve•15m ago•0 comments

The remarkable rise of an Australian deputy mayor to a plum job

https://www.smh.com.au/national/the-remarkable-rise-of-an-australian-deputy-mayor-to-a-plum-trump-job-20250711-p5me60.html
2•KnuthIsGod•15m ago•0 comments

Sipgate discovers null-pointer-dereference in Mediatek VoLTE stack firmware

https://www.sipgate.de/blog/sipgate-discovers-null-pointer-dereference-in-mediatek-volte-stack-firmware
2•todsacerdoti•20m ago•0 comments

Zero-Click Calendar Exfiltration Reveals MCP Security Risk in 11.ai

https://repello.ai/blog/zero-click-calendar-exfiltration-reveals-mcp-security-risk-in-11-ai
1•Dachande663•22m ago•0 comments

Claude Code is now a Bun single-file executable

https://twitter.com/jarredsumner/status/1943492457506697482
1•tosh•25m ago•0 comments

I built a Steam plugin for Dify (now listed on the official plugin marketplace)

https://marketplace.dify.ai/plugins/bdim/steam
1•bdim404•25m ago•1 comments

Apple vs the Law

https://formularsumo.co.uk/blog/2025/apple-vs-the-law/
6•tempodox•30m ago•0 comments

The Yellow Milkmaid Syndrome – paintings with identity problems

https://pro.europeana.eu/post/the-yellow-milkmaid-syndrome-paintings-with-identity-problems
2•thunderbong•31m ago•0 comments

Europe's first HPC ARM processor lands at TSMC

https://www.heise.de/en/news/Europe-s-first-HPC-ARM-processor-lands-at-TSMC-10483298.html
1•doener•33m ago•0 comments

Implement a robust multi-rate-limit throttling using Rails

https://www.prateekcodes.dev/implementing-api-throttling-multiple-endpoints-rails/
1•prateekkish•36m ago•0 comments

Foundation Models of Behavioral Data from Wearables Improve Health Predictions

https://arxiv.org/abs/2507.00191
1•tosh•38m ago•0 comments

Show HN: Gamified AI Tutor for School Students

https://www.edzy.ai/
1•gparashar•39m ago•0 comments

Are LLMs starting to become sentient?

https://garymarcus.substack.com/p/are-llms-starting-to-become-a-sentient
3•Duanemclemore•40m ago•2 comments

Gut microbes could protect us from toxic 'forever chemicals'

https://www.cam.ac.uk/research/news/gut-microbes-could-protect-us-from-toxic-forever-chemicals
1•timthorn•40m ago•0 comments

Mastering Postgres Replication Slots

https://www.morling.dev/blog/mastering-postgres-replication-slots/
1•gunnarmorling•41m ago•0 comments

Local Hole

https://en.wikipedia.org/wiki/Local_Hole
1•benbreen•43m ago•0 comments

GenAI Processors: Build powerful and flexible Gemini applications

https://developers.googleblog.com/en/genai-processors/
28•tzury•47m ago•1 comments

Show HN: Send RSS Feeds to Kobo E-reader

https://my.kobuddy.app/feeds
1•No-Arugula5818•47m ago•0 comments

Solar is EU’s biggest power source for the first time ever in June 2025

https://ember-energy.org/latest-updates/solar-is-eus-biggest-power-source-for-the-first-time-ever-in-june-2025/
4•pentacent_hq•48m ago•3 comments

OpenFront: Realtime Risk-like multiplayer game in the browser

https://openfront.io/
11•thombles•52m ago•0 comments