Meteor Contest - Part 7 Visualisation

Until there, we played with low level bit tricks, and have used the official ASCII board printing, but these bits are frustrating, we are in Smalltalk, a graphical environment. So we are going to illustrate the algorithm with a poor man Morph in Squeak. I say poor man because the morph will be dedicated to visualisation, not interaction, but that will already serve.

First, we craft a morph just for displaying an hexagonal cell. We hardcode the edge length as an integer between 10 and 20 pixels, that fall near a whole pixel when multiplied by 60 degreeSin and 60 degreeCos: that is an even integer, and we catch it with a centered modulo in interval [-1/2,1/2[

(10 to: 20 by: 2) detectMin: [:n | (n * 3 sqrt + 1 / 2 \\ 1 - (1 / 2)) abs]

->14

Supposing the centre of the polygon is in the middle of pixel 0@0, the vertices would thus be:

(30 to: 330 by: 60) collect: [:a | ((a degreeCos@a degreeSin)*14) rounded].
-> {12@7 . 0@14 . -12@7 . -12@ -7 . 0@ -14 . 12@ -7}

We thus create:

Morph subclass: #ShootoutMeteorHexaMorph
    instanceVariableNames: 'fillColor'
    classVariableNames: ''
    poolDictionaries: ''
    category: 'Shootout'

initialize

    super initialize.
    bounds := 0@0 extent: 25@29.
    fillColor := Color transparent.

bounds: newBounds
    bounds := (-12 @ -14 extent: 25@29) translateBy: newBounds center rounded.

fillColor
    ^fillColor

fillColor: aColor
    fillColor := aColor.
    self changed

vertices
    ^{ 12 @ 7. 0 @ 14. -12 @ 7. -12 @ -7. 0 @ -14. 12 @ -7 }

drawOn: aCanvas
    aCanvas
        drawPolygon: (self vertices collect: [:e | e + self bounds center])
        fillStyle: self fillColor
        borderWidth: 1
        borderColor: Color black

And test if magnified drawing is OK:

hexa := ShootoutMeteorHexaMorph new.
aFormCanvas := FormCanvas extent: hexa extent depth: 32.
aFormCanvas fillRectangle: (0@0 extent: hexa extent) fillStyle: Color lightGray.
hexa drawOn: aFormCanvas.
aFormCanvas := FormCanvas on: (aFormCanvas form magnifyBy: 16).
w := hexa bounds width.
h := hexa bounds height.
c := w@h*8.
aFormCanvas fillRectangle: (c-6 corner: c+6) fillStyle: Color green.
vertices := (30 to: 330 by: 60) collect: [:a | ((a degreeCos@a degreeSin)*14*16+c) rounded].
vertices do: [:p | aFormCanvas fillRectangle: (p-5 corner: p+5) fillStyle: Color blue].
vertices do: [:p | aFormCanvas line: c to: p width: 2 color: Color yellow].
aFormCanvas drawPolygon: vertices color: Color transparent borderWidth: 2 borderColor: Color green.
0 to: w-1 do: [:x | aFormCanvas line: x@0*16 to: x@h*16 width: 1 color: Color veryLightGray].
0 to: h-1 do: [:y | aFormCanvas line: 0@y*16 to: w@y*16 width: 1 color: Color veryLightGray].
aFormCanvas line: w@0*16-1 to: w@h*16-1 width: 1 color: Color veryLightGray.
aFormCanvas line: 0@h*16-1 to: w@h*16-1 width: 1 color: Color veryLightGray.
aFormCanvas form asMorph openInWorld.

The line drawing is not very accurate, and don't have anti-alisasing when we draw on a Form, but that will do.

Then we create a board of 50 cells.

 Morph subclass: #ShootoutMeteorBoardMorph
    instanceVariableNames: ''
    classVariableNames: ''
    poolDictionaries: ''
    category: 'Shootout'

initialize
    | cells center hexa x y |

    super initialize.
    cells := Array new: 50.
    x := #(0 2 4 6 8 1 3 5 7 9).
    y := (0 to: 9).
    0 to: 49 do: [:i|
        center := ((x at: 10 - (i \\ 10))*12+12) @ ((y at: 10 - (i // 5))*21+14).
        hexa := ShootoutMeteorHexaMorph new.
        hexa bounds: (center - (12@14) corner: center + (12@14)).
        cells at: i + 1 put: hexa].
    submorphs := cells.
    bounds := cells inject: cells first bounds into: [:b :h | b merge: h bounds]

drawOn: aCanvas

We can test it:

ShootoutMeteorBoardMorph new openInWorld.

Or if we want to create a form that will later be exported as png and feed this blog:.

board := ShootoutMeteorBoardMorph new.
board position: 0@0.
aFormCanvas := FormCanvas extent: board extent depth: 32.
aFormCanvas fillRectangle: (0@0 extent: board extent) fillStyle: Color veryLightGray.
board fullDrawOn: aFormCanvas.
aFormCanvas form asMorph openInWorld.

At this time, we don't reify the piece, we just add a hook to fill a bit mask with pre-defined colours (with an eleventh one useful to mark islands for example).

ShootoutMeteorBoardMorph>>rgbColorSpecs
    ^#(
        #(1.0  0.2  0.2)
        #(0.0  1.0  0.0)
        #(0.2  0.2  1.0)
        #(1.0  1.0  0.0)
        #(0.0  1.0  1.0)
        #(0.8  0.2  0.8)
        #(1.0  0.6  0.1)
        #(0.6  0.1  0.1)
        #(0.1  0.6  0.1)
        #(0.1  0.1  0.6)
        #(0.2  0.2  0.2)
    )

fillPiece: aPiece forRow: row withColor: hColor
    | offset |
    row >= 6
        ifTrue:
            [offset := submorphs size + 1 - (row - 6 * 5).
            aPiece mask bitsDo: [:k | (submorphs at: offset - k) fillColor: hColor]]
        ifFalse:
            [offset := row * 5.
            aPiece mask bitsDo: [:k | (submorphs at: offset + k) fillColor: hColor]].
    self changed.

addPiece: aPiece index: pieceIndex forRow: row

    | rgb hColor |
    rgb := self rgbColorSpecs at: pieceIndex.
    hColor := Color r: rgb first g: rgb second b: rgb third.
    self fillPiece: aPiece forRow: row withColor: hColor

removePiece: aPiece index: pieceIndex forRow: row
    self fillPiece: aPiece forRow: row withColor: Color transparent

We can now instrument our solver to display its own progress. Of course, since last number of loops was more than 800,000 that means that visualizing the whole algorithm would require more than 80,000 seconds even if we display 10 pieces additions per second. But we will stop the animation before the end.

First, we add two empty hooks

ShootoutMeteorBoard>>addPiece: aPiece index: pieceNumber forRow: iRow

ShootoutMeteorBoard>>removePiece: aPiece index: pieceNumber forRow: iRow

And modify inner loop of the solving method

searchPuzzlesWithColorMask: colorMask boardMask: bMask rowOffset: rowOff pieces: pArray ifFound: solutionBlock

    ...snip...

                    ((aPiece := positions at: i) fitOnBoard: boardMask)
                        ifTrue:
                            [pieces at: pieceNumber put: (aPiece forRow: iRow).
                            self addPiece: aPiece index: pieceNumber forRow: iRow.
                            self searchPuzzlesWithColorMask: colorMask - colorBit boardMask: boardMask + aPiece mask rowOffset: iRow pieces: pArray ifFound: solutionBlock.
                            self removePiece: aPiece index: pieceNumber forRow: iRow]]].

    ...snip...

Then we define a subclass

ShootoutMeteorBoard subclass: #ShootoutMeteorInstrumentedBoard
    instanceVariableNames: 'boardMorph'
    classVariableNames: ''
    poolDictionaries: ''
    category: 'Shootout'

initializeMorph
    boardMorph := ShootoutMeteorBoardMorph new.
    boardMorph position: Display boundingBox center.
    boardMorph openInWorld.

fromString: boardString
    super fromString: boardString.
    self initializeMorph

solvedPuzzleDo: solutionBlock
    ^[super solvedPuzzleDo: [:aSolution |
            boardMorph flash.
            (Delay forSeconds: 1) wait.
            solutionBlock value: aSolution]]
        ensure: [boardMorph delete]

addPiece: aPiece index: pieceNumber forRow: iRow
    boardMorph addPiece: aPiece index: pieceNumber forRow: iRow.
    boardMorph displayWorld.
    (Delay forMilliseconds: 200) wait.

removePiece: aPiece index: pieceNumber forRow: iRow
    (Delay forMilliseconds: 200) wait.
    boardMorph removePiece: aPiece index: pieceNumber forRow: iRow.
    boardMorph displayWorld.

And get it to work:

ShootoutMeteorInstrumentedBoard solveDefault.

Here is the first solution found:

This animation clearly confirms that we do not eliminate every island. For example after this case:

 

 3 more trials are necessary before abandoning the solution:

And the second confirmation is that our idea to turn the board above 6th row was very clever for minimizing the possible positions set-up , but not at all optimal for abandoning bad solutions early, because some islands are rejected in upper rows once we rotate the board, as illustrated on this snapshot:

So there is room for further improvements, and in next post I'll be back to a more dumb solution. Also, I created this little movie with the first minutes of solving by simply generating the PNG with instrumented code (and an iFrame instance variable initialized to 0),

ShootoutMeteorInstrumentedBoard>>addPiece: aPiece index: pieceNumber forRow: iRow
    boardMorph addPiece: aPiece index: pieceNumber forRow: iRow.
    boardMorph world displayWorld.
    iFrame := iFrame + 1.
    boardMorph exportAsPNGNamed: 'meteor_' , (iFrame printPaddedWith: $0 to: 5) , '.png'.

 removePiece: aPiece index: pieceNumber forRow: iRow
    boardMorph removePiece: aPiece index: pieceNumber forRow: iRow.
    boardMorph world displayWorld.
    iFrame := iFrame + 1.
    boardMorph exportAsPNGNamed: 'meteor_' , (iFrame printPaddedWith: $0 to: 5) , '.png'.

and then aggregating the PNG with iMovie (the interactive part clearly does not scale, I should better have installed ffmpeg):

This stuff is in http://ss3.gemstone.com/ss/Shootout/Shootout.blog-nice.8.mcz