ON ERROR IF ERR=17 CHAIN @lib$+"../examples/tools/touchide" ELSE MODE 3 : PRINT REPORT$ : END REM 3D Rubik's Cube simulation using Herbert Kociemba's solution REM (C) Copyright R.T.Russell, http://www.rtrussell.co.uk/, 2017 REM Lookup tables from: http://rubiksolve.com/download.php?id=10 REM (run the contained SAMPLE.BAT script to generate the tables) REM Rubik's Cube is a Registered Trade Mark of Rubik's Brand Ltd REM This BBC BASIC demo is strictly for non-commercial use only. HIMEM = PAGE + 8000000 DEBUG = FALSE BB4W = INKEY(-256) == &57 IF BB4W INSTALL @lib$+"d3dliba" ELSE INSTALL @lib$+"ogllib" ON CLOSE PROCcleanup : QUIT ON ERROR PROCcleanup : IF ERR=17 CHAIN @lib$+"../examples/tools/touchide" ELSE MODE 3 : PRINT REPORT$ " at line "; ERL : END PROCtitle("3D Rubik's Cube simulation using Herbert Kociemba's algorithm") BackCol% = &FF7F7F7F nLights% = 0 DIM Light%(0), Object%(53), nVertex%(53), Format%(53), Size%(53), Material%(53), Texture%(53) DIM Ref%(53), Yaw(53), Pitch(53), Roll(53), Xpos(53), Ypos(53), Zpos(53), Eye(2), LookAt(2) REM Coloured textures: COLOR 128 CLS : VDU 5 FOR I% = 0 TO 5 READ r&, g&, b& COLOR 1, r&, g&, b& FOR J% = 0 TO 8 GCOL 1 RECTANGLE FILL 2, 2, 58, 58 GCOL 4,0 IF DEBUG MOVE 16,44 : PRINT ;I%*9+J%; OSCLI "GSAVE """ + @tmp$ + "tex" + STR$(I%*9 + J%) + ".bmp"" 0, 0, 64, 64" NEXT NEXT I% DATA 000, 128, 000 : REM Green DATA 000, 000, 128 : REM Blue DATA 255, 128, 000 : REM Orange DATA 255, 000, 000 : REM Red DATA 255, 255, 255 : REM White DATA 255, 255, 000 : REM Yellow PROCinstructions PROCinit_kociemba REM Three axis-aligned squares each consisting of two triangles: X% = OPENOUT(@tmp$ + "squarex.fvf") Y% = OPENOUT(@tmp$ + "squarey.fvf") Z% = OPENOUT(@tmp$ + "squarez.fvf") ntriangles% = 2 BPUT #X%,ntriangles% * 3 * 2 : BPUT#X%,0 : BPUT #X%,0 : BPUT#X%,0 : REM No. of vertices BPUT #Y%,ntriangles% * 3 * 2 : BPUT#Y%,0 : BPUT #Y%,0 : BPUT#Y%,0 BPUT #Z%,ntriangles% * 3 * 2 : BPUT#Z%,0 : BPUT #Z%,0 : BPUT#Z%,0 BPUT #X%,&02 : BPUT #X%,1 : BPUT #X%,20 : BPUT#X%,0 : REM Vertex format and size BPUT #Y%,&02 : BPUT #Y%,1 : BPUT #Y%,20 : BPUT#Y%,0 BPUT #Z%,&02 : BPUT #Z%,1 : BPUT #Z%,20 : BPUT#Z%,0 FOR V% = 0 TO 3*ntriangles%-1 READ x, y : v = 0.5 + x: u = 0.5 + y PROC4(X%,0) : PROC4(X%,x) : PROC4(X%,y) : PROC4(X%,u) : PROC4(X%,v) PROC4(Y%,x) : PROC4(Y%,0) : PROC4(Y%,y) : PROC4(Y%,u) : PROC4(Y%,v) PROC4(Z%,y) : PROC4(Z%,x) : PROC4(Z%,0) : PROC4(Z%,u) : PROC4(Z%,v) NEXT REM Black back faces: RESTORE +1 FOR V% = 0 TO 3*ntriangles%-1 READ x, y PROC4(X%,0) : PROC4(X%,y) : PROC4(X%,x) : PROC4(X%,0) : PROC4(X%,0.02) PROC4(Y%,y) : PROC4(Y%,0) : PROC4(Y%,x) : PROC4(Y%,0) : PROC4(Y%,0.02) PROC4(Z%,x) : PROC4(Z%,y) : PROC4(Z%,0) : PROC4(Z%,0.02) : PROC4(Z%,0) NEXT CLOSE #0 DATA 0.5, -0.5, -0.5, -0.5, -0.5, 0.5 DATA -0.5, 0.5, 0.5, 0.5, 0.5, -0.5 REM Wait for space bar or click: REPEAT UNTIL INKEY(2) = 32 OR INKEY(-10) OR INKEY(-74) WHILE INKEY(-10) WAIT 2 : ENDWHILE CLS ON MOVE IF @msg% <> 5 RETURN ELSE PROCcleanup VDU 26 IF POS REM SDL thread sync REM Initialise 3D subsystem: IF BB4W THEN Device% = FN_initd3d(@hwnd%, 2, 0) IF Device% = 0 ERROR 100, "Couldn't initialise Direct3D" ELSE Device% = FN_initgl(@hwnd%, 2, 0) IF Device% = 0 ERROR 100, "Couldn't initialise OpenGL" ENDIF REM Create the cube: I% = 0 FOR face% = 0 TO 5 FOR row% = -1 TO 1 FOR col% = -1 TO 1 CASE face% OF WHEN 0: f$ = "squarey" Xpos(I%) = row% : Ypos(I%) = +1.5 : Zpos(I%) = col% : Pitch(I%) = PI : Yaw(I%) = PI WHEN 1: f$ = "squarey" Xpos(I%) = -row% : Ypos(I%) = -1.5 : Zpos(I%) = col% WHEN 2: f$ = "squarez" Xpos(I%) = col% : Ypos(I%) = -row% : Zpos(I%) = -1.5 WHEN 3: f$ = "squarez" Xpos(I%) = -col% : Ypos(I%) = -row% : Zpos(I%) = +1.5 : Yaw(I%) = PI WHEN 4: f$ = "squarex" Xpos(I%) = +1.5 : Ypos(I%) = -row% : Zpos(I%) = col% WHEN 5: f$ = "squarex" Xpos(I%) = -1.5 : Ypos(I%) = -row% : Zpos(I%) = -col% : Yaw(I%) = PI ENDCASE Object%(I%) = FN_load3d(Device%, @tmp$+f$+".fvf", nVertex%(I%), Format%(I%), Size%(I%)) IF Object%(I%) = 0 ERROR 100, "Couldn't load "+f$+".fvf" IF NOT DEBUG IF I% = 40 THEN Texture%(I%) = FN_loadtexture(Device%, @tmp$+"Rubik.bmp") ELSE Texture%(I%) = FN_loadtexture(Device%, @tmp$+"tex"+STR$(I%)+".bmp") ENDIF IF Texture%(I%) = 0 ERROR 100, "Couldn't load tex"+STR$(I%)+".bmp" REM OSCLI "DELETE " + @tmp$ + "tex" + STR$(I%) + ".bmp" I% += 1 NEXT col% NEXT row% NEXT face% nObject% = I% Ref%() = Texture%() REM Main loop: Tilt = 30 Spin = 0 Toff% = TIME Spinning% = TRUE MOUSE MouseX%, MouseY%, MouseB% MouseT% = 0 LookAt() = 0, 0, 0 REPEAT twist% = FALSE CASE INKEY$(2) OF WHEN "1","G","g": twist% = 1 : PROCtitle("Twist up (green) face") WHEN "2","B","b": twist% = 2 : PROCtitle("Twist down (blue) face") WHEN "3","O","o": twist% = 3 : PROCtitle("Twist left (orange) face") WHEN "4","R","r": twist% = 4 : PROCtitle("Twist right (red) face") WHEN "5","W","w": twist% = 5 : PROCtitle("Twist front (white) face") WHEN "6","Y","y": twist% = 6 : PROCtitle("Twist back (yellow) face") WHEN CHR$&91,CHR$&80: PROCscramble : PROCtitle("Scrambled") WHEN CHR$&93,CHR$&81: Spinning% = FALSE : PROCsolve : PROCtitle("Solved") Spinning% = TRUE : Toff% = TIME - 4*Spin WHEN CHR$&95: PROCsave : PROCtitle("Saved to " + @usr$ + "Rubik.dat") WHEN CHR$&97: IF FNload PROCtitle("Loaded") ELSE PROCtitle("File not found or bad format") ENDCASE IF twist% PROCtwist(twist%-1, 1) IF INKEY(-26) Spin += 1 : Spinning% = FALSE IF INKEY(-122) Spin -= 1 : Spinning% = FALSE IF INKEY(-42) IF Tilt < +45 Tilt += 1 IF INKEY(-58) IF Tilt > -45 Tilt -= 1 MOUSE X%, Y%, B% IF B% THEN IF MouseB% THEN Spin += (MouseX% - X%) / 10 : Spinning% = FALSE Tilt += (MouseY% - Y%) / 10 ENDIF MouseT% += 1 ELSE IF MouseB% IF MouseT% < 10 THEN IF X% < @vdu%!208 * 0.25 PROCscramble IF X% > @vdu%!208 * 1.75 THEN Spinning% = FALSE PROCsolve : PROCtitle("Solved") Spinning% = TRUE Toff% = TIME - 4*Spin ENDIF ENDIF MouseT% = 0 ENDIF MouseX% = X% MouseY% = Y% MouseB% = B% PROCrender UNTIL FALSE END DEF PROCrender IF Spinning% THEN Spin = (TIME - Toff%) / 4 Eye() = 7*COSRADTilt*COSRADSpin, 7*SINRADTilt, 7*COSRADTilt*SINRADSpin PROC_render(Device%, BackCol%, nLights%, Light%(), nObject%, Material%(), Texture%(), Object%(), nVertex%(), Format%(), Size%(), \ \ Yaw(), Pitch(), Roll(), Xpos(), Ypos(), Zpos(), Eye(), LookAt(), PI/4, @vdu%!208/@vdu%!212, 1, 1000, 0) ENDPROC REM Twise a face: DEF PROCtwist(F%, S%) LOCAL C%,I%,O%,R%,r,t,yaw(),pitch(),roll(),xpos(),ypos(),zpos() DIM yaw(DIM(Yaw(),1)),pitch(DIM(Pitch(),1)),roll(DIM(Roll(),1)) DIM xpos(DIM(Xpos(),1)),ypos(DIM(Ypos(),1)),zpos(DIM(Zpos(),1)) yaw()=Yaw():pitch()=Pitch():roll()=Roll():xpos()=Xpos():ypos()=Ypos():zpos()=Zpos() IF S% <> 8 THEN FOR I% = S% TO 8*SGNS%-S% STEP S% FOR R% = -1 TO 1 FOR C% = -1 TO 1 O% = F%*9 + R%*3 + C% + 4 r = SQR(R%^2+C%^2) t = FNatan2(R%,C%) + PI*I%/16 CASE F% OF WHEN 0: Xpos(O%) = r*SINt : Zpos(O%) = r*COSt : Yaw(O%) = PI*I%/16-PI WHEN 1: Xpos(O%) = -r*SINt : Zpos(O%) = r*COSt : Yaw(O%) = -PI*I%/16 WHEN 2: Ypos(O%) = -r*SINt : Xpos(O%) = r*COSt : Roll(O%) = -PI*I%/16 WHEN 3: Ypos(O%) = -r*SINt : Xpos(O%) = -r*COSt : Roll(O%) = -PI*I%/16 WHEN 4: Ypos(O%) = -r*SINt : Zpos(O%) = r*COSt : Pitch(O%) = PI*I%/16 WHEN 5: Ypos(O%) = -r*SINt : Zpos(O%) = -r*COSt : Pitch(O%) = PI*I%/16 ENDCASE NEXT NEXT R% FOR C% = -1 TO 1 r = SQR(1.5^2+C%^2) t = FNatan2(1.5,C%) + PI*I%/16 CASE F% OF WHEN 0: O% = 46+C% : Zpos(O%) = -r*COSt : Xpos(O%) = -r*SINt : Yaw(O%) = PI*I%/16-PI O% = 37+C% : Zpos(O%) = r*COSt : Xpos(O%) = r*SINt : Yaw(O%) = PI*I%/16 WHEN 1: O% = 52-C% : Zpos(O%) = r*COSt : Xpos(O%) = -r*SINt : Yaw(O%) = PI-PI*I%/16 O% = 43-C% : Zpos(O%) = -r*COSt : Xpos(O%) = r*SINt : Yaw(O%) = -PI*I%/16 WHEN 2: O% = 12-3*C% : Xpos(O%) = r*COSt : Ypos(O%) = -r*SINt : Roll(O%) = -PI*I%/16 O% = 3-3*C% : Xpos(O%) = -r*COSt : Ypos(O%) = r*SINt : Roll(O%) = -PI*I%/16 WHEN 3: O% = 14+3*C% : Xpos(O%) = -r*COSt : Ypos(O%) = -r*SINt : Roll(O%) = PI*I%/16 O% = 5+3*C% : Xpos(O%) = r*COSt : Ypos(O%) = r*SINt : Roll(O%) = PI*I%/16 WHEN 4: O% = 23+3*C% : Ypos(O%) = -r*COSt : Zpos(O%) = -r*SINt : Pitch(O%) = PI*I%/16 O% = 30-3*C% : Ypos(O%) = r*COSt : Zpos(O%) = r*SINt : Pitch(O%) = -PI*I%/16 WHEN 5: O% = 21-3*C% : Ypos(O%) = r*COSt : Zpos(O%) = -r*SINt : Pitch(O%) = -PI*I%/16 O% = 32+3*C% : Ypos(O%) = -r*COSt : Zpos(O%) = r*SINt : Pitch(O%) = PI*I%/16 ENDCASE NEXT FOR R% = -1 TO 1 r = SQR(R%^2+1.5^2) t = FNatan2(R%,1.5) + PI*I%/16 CASE F% OF WHEN 0: O% = 19-R% : Zpos(O%) = -r*COSt : Xpos(O%) = -r*SINt : Yaw(O%) = PI*I%/16 O% = 28-R% : Zpos(O%) = r*COSt : Xpos(O%) = r*SINt : Yaw(O%) = PI*I%/16-PI WHEN 1: O% = 25+R% : Zpos(O%) = -r*COSt : Xpos(O%) = r*SINt : Yaw(O%) = -PI*I%/16 O% = 34+R% : Zpos(O%) = r*COSt : Xpos(O%) = -r*SINt : Yaw(O%) = PI-PI*I%/16 WHEN 2: O% = 50-3*R% : Xpos(O%) = -r*COSt : Ypos(O%) = r*SINt : Roll(O%) = PI*I%/16 O% = 39+3*R% : Xpos(O%) = r*COSt : Ypos(O%) = -r*SINt : Roll(O%) = -PI*I%/16 WHEN 3: O% = 48+3*R% : Xpos(O%) = -r*COSt : Ypos(O%) = -r*SINt : Roll(O%) = -PI*I%/16 O% = 41-3*R% : Xpos(O%) = r*COSt : Ypos(O%) = r*SINt : Roll(O%) = PI*I%/16 WHEN 4: O% = 10-R% : Ypos(O%) = -r*COSt : Zpos(O%) = -r*SINt : Pitch(O%) = PI*I%/16 O% = 7+R% : Ypos(O%) = r*COSt : Zpos(O%) = r*SINt : Pitch(O%) = PI-PI*I%/16 WHEN 5: O% = 16+R% : Ypos(O%) = -r*COSt : Zpos(O%) = r*SINt : Pitch(O%) = -PI*I%/16 O% = 1-R% : Ypos(O%) = r*COSt : Zpos(O%) = -r*SINt : Pitch(O%) = PI*I%/16-PI ENDCASE NEXT R% PROCrender IF BB4W WAIT 2 NEXT I% ENDIF Yaw()=yaw():Pitch()=pitch():Roll()=roll():Xpos()=xpos():Ypos()=ypos():Zpos()=zpos() FOR I% = 1 TO -3*SGNS% SWAP Texture%(F%*9 + 0), Texture%(F%*9 + 6) : SWAP Texture%(F%*9 + 3), Texture%(F%*9 + 7) SWAP Texture%(F%*9 + 6), Texture%(F%*9 + 8) : SWAP Texture%(F%*9 + 7), Texture%(F%*9 + 5) SWAP Texture%(F%*9 + 8), Texture%(F%*9 + 2) : SWAP Texture%(F%*9 + 5), Texture%(F%*9 + 1) CASE F% OF WHEN 0: SWAP Texture%(29), Texture%(47) : SWAP Texture%(28), Texture%(46) : SWAP Texture%(27), Texture%(45) SWAP Texture%(47), Texture%(20) : SWAP Texture%(46), Texture%(19) : SWAP Texture%(45), Texture%(18) SWAP Texture%(20), Texture%(38) : SWAP Texture%(19), Texture%(37) : SWAP Texture%(18), Texture%(36) WHEN 1: SWAP Texture%(44), Texture%(26) : SWAP Texture%(43), Texture%(25) : SWAP Texture%(42), Texture%(24) SWAP Texture%(26), Texture%(53) : SWAP Texture%(25), Texture%(52) : SWAP Texture%(24), Texture%(51) SWAP Texture%(53), Texture%(35) : SWAP Texture%(52), Texture%(34) : SWAP Texture%(51), Texture%(33) WHEN 2: SWAP Texture%(36), Texture%(0) : SWAP Texture%(39), Texture%(3) : SWAP Texture%(42), Texture%(6) SWAP Texture%(0), Texture%(53) : SWAP Texture%(3), Texture%(50) : SWAP Texture%(6), Texture%(47) SWAP Texture%(53), Texture%(9) : SWAP Texture%(50), Texture%(12) : SWAP Texture%(47), Texture%(15) WHEN 3: SWAP Texture%(2), Texture%(38) : SWAP Texture%(5), Texture%(41) : SWAP Texture%(8), Texture%(44) SWAP Texture%(38), Texture%(11) : SWAP Texture%(41), Texture%(14) : SWAP Texture%(44), Texture%(17) SWAP Texture%(11), Texture%(51) : SWAP Texture%(14), Texture%(48) : SWAP Texture%(17), Texture%(45) WHEN 4: SWAP Texture%(11), Texture%(27) : SWAP Texture%(10), Texture%(30) : SWAP Texture%(9), Texture%(33) SWAP Texture%(27), Texture%(6) : SWAP Texture%(30), Texture%(7) : SWAP Texture%(33), Texture%(8) SWAP Texture%(6), Texture%(26) : SWAP Texture%(7), Texture%(23) : SWAP Texture%(8), Texture%(20) WHEN 5: SWAP Texture%(29), Texture%(17) : SWAP Texture%(32), Texture%(16) : SWAP Texture%(35), Texture%(15) SWAP Texture%(17), Texture%(24) : SWAP Texture%(16), Texture%(21) : SWAP Texture%(15), Texture%(18) SWAP Texture%(24), Texture%(0) : SWAP Texture%(21), Texture%(1) : SWAP Texture%(18), Texture%(2) ENDCASE NEXT I% PROCrender ENDPROC REM Scramble cube by making 20 random twists: DEF PROCscramble LOCAL I% FOR I% = 1 TO 20 PROCtwist(RND(6)-1, 8) NEXT ENDPROC REM Save cube to a data file: DEF PROCsave LOCAL F%, I%, J%, T%, face$, cols$ face$ = "UDLRFB" : cols$ = "GBORWY" F% = OPENOUT(@usr$ + "Rubik.dat") FOR I% = 0 TO 53 IF (I% MOD 9) = 0 BPUT#F%,MID$(face$,I%DIV9+1,1)+":"; T% = Texture%(I%) FOR J% = 0 TO 53 IF T% = Ref%(J%) EXIT FOR NEXT BPUT#F%,MID$(cols$,J%DIV9+1,1); IF (I% MOD 9) = 8 BPUT#F%," "; NEXT I% CLOSE #F% ENDPROC REM Load cube from a data file: DEF FNload LOCAL F%, I%, J%, T%, face$, cols$, dat$ face$ = "UDLRFB" : cols$ = " " F% = OPENIN(@usr$ + "Rubik.dat") IF F% = 0 THEN = FALSE dat$ = GET$#F% BY EXT#F% CLOSE #F% FOR I% = 0 TO 5 J% = INSTR(dat$, MID$(face$,I%+1,1)+":") IF J% = 0 CLOSE #F% : = FALSE MID$(cols$,I%+1,1) = MID$(dat$,J%+6,1) NEXT FOR I% = 0 TO 5 J% = INSTR(dat$, MID$(face$,I%+1,1)+":") FOR T% = 0 TO 8 IF T%<>4 Texture%(I%*9+T%) = Ref%(9*INSTR(cols$,MID$(dat$,J%+T%+2,1))-9) NEXT NEXT I% = TRUE REM Initialise the Kociemba algorithm: DEF PROCinit_kociemba TWISTS = 3^7 FLIPS = 2^11 CHOICES = 495 CORNERPERMS = 8*7*6*5*4*3*2 NMSEPERMS = 8*7*6*5*4*3*2 MSEPERMS = 4*3*2 FOUND = 1 REM Edge locations: UF = 0 : UL = 1 : UB = 2 : UR = 3 FU = 0 : LU = 1 : BU = 2 : RU = 3 DF = 4 : DL = 5 : DB = 6 : DR = 7 FD = 4 : LD = 5 : BD = 6 : RD = 7 RF = 8 : FL = 9 : LB = 10 : BR = 11 FR = 8 : LF = 9 : BL = 10 : RB = 11 REM Corner locations: URF = 0 : UFL = 1 : ULB = 2 : UBR = 3 RFU = 0 : FLU = 1 : LBU = 2 : BRU = 3 FUR = 0 : LUF = 1 : BUL = 2 : RUB = 3 DFR = 4 : DLF = 5 : DBL = 6 : DRB = 7 FRD = 4 : LFD = 5 : BLD = 6 : RBD = 7 RDF = 4 : FDL = 5 : LDB = 6 : BDR = 7 REM Phase 1 move mapping tables: DIM twistMoveTable%(TWISTS-1,5) DIM flipMoveTable%(FLIPS-1,5) DIM choiceMoveTable%(CHOICES-1,5) REM Phase 2 move mapping tables: DIM cornerPermMoveTable%(CORNERPERMS-1,5) DIM nmsePermMoveTable%(NMSEPERMS-1,5) DIM msePermMoveTable%(MSEPERMS-1,5) REM Phase 1 pruning tables: DIM TwistFlipPrunTable&(TWISTS*FLIPS DIV2-1) DIM TwistChoicePrunTable&(TWISTS*CHOICES DIV2+1) DIM FlipChoicePrunTable&(FLIPS*CHOICES DIV2-1) REM Phase 2 pruning tables: DIM CornerPrunTable&(CORNERPERMS*MSEPERMS/2-1) DIM EdgePrunTable&(NMSEPERMS*MSEPERMS/2-1) REM Load tables from disk: PROCloadtable1(twistMoveTable%(), @dir$ + ".Tables/Twist.mtb") PROCloadtable1(flipMoveTable%(), @dir$ + ".Tables/Flip.mtb") PROCloadtable1(choiceMoveTable%(), @dir$ + ".Tables/Choice.mtb") PROCloadtable1(cornerPermMoveTable%(), @dir$ + ".Tables/CrnrPerm.mtb") PROCloadtable1(nmsePermMoveTable%(), @dir$ + ".Tables/EdgePerm.mtb") PROCloadtable1(msePermMoveTable%(), @dir$ + ".Tables/SlicPerm.mtb") PROCloadtable2(TwistFlipPrunTable&(), @dir$ + ".Tables/TwstFlip.ptb") PROCloadtable2(TwistChoicePrunTable&(), @dir$ + ".Tables/TwstChce.ptb") PROCloadtable2(FlipChoicePrunTable&(), @dir$ + ".Tables/FlipChce.ptb") PROCloadtable2(CornerPrunTable&(), @dir$ + ".Tables/CrnrSlic.ptb") PROCloadtable2(EdgePrunTable&(), @dir$ + ".Tables/EdgeSlic.ptb") DIM cornerFacelets&(7,2) cornerFacelets&() = 8, 27, 38, \ URF \ 6, 36, 20, \ UFL \ 0, 18, 47, \ ULB \ 2, 45, 29, \ UBR \ 11, 44, 33, \ DFR \ 9, 26, 42, \ DLF \ 15, 53, 24, \ DBL \ 17, 35, 51 : REM DRB DIM cornerMap&(23) cornerMap&() = 22,132,147, \ URF, RFU, FUR, \ 26,156, 76, \ UFL, FLU, LUF, \ 17,102,182, \ ULB, LBU, BUL, \ 33,198,113, \ UBR, BRU, RUB, \ 63,163,118, \ DFR, FRD, RDF, \ 52, 97,152, \ DLF, LFD, FDL, \ 68,193, 83, \ DBL, BLD, LDB, \ 59,139,189 : REM DRB, RBD, BDR DIM edgeFacelets&(11,1) edgeFacelets&() = 7, 37, \ UF \ 3, 19, \ UL \ 1, 46, \ UB \ 5, 28, \ UR \ 10, 43, \ DF \ 12, 25, \ DL \ 16, 52, \ DB \ 14, 34, \ DR \ 30, 41, \ RF \ 23, 39, \ LF \ 21, 50, \ LB \ 32, 48 : REM RB DIM edgeMap&(23) edgeMap&() = 4,24, \ UF, FU, \ 2,12, \ UL, LU, \ 5,30, \ UB, BU \ 3,18, \ UR, RU \ 10,25, \ DF, FD \ 8,13, \ DL, LD \ 11,31, \ DB, BD \ 9,19, \ DR, RD \ 22,27, \ RF, FR \ 16,26, \ LF, FL \ 17,32, \ LB, BL \ 23,33 : REM RB, BR ENDPROC REM Solve the cube: DEF PROCsolve LOCAL I%, J%, T%, cubie%, cubicle%, corner%, edge% LOCAL cornerLocation%, edgeLocation%, cornerParity%, edgeParity% REM Initialize a "standard" cube. The standard cube represents REM the cube state in terms of cubie permutation and parity: DIM faceletCube&(53) DIM kcube{cornerCubiePerms&(7), cornerCubieOrientations&(7), \ \ edgeCubiePerms&(11), edgeCubieOrientations&(11), \ \ thresh%, newthresh%} FOR I% = 0 TO 53 T% = Texture%(I%) FOR J% = 0 TO 53 IF T% = Ref%(J%) faceletCube&(I%) = J% DIV 9 : EXIT FOR NEXT NEXT I% cornerParity% = 0 FOR cubicle% = 0 TO 7 cubie% = faceletCube&(cornerFacelets&(cubicle%,0)) * 36 + \ \ faceletCube&(cornerFacelets&(cubicle%,1)) * 6 + \ \ faceletCube&(cornerFacelets&(cubicle%,2)) cornerLocation% = -1 FOR corner% = 0 TO 23 IF cubie% = cornerMap&(corner%) THEN cornerLocation% = corner% kcube.cornerCubiePerms&(cubicle%) = corner% DIV 3 kcube.cornerCubieOrientations&(cubicle%) = corner% MOD 3 cornerParity% += corner% MOD 3 EXIT FOR corner% ENDIF NEXT corner% IF cornerLocation% = -1 ERROR 100, "Invalid corner markings" NEXT cubicle% IF cornerParity% MOD 3 ERROR 101, "Invalid corner parity" edgeParity% = 0 FOR cubicle% = 0 TO 11 cubie% = faceletCube&(edgeFacelets&(cubicle%,0)) * 6 + \ \ faceletCube&(edgeFacelets&(cubicle%,1)) edgeLocation% = -1 FOR edge% = 0 TO 23 IF cubie% = edgeMap&(edge%) THEN edgeLocation% = edge% kcube.edgeCubiePerms&(cubicle%) = edge% DIV 2 kcube.edgeCubieOrientations&(cubicle%) = edge% MOD 2 edgeParity% += edge% MOD 2 EXIT FOR edge% ENDIF NEXT edge% IF edgeLocation% = -1 ERROR 102, "Invalid edge markings" NEXT cubicle% IF edgeParity% MOD 2 ERROR 103, "Invalid edge parity" IF FNpermparity(^kcube.cornerCubiePerms&(0), 8) <> \ \ FNpermparity(^kcube.edgeCubiePerms&(0), 12) ERROR 104, "Invalid total parity" REM Globals: DIM solutionMoves1&(31), solutionMoves2&(31) DIM solutionPowers1&(31), solutionPowers2&(31) solutionLength1% = 0 solutionLength2% = 0 REM Solve: PROCsolve1(kcube{}) ENDPROC DEF PROCsolve1(cube{}) LOCAL iteration%, result% iteration% = 1 result% = FALSE cube.thresh% = FNphase1cost(FNtwist(cube{}), FNflip(cube{}), FNchoice(cube{})) REPEAT PROCtitle("Solving phase 1 (" + STR$cube.thresh% + " moves)") cube.newthresh% = 1000 result% = FNsearch1(cube{}, FNtwist(cube{}), FNflip(cube{}), FNchoice(cube{}), 0) cube.thresh% = cube.newthresh% iteration% += 1 UNTIL result% ENDPROC DEF FNsearch1(cube{}, twist%, flip%, choice%, depth%) LOCAL cost%, totalcost%, move%, power%, twist2%, flip2%, choice2%, result% LOCAL phase2cube{} REM Compute cost estimate to phase 1 goal state cost% = FNphase1cost(twist%, flip%, choice%) IF cost% = 0 THEN solutionLength1% = depth% DIM phase2cube{} = cube{} : phase2cube{} = cube{} IF solutionLength1% THEN PROCprintsolution(solutionMoves1&(), solutionPowers1&(), solutionLength1%) FOR move% = 0 TO solutionLength1%-1 FOR power% = 1 TO solutionPowers1&(move%) PROCapplymove(phase2cube{}, solutionMoves1&(move%)) NEXT NEXT move% ENDIF PROCsolve2(phase2cube{}) = FOUND ENDIF REM See if node should be expanded totalcost% = depth% + cost% IF totalcost% <= cube.thresh% THEN FOR move% = 0 TO 5 IF FNallowed(move%, solutionMoves1&(), depth%) THEN twist2% = twist% flip2% = flip% choice2% = choice% solutionMoves1&(depth%) = move% FOR power% = 1 TO 3 solutionPowers1&(depth%) = power% twist2% = twistMoveTable%(twist2%,move%) flip2% = flipMoveTable%(flip2%,move%) choice2% = choiceMoveTable%(choice2%,move%) result% = FNsearch1(cube{}, twist2%, flip2%, choice2%, depth%+1) IF result% THEN = result% NEXT power% ENDIF NEXT move% ELSE REM Maintain minimum cost exceeding threshold IF totalcost% < cube.newthresh% cube.newthresh% = totalcost% ENDIF = FALSE DEF PROCsolve2(cube{}) LOCAL iteration%, result% iteration% = 1 result% = FALSE cube.thresh% = FNphase2cost(FNcornerperm(cube{}), \ \ FNnmseperm(cube{}), FNmseperm(cube{})) REPEAT PROCtitle("Solving phase 2 (" + STR$cube.thresh% + " moves)") cube.newthresh% = 1000 result% = FNsearch2(cube{}, FNcornerperm(cube{}), \ \ FNnmseperm(cube{}), FNmseperm(cube{}), 0) cube.thresh% = cube.newthresh% iteration% += 1 UNTIL result% ENDPROC DEF FNsearch2(cube{}, C%, N%, M%, D%) LOCAL S%, T%, V%, P%, L%, R%, B%, K%, J% S% = FNphase2cost(C%, N%, M%) IF S% = 0 THEN solutionLength2% = D% IF solutionLength2% THEN FOR V% = 0 TO solutionLength2%-1 IF solutionMoves2&(V%)<>2 IF solutionMoves2&(V%)<>3 solutionPowers2&(V%) = 2 NEXT PROCprintsolution(solutionMoves2&(), solutionPowers2&(), solutionLength2%) ENDIF = FOUND ENDIF T% = D% + S% IF T% <= cube.thresh% THEN FOR V% = 0 TO 5 IF FNallowed(V%, solutionMoves2&(), D%) THEN B% = C% K% = N% J% = M% solutionMoves2&(D%) = V% L% = 4 IF V% <> 2 IF V% <> 3 L% = 2 FOR P% = 1 TO L%-1 B% = cornerPermMoveTable%(B%,V%) K% = nmsePermMoveTable%(K%,V%) J% = msePermMoveTable%(J%,V%) solutionPowers2&(D%) = P% R% = FNsearch2(cube{},B%,K%,J%,D%+1) IF R% THEN = R% NEXT ENDIF NEXT ELSE IF T% < cube.newthresh% cube.newthresh% = T% ENDIF = FALSE DEF FNcornerperm(cube{}) = FNpermtoordinal(^cube.cornerCubiePerms&(0), 8) DEF FNnmseperm(cube{}) = FNpermtoordinal(^cube.edgeCubiePerms&(0), 8) DEF FNmseperm(cube{}) = FNpermtoordinal(^cube.edgeCubiePerms&(8), 4) DEF FNpermtoordinal(vector%%, N%) LOCAL I%, ordinal%, limit%, coeff%, temp&, vector&() DIM vector&(11) FOR I% = 0 TO N%-1 : vector&(I%) = vector%%?I% : NEXT FOR limit% = N%-1 TO 1 STEP -1 temp& = 0 FOR I% = 0 TO limit% IF vector&(I%) > temp& temp& = vector&(I%) : coeff% = I% NEXT ordinal% = ordinal%*(limit%+1)+coeff% SWAP vector&(limit%),vector&(coeff%) NEXT limit% =ordinal% DEF PROCapplymove(cube{}, move&) CASE move& OF WHEN 0: REM R PROCfourcyclecorner(cube{}, URF, UBR, DRB, DFR) PROCclockwisetwist(cube{}, URF) PROCcounterclockwisetwist(cube{}, UBR) PROCclockwisetwist(cube{}, DRB) PROCcounterclockwisetwist(cube{}, DFR) PROCfourcycleedge(cube{},UR, BR, DR, RF) PROCflip(cube{},UR):PROCflip(cube{},BR):PROCflip(cube{},DR):PROCflip(cube{},RF) WHEN 1: REM L PROCfourcyclecorner(cube{},ULB, UFL, DLF, DBL) PROCclockwisetwist(cube{}, ULB) PROCcounterclockwisetwist(cube{}, UFL) PROCclockwisetwist(cube{}, DLF) PROCcounterclockwisetwist(cube{}, DBL) PROCfourcycleedge(cube{},UL, FL, DL, LB) PROCflip(cube{},UL):PROCflip(cube{},FL):PROCflip(cube{},DL):PROCflip(cube{},LB) WHEN 2: REM U PROCfourcyclecorner(cube{},ULB, UBR, URF, UFL) PROCfourcycleedge(cube{},UB, UR, UF, UL) WHEN 3: REM D PROCfourcyclecorner(cube{},DLF, DFR, DRB, DBL) PROCfourcycleedge(cube{},DF, DR, DB, DL) WHEN 4: REM F PROCfourcyclecorner(cube{},UFL, URF, DFR, DLF) PROCclockwisetwist(cube{},UFL) PROCcounterclockwisetwist(cube{},URF) PROCclockwisetwist(cube{},DFR) PROCcounterclockwisetwist(cube{},DLF) PROCfourcycleedge(cube{},UF, RF, DF, FL) WHEN 5: REM B PROCfourcyclecorner(cube{},UBR, ULB, DBL, DRB) PROCclockwisetwist(cube{}, UBR) PROCcounterclockwisetwist(cube{}, ULB) PROCclockwisetwist(cube{}, DBL) PROCcounterclockwisetwist(cube{}, DRB) PROCfourcycleedge(cube{},UB, LB, DB, BR) ENDCASE ENDPROC DEF PROCfourcycleedge(cube{}, A%, B%, C%, D%) PROCcyclefour(^cube.edgeCubiePerms&(0), A%, B%, C%, D%) PROCcyclefour(^cube.edgeCubieOrientations&(0), A%, B%, C%, D%) ENDPROC DEF PROCfourcyclecorner(cube{}, A%, B%, C%, D%) PROCcyclefour(^cube.cornerCubiePerms&(0), A%, B%, C%, D%) PROCcyclefour(^cube.cornerCubieOrientations&(0), A%, B%, C%, D%) ENDPROC DEF PROCcyclefour(p%%, A%, B%, C%, D%) SWAP p%%?D%,p%%?C%:SWAP p%%?C%,p%%?B%:SWAP p%%?B%,p%%?A% ENDPROC DEF PROCclockwisetwist(cube{}, C%) cube.cornerCubieOrientations&(C%) = (cube.cornerCubieOrientations&(C%)+1)MOD3 ENDPROC DEF PROCcounterclockwisetwist(cube{}, C%) cube.cornerCubieOrientations&(C%) = (cube.cornerCubieOrientations&(C%)+2)MOD3 ENDPROC DEF PROCflip(cube{}, E%) cube.edgeCubieOrientations&(E%) EOR= 1 ENDPROC DEF FNallowed(M%, solutionmoves&(), D%) LOCAL P% IF D% = 0 THEN = TRUE P% = solutionmoves&(D%-1) IF M% = P% THEN = FALSE IF M% = 4 IF P% = 5 THEN = FALSE IF M% = 0 IF P% = 1 THEN = FALSE IF M% = 2 IF P% = 3 THEN = FALSE IF M% = P% EOR 1 IF D% > 1 IF solutionmoves&(D%-2) = M% THEN = FALSE = TRUE DEF FNtwist(cube{}) LOCAL corner%, twist% FOR corner% = 0 TO 6 twist% = twist%*3 + cube.cornerCubieOrientations&(corner%) NEXT = twist% DEF FNflip(cube{}) LOCAL edge%, flip% FOR edge% = 0 TO 10 flip% = flip%*2 + cube.edgeCubieOrientations&(edge%) NEXT = flip% DEF FNchoice(cube{}) LOCAL I%, edge%, choiceperm%() DIM choiceperm%(3) FOR edge% = 0 TO 11 CASE cube.edgeCubiePerms&(edge%) OF WHEN 8,9,10,11: choiceperm%(I%) = edge% : I% += 1 ENDCASE NEXT = FNchoiceordinal(choiceperm%()) DEF FNchoiceordinal(choiceperm%()) LOCAL edgesremaining%, ordinal%, edge%, edgemarkvector%() DIM edgemarkvector%(11) edgesremaining% = 4 REM Radix sort the edges FOR edge% = 0 TO 3 edgemarkvector%(choiceperm%(edge%)) = 1 NEXT REM Scan the edges and compute the ordinal for this permutation edge% = 0 WHILE edgesremaining% IF edgemarkvector%(edge%) THEN edge% += 1 edgesremaining% -= 1 ELSE REM Skip this many permutations edge% += 1 ordinal% += FNNchooseM(12-edge%, edgesremaining%-1) ENDIF ENDWHILE = ordinal% DEF FNNchooseM(N%, M%) LOCAL novermfact%, mfact%, result% novermfact% = N% mfact% = 1 result% = 1 IF N% < M% THEN = 0 IF M% > N%DIV2 M% = N%-M% : REM Optimization WHILE novermfact% > M% result% *= novermfact% novermfact% -= 1 result% DIV= mfact% mfact% += 1 ENDWHILE = result% DEF FNphase1cost(T%, F%, C%) LOCAL J%, K% J% = FNgetvalue(TwistFlipPrunTable&(), T%*FLIPS + F%) K% = FNgetvalue(TwistChoicePrunTable&(), T%*CHOICES + C%) IF K% > J% J% = K% K% = FNgetvalue(FlipChoicePrunTable&(), F%*CHOICES + C%) IF K% > J% J% = K% = J% DEF FNphase2cost(C%, N%, M%) LOCAL J%, K% J% = FNgetvalue(CornerPrunTable&(), C%*MSEPERMS + M%) K% = FNgetvalue(EdgePrunTable&(), N%*MSEPERMS + M%) IF K% > J% J% = K% = J% DEF FNpermparity(perms%%, numberofcubies%) LOCAL P%,Q%,parity% FOR P% = 0 TO numberofcubies%-2 FOR Q% = P%+1 TO numberofcubies%-1 IF perms%%?P% > perms%%?Q% parity% += 1 NEXT NEXT P% = parity% MOD 2 DEF FNgetvalue(t&(), I%) IF I% AND 1 THEN = t&(I% DIV 2) >>> 4 ELSE = t&(I% DIV 2) AND &F DEF PROCloadtable1(table%(), file$) LOCAL F% F% = OPENIN(file$) IF F% = 0 ERROR 110, "Couldn't open table file " + file$ IF EXT#F% <> 4*(DIM(table%(),1)+1)*(DIM(table%(),2)+1) ERROR 111, "Table file "+file$+" has wrong size" CLOSE #F% *hex 64 OSCLI "LOAD """ + file$ + """ " + STR$~(^table%(0,0)) *hex 32 ENDPROC DEF PROCloadtable2(table&(), file$) LOCAL F% F% = OPENIN(file$) IF F% = 0 ERROR 110, "Couldn't open table file " + file$ IF EXT#F% <> DIM(table&(),1)+1 ERROR 111, "Table file "+file$+" has wrong size" CLOSE #F% *hex 64 OSCLI "LOAD """ + file$ + """ " + STR$~(^table&(0)) *hex 32 ENDPROC DEF PROCprintsolution(moves&(), powers&(), N%) LOCAL I%, lookup&() : DIM lookup&(5) lookup&() = 3,2,0,1,4,5 FOR I% = 0 TO N%-1 CASE powers&(I%) OF WHEN 1: PROCtwist(lookup&(moves&(I%)), 1) WHEN 2: PROCtwist(lookup&(moves&(I%)), 1) : PROCtwist(lookup&(moves&(I%)), 1) WHEN 3: PROCtwist(lookup&(moves&(I%)), -1) ENDCASE WAIT 20 NEXT ENDPROC DEF PROCinstructions VDU 23,22,640;500;8,16,16,8 : VDU 5 *REFRESH OFF OSCLI "DISPLAY """ + @dir$ + "Rubik.bmp"" 0,0,512,512" OSCLI "GSAVE """ + @tmp$ + "Rubik.bmp"" 0,0,512,512" OSCLI "DISPLAY """ + @dir$ + "Rubik.bmp"" -80,-40,1440,1204" GCOL 4,0 RECTANGLE FILL 0,0,1280,1024 GCOL 2,4 RECTANGLE FILL 0,0,1280,1024 GCOL 11 OSCLI "font """ + @lib$ + "FreeSans.ttf"",24" PROCcentre(980, "3D Rubik's Cube simulation") OSCLI "font """ + @lib$ + "FreeSans.ttf"",20" PROCcentre(910, "using Herbert Kociemba's algorithm") GCOL 14 PROCcentre(90, "Press SPACE or click to start") OSCLI "font """ + @lib$ + "FreeSans.ttf"",16" GCOL 10 MOVE 300,820 : PRINT "F1: Scramble cube"; MOVE 670,820 : PRINT "(or click on left)"; MOVE 300,770 : PRINT "F3: Solve cube"; MOVE 670,770 : PRINT "(or click on right)"; MOVE 300,720 : PRINT "F5: Save cube"; MOVE 300,670 : PRINT "F7: Load cube"; MOVE 300,620 : PRINT "1 or G: Twist up (green) face"; MOVE 300,570 : PRINT "2 or B: Twist down (blue) face"; MOVE 300,520 : PRINT "3 or O: Twist left (orange) face"; MOVE 300,470 : PRINT "4 or R: Twist right (red) face"; MOVE 300,420 : PRINT "5 or W: Twist front (white) face"; MOVE 300,370 : PRINT "6 or Y: Twist back (yellow) face"; MOVE 300,320 : PRINT "←: Spin cube left"; MOVE 300,270 : PRINT "→: Spin cube right"; MOVE 670,295 : PRINT "(or drag)"; MOVE 300,220 : PRINT "↑: Tilt cube up"; MOVE 300,170 : PRINT "↓: Tilt cube down"; MOVE 670,195 : PRINT "(or drag)"; *REFRESH ON *REFRESH ENDPROC DEF PROCcentre(Y%, text$) MOVE @vdu%!208 - WIDTH(text$)/2,Y% PRINT text$; ENDPROC DEF PROCtitle(title$) IF BB4W THEN SYS "SetWindowText", @hwnd%, title$ ELSE SYS "SDL_SetWindowTitle", @hwnd%, title$, @memhdc% ENDIF ENDPROC DEF PROCcleanup LOCAL I% Device% += 0 IF Device% THEN FOR I% = 0 TO DIM(Object%(),1) IF Object%(I%) PROC_release(Object%(I%)) NEXT FOR I% = 0 TO DIM(Texture%(),1) IF Texture%(I%) PROC_release(Texture%(I%)) NEXT PROC_release(Device%) Device% = 0 ENDIF *REFRESH ON ENDPROC DEF PROC4(F%,a) : LOCAL A% : A%=FN_f4(a) : BPUT #F%,A% : BPUT #F%,A%>>8 : BPUT#F%,A%>>16 : BPUT#F%,A%>>24 : ENDPROC DEF FNatan2(y,x) : ON ERROR LOCAL = SGN(y)*PI/2 IF x>0 THEN = ATN(y/x) ELSE IF y>0 THEN = ATN(y/x)+PI ELSE = ATN(y/x)-PI REM!Embed @lib$+"ogllib", @lib$+"webgllib", @lib$+"FreeSans.ttf", @dir$+"Rubik.bmp" REM!Embed @dir$+".Tables/Choice.mtb", @dir$+".Tables/CrnrPerm.mtb", @dir$+".Tables/CrnrSlic.ptb" REM!Embed @dir$+".Tables/EdgePerm.mtb", @dir$+".Tables/EdgeSlic.ptb", @dir$+".Tables/Flip.mtb" REM!Embed @dir$+".Tables/FlipChce.ptb", @dir$+".Tables/SlicPerm.mtb", @dir$+".Tables/Twist.mtb" REM!Embed @dir$+".Tables/TwstChce.ptb", @dir$+".Tables/TwstFlip.ptb"