Moving around the edges of a cube efficiently

Paul thanks for that. It uses the same principles as as my brute force example but done more neatly. However, there needs to be code for each plane which multiplies the amount of code and brings us back to the clumsy nature of the solution.

I need a cup of coffee and a chance to examine your code in more detail, but does it allow for the fact that when moving on the XY plane the snake could be either at the top or the bottom of the cube ?

does it allow for the fact that when moving on the XY plane the snake could be either at the top or the bottom of the cube ?

Yes. the z coodinate stays where it is - at zero or at 7 - and the algorithm won’t affect that.

UKHeliBob:
However, there needs to be code for each plane which multiplies the amount of code and brings us back to the clumsy nature of the solution.

Hmm, so you want prettier, eh? Ok.

At any moment, we have the axis we move along, the axis that completes the square, and the third axis that we don’t care about. These can be indexes into the position array.

We don’t need x/y/xinc - all we need is “are we moving forward or bacward along the current axis”?

Oh - and I’ll use some pointer arithmetic for the snake history. There are fine distinctions to be made betweeen “pointer to byte” and “pointer to an array of 3 byte”.

Finally, there are three optins when hitting a corner: continue around the current plane, switch planes, or reverse direction. I have added this as a possibility via random(). As before - add button code to suit.

Here ya go. Prettier, as promised:

–EDIT-- Added enough code to make this a complete sketch. Appears to work.

byte snake[5][3]; // the compiler sets this to all zero for our starting position
byte *xyz = snake[0]; // the first iteration will increment this, but that's ok.
// the effect is that snake[0] contains the starting position, snake[1] will be the first move.

int movingAxis = 0;
int squareAxis = 1;
int otherAxis = 2;

boolean inc = true; // we are starting at (0,0,0), so need to inc.

#define SWAP(a,b) { int n = (a); (a)=(b); (b)=(n);}

void setup() {
  Serial.begin(9600);
  set(xyz[0], xyz[1], xyz[2]);
}

void loop() {
  delay(200);

  byte *prevxyz = xyz;

  // I'm pretty sure that this is right.
  xyz += sizeof(*snake);
  if (xyz - snake[0] >= sizeof(snake)) {
    xyz = snake[0];
  }

  clear(xyz[0], xyz[1], xyz[2]);

  memcpy(xyz, prevxyz, sizeof(*snake));
  boolean snakeHitTheCorner;
  if (inc)
    snakeHitTheCorner = ++xyz[movingAxis] >= 7;
  else
    snakeHitTheCorner = --xyz[movingAxis] <= 0;

  set(xyz[0], xyz[1], xyz[2]);

  if (snakeHitTheCorner) {
    // choose the new axis
    if (random(10)) {
      // the usual case - progress around the square
      SWAP(movingAxis, squareAxis);
    }
    else if (random(3)) {
      // switch to the other plane
      SWAP(movingAxis, otherAxis);
    }
    else {
      // leave axis as-is: this will make the snake 'reflect' off the corner
    }

    // and decide what direction to go:
    inc = xyz[movingAxis] <= 0;
  }
}

void set(int x, int y, int z) {
  Serial.print(x);
  Serial.print(", ");
  Serial.print(y);
  Serial.print(", ");
  Serial.print(z);
  Serial.println();
}

void clear(int x, int y, int z) {
}

tricky..

How do you set the start point of I assume, the head of the snake? What would you like that call to look like?

-jim lee

@PaulMurrayCbr - I have just tried your new code in reply #21 and have an LED happily buzzing around the cube at random as I type this. How your code works is going to be interesting to work out. My first challenge is to prevent reflections

Many thanks for the work that you have put into this and should I share the code with anyone I will credit you with its creation with a link to this thread.

My first challenge is to prevent reflections

That was easy thanks to the very informative comments in the code

UKHeliBob:
The initial goal is to have the snake travel continuously around the edges of a given face of the cube
[...]
The next goal will be to read an input button and cause the snake to change to another face at the next corner if the button is/has been pressed.

It seems to me that the code to circumnavigate a face can be used on any face without needing to know which face it is on - in other words treat it as a 2D object. Then another variable (perhaps updated by a button) can select the face on which the LEDS light.

...R

Moving round any single face is easy given a rotation to move in and the current position. It is determining which face to change to when reaching a corner whilst on one of 3 faces and deciding which way round to go on the new face that is the problem

UKHeliBob:
It is determining which face to change to when reaching a corner whilst on one of 3 faces and deciding which way round to go on the new face that is the problem

I'm not sure that is a good description of the problem. That sentence just suggests that two decisions are needed. Decisions are simple.

I often find that a clearer description of the problem helps me towards a solution.

...R

I often find that a clearer description of the problem helps me towards a solution.

That is fair comment because of the general nature of my description. Perhaps some particular examples of decisions needed will better explain the problem

Taking this cube layout

        D----C
       /|   /|
      A----B |
      | H--|-G
      |/   |/
      E----F

Suppose that we reach corner B
Which edge we move on to depends on which face we are currently on and the current rotation

If we are on face ABFE going clockwise we need to move on to edge BF to keep going clockwise on the same face. This requires a change of X and Z increment values

If we are on face ABFE going counter clockwise we need to move on to edge AB to keep going counter clockwise on the same face. This requires a different change of X and Z increment values

If we are on face ABCD going counter clockwise we need to move on to edge BC to keep going counter clockwise on the same face. This requires a change of X and Y increment values

If we are on face ABCD going clockwise we need to move on to edge AB to keep going clockwise on the same face. This requires a different change of X and Y increment values

If we are on face BCGF going counter clockwise we need to move on to edge BF to keep going counter clockwise on the same face. This requires a change of Y and Z increment values

If we are on face BCGF going clockwise we need to move on to edge BC to keep going clockwise on the same face. This requires a different change of Y and Z increment values

Note that this is just for one corner and there are 8 of them, and it does not take into account the need to allow for a change of face, perhaps with a change of rotation to prevent bouncing back along the current side

All of this is easy to program using an array of structs (one per face) holding data describing what should happen in all circumstances. This is neater than my original brute force switch/case but Paul's code manages to drive an LED, or potentially a snake of LEDs around the edges of the cube, changing face at random, without the need for masses of data and is the sort of solution I was looking for

Referring to Reply #28 ...

I may be grossly over simplifying but I come back to what I said in Reply #25 - but maybe I did not express myself clearly.

What I have in mind is that the motion is ONLY calculated on the face WXYZ which is not any of the actual faces. Then (I think) it should be straightforward to map the position on WXYZ to its equivalent on any of the other faces - the actual face being determined by an appropriate variable.

...R

What I have in mind is that the motion is ONLY calculated on the face WXYZ which is not any of the actual faces. Then (I think) it should be straightforward to map the position on WXYZ to its equivalent on any of the other faces - the actual face being determined by an appropriate variable.

I think that the pertinent word here is "map", hence my use of an array to hold the "map" in a data driven version. Given the current face you can have an array of structs of the form

struct edgeData
{
  byte nextEdge[2]; //indexed using current rotation
  int xInc;  //CCW values - CW value will be derived
  int yInc;
  int zInc;
  byte altFace[2] = {99, 99}; //dummy values for testing
  byte altEdge[2] = {99, 99};
  byte altRotation[2] = {99, 99};
} edges[6][12]; //face and edge

Given the current edge and rotation as keys the program can read where to move to at the next corner for both the normal (continue round the same face) and alternate (change to new face) cases. I was hoping by creating a portion of the data I would spot patterns and/or common data thus enabling more efficient use of the data.

The only helpful observation that I made was that the CW values for the x, y, z increments could be derived from the CCW values by multiplying by -1 and I used that in the program. There may well be other possible simplifications such as FRONT/BACK, LEFT/RIGHT or TOP/BOTTOM symmetry but I have not looked very closely

To make things simple let's assume that the snake only traverses the edges of a rectangle. Suppose (again for simplicity) there are 6 positions along each edge. That means that the circumference of a rectangle can be represented by an array of 20 elements. So there needs to be an array of 20 elements for each side of the cube.

On what I earlier called the WXYZ face there is also an array of 20 elements. The snake movement calculations take place on it. Imagine with a 3-element snake that elements 12, 13 and 14 are occupied.

Then based on the variable that determines the side of the cube that is in-use the equivalent elements 12, 13 and 14 can be lit on the in-use face.

Now the problem reduces to how you link the elements of the linear arrays to the LEDs on the different faces.

Just my 3 cents

...R

UKHeliBob:
@PaulMurrayCbr - I have just tried your new code in reply #21 and have an LED happily buzzing around the cube at random as I type this. How your code works is going to be interesting to work out.

A pleasure. It's always a happy thing when someone tries your code and finds it useful.

It's always a happy thing when someone tries your code and finds it useful.

I also suspect that coming up with such a neat solution gave you some satisfaction too. I know that it puts a smile on my face when something neat works

UKHeliBob:
Moving round any single face is easy given a rotation to move in and the current position. It is determining which face to change to when reaching a corner whilst on one of 3 faces and deciding which way round to go on the new face that is the problem

At the moment, there’s code to swap ‘moving axis’ and ‘square axis’ to continue moving around the face, and code to swap ‘moving axis’ and ‘other axis’ to switch to another face. The face switched to will be the one with no edge in common with the moving axis, and that’s probably a mistake.

There are six permutations of what can be done when the snake hits the corner. I think that the only permutations you are really interested in are:

  if (snakeHitTheCorner) {
    // choose the new axis
    if (random(10)) {
      // the usual case - progress around the square
      SWAP(movingAxis, squareAxis);
    }
    else if (random(2)) {
      // switch to the other plane sharing an edge
      SWAP(movingAxis, otherAxis);
    }
    else {
      // switch to the plane at the *end* of this edge
      SWAP(movingAxis, otherAxis);
      SWAP(squareAxis, otherAxis);
    }

    // and decide what direction to go:
    inc = xyz[movingAxis] <= 0;
  }

Try it, see if it does what you want.

Hang on .... Im getting confused, now. I think I mixed up the two 'change' cases. They should work, but I have the comments the wrong way around. I think.

it's 10PM here in Oz, and I'm drinking Coopers Red.

I found this challenge interesting and gave it a go (not as condensed as PaulMurrayCbr approach)

My cube is as such

     Z
      ^
      |
      |   B----------C
      |  /|         /|
      | / |        / |
      |/  |       /  |
      A----------D   |
      |   |      |   |
      |   F------|---G
      |  /       |  /
      | /        | /
      |/         |/
   ---E----------H---------------> X
      |
      |

There are nbLedsPerEdge on each edge (counting the corners)
Each LED is at a positive integral position in the coordinate system.

For example if we say we have 5 LEDs total per edge (counting the corners) and we look at E—H

  • E is at (0,0,0) and has a LED
  • H is at (4, 0, 0) and has a LED
    You have 3 others LEDs at (1,0,0) , (2,0,0) and (3,0,0)

You have 6 faces, so 6 possible clockwise paths described in the array cwFacePaths[] (CW as defined when user is looking at that face)

The current path index is in variable currentFacePath
At any point in time you are coming from a specific corner of the current path (held in variable currentCorner which varies between 0 and 3)
The snake travels CW or CCW (decided by variable currentDirection)

The snakes circles on a given face until being asked to switch face. I don’t have a cube with LEDs so I have a code working in the Serial monitor. Sending an ‘\n’ in the monitor asks the snake to go to another face (next time it hits a corner).

The face I select is the next one in list of face paths containing this corner (each corner belongs to three faces, so each corner appears in two other paths). This is arbitrary, you could also find the 2 other paths and pick one at random.

The snake head moves every ∆t (in variable snakeSpeed) by making one step from the current corner towards the next corner. its coordinates are in the variable snakeHeadCoordinates (I did not implement a snake body as it’s just an array of coordinates where you shift previous positions each time the snake moves).

here is the code - the Serial monitor @115200 bauds should give you a sense for what’s going on

/* THIS IS THE CUBE

      Z
      ^
      |
      |   B----------C
      |  /|         /|
      | / |        / |
      |/  |       /  |
      A----------D   |
      |   |      |   |
      |   F------|---G
      |  /       |  /
      | /        | /
      |/         |/
   ---E----------H---------------> X
      |
      |

  we have nbLedsPerEdge on each edge
*/

const byte nbLedsPerEdge = 5;                   // ie 3 LEDs in between two corners + 2, one for each corners
const byte nbStepsPerEdge = nbLedsPerEdge - 1;  // we take nbStepsPerEdge to go from one corner to the next

struct t_coordinate {
  uint8_t x;
  uint8_t y;
  uint8_t z;
};

const t_coordinate cornerCoordinates[] =
{
  {0, 0, nbStepsPerEdge},                             // A
  {0, nbStepsPerEdge, nbStepsPerEdge},                // B
  {nbStepsPerEdge, nbStepsPerEdge, nbStepsPerEdge},   // C
  {nbStepsPerEdge, 0, nbStepsPerEdge},                // D
  {0, 0, 0},                                          // E
  {0, nbStepsPerEdge, 0},                             // F
  {nbStepsPerEdge, nbStepsPerEdge, 0},                // G
  {nbStepsPerEdge, 0, 0},                             // H
};

t_coordinate snakeHeadCoordinates;

enum t_corner : char {A = 'A', B, C, D, E, F, G, H};
enum t_direction : int8_t {CCW = -1, CW = +1};

struct t_cwFacePath {
  t_corner corner[4];
};

// the only 6 possible clockwise path on the 6 faces. CW as defined when user is looking at that face
const t_cwFacePath cwFacePaths[] = {
  {A, B, C, D},
  {A, D, H, E},
  {A, E, F, B},
  {D, C, G, H},
  {C, B, F, G},
  {E, H, G, F},
};
const byte numberOfPaths = sizeof cwFacePaths / sizeof cwFacePaths[0];

uint8_t currentFacePath = 0; // the index of the face
uint8_t currentCorner = 0; // the index of the corner we are coming from
uint8_t currentStepOnEdge = 0; // at which LED we are
uint32_t snakeSpeed = 1000ul; // snake moves 1 LED every snakeSpeed ms

t_direction currentDirection = CW;

bool changeFaceRequested = false;

t_corner comingFrom()
{
  return cwFacePaths[currentFacePath].corner[currentCorner];
}

t_corner goingTo()
{
  return cwFacePaths[currentFacePath].corner[((uint8_t) (currentCorner + currentDirection)) % 4];
}

uint8_t atLedNumber()
{
  return currentStepOnEdge;
}


void printCurrenFace()
{
  Serial.print(F(" circling "));
  Serial.print(currentDirection == CW ? F("CW") : F("CCW"));
  Serial.print(F(" on Face ["));
  for (byte i = 0; i < 4; i++) {
    Serial.write(cwFacePaths[currentFacePath].corner[i]);
  }
  Serial.print(F("] "));
}

void printInformation()
{
  printCurrenFace();
  if (currentStepOnEdge == 0) {
    Serial.print(F("at corner '"));
  } else {
    Serial.print(F("coming from '"));
  }
  Serial.write(comingFrom());
  Serial.print(F("' and going towards '"));
  Serial.write(goingTo());
  Serial.print(F("' at LED# "));
  Serial.print(currentStepOnEdge);
  Serial.print(F(" ( "));
  Serial.print(snakeHeadCoordinates.x);
  Serial.print(F(", "));
  Serial.print(snakeHeadCoordinates.y);
  Serial.print(F(", "));
  Serial.print(snakeHeadCoordinates.z);
  Serial.println(F(")"));
}

void updatePosition()
{
  uint8_t comingFromIndex = comingFrom() - A;
  uint8_t goingToIndex = goingTo() - A;
  snakeHeadCoordinates.x =  cornerCoordinates[comingFromIndex].x + ((cornerCoordinates[goingToIndex].x - cornerCoordinates[comingFromIndex].x) * currentStepOnEdge) / nbStepsPerEdge;
  snakeHeadCoordinates.y =  cornerCoordinates[comingFromIndex].y + ((cornerCoordinates[goingToIndex].y - cornerCoordinates[comingFromIndex].y) * currentStepOnEdge) / nbStepsPerEdge;
  snakeHeadCoordinates.z =  cornerCoordinates[comingFromIndex].z + ((cornerCoordinates[goingToIndex].z - cornerCoordinates[comingFromIndex].z) * currentStepOnEdge) / nbStepsPerEdge;

  printInformation();
}

void resetSnake()
{
  currentFacePath = 0;          // TOP FACE
  currentCorner = 0;            // Coming from corner A
  currentStepOnEdge = 0;        // First LED (on Corner)
  currentDirection = CCW;        // Turning ClockWise
  changeFaceRequested = false;
}

void moveSnakeHead()
{
  if (changeFaceRequested && (currentStepOnEdge == 0)) { // if we are at a corner and need to change direction
    // decide which new face we go to. We are at corner comingFrom()
    // we look for the next face containing that corner and switch to that one
    Serial.println(F("CHANGING FACE"));
    t_corner standingAtCorner = comingFrom();
    bool nextCornerFound = false;
    for (byte p = 1; p <= numberOfPaths; p++) {
      for (byte c = 0; c < 4; c++) {
        if (cwFacePaths[(currentFacePath + p) % numberOfPaths].corner[c] == standingAtCorner) {
          currentFacePath = (currentFacePath + p) % numberOfPaths;
          currentCorner = c;
          nextCornerFound = true;
          break;
        } // end if searching for the next path containing this corner
      } // end for each corner in path p
      if (nextCornerFound) break;
    } // end for each path following the current one
    updatePosition();
    changeFaceRequested = false;
  } else {
    static uint32_t lastChrono;
    if (millis() - lastChrono >= snakeSpeed) {          // time to take a step ?
      if (++currentStepOnEdge >= nbStepsPerEdge) {
        currentStepOnEdge = 0;
        currentCorner = ((uint8_t) (currentCorner + currentDirection)) % 4;
      }
      updatePosition();
      lastChrono = millis();
    }
  }
}

void setup()
{
  Serial.begin(115200);
  resetSnake();
  Serial.println(F("===== SNAKE STARTING ====="));
  updatePosition();
}


void loop()
{
  changeFaceRequested |= (Serial.read() == '\n'); // sending a LF asks for face change. To be replaced by handling button
  moveSnakeHead();
}

Serial Monitor (@ 115200 bauds) sample
*_</em></em> <em><em><em>*[color=purple] ===== SNAKE STARTING ===== circling CCW on Face [ABCD] at corner 'A' and going towards 'D' at LED# 0 ( 0, 0, 4) circling CCW on Face [ABCD] coming from 'A' and going towards 'D' at LED# 1 ( 1, 0, 4) circling CCW on Face [ABCD] coming from 'A' and going towards 'D' at LED# 2 ( 2, 0, 4) circling CCW on Face [ABCD] coming from 'A' and going towards 'D' at LED# 3 ( 3, 0, 4) circling CCW on Face [ABCD] at corner 'D' and going towards 'C' at LED# 0 ( 4, 0, 4) CHANGING FACE [color=red][i](I sent \n through the console)[/i][/color] circling CCW on Face [ADHE] at corner 'D' and going towards 'A' at LED# 0 ( 4, 0, 4) circling CCW on Face [ADHE] coming from 'D' and going towards 'A' at LED# 1 ( 3, 0, 4) ... [/color]*</em></em></em> <em><em>_*
any interest or questions, feel free to ask

I keep seeing it as 8 vertex nodes with double links between them.

 A vertedx has three paths in/out. A B C

               A

            B       C

paths between nodes are double links (Both directions)

Start at initial node

initial node, save current node address.
Choose A B or C as exit. // Left or right can't be defined yet.
Jump to node X, 
We now have a vector, choose direction Left or right.
 
 while(running) {
    Arrival from A -> left = C; right = B;
    Arrival from B -> left = A; right = C;
    Arrival from C -> left = B; right = A;
    save current node address
    direction is already set.
    jump to node X1;
 }

-jim lee

J-M-L:
here is the code - the Serial monitor @115200 bauds should give you a sense for what's going on

I still think that treating the circumference of a face as a linear array is simpler. No need to worry about corners.

...R

Robin2:
I still think that treating the circumference of a face as a linear array is simpler. No need to worry about corners.

I deal with them as a linear array.
The only reason I single out corners is to switch face when users asks.

@Jim Lee - isn’t that making it more difficult to walk the graph CW or CCW. (May be left and right is enough if you orient them the right way)