LOS追跡

照準（Line-of-Sight: LOS）法を使った追跡アルゴリズムを実装してみます。環境はタイルベースです。LOS法を使うと獲物に対して最短経路（つまり直線）で移動できます。最短経路を求めるためにブレゼンハムアルゴリズム（2005/4/2）を使います。獲物（青い点）は矢印キーで動かせます。追跡者から獲物への最短経路は黄色い点で表示されてます。単純な追跡アルゴリズムと経路を比べてみてください。

los.jar

ブレゼンハムによる経路設定

ブレゼンハムアルゴリズムは始点と終点間を結ぶ直線を求めるアルゴリズムです。直線は2点間の最短経路です。つまり、この直線上をたどって獲物を追いかければ最短経路で追いかけることになります。直線の始点は追跡者の位置、終点は獲物の位置です。まず、ブレゼンハムアルゴリズムを使って直線の座標を求めます。Predatorクラスの buildPathTo()がそうです。

    /**
     * 獲物までの追跡経路をブレゼンハムアルゴリズムで求める
     * 
     * @param prey 獲物
     */
    public void buildPathTo(Prey prey) {
        // 経路が再計算されるのでカレントステップは初期化
        currentStep = 1;

        if (x == prey.x && y == prey.y) return;

        int nextX = x;
        int nextY = y;
        int deltaX = prey.x - x;
        int deltaY = prey.y - y;
        int stepX, stepY;
        int step;
        int fraction;

        for (step = 0; step<MAX_PATH_LENGTH; step++) {
            path[step] = null;
        }

        step = 0;

        if (deltaX < 0) stepX = -1; else stepX = 1;
        if (deltaY < 0) stepY = -1; else stepY = 1;

        deltaX = Math.abs(deltaX * 2);
        deltaY = Math.abs(deltaY * 2);

        path[step] = new Point(nextX, nextY);
        step++;

        if (deltaX > deltaY) {
            fraction = deltaY - deltaX / 2;
            while (nextX != prey.x) {
                if (fraction >= 0) {
                    nextY += stepY;
                    fraction -= deltaX;
                }
                nextX += stepX;
                fraction += deltaY;
                path[step] = new Point(nextX, nextY);
                step++;
            }
        } else {
            fraction = deltaX - deltaY / 2;
            while (nextY != prey.y) {
                if (fraction >= 0) {
                    nextX += stepX;
                    fraction -= deltaY;
                }
                nextY += stepY;
                fraction += deltaX;
                path[step] = new Point(nextX, nextY);
                step++;
            }
        }
    }

このメソッドはPredatorクラスのメソッドなので追跡者の位置はわかってます。獲物（Prey）の位置がわからないと直線はひけませんので引数にPreyを渡してます。直線上のピクセルの座標はpath[]に入ります。詳しくはブレゼンハムアルゴリズム（2005/4/2）の解説を参考にしてください。

LOS追跡は獲物に対してまっすぐ追跡する方法です。先ほど獲物への直線を求めてpathへ入れたのでこのpathをたどれば追跡できます。PredatorクラスのchaseByLOS()を見てください。

    /**
     * LOS追跡
     * 
     * @param prey 獲物
     */
    public void chaseByLOS(Prey prey) {
        if (path[currentStep] == null) return;

        x = path[currentStep].x;
        y = path[currentStep].y;
        currentStep++;
    }

path[]から呼び出した座標をPredatorの位置座標（x, y)にセットしています。chaseByLOS()が1回呼び出されると獲物をめがけて1歩だけ進みます。currentStepは何歩移動したかをあらわす変数です。次に、メソッドを使うところです。MainPanelクラスのrun()を見てください。

    public void run() {
        while (true) {
            // 追跡者は獲物を追いかける
            predator.chaseByLOS(prey);
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

            repaint();
        }
    }

スレッドでrun()が呼ばれるたびに追跡者は獲物に向けて1歩だけ移動します。

経路の再計算

ブレゼンハムアルゴリズムで求めた最短経路は獲物が移動してしまったら再計算しないといけません。獲物はあなたがキーボードで動かしているので keyPressed()で経路を再計算しています。

    /**
     * キー操作で獲物を動かす
     */
    public void keyPressed(KeyEvent e) {
        ・・・

        // 獲物が動くとパスは再計算される
        predator.buildPathTo(prey);

        repaint();
    }