QUANG HOANG'S BLOG

hodawa
Download source code

Chắc hẳn chò chơi Line rất quen thuộc với các bạn, trò chơi gồm một bảng chứa các viên bi, có 5 loại bi được đặt bằng 5 màu khác nhau. Người chơi sẽ di chuyển vị trí của các viên bi để chúng thành một hàng ngang (từ trái qua phải), hàng đứng (từ trên xuống dưới) hay đường chéo 5 viên bi liên tiếp thì 5 viên bi này sẽ được xóa khỏi bảng. Trò chơi kết thúc khi bảng đầy các viên bi.

Để làm chò chơi Line đầu tiên các bạn phải xác định được đường đi của viên bi (khi các bạn chọn một viên bi và chọn vào một ô trống nào đó trên bảng). Có thể có rất nhiền cách để xác định đường đi này, ở đây tôi chỉ xin trình bày cách sử dụng thuật toán BFS để tìm đường đi của viên bi trên bảng. Để áp dụng thuật toán BFS các bạn xem bảng như một đồ thị với mỗi ô trên bảng như một đỉnh của đồ thị.

Trong khi (Hàng đợi[0] chưa rỗng)
{	
    Lấy từng phần tử trong Hàng đợi[0] 
    {	
        Kiểm tra 4 ô xung quanh (trên, dưới, trái, phải) của phần tử này 
        {	
            Nếu là ô còn trống
            {	
                - Bỏ phần tử này vào Hàng đợi[1]
                - Lưu lại đường đi từ phần từ này đến vị trí mới (là 1 trong 4 ô xung quanh phần tử hiện tại)
                - Nếu phần tử này là ô đích
                Dừng vòng lặp chính	(Thành công)
            }
        }
    }
    Bỏ tất cả các phần tử của Hàng đợi[1] vào Hàng đợi[0] để tiếp tục loang
}

//Loang (BFS) trên lưới để tìm đường đi từ (si, sj) đến (fi, fj)
private bool BFS(int si, int sj, int fi, int fj, Point [] pPath)
{
    int [] di = {-1, 1, 0, 0};  //mảng lưu hướng đi (trên, dưới, trái, phải)
    int [] dj = {0 , 0,-1, 1};

    int i, j, k, nCount;
    bool [,] bCheck = new bool[ nMaxCell, nMaxCell ];	 //mảng đánh dấu các ô đã xét
    Point [,] pQuery = new Point[ 2, nMaxCell * nMaxCell ]; //2 hàng đợi để loang
    Point [,] pPathBall = new Point[ nMaxCell, nMaxCell ];  //mảng lưu các ô đã đi qua
    Point pStart, pFinish, pCurrent;
    pStart = new Point(si, sj);
    pFinish = new Point(fi, fj);
    //Bỏ phần tử đầu tiên vào hàng đợi
    int nQueryLast = 1;
    pQuery[0, 0] = pStart;
    //Khởi tạo mảng đánh dấu các ô đã đi qua
    for (i=0; i < nMaxCell; i++)
        for (j=0; j < nMaxCell; j++)
            bCheck[i,j] = anBoard[i,j] > 0; //đánh dấu các ô đã có viên bi là true
    bCheck[pStart.X, pStart.Y] = true; //đánh dấu ô xuất phát

    if (bCheck[fi, fj]) //nếu ô đích là ô đã có viên bi 
        return false;	//thì không cần tìm kiếm vì chắc chắn không có kết quả
    pPathBall[pStart.X, pStart.Y] = new Point(-1,-1); //danh dấu ô xuất phát
    //LOANG (BFS)
    while (nQueryLast > 0) //Trong khi Hàng đợi[0] chưa rỗng
    {	
        nCount = 0;
        //Xét tất cả các phần tử trong Hàng đợi[0]
        for (int nLast=0; nLast < nQueryLast; nLast++)
        {
            pCurrent = pQuery[0, nLast ];					
            //Tìm xung quanh 4 hướng của ô (i,j) xem có hướng nào có thể đi được không ?
            for (k=0; k < 4; k++)
            {
                i = pCurrent.X + di[k];
                j = pCurrent.Y + dj[k];
                if (i>=0 && i < nMaxCell && j >=0 & j < nMaxCell && !bCheck[i, j])
                {							
                    pQuery[1, nCount++] = new Point( i, j);
                    bCheck[ i , j ] = true;
                    pPathBall[ i , j ] = new Point(pCurrent.X, pCurrent.Y);
                    if (bCheck[ fi, fj])  //Tìm thấy ô đích, thì dừng tìm kiếm
                    {	
                        nCountPath = 0;
                        FindPath(new Point(fi, fj), pPathBall);
                        nIndexPath = 0;						
                        tmrPath.Enabled = true;	
                        return true;
                    }
                }
            }
        }	
        //Bỏ tất cả các phần tử của pQuery[1] vào pQuery[0] để tiếp tục loang
        for (k=0; k < nCount; k++)
            pQuery[ 0, k ] = pQuery[ 1, k ];
        nQueryLast = nCount;				
    }
    return false;
}

private void FindPath(Point p, Point [,] pPathBall)
{
    //Nếu đỉnh trước của đỉnh (p.X, P.Y) không phải là đỉnh xuất phát
    if (pPathBall[ p.X, p.Y ] != new Point(-1,-1))  
        FindPath(pPathBall[ p.X, p.Y ], pPathBall); //Tiếp tục truy hồi
    pPath[nCountPath++] = p;	//Lưu các đỉnh đã truy hồi vào mảng pPath
}