Programming Rubik's Cube

1. Overview.

Developed using MS Visual Studio 2003.

2. Cube.

2.1. Compilation.

To build cube you need:

MS VS 2003 + Eiffel Envision 2.0 Beta 1
DirectX 9.0
NUnit 2.1

If you don't use latest DirectX SDK, to make Managed DirectX available to VS you can add key like this one to the registry:

[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\.NETFramework\AssemblyFolders\DirectX]
@="F:\\WINDOWS\\Microsoft.NET\\Managed DirectX"

Then copy your dll files (like Microsoft.DirectX.DirectSound.dll) to this directory.

I use custom precompile library which includes only EiffelBase to reduce binary distribution size. You can also make this precompile for yourself or you can use standard precompile (Compiler\eBCL\v1.1.4322\release\precomp.epr). In both cases you should change my local Precompiled library path to match your system.

Also replace in Assembly References cube recources and cube solver to your local files, nunit.framework v2.1.4.0 and Microsoft.DirectX v1.0.900.0 files to your GAC references.

Change root Cluster path in Project - Properties to where you place this sources.

ISE.Runtime.dll lives in the GAC on developer machine, but it's not a standard component and you should distribute it to user.

2.2. Eiffel Envision.

Main limitation of current Envision version is a lack of custom expanded classes support, so I had to imitate it redefining is_equal and copy. In some cases, I redefine is_equal and copy even when they do exactly the same as standard ones - it's for performance, standard "reflection" operations in ANY is slow and memory hungry.

2.3. Demo loop.

Program has separate thread to scramble/unscramble the cube in a loop:

celebrate
feature {THREAD}.sleep_integer(3000)
shuffle
feature {THREAD}.sleep_integer(2000)
solve

When user presses s, this thread terminates.

2.4. 3D.

3D part uses Managed Direct3D from DirectX 9.

I made brick shape brick.x using MetasequoiaLE R2.1 by O.Mizno. I don't use lighting, cell colors are displayed using ambient material property.

Application performance depends on window size. So, if you encounter low frame rate, try to reduce it.

See also this picture that describes used geometry conventions.

Antialiasing highly recommended for this app. But it defined mostly by video drivers than by app commands. So, I don't play with it in the app and recommend you to turn AA to maximum in global video card settings.

Fullscreen mode used is an exclusive mode, not just a big window without title and border. It allows to work on video cards which don't support window mode and should give better performance. Exclusive fullscreen mode also means that we can't use any 2D Windows GUI (particularly dialogs). So, before showing About dialog, cube IO dialogs or error dialogs I switch to window mode.

2.5. Multithreading.

Program uses separate (worker) thread to run demo loop (using .NET Framework facilities). As all painting in .NET should be done from UI thread, update function in VIEW class (which could be called from any thread) delegates render to UI thread via Invoke mechanism. If update function called simultaneously from 2 threads, Framework will synchronise access, i.e. second thread will wait until first finished.

Worker thread should have lower priority then UI thread to make UI responsive, so it has BelowNormal priority.

When worker thread terminates (on s command or when application is closing) it needs some time to finish current (move) step. To respond on worker thread update requests, UI thread calls do_events while waiting for worker thread to terminate.

2.6. Error handling.

Robustness doesn't have mush sense for demo application like this one. Most probable source of problems is a missed assemblies and files, that this app depends on. Global exceptions handlers in worker and UI threads should give these missed names to a user.

2.7. Performance tracking.

Rendering cube, application updates three Rubik's Cube performance counters. But only if they were installed (using cube performance counter).

Current counter value is calculated from internal buffer which stores 100 last frames. So Max FPS is the maximal fps for the last 100 frames, Min FPS is minimal and Avg FPS is arithmetical sum of 100 last fps divided by 100.

Time between consecutive renderings might be quite big (when demo loop is paused or when demo loop is stopped and user rotates cube using keyboard). So, only if this delay is less than 100 ms, it is used to calculate frame rate.

If computer is fast enough, Avg FPS will be equal to monitor vertical refresh rate.

2.8. Solver.

Principles of cube solver are described in Cube solver section. One distinctive feature of the used solver is that derived solution contains many superfluous moves. Typical solution consists of 250 - 350 moves. Removing obvious duplication (as [+ u, - u]) reduces solution size to 125 - 175 moves. It's all in cube_solver.e.

Solver uses cube solver that depends on amzi.dll. When amzi.dll is missed I'd like to inform user about it. Unfortunately, standard exceptions says "cube solver or one of its components is missed". So, I need to replace it with "cube solver.dll or amzi.dll is missed". load_rubik_solver_dll loads cube solver.dll explicitly and replace error message. call_solver inhibit find_solution from premature implicit loading of cube solver.dll (dependent assembly is automatically loaded just before call to function that references types from that assembly).

2.9. HIGH_RESOLUTION_TIMER.

"Standard" Windows timers have resolution 10 ms or worse. For app running at 100 fps or higher it's not enough. QueryPerformanceCounter function from Win32 API allows resolution better than 1 micro-second, but this class rounds it to 1 ms for client convenience.

2.10. NUnit.

Program has lots of units tests in cube.exe. Performance tests run only for release build, they might fail on your machine.

You should place rubik.xpl and amzi.dll to cube.exe directory to be found when executing tests from NUnit GUI.

3. Cube solver engine.

It's a Prolog program "A Rubik's Cube Solver" written by Dennis Merritt in 1994. Using Amzi! Prolog + Logic Server we can access Prolog programs from C++ (and other languages, see www.amzi.com).

To be able to send cube position from external program to "A Rubik's Cube Solver", I added 2 lines to rubik.mov:

initial(external):-
  external_cube_init, !.

And then in Cube solver I execute:

wininit,
solve(external),

Implementation of external_cube_init is described in Cube solver section.

To build rubik.xpl you should "Open Project" rubik.ppj in Amzi! Development Environment (ignoring warning boxes) and click "BLD" button in toolbar.

4. Cube solver.

It's a Managed C++ library, offering .NET interface to Cube solver engine. Class RubikSolver exports static solve function which gets ArrayList of 54 integers (representing cube position) as a parameter and returns ArrayList of strings (representing moves to solve given cube). In case of failure, it throws ApplicationException.

Input data for solve function.

Each integer on unfolded cube represents color of one cell. Color value should be from 0 to 5.

For example: 0 - red, 1 - green, 2 - blue, 3 - yellow, 4 - pink, 5 - white.
You can use any color scheme you like, but preserve colors relation - I think it's important for solver. I.e. when your cube is in original (pristine) state, colors with value 2 should be on top, 5 - on bottom, etc.

Solve function results.

Each string contains 1 or more moves. Total number of strings might be from 30 to 50. To decipher moves signatures you could look in rubmov.pro from Cube solver engine and in cube_solver.e from Cube.

This library is based on "C++ Win32 Multi-Threaded Rubik Cube Sample" from Amzi! Prolog + Logic Server. Solution strings are accumulated via disp_hist function, called from Prolog. Initial scrumbled cube position goes to Prolog via cube_init function, which executes:

retractall(state(_)),
assert(state(cube('F','R','U', ...))),
new_colors(cube('F','R','U', ...)),

Call to new_colors is important, as it allows to scramble cube rotating not only "edge" sides, but also the "central" sides.

Compilation of this library gives a linker warning about existent entry point, but it's OK to ignore it (well, I hope so) - fixing it is not very easy.

I use /d1PrivateNativeTypes compiler switch to hide C++ standard library names from Envision, otherwise I wouldn't be able to reference this library in cube.

5. Cube resources.

This assembly contains mesh brick.x and icon cube.ico for main program. Storing such files in one dll is more clear and safe. Unfortunately, I can't put rubik.xpl here - it must be accessible via standard windows file functions.

6. Cube performance counter.

Creation and removal of performance counters are privileged operations. They require Administrator rights (from a role based security POV) and Full trust (from code access security POV). Thus this separate executable. "This is done so that the privileged code can be configured separately from the rest of the application and granted the necessary additional permissions."