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.

Improve this question
\$\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\$
    – BlueRaja - Danny Pflughoeft
    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
  • 1
    \$\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

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .