Cài đặt thuật toán game pokemon bằng ngôn ngữ lập trình Java

Lưu ý: Full source thuật toán pokemon bằng Java có link download phía dưới

Trường hợp cùng nằm trên một hàng hoặc cột

Các bạn có thể xem qua Best Bootcamp

TH1: Hai điểm xét cùng thuộc một hàng (đường thẳng theo trục x)

TH2: Hai điểm xét cùng thuộc một cột (đường thẳng theo trục y)

Với 2 TH cơ bản này thì chúng ta chỉ cần dùng vòng lặp for từ điểm đầu đến điểm cuối và kiểm tra xem đường thẳng đó có thông với nhau được không. Nếu được thì coi như xong, nếu không được ta sẽ sử dụng các TH mở rộng theo chiều ngang hoặc dọc để làm tiếp. Để xét 2 TH này chúng ta sử dụng 2 hàm là checkLineX(int y1, int y2, int x) và checkLineY(int x1, int x2, int y) tương ứng là xét theo hàng và xét theo cột. Hàm trả về true nếu đi được giữa 2 điểm, false nếu không đi được.

Xét duyệt các đường đi theo chiều ngang, dọc trong phạm vi hình chữ nhật

Với 2 điểm không thẳng hàng, cột thì trước tiên ta sẽ xét trong phạm vi hình chữ nhật mà 2 điểm đó tạo ra, đây là TH xét đường đi hình chữ Z.

TH3: Xét duyệt các đường đi theo chiều ngang trong phạm vi hình chữ nhật

Ta xây dựng hàm checkRectX(Point p1, Point p2), (kiểm tra trong phạm vi hình chữ nhật theo chiều ngang mà 2 điểm p1 và p2 tạo ra). Trước tiên chúng ta sẽ tìm xem điểm nào có tọa độ cột (y) nhỏ hơn (pMinY), điểm nào lớn hơn (pMaxY). Tiếp theo chúng ta cho y chạy tử bé đến lớn (từ trái sang phải), với mỗi cột (y) tương ứng chúng ta sẽ xét xem 3 đường thẳng nhỏ gấp khúc có liền mạch không bằng cách sử dụng hàm checkLineX và checkLineY đã xây dựng. Nếu tồn tại một cột y nào đó mà làm cho 3 đường này thông nhau chứng tỏ chúng ta có đường đi được giữa 2 điểm và ta sẽ trả về giá trị y là cột đó. Nếu không thì trả về -1.

TH4: Xét duyệt các đường đi theo chiều dọc

Xây dựng hàm checkRectY(Point p1, Point p2) tuơng tự như TH3 đã làm nhưng xét theo chiều dọc.

Xét mở rộng theo chiều ngang, dọc

Cuối cùng là 2 TH xét mở rộng ra nếu 4 TH trên đều thất bại. Tức là chúng ta phải xét đến trường hợp đường đi có hình dạng chữ U hoặc chữ L.

TH5: Xét mở rộng theo chiều ngang

Trong TH này chúng ta sẽ xét mở rộng chiều ngang về phía bên trái hoặc bên phải bằng hàm checkMoreLineX(Point p1, Point p2, int type) Trong đó p1, p2 là 2 điểm cần kiểm tra, tìm đường đi, type là loại, type sẽ nhận giá trị là 1 (đi về phải) hoặc -1 (đi về trái). Trước tiên chúng ta cũng tìm xem điểm có cột (y) nào nhỏ hơn (pMinY), điểm nào có y lớn hơn (pMaxY). Vì khi xét trong phạm vi hình chữ nhật hoặc trên đường thẳng thì 2 điểm đều không đến được với nhau, do đó chúng ta mở rộng nó ra bằng cách xét về bên trái từ cột pMaxY.y (cột của điểm chứa cột lớn hơn) và về bên phải từ cột pMinY. Và cứ tăng hoặc giảm dần chỉ số cột lên khi 2 điểm (pMinY.x, y) và (pMaxY.x, y) không phải chướng ngại vật. Nếu gặp giá trị y nào mà làm cho đường thẳng đứng (màu xanh lục) được thông thì chứng tỏ đã tìm thấy đường đi. Khi đó hàm trả về giá trị là cột y tìm được, nếu không thì trả về -1. Tuy nhiên trước khi xét từng cột như vậy chúng ta cần xét đoạn từ pMinY đến pMaxY (doạn màu xanh lá) có thông không đã.

TH6: Xét mở rộng theo chiều dọc

Thực hiện hàm checkMoreLineY(Point p1, Point p2, int type) tương tự như trên nhưng duyệt theo từng hàng.

Các bạn chú ý là ta hoàn toàn có thể ghép các TH3,4,5,6 vào với nhau vì nó tương tự nhau, nhưng ở đây mình không làm vậy vì như nói ở trên là cần quá nhiều if, else để phân nhỏ nó ra các TH như thế này.

Một điều nữa là TH 5, 6 hoàn toàn có thể chứa đựng cả TH1,2,3,4 nhưng mình vẫn tách ra vì lý do là khi xét các TH1,2,3,4 trước thì chúng ta sẽ tìm được đường đi nhanh và ngắn nhất giữa 2 điểm (nếu có), còn nếu gộp lại thì chúng ta lại không tìm được đường đi ngắn nhất nếu có đường hình chữ U thoả mãn được xét trước.

Cuối cùng chúng ta sẽ viết hàm checkTwoPoint(Point p1, Point p2) để kiểm tra và tìm đường đi gữa 2 điểm p1, p2 bất kỳ. Hàm sẽ trả về đối tượng là MyLine gồm 2 điểm p1 và p2. Trong TH đường thẳng giữa 2 điểm p1, p2 được thông thì trả về MyLine gồm p1 và p2, trong TH đường đi là gấp khúc thì trả về MyLine gồm 2 điểm ở đoạn gấp khúc.

Màn hình chính của Game Pokemon

Cài đặt

package nguyenvanquan7826;

import java.awt.Point;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Algorithm {
    private int size = 5;
    private int barrier = 2;
    private int[][] matrix;

    public Algorithm() {
        readFile();
        showMatrix();
        System.out.println(checkTwoPoint(new Point(2, 2), new Point(4, 4))
                .toString());
    }

    // read matrix from file input
    private void readFile() {
        File fileInput = new File(getClass().getResource(
                "/nguyenvanquan7826/input").getFile());
        try {
            Scanner scan = new Scanner(fileInput);
            size = scan.nextInt();
            size += 2;
            matrix = new int[size][size];
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    matrix[i][j] = scan.nextInt();
                }
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    // show matrix
    private void showMatrix() {
        for (int i = 1; i < size - 1; i++) {
            for (int j = 1; j < size - 1; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    // check with line x, from column y1 to y2
    private boolean checkLineX(int y1, int y2, int x) {
        // find point have column max and min
        int min = Math.min(y1, y2);
        int max = Math.max(y1, y2);
        // run column
        for (int y = min; y <= max; y++) {
            if (matrix[x][y] == barrier) { // if see barrier then die
                System.out.println("die: " + x + "" + y);
                return false;
            }
            System.out.println("ok: " + x + "" + y);
        }
        // not die -> success
        return true;
    }

    private boolean checkLineY(int x1, int x2, int y) {
        int min = Math.min(x1, x2);
        int max = Math.max(x1, x2);
        for (int x = min; x <= max; x++) {
            if (matrix[x][y] == barrier) {
                System.out.println("die: " + x + "" + y);
                return false;
            }
            System.out.println("ok: " + x + "" + y);
        }
        return true;
    }

    // check in rectangle
    private int checkRectX(Point p1, Point p2) {
        // find point have y min and max
        Point pMinY = p1, pMaxY = p2;
        if (p1.y > p2.y) {
            pMinY = p2;
            pMaxY = p1;
        }
        for (int y = pMinY.y + 1; y < pMaxY.y; y++) {
            // check three line
            if (checkLineX(pMinY.y, y, pMinY.x)
                    && checkLineY(pMinY.x, pMaxY.x, y)
                    && checkLineX(y, pMaxY.y, pMaxY.x)) {

                System.out.println("Rect x");
                System.out.println("(" + pMinY.x + "," + pMinY.y + ") -> ("
                        + pMinY.x + "," + y + ") -> (" + pMaxY.x + "," + y
                        + ") -> (" + pMaxY.x + "," + pMaxY.y + ")");
                // if three line is true return column y
                return y;
            }
        }
        // have a line in three line not true then return -1
        return -1;
    }

    private int checkRectY(Point p1, Point p2) {
        // find point have y min
        Point pMinX = p1, pMaxX = p2;
        if (p1.x > p2.x) {
            pMinX = p2;
            pMaxX = p1;
        }
        // find line and y begin
        for (int x = pMinX.x + 1; x < pMaxX.x; x++) {
            if (checkLineY(pMinX.x, x, pMinX.y)
                    && checkLineX(pMinX.y, pMaxX.y, x)
                    && checkLineY(x, pMaxX.x, pMaxX.y)) {

                System.out.println("Rect y");
                System.out.println("(" + pMinX.x + "," + pMinX.y + ") -> (" + x
                        + "," + pMinX.y + ") -> (" + x + "," + pMaxX.y
                        + ") -> (" + pMaxX.x + "," + pMaxX.y + ")");
                return x;
            }
        }
        return -1;
    }

    /**
     * p1 and p2 are Points want check
     *
     * @param type
     *            : true is check with increase, false is decrease return column
     *            can connect p1 and p2
     */
    private int checkMoreLineX(Point p1, Point p2, int type) {
        // find point have y min
        Point pMinY = p1, pMaxY = p2;
        if (p1.y > p2.y) {
            pMinY = p2;
            pMaxY = p1;
        }
        // find line and y begin
        int y = pMaxY.y;
        int row = pMinY.x;
        if (type == -1) {
            y = pMinY.y;
            row = pMaxY.x;
        }
        // check more
        if (checkLineX(pMinY.y, pMaxY.y, row)) {
            while (matrix[pMinY.x][y] != barrier
                    && matrix[pMaxY.x][y] != barrier) {
                if (checkLineY(pMinY.x, pMaxY.x, y)) {

                    System.out.println("TH X " + type);
                    System.out.println("(" + pMinY.x + "," + pMinY.y + ") -> ("
                            + pMinY.x + "," + y + ") -> (" + pMaxY.x + "," + y
                            + ") -> (" + pMaxY.x + "," + pMaxY.y + ")");
                    return y;
                }
                y += type;
            }
        }
        return -1;
    }

    private int checkMoreLineY(Point p1, Point p2, int type) {
        Point pMinX = p1, pMaxX = p2;
        if (p1.x > p2.x) {
            pMinX = p2;
            pMaxX = p1;
        }
        int x = pMaxX.x;
        int col = pMinX.y;
        if (type == -1) {
            x = pMinX.x;
            col = pMaxX.y;
        }
        if (checkLineY(pMinX.x, pMaxX.x, col)) {
            while (matrix[x][pMinX.y] != barrier
                    && matrix[x][pMaxX.x] != barrier) {
                if (checkLineX(pMinX.y, pMaxX.y, x)) {
                    System.out.println("TH Y " + type);
                    System.out.println("(" + pMinX.x + "," + pMinX.y + ") -> ("
                            + x + "," + pMinX.y + ") -> (" + x + "," + pMaxX.y
                            + ") -> (" + pMaxX.x + "," + pMaxX.y + ")");
                    return x;
                }
                x += type;
            }
        }
        return -1;
    }

    private MyLine checkTwoPoint(Point p1, Point p2) {
        // check line with x
        if (p1.x == p2.x) {
            if (checkLineX(p1.y, p2.y, p1.x)) {
                return new MyLine(p1, p2);
            }
        }
        // check line with y
        if (p1.y == p2.y) {
            if (checkLineY(p1.x, p2.x, p1.y)) {
                return new MyLine(p1, p2);
            }
        }

        int t = -1; // t is column find

        // check in rectangle with x
        if ((t = checkRectX(p1, p2)) != -1) {
            return new MyLine(new Point(p1.x, t), new Point(p2.x, t));
        }

        // check in rectangle with y
        if ((t = checkRectY(p1, p2)) != -1) {
            return new MyLine(new Point(t, p1.y), new Point(t, p2.y));
        }
        // check more right
        if ((t = checkMoreLineX(p1, p2, 1)) != -1) {
            return new MyLine(new Point(p1.x, t), new Point(p2.x, t));
        }
        // check more left
        if ((t = checkMoreLineX(p1, p2, -1)) != -1) {
            return new MyLine(new Point(p1.x, t), new Point(p2.x, t));
        }
        // check more down
        if ((t = checkMoreLineY(p1, p2, 1)) != -1) {
            return new MyLine(new Point(t, p1.y), new Point(t, p2.y));
        }
        // check more up
        if ((t = checkMoreLineY(p1, p2, -1)) != -1) {
            return new MyLine(new Point(t, p1.y), new Point(t, p2.y));
        }
        return null;
    }
}