I'm looking for a JS DAG algorithm to draw lines passing through all the points of a set of stacked cubes from the center without ever going through the same one twice. Imagine something like a 4x4 Rubik's Cube made of 64 cubes: you start from center point and turn around increasing by one cube width at a time in x,y or z direction, until the 125 corners are linked (25 corners on each face).
I have tried and tried to draw a lot of diagrams on paper but I can't reach all the points without going through the same one twice . I don't know if it's possible or not. I guess it is, but how?
On a flat graph made of adjacent squares you just start from center and turn clockwise till all corners are linked, bu how to achieve it in a 3D set of cubes?
The reason I need this is that I have objects - each one getting its own ID - arranged in a virtual cube and I need to explore them one by one until a certain value is reached: the result of a calculation defines the starting point in x,y,z and the algorithm runs in 3d around this point looking for this value.
Another possibility is to start from one of the outer corners and reach the opposite one but in this case we're only going in one direction, e.g. from the starting point to the north-west.
I know a number of DAG algorithms to go from one point to another or from one value to another by the shortest path, but not in a circular 3d way. Any help is welcome :-)
EDIT: quick and weird solution but it works :
<style>
body { font: 100%/1.3 Arial; }
section { width: 160px; margin-left: calc(50% - 80px); }
div { position: relative; width: 160px; height: 160px; border:1px solid #aaa; margin: 10px 0; transform: skewY(-15deg) rotate(40deg) scaleY(0.7); }
span { display: inline-block; width: 38px; height: 38px; border:1px solid #ccc; margin: 0; }
ins { display: block; position: absolute; margin: -5px 0 0 -5px; width: 10px; height: 10px; background-color: #ccc; border-radius: 50%; }
</style>
<button onclick="start()">START</button>
<section id="cubes"></section>
Create objets and array
$id=function(id){ return document.getElementById(id); }
// create a 120 objects array
let ref = [];
for(i=0; i<120; i++){
ref[i] = [];
}
// draw 5 faces (4 bottom + 1 last top) + 16 squares on each face
for(i=0; i<5; i++){
let cube = '<div id="cube'+i+'">';
for(j=0; j<16; j++){
cube += '<span> </span>';
}
cube += '</div>';
$id("cubes").innerHTML += cube;
}
// randomize a spot number to get value=1
let rand = Math.floor((Math.random() * 120)+1);
// create spots in divs
for(i=0; i<5; i++){
let spots ='';
for(j=0; j<25; j++){
let left = (j*40) % 200;
let top = Math.floor(j/5) * 40;
spots += '<ins id="s-'+left+'-'+top+'-'+i+'" style="left:'+left+'px;top:'+top+'px;"></ins>';
if( (i*24)+j == rand ) { ref[(i*24)+j]=[ i,left,top,1 ]; } // only ONE spot with value=1
else { ref[(i*24)+j]=[ i,left,top,0 ]; } // default value=0
}
$id("cube"+i).innerHTML += spots;
}
// verify that one of them got value=1
console.table(ref);
Let's go
function start(){
// 1st spot id="s-80-80-2" = 2nd face in the middle
$id("s-80-80-2").style.backgroundColor = "red";
/* rules for switching between spots from first to 120th
* we first explore spots around the first one (central)
+-----+-----+-----+-----+
| | | | |
| | | | |
+-----•-----•-----•-----+
| | | | |
| | | | |
+-----•-----c-----•-----+
Y | | | | |
^ | | | | |
| +-----•-----•-----•-----+
| | | | | |
| | | | | |
| +-----+-----+-----+-----+
----------> X
* 1. get current spot by ID
* 2. we select the next one depending its left/top
* 3. when current spot on 3rd face is the 8th we jump to 2nd/4th face
* 4. when thses 3 faces centers are explored we explore the outer spots of these 3 faces
* 5. then switch to 1st and 5th central spots
* 6. then to outer spots of 1st and 5th faces
*/
next("s-80-80-2",1,1); // starting spot ID
}
Then loop in defined order
function next(id,num,cycle){
let o = id.split('-')
let pos_x = parseInt(o[1]); // 80
let pos_y = parseInt(o[2]); // 80
let pos_z = parseInt(o[3]); // face 2
let goto;
/* num = how many spots explored on this face?
* num is 1 on start because the 1st one (central) is explored
* cycle = exploration: 1->around central [• on graph], 2->outer spots [+ on graph]
* cycle=1 : num value from 1 to 8 (central+7 •)
* cycle=2 : num value from 1 to 16 (16 +)
*/
// looking for value 0/1
let val;
for(i=0; i<120; i++){
if(ref[i][3] == 1) {
val = 's-'+ref[i][1]+'-'+ref[i][2]+'-'+ref[i][0]; break;
}
}
// stop when founded
if(id==val) { $id(id).style.backgroundColor = "red"; }
else {
setTimeout(function(){
// turning around central spot on same face
if (cycle == 1) {
let matrix = [ [],[1,0],[0,1],[-1,0],[-1,0],[0,-1],[0,-1],[1,0],[1,0] ];
if (num <= 8) {
goto = 's-'+( pos_x + (matrix[num][0]*40) )+'-'+( pos_y + (matrix[num][1]*40) )+'-'+pos_z;
num++;
}
else { // explore other faces (up and down)
if( pos_z == 0 ) { goto = 's-'+80+'-'+80+'-'+4; }
if( pos_z == 1 ) { cycle = 2; goto = 's-'+160+'-'+160+'-'+2; }
if( pos_z == 2 ) { goto = 's-'+80+'-'+80+'-'+3; }
if( pos_z == 3 ) { goto = 's-'+80+'-'+80+'-'+1; }
if( pos_z == 4 ) { cycle = 2; goto = 's-'+160+'-'+160+'-'+0; }
num = 1;
}
}
// turning around face's outer spots
else if (cycle == 2) {
if (num < 17){
if (num <= 4) goto = 's-'+( pos_x - 40 )+'-'+pos_y+'-'+pos_z;
if (num >4 && num <= 8) goto = 's-'+pos_x+'-'+( pos_y - 40 )+'-'+pos_z;
if (num >8 && num <= 12) goto = 's-'+( pos_x + 40 )+'-'+pos_y+'-'+pos_z;
if (num >12 && num <= 15) goto = 's-'+pos_x+'-'+( pos_y + 40 )+'-'+pos_z;
num++;
}
if (num == 17){
if( pos_z == 0 ) { goto = 's-'+160+'-'+160+'-'+4; }
if( pos_z == 1 ) { cycle = 1; goto = 's-'+80+'-'+80+'-'+0; }
if( pos_z == 2 ) { goto = 's-'+160+'-'+160+'-'+3; }
if( pos_z == 3 ) { goto = 's-'+160+'-'+160+'-'+1; }
num = 1;
}
}
$id(id).style.backgroundColor = "#000";
if($id(goto)) {
$id(goto).style.backgroundColor = "#999";
next(goto,num,cycle);
}
},1); // 500 to quietly see how it works
}
}
When the spot getting "1" as value is reached the script stops and the spot turns red.
