1

CubeLayout

I'm creating a game world that consists of a 16 x 16 x 16 rubix cube (pictured), where the individual cubes are floating in space. The cubes continuously move along a single set path that links up with itself at the end. It might be helpful to think of them as traversing a 3D maze. Are there any algorithms or solutions that could help me generate this path?

Adam
  • 33
  • 2
  • You just need a single closed loop path that visits each node? – Dan Pichelman Oct 27 '15 at 21:16
  • Yes, that's exactly right. – Adam Oct 27 '15 at 21:17
  • 1
    [Sharing your research helps everyone](http://meta.programmers.stackexchange.com/questions/6559/why-is-research-important). Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see [ask] – gnat Oct 27 '15 at 21:18
  • I wonder if arrays can be nested, as well as the loops to populate them... –  Oct 27 '15 at 21:22
  • Gnat, I'm afraid I'm very new to pathing algorithms so I've been completely stumped by the complexity of this task. I considered simply weaving the path up and down along the sides and working inwards but then the path end wouldn't be able to link to the path start – Adam Oct 27 '15 at 21:24
  • I have a solution, but no time to write it up :-(. Weave a path up & down across a face, but use 2 pencils. One is the start of the path, & the other is the end of the path. You'll cover a single face, drop down to the next face, then repeat. When you get to the end of the last face, just link the 2 paths (pencil lines) together. – Dan Pichelman Oct 27 '15 at 21:37

1 Answers1

1

As I mentioned in a comment, one possible way to solve this is to weave a path back & forth across a face using 2 pencils. One pencil draws the beginning of the path, and the other draws the end.

Here's an example for one face:

+----------------+
|abcdefghijklmnop|
|ZYXWVUTSRQPONMLq|
|****ABCDEFGHIJKr|
|*###3210zyxwvuts|
|*###############|
|***************#|
|***************#|
|*###############|
|*###############|
|***************#|
|***************#|
|*###############|
|*###############|
|***************#|
|***************#|
|*###############|
+----------------+

One pencil starts in the top row, left column, "abcd..."

The other pencil starts in the 2nd row, left column, "ZYXWV..."

As you can see, both paths end in the left column, bottom 2 rows. At that point you move to the next face & repeat the process.

When you've finished you have to "parallel" paths. Just tie the ends together & you have your loop that visits each node.

a limitation

This only works because the number of rows (or columns) is a multiple of 2. If your grid was 15x15x15, you'd have a problem.

Dan Pichelman
  • 13,773
  • 8
  • 42
  • 73