8
\$\begingroup\$

I have a tree graph that I'd like to fit into a grid, the result being a grid-based maze that adheres to the tree graph. Are there any good maze algorithms that are able to start with a known structure?

Here's a crude example:

enter image description here

The child nodes do not have to be immediately adjacent to their parent in the grid, but must maintain the same reachability. This is reflected in the black "dummy" node in the image.

The basic concept is to build a node tree reflecting the "logic" of a space, then building a reasonably compact, grid-based "maze" that maintains that logic.

\$\endgroup\$
10
  • 3
    \$\begingroup\$ This is an interesting question that I haven't seen before. You'll probably get better answers on cs.stackexchange.com or even cstheory.stackexchange.com \$\endgroup\$ May 9, 2022 at 3:24
  • 1
    \$\begingroup\$ Concise answer: No, you can't, unless many nodes in the tree graph have only one branch or less. The space required for tree graph grows exponentially. But the space grows geometrically in grid. It's like (n^k) vs k^2. \$\endgroup\$
    – Mangata
    May 9, 2022 at 4:43
  • 2
    \$\begingroup\$ Mangata: I think it's safe to presume in this context that the grid is either unbounded/grows appropriately as we place nodes, or that the first step of our algorithm pre-sizes the grid large enough to fit the tree with at least high probability, even if that means making the grid dimensions disproportionately large compared to the tree depth. \$\endgroup\$
    – DMGregory
    May 9, 2022 at 11:03
  • 2
    \$\begingroup\$ I mean, This problem arises if there are similar restrictions like parent and child nodes must be adjacent in the grids. Maybe i'm wrong because I noticed that there is a ‘fake’ node in the example graph of the post. \$\endgroup\$
    – Mangata
    May 9, 2022 at 11:32
  • 2
    \$\begingroup\$ For general trees on a square grid the answer is no, as any tree with more than 4 edges to a node will not map. However, I think it works with modifications. First, you need to 'split' nodes w/ too many edges. For instance, say you have node A with edges to B,C,D,E,F. A could be split A1 & A2 such that A1 connects to A2,B,C,D and A1 connects to A1,E,F. Reachability is the same & distance is preserved provided that edges between split nodes have a distance of 1. And as sort of mention, you either need to allow for dummy nodes or you need to allow edges to span across more than one cell. \$\endgroup\$
    – Pikalek
    May 9, 2022 at 14:33

1 Answer 1

-2
\$\begingroup\$

You cannot fit a tree graph into a 2d grid because of one simple reason - one vertice can have 8+ connections in the 2d grid you have only 8 bordered cells. Even if you limit the nodes connection to for example only a maximum of 2. You will shortly get dead end situations very fast.

\$\endgroup\$
2
  • \$\begingroup\$ See the comment thread above where workarounds for these problems have already been proposed. \$\endgroup\$
    – DMGregory
    Dec 30, 2023 at 18:53
  • \$\begingroup\$ So you think my answer is not correct can you explain why? And why nobody post the answer this problem have no solution. It can only have solution if you hard limit input tree. Who need such solution with such limitation? \$\endgroup\$
    – Bogdan
    Dec 30, 2023 at 22:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .