N-Puzzle game with React
Bài đăng này đã không được cập nhật trong 4 năm
1. Giới thiệu
Bài toán n-puzzle, hay với các tên gọi khác như "Gem puzzle", "Mystic Square" nằm trong nhóm các bài toán puzzle (xếp hình, đẩy hộp đại loại). Trò chơi này gồm một bảng có n - 1 ô vuông (phổ biến n = 8, 15, 24, ...) tức là sẽ có một ô trống trong bảng. Các ô liền kề có để di chuyển đến ô trống này.
Từ một trạng thái bất kì, người chơi cần di chuyển các ô của bảng về một trạng thái đích nào đó với số lần di chuyển càng ít càng tốt.
Về thuật toán giản bài toán này, có khá là nhiều cách:
- Breadth-first Search (BFS)
- Depth-first Search (DFS)
- Iterative Deepening DFS (ID-DFS)
- Greedy Search
- A* Search
Nếu sử dụng Greedy Search hoặc A* Search để giải bài toán này chúng ta cần phải sử dụng thêm 3 hàm heuristic:
- Euclidean distance heuristic
- Manhattan distance heuristic
- Tiles-out heuristic
Heuristic: Là phương pháp tiếp cận bằng cảm tính, mang tính kinh nghiệm, dùng trong phương pháp "thử và sai" để giải quyết tương đối các bài toán khó. (đối lập phương pháp tiếp cận bằng thuật toán - algorithmic).
Tuy nhiên trong bài viết này, mình sẽ chỉ đề cập tới việc xây dựng game này 1 cách đơn giản bằng React 
2. Coding....
Ý tưởng của mình khá là đơn giản, tất cả những gì cần xây dựng gồm:
- Cell: các
ôhiển thị số (các bạn có thể sử dụng ảnh và cắt nó ra bằngcanvas) - Board: là bảng chứa các
Cell - Timer: hiển thị các thông tin về thời gian và số lần di chuyển
- Buttons: là các nút bấm để thay đổi kích thước của
Board - Puzzle: chứa tất cả những
componentstrên vàstate
2.1. Puzzle
Cấu trúc code cũng khá đơn giản:
- 1
headerđể thông báo đãsolvedxong hay chưa - 1
boardchứa các mảnh ghép - 1
footerchứa các thông tin về thời gian và cácbuttonsđể thay đổi kích thước củaborad
class Puzzle extends React.Component {
// ...
render() {
const { board, size, move, start, done } = this.state;
return (
<div className='puzzle'>
<div className="puzzle-header">
{done ? <h3>You won!</h3> : ''}
</div>
<div className="puzzle-body">
{board ?
<Board
size={size}
board={board}
updateBoard={this.updateBoard}
/>
: null
}
</div>
<Footer
move={move}
start={start}
done={done}
newGame={this.newGame}
/>
</div>
);
}
}
export default Puzzle;
2.2. Board
Các logic về xử lý hầu hết được đặt trong đây:
- Kiểm tra xem mảnh ghép nào có thể di chuyển, và hướng di chuyển của nó
- Xử lý sự kiện khi click vào các mảnh ghép
- Xử lý sự kiện của bàn phím -
keydown(các phím mũi tên: lên, xuống, trái, phải)
import React from 'react';
import Cell from '../Cell';
class Board extends React.Component {
// .....
render() {
const { board, size } = this.props;
let squares = [];
// Handle size of board
let docWidth = document.body.clientWidth,
docHeight = document.body.clientHeight;
const maxWidth = parseInt(docWidth / size) - 10,
maxHeight = parseInt((docHeight - 200) / size),
unit = maxHeight > maxWidth ? maxWidth : maxHeight;
// Generate board with cells
this.props.board.map((val, index) => {
squares.push(
<Cell
key={index}
value={val}
size={size}
clickHandler={this.cellClickHandler}
right={index+1 === val}
unit={unit}
/>
);
if ((index + 1) % size === 0) {
squares.push(<br key={`br_${index}`} />)
}
});
return (
<div className='board'>
{squares}
</div>
);
}
}
export default Board;
2.3. Cell, Footer & Timer
Cell nhận giá trị được truyền vào từ Board và hiển thị
// Cell/index.js
import React from 'react';
const Cell = (value, clickHandler) => <span onClick={clickHandler}>{value}<span>;
export default Cell;
Nếu các bạn sử dụng ảnh và canvas thì thay thẻ span bằng thẻ image với src là canvas được cắt từ ảnh
Footer
Footer của mình chứa các nút để thay đổi kích thước của board và 1 timer để tính giờ
import React from 'react';
import Timer from './Timer';
import './footer.scss';
const Footer = (move, newGame, start, done) => {
return (
<div className="puzzle-footer">
<div className="move">
<span>Move: {move}</span>
<Timer start={start} done={done} />
</div>
<span className="button" onClick={() => newGame(3)}>3x3</span>
<span className="button" onClick={() => newGame(4)}>4x4</span>
<span className="button" onClick={() => newGame(5)}>5x5</span>
<span className="button" onClick={() => newGame(6)}>6x6</span>
<span className="button" onClick={() => newGame(7)}>7x7</span>
<span className="button" onClick={() => newGame(8)}>8x8</span>
<span className="button" onClick={() => newGame(9)}>9x9</span>
<span className="button" onClick={() => newGame(10)}>10x10</span>
</div>
);
}
export default Footer;
Timer
Tạo 1 timer khá là đơn giản, chúng ta sẽ bắt đầu chạy nó khi game được tạo mới, dừng lại khi hoàn thành và reset khi thay đổi kích thước board hoặc bắt đầu game mới.
3. Mở rộng
Code mình đã đẩy lên github tại địa chỉ: https://github.com/doanhpv-0200/n-puzzle (Note: code của mình code từ khá lâu rồi, nên khi chạy sẽ gặp 1 số warning nhé :3) Các bạn có thể chơi thử tại đây: https://doanhpv-0200.github.io/n-puzzle/
Như đã nói ở trên, việc sử dụng số khá là đơn giản và nhàm chán.
Chúng ta có thể sử dụng các hình ảnh bất kì mà người dùng có thể upload lên, cắt nó ra và shuffle các mảnh ghép.
Các bạn có thể tham khảo ở đây: hình của đấng được cắt làm 9 mảnh và trộn lên
All rights reserved
