Oop lab/sokoban

หน้านี้เป็นส่วนหนึ่งของ oop lab

เกม Sokoban เป็นเกมปัญหาที่โด่งดังมากในอดีต ทดลองเล่นได้ที่ [1] หรือ [2]

ในเกมนี้ผู้เล่นจะเดินเข็นกล่องไปมาให้ไปอยู่ในตำแหน่งปลายทาง ผู้เล่นจะดันกล่องได้เท่านั้น (ดึงไม่ได้ถ้าดันไปติดกำแพงก็จบเกม) และจะสามารถดันกล่องได้แค่ใบเดียวเท่านั้น (ถ้าติดกันสองใบจะหนักเกิน ดันไม่ไหว)

หมายเหตุ: โค้ดที่ได้จากแบบฝึกหัดนี้ มีคลาส GameBoard ที่ใหญ่โตมาก (แม้ว่า method โดยมากจะสั้น) น่าจะเป็นเป้าหมายที่ดีของการ refactor ต่อไป (จริง ๆ แล้วควร refactor ไประหว่างที่ทำ TDD ด้วยเลย แต่ในส่วนแบบฝึกหัดนี้เน้นให้พยายามเขียนเทสก่อนเป็นหลัก)

เริ่มต้น

เราจะพัฒนาเกมดังกล่าวด้วยกระบวนการ TDD และหัดใช้ git ไปพร้อม ๆ กัน ดังนั้นให้สร้างโปรเจ็ค จากนั้นให้สร้าง git repository ของโปรเจ็คด้วย (ดูวิธีการได้ในคลิป egit)

ด้านล่างเป็นคลาส GameBoard และ unit test เบื้องต้น GameBoardTest ให้สร้างคลาสดังกล่าวใน project และนำโค้ดด้านล่างไปใช้ อย่าลืมดูชื่อ package ให้สอดคล้องกับ project ที่สร้างขึ้นด้วย (โดยมากนิยมใช้ชื่อเดียวกัน)

ในคลาส GameBoardTest จะมีการใช้ @Before ในการระบุเมท็อดที่ใช้กำหนดค่าเริ่มต้นก่อนการทำงานของแต่ละเทสเคสด้วย เราใช้เมท็อดนี้ในการสร้างตารางเกม smallBoard เอาไว้ใช้เทส (ชื่อ small เพราะว่า เดี๋ยวเราคาดว่าจะเพิ่ม largeBoard สำหรับเทสต่อไปด้วย)

ให้ทดลองสั่งให้ unit test ทำงาน ถ้าเขียวหมด ให้ commit เวอร์ชันนี้ลง git

ถ้า unit test เขียวหมด ให้ commit สามารถใส่ commit message ว่า initial project template

GameBoard.java

package sokoban;

public class GameBoard {

    private int height;
    private int width;
    private String[] baseBoard;
    
    private int playerRow;
    private int playerCol;
    
    private int numBoxes;
    private int[] boxRows;
    private int[] boxCols;

    public GameBoard(String[] map) {
        loadBoard(map);
    }

    public void loadBoard(String[] map) {
        height = map.length;
        width = map[0].length();
        numBoxes = 0;
        boxRows = new int[height*width];
        boxCols = new int[height*width];
        
        baseBoard = new String[height];
        for(int r = 0; r < height; r++) {
            baseBoard[r] = "";
            for(int c = 0; c < width; c++) {
                char mch = map[r].charAt(c);
                char sch = '.';
                switch(mch) {
                case 'A': 
                    playerRow = r;
                    playerCol = c;
                    break;
                case 'O':
                    boxRows[numBoxes] = r;
                    boxCols[numBoxes] = c;
                    numBoxes++;
                    break;
                default:
                    sch = mch;
                }
                baseBoard[r] += sch;
            }
        }
    }

    public int getHeight() {
        return height;
    }

    public int getWidth() {
        return width;
    }

    public int getPlayerRow() {
        return playerRow;
    }
    
    public int getPlayerCol() {
        return playerCol;
    }
    
    public void setPlayerPosition(int r, int c) {
        playerRow = r;
        playerCol = c;
    }

    public int getNumBoxes() {
        return numBoxes;
    }

    public int[] getBoxPosition(int i) {
        return new int[] { 
                boxRows[i],
                boxCols[i]
        };
    }
    
    public void setBoxPosition(int i, int r, int c) {
        boxRows[i] = r;
        boxCols[i] = c;
    }

    public boolean hasPlayerAt(int r, int c) {
        return (playerRow == r) && (playerCol == c);
    }
    
    public boolean hasBoxAt(int r, int c) {
        return false;
    }
    
    public boolean hasExitAt(int r, int c) {
        return false;
    }
    
    public String toString() {
        return "";
    }
}

GameBoardTest.java

package sokoban;

import static org.junit.Assert.*;

import org.junit.Before;
import org.junit.Test;

public class GameBoardTest {

    static String smallBoardMap[] = {
        " #####",
        "#*O.A#",
        "#...O#",
        "##..*#",
        " #####"
    };
    private GameBoard smallBoard;

    @Before
    public void setUp() {
        smallBoard = new GameBoard(smallBoardMap);
    }
    
    @Test
    public void testLoadBoardProperties() {
        assertEquals(5, smallBoard.getHeight());
        assertEquals(6, smallBoard.getWidth());
    }

    @Test
    public void testLoadBoardPlayerPosition() {
        assertEquals(1, smallBoard.getPlayerRow());
        assertEquals(4, smallBoard.getPlayerCol());
    }
    
    @Test
    public void testLoadBoardNumBoxes() {
        assertEquals(2, smallBoard.getNumBoxes());
    }

    @Test
    public void testLoadBoardBoxPositions() {
        assertArrayEquals(new int[] {1, 2}, smallBoard.getBoxPosition(0));
        assertArrayEquals(new int[] {2, 4}, smallBoard.getBoxPosition(1));
    }    
    
    @Test
    public void testPlayerPositionCheck() {
        assertFalse(smallBoard.hasPlayerAt(0,0));
        assertTrue(smallBoard.hasPlayerAt(1,4));
    }
    
    @Test
    public void testPlayerPositionCheckAfterChange() {
        smallBoard.setPlayerPosition(2, 3);
        assertFalse(smallBoard.hasPlayerAt(1,4));
        assertTrue(smallBoard.hasPlayerAt(2, 3));
    }
}

กระดานเกมทั่วไป และการแสดงผล

คลาส GameBoard มีเมท็อดทั่วไปต่าง ๆ ให้ใช้ในการโหลดตารางเกมและอ่านข้อมูลพื้นฐาน

พิจารณาการเก็บข้อมูลใน GameBoard จากโค้ดตั้งต้น จะมีการเก็บข้อมูลดังนี้

• ข้อมูลตารางเกมพื้นฐาน (ที่ไม่มีการเปลี่ยนแปลงระหว่างเล่น) จะเก็บในอาร์เรย์ baseBoard ที่เก็บตารางเป็นสตริงทีละแถว สตริงจะประกอบด้วย '#' แทนกำแพง '.' แทนทางเดินในห้อง และ '*' แทนจุดเป้าหมาย (เรียกว่า exit)
• ตำแหน่งในตารางเกมจะเก็บเป็น row, column โดยเริ่มนับจาก 0 (แถวแรกคือแถวที่ 0, คอลัมน์แรกคือคอลัมน์ที่ 0)
• ตำแหน่งผู้เล่น เก็บใน playerRow และ playerCol
• จำนวนกล่อง เก็บใน numBoxes
• ตำแหน่งของกล่อง เก็บเป็นอาเรย์ boxRows และ boxCols โดยกล่องที่ i อยู่ที่แถว boxRows[i] และคอลัมน์ boxCols[i]

คลาสที่ให้มาขาดเมท็อดที่จำเป็นอีกหลายอย่าง ในส่วนนี้เราจะเขียนเมท็อดสำหรับตรวจสอบว่าในช่องที่ระบุมีกล่องอยู่หรือไม่ และในช่องที่ระบุมีทางออกอยู่หรือไม่ จากนั้นเราจะเขียนเมท็อด toString เพื่อเตรียมไว้สำหรับพิมพ์ตารางเกมออกทางหน้าจอ

การตรวจสอบตำแหน่งผู้เล่นที่ยืดหยุ่นมากขึ้น

เราต้องการเมท็อด hasPlayerAt ทำงานได้แม้ว่าจะมีการส่งค่าที่ผิดพลาด เช่น ส่งออกนอกขอบเขตเป็นต้น ดังนั้น เราจะปรับปรุงโค้ดโดยเริ่มจากการเพิ่มเทสเคส

    @Test
    public void testPlayerPositionCheckOutside() {
        assertFalse(smallBoard.hasPlayerAt(-10, 1));
        assertFalse(smallBoard.hasPlayerAt(1, -10));
        assertFalse(smallBoard.hasPlayerAt(1, 100));
        assertFalse(smallBoard.hasPlayerAt(100, 1));
    }

อย่างไรก็ตาม เนื่องจากเมท็อดเราเขียนโดยไม่ได้สนใจขนาดของตารางอยู่แล้ว เทสนี้จึงผ่านโดยไม่ต้องแก้โค้ดอะไรเลย

ตรงนี้เป็นจุดที่ดีที่ควรจะ commit อาจจะใส่ commit message เพื่อระบุว่ามีการเพิ่มเทสตรวจสอบตำแหน่งผู้เล่นที่อยู่นอกตาราง

ตรวจสอบทางออก

เราจะเขียนเมท็อด hasExitAt (ในโค้ดคืน false ตลอด)

เพิ่มเทสเคสนี้ลงใน GameBoardTest

    @Test
    public void testExitPositionCheck() {
        assertFalse(smallBoard.hasExitAt(0, 0));
    }

จากนั้นให้ทดลองสั่งให้ unit test ทำงาน จะพบว่า test ผ่านหมด (เพราะว่าเมท็อดที่เราเขียนคืน false หมด)

ให้เพิ่มการ assert เพิ่มเติมให้มีกรณีที่คืนค่าเป็น true และรัน unit test ใหม่ ควรจะเห็นผลเป็น red จากนั้นให้กลับไปแก้เมท็อด hasExitAt ให้เทสผ่าน

ให้ใส่กรณีเพิ่มเติมที่ต้องการทดสอบอีก 1-2 กรณี เช่นตรวจสอบในส่วนที่เป็นกำแพง

เราต้องการให้เมท็อดนี้ทำงานได้แม้กระทั่งมีการถามที่ออกนอกขอบเขต ดังนั้นเราจะเพิ่มเทส

    @Test
    public void testExitPositionCheckOutsideBoard() {
        assertFalse(smallBoard.hasExitAt(-10, -1));
        assertFalse(smallBoard.hasExitAt(100, 1));
        assertFalse(smallBoard.hasExitAt(1, 500));
    }

ทดลองรันเทส และแก้ให้ผ่านเทส

ตรงนี้เป็นจุดที่ดีที่ควรจะ commit

ตรวจสอบตำแหน่งกล่อง

เราจะเขียนเมท็อด hasBoxAt (ตอนนี้ในโค้ดคืน false ตลอด) เมท็อดนี้จะคืนค่า true ถ้าที่แถว r คอลัมน์ c มีกล่องอยู่

ให้เริ่มโดยเพิ่มเทสเคสของเมท็อดนี้ใน GameBoardTest จากนั้นแก้เมท็อด hasBoxAt ให้ผ่านเทส จากนั้นทยอยเพิ่มเทสจนคิดว่าเทสเคสครอบคลุม

ถึงตรงนี้ก็ควร commit อีกสักที

เมท็อด toString

ให้เพิ่มเทสเคสนี้ลงใน GameBoardTest

    @Test
    public void testToStringWithInitialPositions() {
        assertEquals(		
                " #####\n"+
                "#*O.A#\n"+
                "#...O#\n"+
                "##..*#\n"+
                " #####\n",
                smallBoard.toString());
    }

จากนั้นเขียนเมท็อด toString() ใน GameBoard เมท็อดนี้จะสร้างสตริงที่เป็นรูปกระดานเกมตามสถานะของเกมที่เป็นอยู่

เทสเคส testToStringWithInitialPositions จะเป็นตัวอย่างทดสอบของสถานะเกมเมื่อเริ่มต้น

ให้เพิ่มเทสเคสอื่น ๆ และทยอยแก้เมท็อด toString ให้ทำงานผ่านเทสเคสเหล่านั้น ยกตัวอย่างเช่น เพิ่มกรณีที่ผู้เล่นเปลี่ยนตำแหน่ง (สั่ง setPlayerPosition) หรือกรณีที่มีการเปลี่ยนตำแหน่งของกล่อง (ผ่านทางเมท็อด setBoxPosition) เป็นต้น

ทำจนเหนื่อย ก็อย่าลืม commit ด้วย!

การขยับ (แบบไม่ดันกล่อง)

ในส่วนนี้ เราจะเขียนโค้ดส่วนที่ตรวจสอบว่าตัวละครสามารถเดินไปในทิศทางต่าง ๆ ได้หรือไม่ และบังคับให้ตัวละครเดินไปในทิศทางต่าง ๆ เหล่านั้น

เราจะสร้างคลาส BoardGameMovementTest เพื่อเก็บเทสเคสของส่วนนี้ เราสร้างคลาสแยกออกมาเพราะไม่ต้องการเก็บทุกอย่างรวมอยู่ใน BoardGameTest ก่อนที่เราจะเริ่ม ให้ไปเพิ่ม jUnit Test Case และระบุชื่อคลาสเป็น BoardGameMovementTest ไว้ก่อนได้เลย เราจะ copy setUp method มาจาก GameBoardTest ด้วยเลย

public class GameBoardMovementTest {
    static String smallBoardMap[] = {
            " #####",
            "#*O.A#",
            "#...O#",
            "##..*#",
            " #####"
        };

    private GameBoard smallBoard;

    @Before
    public void setUp() {
        smallBoard = new GameBoard(smallBoardMap);
    }
}

เมท็อดที่เราจะเขียนคือ

• boolean canPlayerMove(Direction dir)
• void movePlayer(Direction dir)

ส่วนประกอบช่วยเหลือ

เนื่องจากเราต้องใช้ทิศทางในโปรแกรม เราจะสร้างชนิดข้อมูลแบบ Direction ขึ้นมา (เป็นชนิดข้อมูลแบบ enum อ่านเพิ่มเติม) เพื่อให้เราเขียนได้สะดวกและชัดเจนขึ้น (แทนที่จะใช้ 1 แทนขึ้นบน 2 แทนไปทางขวา เป็นต้น)

เราจะเพิ่ม enum Direction เข้าไปในคลาส GameBoard เราจะแสดงวิธีใช้ตามตัวอย่างต่อไป

public class GameBoard {
    // ...
    public enum Direction {
        UP, RIGHT, DOWN, LEFT
    }
    // ...
}

จากนั้นเราจะเพิ่มเมท็อด getRowDiff และ getColDiff เพื่อคืนค่าการเปลี่ยนแปลงตำแหน่ง เมื่อตัวละคร หรือกล่องเคลื่อนที่ไปตามทิศทางต่าง ๆ

    public int getColDiff(Direction dir) {
        switch(dir) {
        case LEFT:
            return -1;
        case RIGHT:
            return 1;
        default:
            return 0;
        }
    }

    public int getRowDiff(Direction dir) {
        switch(dir) {
        case UP:
            return -1;
        case DOWN:
            return 1;
        default:
            return 0;
        }
    }

เมท็อด getBoardNextItem

เพื่อเขียนเมท็อดเกี่ยวกับการเคลื่อนที่ เราจะเขียนเมท็อด char getBoardItem(int r, int c, Direction dir) ที่คืนค่าเป็นตัวอักษรแสดงของที่อยู่ในช่องที่มีทิศทาง dir ไปจากช่องในตำแหน่งแถว r คอลัมน์ c ฟังก์ชันดังกล่าวที่คืนค่าแต่ 'x' แสดงดังด้านล่าง

    public char getBoardNextItem(int r, int c, Direction dir) {
        return 'x';   // ผิดชัวร์!!!
    }

เราต้องการให้เมท็อดคืนค่าดังนี้

• '#' ถ้าในทิศทางดังกล่าวเป็นกำแพง หรือว่าอยู่นอกขอบเขตตารางเกม
• '*' ถ้าในทิศทางดังกล่าวเป็น exit
• '.' ถ้าในทิศทางดังกล่าวเป็นช่องว่างของห้อง (เดินไปได้)
• 'O' ถ้าในทิศทางดังกล่าวมีกล่องอยู่
• 'A' ถ้าในทิศทางดังกล่าวของช่องมีผู้เล่นอยู่
• ' ' ช่องว่างภายนอกห้อง (ค่านี้เป็นไปได้ ถ้าเป็นช่องที่ในแผนที่ตอนต้นเป็นช่องว่าง)

แน่นอนว่าเมท็อดนี้ในโค้ดข้างต้นทำงานไม่ถูก เราจะเพิ่มเทสเคสด้านล่างลงใน BoardGameMovementTest

    @Test
    public void testGetBoardNextItem() {
        assertEquals('#', smallBoard.getBoardNextItem(1, 1, GameBoard.Direction.UP));
        assertEquals('#', smallBoard.getBoardNextItem(1, 1, GameBoard.Direction.LEFT));
    }

ให้รัน unit test ผลจะเป็นสีแดง ให้กลับไปแก้โค้ด getBoardItem จนผ่าน

ให้เพิ่มเทสเคสอื่น ๆ และแก้โค้ด getBoardNextItem จนกระทั่งคิดว่าเมท็อดทำงานได้ถูกต้อง (อย่างน้อย เทสเคสควรจะครอบคลุมทุกกรณีที่เมท็อดควรจะคืนค่ากลับ) อย่าลืมว่าเรามีเมท็อด hasBoxAt เอาไว้ใช้ด้วย สามารถใช้ในการเขียนเมท็อดนี้ได้

ทำมาได้สักระยะ ควร commit ได้แล้ว

เมท็อด canPlayerStepOn

เราจะได้ข้อมูลของช่องจากเมท็อด getBoardItem แต่หลายกรณีเราจะพบว่าเราต้องไปตรวจสอบเพิ่มเติมก่อนจะทราบว่าผู้เล่นจะเดินไปได้หรือไม่ เราจะเขียนเมท็อด canPlayerStepOn เพื่อใช้ในกรณีนี้ เนื่องจากเมท็อดนี้ง่าย เราจะเขียนตรง ๆ เลย โดยไม่เทสเพิ่มเติม เพิ่มเมท็อดดังกล่าวลงใน GameBoard

    public boolean canPlayerStepOn(char item) {
        return (item == '.') || (item == '*') || (item == ' ');
    }

ในช่วงแรกนี้เราจะไม่สามารถดันกล่องได้ เราจะพิจารณาให้ช่องที่เป็นกล่องนั้นเดินไปไม่ได้ด้วย

เมท็อด canPlayerMove และ movePlayer

ให้เขียนเมท็อดทั้งสอง โดยโครงเริ่มต้นเป็นดังนี้

    public boolean canPlayerMove(Direction dir) {
        return false;
    }
    
    public void movePlayer(Direction dir) {
    }

เทสเคสของเมท็อดทั้งสองควรจะต้องใช้ตารางที่ซับซ้อนกว่า smallBoard ดังนั้นเราจะเพิ่ม largeBoard ลงในคลาส GameBoardMovementTest เพื่อทำให้การเทสทำได้สะดวก ด้านล่างเป็นตัวอย่างของการเพิ่ม เราประกาศค่าคงที่ largeBoardMap ที่เป็นแผนที่ ประกาศ field ชื่อ largeBoard และเพิ่มคำสั่งสำหรับสร้าง largeBoard ใน setUp อย่างไรก็ตามเราไม่ได้เตรียมตารางสำหรับทดสอบไว้ให้ คุณจะต้องออกแบบตารางเกมขนาดใหญ่ขึ้นเพื่อทดสอบเอง

    static String largeBoardMap[] = {
            "ใส่ตารางสำหรับทดสอบเอง",
            "ใส่ตารางสำหรับทดสอบเอง"
        };

    private GameBoard largeBoard;

    @Before
    public void setUp() {
        smallBoard = new GameBoard(smallBoardMap);
        largeBoard = new GameBoard(largeBoardMap);
    }

เริ่มโดยการใส่เทสเคสใน GameBoardMovementTest ก่อน และทยอยแก้เมท็อดทั้งสอง ให้เริ่มโดยทำเมท็อด canPlayerMove ก่อน จากนั้นให้ทำเมท็อด movePlayer ในลักษณะคล้ายกัน

ในการทำเมท็อด movePlayer สามารถใช้เมท็อด canPlayerMove ได้ ถ้าไม่สามารถเดินไปได้ เมท็อดจะไม่ทำงานใด ๆ ในการเขียนเทสเคส สามารถใช้เมท็อด getPlayerRow, getPlayerCol, และ setPlayerPosition ได้

ทำมาได้สักระยะ ควร commit ได้แล้ว

เดินได้ (โปรแกรมหลักและลูป)

คลาส Main ด้านล่างใช้ GameBoard ในการเล่นเกม และให้ผู้เล่นเดินไปมาได้ สามารถปรับ gameMap ได้ตามใจชอบ

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        String gameMap[] = {
            " #####",
            "#*O.A#",
            "#...O#",
            "##..*#",
            " #####"
        };
        
        GameBoard board = new GameBoard(gameMap);
        Scanner scanner = new Scanner(System.in);
        int round = 0;
        
        while(true) {
            System.out.println("Round: " + round);
            System.out.println(board);
            System.out.println();
        
            System.out.print("Your choice (awsd - movement, q - quit):");
            
            String choiceStr = scanner.nextLine();
            
            if(choiceStr.length() == 0) {
                continue;
            }
            
            char choice = choiceStr.toLowerCase().charAt(0);
            
            if(choice == 'q') {
                System.out.println("Good bye");
                break;
            }
            
            GameBoard.Direction dir = GameBoard.Direction.STILL;
            switch(choice) {
            case 'a':
                dir = GameBoard.Direction.LEFT;
                break;
            case 'w':
                dir = GameBoard.Direction.UP;
                break;
            case 's':
                dir = GameBoard.Direction.DOWN;
                break;
            case 'd':
                dir = GameBoard.Direction.RIGHT;
                break;
            }
            if(board.canPlayerMove(dir)) {
                board.movePlayer(dir);
            }
            round++;
        }
    }
}

เล่นได้แล้ว commit เถอะ

ดันกล่อง

เราจะปรับเมท็อด canPlayerMove และ movePlayer ให้รองรับการดันกล่อง เมื่อแก้ส่วนนี้เสร็จแล้ว เราจะสามารถใช้คลาส Main เดิมในการเล่นเกมที่เราดันกล่องได้เลย

ก่อนอื่นกลับไปดูเทสเคสที่เราสร้างไว้ตั้งแต่ส่วนก่อน ถ้ามีบางส่วนที่ทดสอบการเดินที่ต้องดันกล่อง (และดันได้) แล้วเราเทสว่า canPlayerMove จะต้องคืนค่า false ให้ปรับให้กลายเป็น true ถ้ามีการแก้ตรงนี้ ให้แก้ canPlayerMove ให้ผ่านเทสเคสชุดนี้

จากนั้นให้พิจารณากรณีอื่น ๆ ที่น่าสนใจของ canPlayerMove เช่น

• ดันหนึ่งกล่องได้
• คนติดกับหนึ่งกล่อง แต่ไม่สามารถดันได้ เพราะว่ากล่องติดกับกำแพง
• คนติดกับหนึ่งกล่อง แต่ไม่สามารถดันได้ เพราะว่ามีอีกกล่องติดอยู่ด้วย

ให้ทยอยเพิ่มเทสเคสทีละประเด็น และปรับแก้ canPlayerMove ให้ทำงานได้ทีละประเด็น ระวังอย่างเพิ่มทุกเทสเคสทั้งหมดลงไปใน test method เดียว พยายามแบ่ง test case เป็นชุดย่อย ๆ ที่เกี่ยวข้องกัน

เมื่อทำ canPlayerMove เสร็จ ให้เขียนเมท็อด movePlayer โดยทำตามกระบวนการเดิม คือ เพิ่มเทสเคส และแก้เมท็อด สลับกันไป จนกระทั่งพิจารณาครบทุกกรณีที่น่าสนใจ

เมื่อแก้เสร็จและเทสผ่านหมดแล้ว โปรแกรมจากคลาส Main น่าจะทำงานได้ทันที ทดลองเล่น และแก้บั๊กถ้าพบในการเล่นจริง (ถ้าพบบั๊ก แสดงว่า unit test ของเรายังไม่ครบคลุมเพียงพอ)

commit เถอะ ทำมาตั้งนาน