[HTML5/Javascript] 직소퍼즐 만들기 3: 퍼즐 조각 무작위로 섞기

dog-foooot.tistory.com/21

[HTML5/JavaScript] 직소퍼즐 만들기 - 2: 드래그드롭으로 퍼즐넣기

안녕하세요, 김선진입니다.

저번 시리즈에 이어 이번에는 아래 3가지 기능을 퍼즐에 추가해봅시다.

 

1. 퍼즐 조각을 랜덤하게 셔플

2. 퍼즐 다시 시작

 

기존 코드에 이어서 작업합니다.

 

1. Suffle 알고리즘

1-1. O(N log N)

간단하게 접근해보면 각각의 퍼즐 조각에 난수를 할당하고 난수를 기준으로 정렬하는 방법이 있을 수 있다.

하지만 이 방법은 정렬이 1번 들어가기 때문에 최소 정렬 알고리즘의 시간복잡도를 갖게 된다.

심지어 위 방법으로 구현하면 셔플 빈도가 쏠리는 현상이 나타나게 된다.

빈도 결과표 출처 https://ko.javascript.info/task/shuffle

1-2. O(N)

정렬 없이 구현하려면 어떻게 해야 할까? 피셔 예이츠는 연필과 종이를 이용하여 동등한 확률을 가진 랜덤 알고리즘을 만들었고, 크누스는 그 알고리즘에서 불필요한 고정 부분을 제외한 현대판 알고리즘을 정의했다.

구현은 아주 쉽다. 퍼즐 조각 리스트를 뒤에서부터 1바퀴 돌면서 현재 위치를 무작위로 생성된 index번째의 위치와 swap하면 된다. 그럼 마지막 퍼즐 조각까지 끝났을 때 무작위로 퍼즐 리스트가 섞여 있을 것이다.

sudo 코드는 아래와 같다.

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

 

피셔 예이츠 셔플 순서도 출처 https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Fisher_and_Yates'_original_method

 

 

2. Suffle 적용

2-1. Suffle 코드 작성

function suffleList(array) {
  for (let i = array.length - 1; i > 0; i -= 1) {
    let j = Math.floor(Math.random() * (i + 1));
    [array[i], array[j]] = [array[j], array[i]];
  }
}
function suffleRendering() {
const box = document.getElementById('puzzle-box');
suffleList(imagePieces);
imagePieces.forEach(img => {
	box.appendChild(img);
	});
}

2-2. 퍼즐 게임 시작 시 suffleList 호출

셔플되지 않은 퍼즐조각

셔플된 퍼즐조각

 

3. 퍼즐 다시 시작

3-1. 셔플 기능을 등록한 버튼 생성

<button onclick="suffleRendering()">다시시작</button>

 

4. 전체 js 코드

전체 변경된 코드는 길어서 접었다.

const numColsToCut = 4;
const numRowsToCut = 4;
const imagePieces = [];

function suffleList(array) {
  for (let i = array.length - 1; i > 0; i -= 1) {
    let j = Math.floor(Math.random() * (i + 1));
    [array[i], array[j]] = [array[j], array[i]];
  }
}
function suffleRendering() {
const box = document.getElementById('puzzle-box');
suffleList(imagePieces);
imagePieces.forEach(img => {
   box.appendChild(img);
   });
}
function allowDrop(ev) {
  ev.preventDefault();
}

function drag(ev) {
  ev.dataTransfer.setData("text", ev.target.id);
}

function drop(ev) {
  ev.preventDefault();
  var data = ev.dataTransfer.getData("text");
  if (!data) return;
  if (ev.target.nodeName !== 'TD') {
    console.log(ev.target.parentNode);
    const currentImage = ev.target;
    const td = ev.target.parentNode;
    td.removeChild(currentImage);
    td.appendChild(document.getElementById(data))
    const box = document.getElementById('puzzle-box');
    box.appendChild(currentImage);
    return;
  }
  ev.target.appendChild(document.getElementById(data));
}

function updateImageDisplay() {
  const preview = document.querySelector('.preview');
  const input = document.querySelector('input');
  const board = document.getElementById('puzzle-board');

  while(preview.firstChild) {
    preview.removeChild(preview.firstChild);
  }
  const curFiles = input.files;
    for(const file of curFiles) {
         const para = document.createElement('p');
         const imageItem = document.createElement('div');
           const img = new Image();
           img.onload = function() {
             const widthOfOnePiece = this.width/numColsToCut;
             const heightOfOnePiece = this.height/numRowsToCut;
             para.innerHTML = `${numColsToCut}X${numRowsToCut}로 생성된 퍼즐입니다.`;

              while(board.firstChild) {
                board.removeChild(board.firstChild);
              }
                 for(var x = 0; x < numColsToCut; ++x) {
                    let tableRow = document.createElement('tr');
                     for(var y = 0; y < numRowsToCut; ++y) {
                         var canvas = document.createElement('canvas');
                         canvas.width = widthOfOnePiece;
                         canvas.height = heightOfOnePiece;
                         var context = canvas.getContext('2d');
                         context.drawImage(img, y * widthOfOnePiece, x * heightOfOnePiece, widthOfOnePiece, heightOfOnePiece, 0, 0, canvas.width, canvas.height);
                         let pieceImage = new Image();
                         pieceImage.src = canvas.toDataURL();
                         pieceImage.id = canvas.toDataURL();
                         pieceImage.draggable = true;
                         pieceImage.ondragstart = drag;
                         let tableData = document.createElement('td');
                         tableData.ondrop = drop;
                         tableData.ondragover = allowDrop;
                         tableData.width = widthOfOnePiece;
                         tableData.height = heightOfOnePiece;
                         tableRow.appendChild(tableData);
                         imagePieces.push(pieceImage);
                     }
                     board.appendChild(tableRow);
                 }
   suffleRendering();
   }   
           img.src = URL.createObjectURL(file);

           imageItem.appendChild(img);
           imageItem.appendChild(para);
           preview.appendChild(imageItem);
     }
}

5. References

https://ko.javascript.info/task/shuffle

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Fisher_and_Yates'_original_method

 

다음 포스트에서는 퍼즐을 게임으로 만들고 퍼즐 시리즈를 마치도록 하겠습니다.

오랜만에 아주 열심히 블로그를 썼습니다^^... (자극 받아서)

그럼 이만~.