06. Sinh bàn cờ và điều khiểu touch

Trong nước này, ta cần implement 2 chức năng là sinh bàn cờ ngẫu nhiên và điều khiển touch để sắp xếp bàn cờ.

Bước 1: Kiểm tra bàn cờ có thể "giải" được hay không.

Với trò chơi n-puzzle, không phải cách sắp xếp ngẫu nhiên nào cũng có lời giải. Bàn cờ là một hình vương nxn, nhưng nếu trãi ra dưới dạng một chiều, bàn cờ có dạng sau:

Sau khi giải thành công, ta có 1 dãy số tăng dần từ 1 đến SxS-1 (S = size). Khi có sự xáo trộn, gọi N là tổng "lỗi", trong đó N[i] là số phần tử nhỏ hơn phần tử thứ i nằm về phía bên phải (mãng 1 chiều)

Ví dụ:

N[0] = 4 (5 lớn hơn 4, 3, 1, 2)

N[1] = 0 (ô trống, không tính)

N[2] = 3 (4 lớn hơn 3, 2, 1)

N[3] = 2 (3 lớn hơn 1, 2)

N[4] = 0

N[5] = 1

N[6] = 1

N[7] = 1

N = 12

• Nếu n chẵn (8-puzzle (3x3), 24 puzzle (5x4)), bài toán có lời giải nếu N chẵn
• Nếu n lẽ (15-puzzle (4x4)), bài toán có lời giải khi
  • N chẵn và ô trống nằm ở dòng chẵn (dòng đếm từ 1, từ trên xuống)
  • N lẽ và ô trống nằm ở dòng lẽ (dòng đếm từ 1, từ trên xuống)

#define BLANK_CELL (m_iSizeSquare - 1)

#define IS_ODD(a) (((a)&1) == 1)

#define IS_EVEN(a) (((a)&1) == 0)

bool CBoard::IsSolubility()

{

    int N = 0;

    int blankRow = m_iSize - 1;

    for (int i = 0 ; i < m_iSizeSquare - 1; i++)

    {

        if (m_pBoardData[i] == BLANK_CELL)

        {

            blankRow = (i / m_iSize) + 1;

        }

        else

        {

            for (int j = i + 1 ; j < m_iSizeSquare; j++)

            {

                if (m_pBoardData[i] > m_pBoardData[j])

                {

                    N++;

                }

            }

        }

    }

    if (IS_ODD(m_iSize))

    {

        return (IS_EVEN(N));

    }

    else

    {

        return ( (IS_EVEN(N) && IS_EVEN(blankRow)) || (IS_ODD(N) && IS_ODD(blankRow)) );

    }

}

Bước 2: Sinh ngẫu nhiên bàn cờ

Cách 1:

Bàn cờ được xáo trộn với qui tắt như sau:

• Tiến hành xáo trộn bàn cờ K lần (K tùy ý), trong mỗi lần. chọn 2 quân cờ bất kỳ trên bàn, đổi vị trí

int r1, r2 = 0;

CRandom* random = new CRandom();

bool success = false;

for (int i = 0; i < m_iSizeSquare; i++)

{

    r1 = random->NextInt(m_iSizeSquare);

    r2 = random->NextInt(m_iSizeSquare);

    __INT32 tmp = m_pBoardData[r1];

    m_pBoardData[r1] =  m_pBoardData[r2];

    m_pBoardData[r2] =  tmp;

}

• Tiếp tục xáo từng cặp quân cờ cho đến khi thỏa điều kiện bàn cờ có thể giải được:

while (!IsSolubility())

{

    r1 = random->NextInt(m_iSizeSquare);

    r2 = random->NextInt(m_iSizeSquare);

    __INT32 tmp = m_pBoardData[r1];

    m_pBoardData[r1] =  m_pBoardData[r2];

    m_pBoardData[r2] =  tmp;

}

Lưu ý cần kiểm tra xem CRandom đã được include để sử dụng hay chưa. Nếu chưa, include CRandom.h trong file gametutor.h (thiếu sót ở những phần trước)

void CBoard::Shuffle()

{

int r1, r2 = 0;

CRandom* random = new CRandom();

bool success = false;

for (int i = 0; i < m_iSizeSquare; i++)

{

r1 = random->NextInt(m_iSizeSquare);

r2 = random->NextInt(m_iSizeSquare);

__INT32 tmp = m_pBoardData[r1];

m_pBoardData[r1] = m_pBoardData[r2];

m_pBoardData[r2] = tmp;

}

while (!IsSolubility())

{

r1 = random->NextInt(m_iSizeSquare);

r2 = random->NextInt(m_iSizeSquare);

__INT32 tmp = m_pBoardData[r1];

m_pBoardData[r1] = m_pBoardData[r2];

m_pBoardData[r2] = tmp;

}

SAFE_DEL(random);

}

Cách sinh bàn cờ này đòi hỏi thời gian kiểm tra, nhưng đảm bảo sự ngẫu nhiên một cách tối đa nhưng có nguy cớ xãy ra số vòng lặp quá lớn.

Cách 2:

Một cách tiếp cận sinh ngẫu nhiên khác đơn giản hơn, không cần kiểm tra tính đúng đắn của bàn cờ nhằm giảm nguy cơ vòng lặp quá lớn. tuy nhiên, sẽ giảm bớt tính ngẫu nhiên và bàn cờ sinh ra có thể không thật sử "xáo trộn".

• Từ bàn cờ đúng ban đầu
• Tìm ô trống
• Di chuyển ngẫu nhiên ô trống sang ô lân cận. Thực hiện bước này K lần tùy ý:

void CBoard::Shuffle2()

{

    int blank = 0;

    CRandom* random = new CRandom();

    for (int i = 0; i < m_iSizeSquare; i++)

    {

        if (m_pBoardData[i] == BLANK_CELL)

        {

            blank = i;

            break;

        }

    }

    int blankRow = blank / m_iSize;

    int blankCol = blank % m_iSize;

    int DirRow[] = {1, 0, -1, 0};

    int DirCol[] = {0, 1, 0, -1};

    int loop = 0;

    while (loop < 20000)

    {

        int dir = random->NextInt(4);

        int tmpRow = blankRow + DirRow[dir];

        int tmpCol = blankCol + DirCol[dir];

        if (tmpRow >= 0 && tmpRow < m_iSize && tmpCol >=0 && tmpCol < m_iSize)

        {

            m_pBoardData[GET_INDEX(blankRow, blankCol)] = m_pBoardData[GET_INDEX(tmpRow, tmpCol)];

            m_pBoardData[GET_INDEX(tmpRow, tmpCol)] = BLANK_CELL;

            blankRow = tmpRow;

            blankCol = tmpCol;

            loop++;

        }

    }

    SAFE_DEL(random);

}

Bước 3: Bổ sung hàm nhận sự kiện touch cho CBoard

Hiện tại, ta lưu trữ torng CBoard 2 giá trị m_iX, m_iY. Ta tiến hành thay thể 2 biết này bằng một biến duy nhất m_Region có kiểu SRect<__INT32>. Biến này giúp ta lưu trữ thuận tiện 4 giá trị cùng lúc là x, y, width, height của bàn cờ.

Trong SGraphics.h, bổ sung hàm kiểm tra 1 điểm có nằm trong vùng SRect hay không (giúp tái sử dụng sau này)

template <class T>

struct SRect

{

    SRect(T x=0, T y=0, T w=0, T h=0) 

    {

        X = x; Y = y; W = w; H = h;

    }

    bool IsInside(T x, T y)

    {

        return (x >= X && y >= Y && x < X + W && y < Y + H);

    }

    T X;

    T Y;

    T W;

    T H;

};

Khi này việc kiểm tra người dùng có touch vào bàn cờ hay không được thực hiện khác đơn giản:

void CBoard::OnTouch(__INT32 x, __INT32 y)

{

    if (this->m_Region.IsInside(x, y))

    {

        int x0 = x - m_Region.X;

        int y0 = y - m_Region.Y;

        int col = x0 / CELL_REGION;

        int row = y0 / CELL_REGION;

        int pos = GET_INDEX(row, col);

        if (m_pBoardData[pos] != BLANK_CELL)

        {

            int blank = -1;

            if (col > 0 && m_pBoardData[GET_INDEX(row, col - 1)] == BLANK_CELL)

            {

                blank = GET_INDEX(row, col - 1);

            }

            else if  (col < m_iSize - 1 && m_pBoardData[GET_INDEX(row, col + 1)] == BLANK_CELL)

            {

                blank = GET_INDEX(row, col + 1);

            }

            else if  (row < m_iSize - 1 && m_pBoardData[GET_INDEX(row + 1, col)] == BLANK_CELL)

            {

                blank = GET_INDEX(row + 1, col);

            }

            else if  (row > 0 && m_pBoardData[GET_INDEX(row - 1, col)] == BLANK_CELL)

            {

                blank = GET_INDEX(row - 1, col);

            }

            if (blank >= 0)

            {

                m_pBoardData[blank] = m_pBoardData[pos];

                m_pBoardData[pos] = BLANK_CELL;

            }

        }

    }

}

Sau khi kiểm tra x, y có nằm trong bàn cờ hay không, tiến hành xác định chính xác ô nào của bàn cờ được touch, từ đó ánh xạ về vị trí ô trong mãng một chiều m_pBoardData:

int x0 = x - m_Region.X;

int y0 = y - m_Region.Y;

int col = x0 / CELL_REGION;

int row = y0 / CELL_REGION;

int pos = GET_INDEX(row, col);

Trong trường hợp ô được touch không phải là ô trống, kiểm tra 4 ô lân cận nếu là ô trống thì tiến hành đổi vị trí:

Bước 4: Nhận sự kiện từ người dùng

Trong CStateIngame.cpp, bổ sung nội dung cho hàm OnControllerEvent:

• Nếu người dùng touch và nhả chuột, chuyển xử lý touch cho Board
• Nếu người dùng nhấn Spacebar, sinh lại bàn cờ

void CStateIngame::OnControllerEvent(SControllerEvent Event) 

{

    if ((Event.Type == ECE_POINTER) && (Event.PointerData.Event == EPE_RELEASED) && Event.PointerData.ID == 0)

    {

        m_pBoard->OnTouch(Event.PointerData.X, Event.PointerData.Y);

    }

    else if ((Event.Type == ECE_KEY) && Event.KeyData.KeyCode == EKEY_SPACE)

    {

        m_pBoard->Shuffle();

    }

}

Lưu ý, kiểm tra file CVSView.cpp, và thay đổi hàm update với nội dung sau để fix bug "dính key"

void CVSView::Update()

{

    while (true)

    {

        // handle win32 message

        MSG msg;

        if (PeekMessage(&msg, NULL, 0, 0, PM_REMOVE))

        {

            TranslateMessage(&msg);

            if (msg.hwnd == m_hwndWindow)

            {

                //WndProc(m_hwndWindow, msg.message, msg.wParam, msg.lParam);

                DispatchMessage(&msg);

            }

        }

        CGame::GetInstance()->Update();

        if (!CGame::GetInstance()->IsAlive())

        {

            DestroyWindow(m_hwndWindow);

            return;

        }

        RefreshGL();

    }

}

Ngoài cách dùng hàm sự kiện trực tiếp, ta có thể dùng cách gián tiếp như sau:

void CStateIngame::Update() 

{

if (CControllerKeyManager::GetInstance()->WasKeyRelease(EKEY_SPACE))

{

m_pBoard->Shuffle();

}

}

void CStateIngame::OnControllerEvent(SControllerEvent Event) 

{

if ((Event.Type == ECE_POINTER) && (Event.PointerData.Event == EPE_RELEASED) && Event.PointerData.ID == 0)

{

m_pBoard->OnTouch(Event.PointerData.X, Event.PointerData.Y);

}

}

Source code: Board

//Board.h #ifndef __BOARD__ #define __BOARD__ #include "gametutor.h" class CCell { public: CCell(__INT32 ID); virtual ~CCell(); void Render(CGraphics2D* g, int x, int y); private: __INT32 m_iID; CSprite* m_pSpriteRef; }; class CBoard { public: CBoard(__INT32 size); virtual ~CBoard(); void SetPosition(__INT32 x, __INT32 y); void Render(CGraphics2D* g); void Shuffle(); void Shuffle2(); void OnTouch(__INT32 x, __INT32 y); private: __INT32 m_iSize; __INT32 m_iSizeSquare; CCell** m_Cells; __INT32* m_pBoardData; SRect<__INT32> m_Region; bool IsSolubility(); }; #endif <hr> //Board.cpp #include "Board.h" #define CELL_REGION 96 #define BLANK_CELL (m_iSizeSquare - 1) #define GET_INDEX(row, col) ((row)*(m_iSize) + (col)) #define SHUFFLE_TIMES 20000

CCell::CCell(__INT32 ID): m_iID(ID), m_pSpriteRef(0) { char spr_name [10]; char anim_name [10]; sprintf (spr_name, "CELL_%d", m_iID); m_pSpriteRef = CSpriteManager::GetInstance()->Get(spr_name); if (!m_pSpriteRef) { char ErrorMessage [100]; sprintf (ErrorMessage, "Sprite %s is not found", spr_name); BREAK(ErrorMessage); } else { memset(anim_name, 0, 10); sprintf (anim_name, "%d", ID); m_pSpriteRef->SetAnimation(anim_name); } } CCell::~CCell() {} void CCell::Render(CGraphics2D* g, int x, int y) { m_pSpriteRef->SetPosition(SPosition2D<__INT32>(x, y)); m_pSpriteRef->RenderAnimation(g); } CBoard::CBoard(__INT32 size): m_iSize(size), m_iSizeSquare(size*size), m_Cells(0) { m_Cells = new CCell*[m_iSizeSquare - 1]; for (int i = 0; i < m_iSizeSquare - 1; i++) { m_Cells[i] = new CCell(i+1); } m_pBoardData = new __INT32[m_iSizeSquare]; for (int i = 0; i < m_iSizeSquare; i++) { m_pBoardData[i] = i; } m_Region.X = 0; m_Region.Y = 0; m_Region.W = size*CELL_REGION; m_Region.H = size*CELL_REGION; } CBoard::~CBoard() { SAFE_DEL_ARRAY_OBJ(m_Cells, m_iSizeSquare - 1); SAFE_DEL_ARRAY(m_pBoardData); } void CBoard::SetPosition(__INT32 x, __INT32 y) { m_Region.X = x; m_Region.Y = y; } void CBoard::Render(CGraphics2D* g) { int x = m_Region.X; int y = m_Region.Y; int index = 0; for (int i = 0; i < m_iSize; i++) { for (int j = 0; j < m_iSize; j++) { int spr_id = m_pBoardData[index++]; if (spr_id < m_iSizeSquare - 1) { m_Cells[spr_id]->Render(g, x, y); } x += CELL_REGION; } y += CELL_REGION; x = 0; } } void CBoard::Shuffle() { int r1, r2 = 0; CRandom* random = new CRandom(); bool success = false; for (int i = 0; i < SHUFFLE_TIMES ; i++)

{ r1 = random->NextInt(m_iSizeSquare); r2 = random->NextInt(m_iSizeSquare); __INT32 tmp = m_pBoardData[r1]; m_pBoardData[r1] = m_pBoardData[r2]; m_pBoardData[r2] = tmp; } while (!IsSolubility()) { r1 = random->NextInt(m_iSizeSquare); r2 = random->NextInt(m_iSizeSquare); __INT32 tmp = m_pBoardData[r1]; m_pBoardData[r1] = m_pBoardData[r2]; m_pBoardData[r2] = tmp; } SAFE_DEL(random); } void CBoard::Shuffle2() { int blank = 0; CRandom* random = new CRandom(); for (int i = 0; i < m_iSizeSquare; i++) { if (m_pBoardData[i] == BLANK_CELL) { blank = i; break; } } int blankRow = blank / m_iSize; int blankCol = blank % m_iSize; int DirRow[] = {1, 0, -1, 0}; int DirCol[] = {0, 1, 0, -1}; int loop = 0; while (loop < SHUFFLE_TIMES)

{ int dir = random->NextInt(4); int tmpRow = blankRow + DirRow[dir]; int tmpCol = blankCol + DirCol[dir]; if (tmpRow >= 0 && tmpRow < m_iSize && tmpCol >=0 && tmpCol < m_iSize) { m_pBoardData[GET_INDEX(blankRow, blankCol)] = m_pBoardData[GET_INDEX(tmpRow, tmpCol)]; m_pBoardData[GET_INDEX(tmpRow, tmpCol)] = BLANK_CELL; blankRow = tmpRow; blankCol = tmpCol; loop++; } } SAFE_DEL(random); } void CBoard::OnTouch(__INT32 x, __INT32 y) { if (this->m_Region.IsInside(x, y)) { int x0 = x - m_Region.X; int y0 = y - m_Region.Y; int col = x0 / CELL_REGION; int row = y0 / CELL_REGION; int pos = GET_INDEX(row, col); if (m_pBoardData[pos] != BLANK_CELL) { int blank = -1; if (col > 0 && m_pBoardData[GET_INDEX(row, col - 1)] == BLANK_CELL) { blank = GET_INDEX(row, col - 1); } else if (col < m_iSize - 1 && m_pBoardData[GET_INDEX(row, col + 1)] == BLANK_CELL) { blank = GET_INDEX(row, col + 1); } else if (row < m_iSize - 1 && m_pBoardData[GET_INDEX(row + 1, col)] == BLANK_CELL) { blank = GET_INDEX(row + 1, col); } else if (row > 0 && m_pBoardData[GET_INDEX(row - 1, col)] == BLANK_CELL) { blank = GET_INDEX(row - 1, col); } if (blank >= 0) { m_pBoardData[blank] = m_pBoardData[pos]; m_pBoardData[pos] = BLANK_CELL; } } } } #define IS_ODD(a) (((a)&1) == 1) #define IS_EVEN(a) (((a)&1) == 0) bool CBoard::IsSolubility() { int N = 0; int blankRow = m_iSize - 1; for (int i = 0 ; i < m_iSizeSquare - 1; i++) { if (m_pBoardData[i] == BLANK_CELL) { blankRow = (i / m_iSize) + 1; } else { for (int j = i + 1 ; j < m_iSizeSquare; j++) { if (m_pBoardData[i] > m_pBoardData[j]) { N++; } } } } if (IS_ODD(m_iSize)) { return (IS_EVEN(N)); } else { return ( (IS_EVEN(N) && IS_EVEN(blankRow)) || (IS_ODD(N) && IS_ODD(blankRow)) ); } } #undef GET_INDEX