# Moving around the edges of a cube efficiently

Background
I am programming the movement of a ‘snake’ of 5 pixels along the edges of any face of an 8x8x8 LED cube. When the snake reaches a corner it needs to turn in the appropriate direction and continue around the same face. Being a cube there are 6 faces and 8 corners and the snake could be moving clockwise or counter clockwise on any face. So, the snake could reach a corner in one of 6 * 8 * 2 cases

The challenge
Whilst it is possible to program this by brute force by checking for the current face, the direction the snake is moving in, rotation and which edge has been reached that naturally does not appeal to me

Brute force
I had hoped that by programming some of the cases by brute force I would spot some common code whereby several cases could be taken care of by common code but I have not spotted anything. The brute force code for clockwise or counter clockwise rotation on1 of 3 faces (TOP, FRONT and LEFT) is attached and the code for one face is included below as I think that it illustrates the problem.

Possible simplification
I hope that the number of cases and/or the code to deal with them can be reduced but I have not come up with a solution. Ideally the code would be of the form

``````if (thisIsTrue || thatIsTrue || somethingElseIsTrue)
{
someFunction();
}
``````

where someFunction() would deal with several cases without the need for more tests to establish what needs to be updated. I had high hopes of detecting a corner (easy) and turning right or left depending on rotation, but turning requires testing which face you are on and which data to update so it just moves the code into a function

Data representation
The snake data is in an array holding the X, Y and Z coordinates of the snake segments and is managed as a circular buffer to keep track of the head and tail segments when it moves. Turning LEDs on and off is managed by library functions and the LEDs are updated by a timer driven ISR in the library.

Brute force code for one face

``````void moveSnake() //update head position and move
{
switch (currentView)
{
case TOP: //from top
switch (currentDirection)
{
case RIGHT_LEFT:
Serial.println("moving to left");
if (body[headIndex][X] == 0) //reached the left
{
switch (rotation)
{
case CW:  //on top, right to left, at left, clockwise
xInc = 0;
yInc = 1; //move towards back
zInc = 0;
currentDirection = FRONT_BACK;
break;
case CCW:  //on top, right to left, at left, anticlockwise
xInc = 0;
yInc = -1;  //move towards front
zInc = 0;
currentDirection = BACK_FRONT;
break;
}
}
break;
case LEFT_RIGHT:
Serial.println("moving to right");
if (body[headIndex][X] == 7) //reached the right
{
switch (rotation)
{
case CW:  //on top, left to right, at right, clockwise
xInc = 0;
yInc = -1; //move towards front
zInc = 0;
currentDirection = BACK_FRONT;
break;
case CCW:  //on top, left to right, at left, anticlockwise
xInc = 0;
yInc = 1;  //move towards back
zInc = 0;
currentDirection = FRONT_BACK;
break;
}
}
break;
case FRONT_BACK:
Serial.println("moving to back");
if (body[headIndex][Y] == 7) //reached the back
{
switch (rotation)
{
case CW:  //on top, front to back, at back, clockwise
xInc = 1; //move towards right
yInc = 0;
zInc = 0;
currentDirection = LEFT_RIGHT;
break;
case CCW:  //on top, front to back, at back, anticlockwise
xInc = -1; //move towards left
yInc = 0;
zInc = 0;
currentDirection = RIGHT_LEFT;
break;
}
}
break;
case BACK_FRONT:
Serial.println("moving to front");
if (body[headIndex][Y] == 0) //reached the front
{
switch (rotation)
{
case CW:  //on top, back to front, at front, clockwise
xInc = -1; //move towards left
yInc = 0;
zInc = 0;
currentDirection = RIGHT_LEFT;
break;
case CCW:  //on top, back to front, at front, anticlockwise
xInc = 1; //move towards right
yInc = 0;
zInc = 0;
currentDirection = LEFT_RIGHT;
break;
}
}
break;
}
break;
``````

I think I would model it with an array of structs containing x,y,z that tell you where the corners are. Start at 0,0,0. Look at the first element of the array and go there and proceed through the array in the same fashion.

This way the code is data driven. Start at the end of the array to rotate in the opposite direction. At each corner, now you know the destination so you will be incrementing or decrementing just one coordinate to move towards your target corner.

Not as elegant as you're looking for I suspect though. Could be made less prosaic by making the code pick a new destination corner on the fly.

Could be made less prosaic by making the code pick a new destination corner on the fly.

The idea of a destination corner sounds appealing. My intention is to have the snake change direction at a corner if a button is pressed so that a user (me) can turn towards a target (sound familiar ?)

not clear to me what the goal is? is it to have traveled the edge of each surface until all edges have been traveled?

is the question what to do at a corner and what needs to be known?

The initial goal is to have the snake travel continuously around the edges of a given face of the cube either clockwise or counter clockwise, which I can do using brute force by checking each case when it reaches a corner, as you will see from the TOP, FRONT and LEFT cases in the code.

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. For instance, if the current face is the top, the snake is moving clockwise and it reaches the top/left/front corner it would normally turn right and continue round the top but if the button is/has been pressed then it will turn left, the face would change to FRONT and the snake would rotate counter clockwise around the front until another button press

None of the button reading, change of face and direction is yet in the code.

I could add the BOTTOM, RIGHT and BACK cases using the same method as now, however, this seems very primitive so I am seeking a neater way of doing it

I hope that this helps clarify what I am doing. If not, then feel free to ask more questions

Longer term I have ideas to incorporate a target to try and reach with the snake, maybe have more than one snake running (snake objects here we come !), maybe a two person version or a snake moving at random that you have to avoid or even the ability to turn before a corner so that the snake cuts across the centre of the cube. I suspect that most of these will not be realised, but I am having fun so far as I did soldering 512 LEDs into the cube. (Well, the first 64 or so were fun !)

i'm not sure i understand the way you want to solve this problem (e.g. brute force, ...) seems like there's plenty of time to make decisions.

a less computational approach is pre-compute decisions. have a set of paths (i.e. corners) the snake travels. when a button is pushed the path changes to a different one with a common corner. each corner has three possible paths, so pick one of the two other paths for a specific corner.

it needs to turn in the appropriate direction and continue around the same face

Since every edge of a cube is shared by two faces, how is the "same" face specified?

sounds like you're describing each face by the edges. i'm suggesting travelling between corners.

so when a button is pressed and you reach a corner select one of the two paths other than the current path.

below is a diagram of a cube with top corners A, B, C, D and bottom corners W, X, Y, Z.

to the right is a list of the 6 paths

on the far right are the paths for each corner

use arrays of structs with indices to corners or paths

once a new path is selected, you need to locate the position in the path corresponding to the corner at. either that or the table identifying the paths for each corner not only identifies the path but the corresponding position in the path

``````        D----C     1  A B C D       A  1 2 5
/|   /|     2  A B X W       B  1 2 3
A----B |     3  B C Z X       C  1 3 4
| Y--|-Z     4  C D Y Z       D  1 4 5
|/   |/      5  D A W Y       W  2 5 6
W----X       6  W X Y Z       X  2 3 6
Y  4 5 6
Z  3 4 6
``````

jremington:
Since every edge of a cube is shared by two faces, how is the "same" face specified?

Because the face does not change. If the snake is on the top it stays there until/unless signalled to start circulating around another adjacent face at the next corner

The fact that each edge is shared by two faces is one of the complications of the program as currently written because it needs to know which face it is on in order to know which way to turn at the next corner, so the number of tests required is doubled

A lookup table of the two allowed continuous paths on a single face, plus the allowed branches and consequent face changes at each corner, would be applicable to the entire cube by symmetry.

Agreed, it would take some serious head scratching to come up with the transformations.

UKHeliBob:
Because the face does not change. If the snake is on the top it stays there until/unless signalled to start circulating around another adjacent face at the next corner

i outlined an approach based on paths defined by corners where there are 3 faces in common with each corner. if you do something similar, defining paths based on edges, there are simply two paths for each edge to choose from and you simply switch to the other path

don't understand the complication. what am i missing?

i'm not sure i understand the way you want to solve this problem (e.g. brute force, ...) seems like there's plenty of time to make decisions.

There is plenty of time, but testing each and every possibility of face, edge, direction of travel and whether a corner (actually the edge) reached is clumsy as it results in a massive set of if/else or, as I prefer switch/case tests

sounds like you're describing each face by the edges. i'm suggesting travelling between corners.

That does sound like a good idea and it is one that I had considered but not tried

As to your example cube (nice drawing BTW), although there are 6 paths, any of them may be traversed clockwise or counter clockwise which is another factor to take into account but I will give it some thought

Forget about buttons and changing faces for now. For now I would be happy with a neat way to keep a snake circulating around a given face in either direction

UKHeliBob:
although there are 6 paths, any of them may be traversed clockwise or counter clockwise which is another factor to take into account but I will give it some thought

you have an array defining a path. incrementing or decrementing an index thru the array determines direction

there are simply two paths for each edge to choose from and you simply switch to the other path

Simply switching to the other path or using it in the opposite rotation requires a test to be made. Not complicated as such (I expressed that badly in a previous reply) but testing for rotation doubles the number of possible outcomes that need to be acted on

I am beginning to favour the use of a data driven, precomputed solution and will probably write the code to deal with rotation about one face using the ideas presented in this thread to see how it works out

you have an array defining a path. incrementing or decrementing an index thru the array determines direction

But only if you know the direction which needs another test or for it to be part of the data, which would be better, of course

not sure i understand your concerns

using an array, direction is determined by the increment value. to change direction, reverse the sign of the increment (i.e. inc = -inc;)

i understand that changing the architecture is major, but if you start with an adequate one, the code can be tightened up to minimize its size.

This is an easy problem once you realise it can be done in 3D vector geometry, where a face has a normal
vector to represent it and the cross-product allows consistent turn-direction - the cross product of an edge’s
vector with the normal to the face will be the next edge if going one way round the face, and the inverse of the next edge going the other way.

isn't the problem which are the next LEDs to turn on and off?

So store the LED list for each edge indexed by the 2 corner coordinates - cube corners have
coords like (+/-1, +/-1, +/-1), which can be coded as 3 bits if you use bit = (coord+1)/2.

Thus 3 bits code each end of an edge, making indexing schemes fairly easy, although with only
12 edges a linear search isn't too woeful.

UKHeliBob:
Being a cube there are 6 faces and 8 corners and the snake could be moving clockwise or counter clockwise on any face. So, the snake could reach a corner in one of 6 * 8 * 2 cases

Hmm.

Keep variables xinc, yinc, and zinc. At any time, one of them will be nonzero, and the third will be -1 or +1.

The question becomes, what do you change these values to after hitting the edge: moving to xyz=0 or xyz=7 ? For each of the three possible axes along which you might be moving, there's only ever two possibilities. Let's say xinc is currently -1 and x has just hit 0, then your snake is either moving on the XY plane (so you need to set yinc), or the XZ plane (so you need to set zinc). What yinc or zinc need to be set to depends on the current value of y or z, which will always either be 0 (in which case, 1) or 7 (in which case, -1).

So without further ado, here ya go! I have added code to switch direction on a 1 in 10 basis - add button code to suit:

``````enum Plane {XY, YZ, XZ} plane = XY;

int xinc = 1, yinc = 0, zinc = 0;

byte snake[5][3];
int snakeIdx = 0;

oid loop() {
delay(50);

// next snake location
int prevIdx = snakeIdx;
snakeIdx = (snakeIdx+1)%5;

clear(snake[snakeIdx][0],snake[snakeIdx][1],snake[snakeIdx][2]);
snake[snakeIdx][0] = snake[prevIdx][0] + xinc;
snake[snakeIdx][1] = snake[prevIdx][1] + yinc;
snake[snakeIdx][2] = snake[prevIdx][2] + zinc;
set(snake[snakeIdx][0],snake[snakeIdx][1],snake[snakeIdx][2]);

// now to determine new direction

if(xinc != 0 && (
snake[snakeIdx][0] ==0 || snake[snakeIdx][0]==7)) {
// we have hit the X boundary
xinc = 0;

if(random(10)==0) // switch plane, for random fun
plane = (plane==XY) ? XZ:XY;

if(plane == XY) {
yinc = snake[snakeIdx][1]==0 ? 1 : -1;
else // plane must be XZ
zinc = snake[snakeIdx][2]==0 ? 1 : -1;

}
else
if(yinc != 0 &&  (
snake[snakeIdx][1] ==0 || snake[snakeIdx][1]==7)) {
// we have hit the Y boundary
yinc = 0;

if(random(10)==0) // switch plane, for random fun
plane = (plane==XY) ? YZ:XY;

if(plane == XY) {
xinc = snake[snakeIdx][0]==0 ? 1 : -1;
else // plane must be YZ
zinc = snake[snakeIdx][2]==0 ? 1 : -1;
}
else
if(zinc != 0 &&  (
snake[snakeIdx][2] ==0 || snake[snakeIdx][2]==7)) {
// we have hit the Z boundary
zinc = 0;

if(random(10)==0) // switch plane, for random fun
plane = (plane==XZ) ? YZ:XZ;

if(plane == XZ) {
xinc = snake[snakeIdx][0]==0 ? 1 : -1;
else // plane must be YZ
yinc = snake[snakeIdx][1]==0 ? 1 : -1;
}
}
``````