/**
 * 自定義的Drawable，類似于AnimationDrawable
 */
public class MyDrawable extends Drawable implements Cloneable {

    private final int mDelay;//幀延時(shí)
    private final byte[] mLock;//控制線程暫停的鎖
    private Semaphore mSemaphore;//來(lái)用控制線程更新問(wèn)題
    private Bitmap[] mBitmaps;//幀
    private Paint mPaint;
    private int mCurrentIndex;//當(dāng)前幀索引
    private float x, y;//當(dāng)前坐標(biāo)
    private Future mTask;//幀動(dòng)畫(huà)播放的任務(wù)
    private volatile boolean isPaused;//已暫停

    public MyDrawable(int delay, Bitmap... bitmaps) {
        mSemaphore = new Semaphore(1);
        mBitmaps = bitmaps;
        mDelay = delay;
        mPaint = new Paint();
        mPaint.setAntiAlias(true);
        mLock = new byte[0];
    }

    public void start() {
        stop();
        mTask = ThreadPool.getInstance().execute(() -> {
            while (true) {
                synchronized (mLock) {
                    while (isPaused) {
                        try {
                            mLock.wait();
                        } catch (InterruptedException e) {
                            return;
                        }
                    }
                }
                try {
                    Thread.sleep(mDelay);
                } catch (InterruptedException e) {
                    return;
                }
                try {
                    mSemaphore.acquire();
                } catch (InterruptedException e) {
                    return;
                }
                mCurrentIndex++;
                if (mCurrentIndex == mBitmaps.length) {
                    mCurrentIndex = 0;
                }
                mSemaphore.release();
            }
        });
    }

    void pause() {
        isPaused = true;
    }

    void resume() {
        isPaused = false;
        synchronized (mLock) {
            mLock.notifyAll();
        }
    }

    private void stop() {
        if (mTask != null) {
            mTask.cancel(true);
            mTask = null;
            mCurrentIndex = 0;
        }
    }

    @Override
    public void draw(@NonNull Canvas canvas) {
        try {
            mSemaphore.acquire();
        } catch (InterruptedException e) {
            return;
        }
        canvas.drawBitmap(mBitmaps[mCurrentIndex], x, y, mPaint);
        mSemaphore.release();
    }

    public void release() {
        stop();
        if (mBitmaps != null) {
            for (Bitmap bitmap : mBitmaps) {
                if (bitmap != null && !bitmap.isRecycled()) {
                    bitmap.recycle();
                }
            }
        }
        mBitmaps = null;
        mPaint = null;
        mTask = null;
    }

    public float getX() {
        return x;
    }

    public void setX(float x) {
        this.x = x;
    }

    public float getY() {
        return y;
    }

    public void setY(float y) {
        this.y = y;
    }

    public Bitmap getBitmap() {
        Bitmap result = null;
        if (mBitmaps != null && mBitmaps.length > 0) {
            result = mBitmaps[0];
        }
        return result;
    }

    @Override
    public int getIntrinsicWidth() {
        if (mBitmaps.length == 0) {
            return 0;
        }
        return mBitmaps[0].getWidth();
    }

    @Override
    public int getIntrinsicHeight() {
        if (mBitmaps.length == 0) {
            return 0;
        }
        return mBitmaps[0].getHeight();
    }

    @Override
    public void setAlpha(int alpha) {
        mPaint.setAlpha(alpha);
    }

    @Override
    public void setColorFilter(ColorFilter cf) {
        mPaint.setColorFilter(cf);
    }

    @Override
    public int getOpacity() {
        return PixelFormat.TRANSLUCENT;
    }

    @SuppressWarnings("MethodDoesntCallSuperMethod")
    public MyDrawable clone() {
        return new MyDrawable(0, mBitmaps[0]);
    }
}

public class PathAnimation {

    private Keyframes mPathKeyframes;//關(guān)鍵幀
    private long mAnimationDuration;//動(dòng)畫(huà)時(shí)長(zhǎng)
    private OnAnimationUpdateListener mOnAnimationUpdateListener;//動(dòng)畫(huà)更新監(jiān)聽(tīng)
    private AnimationListener mAnimationListener;//動(dòng)畫(huà)事件監(jiān)聽(tīng)
    private volatile boolean isAnimationRepeat, //反復(fù)播放的動(dòng)畫(huà)
            isAnimationStopped,//已停止
            isAnimationCanceled, //已取消 (停止和取消的區(qū)別: 取消是在動(dòng)畫(huà)播放完之前主動(dòng)取消的,  停止是動(dòng)畫(huà)播放完,自動(dòng)停止的)
            isAnimationEndListenerCalled;//動(dòng)畫(huà)已取消的監(jiān)聽(tīng)已經(jīng)回調(diào)

    PathAnimation(MyPath path) {
        updatePath(path);
    }

    public PathAnimation setDuration(long duration) {
        mAnimationDuration = duration;
        return this;
    }

    void updatePath(MyPath path) {
        //根據(jù)系統(tǒng)版本選擇更合適的關(guān)鍵幀類
        mPathKeyframes = Build.VERSION.SDK_INT >= Build.VERSION_CODES.LOLLIPOP ? new PathKeyframes(path) : new PathKeyframesSupport(path);
    }

    OnAnimationUpdateListener getUpdateListener() {
        return mOnAnimationUpdateListener;
    }

    void setUpdateListener(OnAnimationUpdateListener listener) {
        mOnAnimationUpdateListener = listener;
    }

    /**
     * 設(shè)置動(dòng)畫(huà)是否重復(fù)播放
     */
    public PathAnimation setRepeat(boolean isAnimationRepeat) {
        this.isAnimationRepeat = isAnimationRepeat;
        return this;
    }

    boolean isAnimationRepeat() {
        return isAnimationRepeat;
    }

    AnimationListener getAnimationListener() {
        return mAnimationListener;
    }

    void setAnimationListener(AnimationListener listener) {
        mAnimationListener = listener;
    }

    void start() {
        if (mAnimationDuration > 0) {
            ThreadPool.getInstance().execute(() -> {
                isAnimationStopped = false;
                isAnimationCanceled = false;
                isAnimationEndListenerCalled = false;
                final long startTime = SystemClock.uptimeMillis();
                long currentPlayedDuration;//當(dāng)前動(dòng)畫(huà)已經(jīng)播放的時(shí)長(zhǎng)
                if (mAnimationListener != null) {
                    mAnimationListener.onAnimationStart();
                }
                while ((currentPlayedDuration = SystemClock.uptimeMillis() - startTime) < mAnimationDuration) {
                    //如果動(dòng)畫(huà)被打斷則跳出循環(huán)
                    if (isAnimationInterrupted()) {
                        break;
                    }
                    //根據(jù)當(dāng)前動(dòng)畫(huà)已經(jīng)播放的時(shí)長(zhǎng)和總動(dòng)畫(huà)時(shí)長(zhǎng)計(jì)算出當(dāng)前動(dòng)畫(huà)的播放進(jìn)度
                    float progress = (float) currentPlayedDuration / (float) mAnimationDuration;
                    if (mOnAnimationUpdateListener != null) {
                        if (!isAnimationInterrupted()) {
                            mOnAnimationUpdateListener.onUpdate(progress, mPathKeyframes.getValue(progress));
                        }
                    }
                }
                if (isAnimationRepeat && !isAnimationInterrupted()) {
                    //如果是設(shè)置了重復(fù)并且還沒(méi)有被取消,則重復(fù)播放動(dòng)畫(huà)
                    mPathKeyframes.reverse();
                    if (mAnimationListener != null) {
                        mAnimationListener.onAnimationRepeat();
                    }
                    start();
                } else {
                    isAnimationStopped = true;
                    if (mAnimationListener != null) {
                        //判斷應(yīng)該回調(diào)哪一個(gè)接口
                        if (isAnimationCanceled) {
                            mAnimationListener.onAnimationCanceled();
                        } else {
                            mAnimationListener.onAnimationEnd();
                        }
                    }
                    //標(biāo)記接口已回調(diào)
                    isAnimationEndListenerCalled = true;
                }
            });
        }
    }

    /**
     會(huì)阻塞,直到動(dòng)畫(huà)真正停止才返回
     */
    private void waitStopped() {
        isAnimationStopped = true;
        //noinspection StatementWithEmptyBody
        while (!isAnimationEndListenerCalled) {
        }
    }

    /**
     會(huì)阻塞,直到動(dòng)畫(huà)真正取消才返回
     */
    private void waitCancel(){
        isAnimationCanceled = true;
        //noinspection StatementWithEmptyBody
        while (!isAnimationEndListenerCalled) {
        }
    }

    void stop() {
        waitStopped();
    }

    void cancel() {
        waitCancel();
    }

    /**
     動(dòng)畫(huà)被打斷
     */
    private boolean isAnimationInterrupted() {
        return isAnimationCanceled || isAnimationStopped;
    }

    public interface OnAnimationUpdateListener {
        void onUpdate(float currentProgress, PointF position);
    }

    public interface AnimationListener {
        void onAnimationStart();//動(dòng)畫(huà)開(kāi)始

        void onAnimationEnd();//動(dòng)畫(huà)結(jié)束

        void onAnimationCanceled();//動(dòng)畫(huà)取消

        void onAnimationRepeat();//動(dòng)畫(huà)重復(fù)播放
    }
}

    0   0   0   0   0   0   0   0   0
      0   0   0   0   0   0   0   0   0
    0   0   0   0   0   0   0   0   0
      0   0   0   0   0   0   0   0   0
    0   0   0   0   0   0   0   0   0
      0   0   0   0   0   0   0   0   0
    0   0   0   0   0   0   0   0   0
      0   0   0   0   0   0   0   0   0
    0   0   0   0   0   0   0   0   0

    0   0   0   0   0   0   0   0   0
      0   0   0   0   0   0   0   0   0
    0   0   0   0   2   2   0   0   0
      0   0   0   2   1   2   0   0   0
    0   0   0   2   0   2   0   0   0
      2   0   2   0   2   0   0   0   0
    2   0   0   0   0   0   0   0   0
      0   2   2   2   2   0   0   0   0
    0   2   0   0   0   0   0   0   0

    先傳入這個(gè)狀態(tài)數(shù)組和當(dāng)前小豬的坐標(biāo);
    創(chuàng)建一個(gè)List<List<Point>>，存放出路，名字就叫做footprints吧;
    創(chuàng)建一個(gè)隊(duì)列，這個(gè)隊(duì)列存放待查找的點(diǎn);
    當(dāng)前小豬的坐標(biāo)先放進(jìn)footprints;
    當(dāng)前小豬的坐標(biāo)入隊(duì);
    標(biāo)記小豬坐標(biāo)已經(jīng)走過(guò);
    進(jìn)入循環(huán) (循環(huán)條件就是隊(duì)列不為空){
        創(chuàng)建一個(gè)臨時(shí)的footprints;(因?yàn)樽疃嗫赡苡?個(gè)新的路徑)
        隊(duì)頭出隊(duì);
        尋找周?chē)?個(gè)方向(上，下，左，右，左上，右上，左下，右下)可以到達(dá)的位置 (不包括越界的、標(biāo)記過(guò)的、不是空閑的);
        遍歷這個(gè)可到達(dá)位置的數(shù)組{
            遍歷footprints{
                檢查隊(duì)頭的坐標(biāo)是否跟footprints的元素(List<Point>)的最后一個(gè)元素(Point)的位置(x,y)是一樣的(即可以鏈接)
                (比如: 現(xiàn)在footprints是[[(5,5), (5,4)], [(6,5), (6,4)]]，隊(duì)頭的坐標(biāo)是(5,4), 那可達(dá)位置的數(shù)組就可能是[(5,3), (5,5), (4,4), (4,5), (6,4), (6,5)]){
                    則創(chuàng)建一個(gè)新的List<Point>;
                    add footprints的元素(比如: [(5,5), (5,4)]);
                    再add可達(dá)位置的坐標(biāo)(比如： (5，3);
                    臨時(shí)的footprints add 這個(gè)新的List (那臨時(shí)的footprints現(xiàn)在就是 [[(5,5), (5,4), (5，3)]]了);
                }                 
            }
            檢查本次可達(dá)位置的坐標(biāo)是否已經(jīng)是在邊界 (已經(jīng)找到出路){
                footprints add 臨時(shí)的footprints的元素;
                遍歷footprints{
                    判斷footprints的元素的最后一位是否邊界位置{
                        return 這個(gè)footprints的元素; (必然是最短的路徑);
                    }
                }
            }
            隊(duì)列入隊(duì)本次可達(dá)位置的坐標(biāo);
        }
        (本次沒(méi)有找到出路) footprints addAll 臨時(shí)的footprints的元素，準(zhǔn)備下一輪循環(huán);
    }
    執(zhí)行到了這里， 即表示沒(méi)有出路， 如果footprints里面是空的話，我們直接返回null,如果不為空，就返回footprints最后一個(gè)元素，即能走的最長(zhǎng)的一條路徑;

    public static List<WayData> findWay(int[][] items, WayData currentPos) {
        //獲取數(shù)組的尺寸
        int verticalCount = items.length;
        int horizontalCount = items[0].length;
        //創(chuàng)建隊(duì)列
        Queue<WayData> way = new ArrayDeque<>();
        //出路
        List<List<WayData>> footprints = new ArrayList<>();
        //復(fù)制一個(gè)新的數(shù)組 （因?yàn)橐獦?biāo)記狀態(tài)）
        int[][] pattern = new int[verticalCount][horizontalCount];
        for (int vertical = 0; vertical < verticalCount; vertical++) {
            System.arraycopy(items[vertical], 0, pattern[vertical], 0, horizontalCount);
        }
        //當(dāng)前坐標(biāo)入隊(duì)
        way.offer(currentPos);
        //添加進(jìn)集合
        List<WayData> temp = new ArrayList<>();
        temp.add(currentPos);
        footprints.add(temp);
        //標(biāo)記狀態(tài) （已走過(guò)）
        pattern[currentPos.y][currentPos.x] = STATE_WALKED;

        while (!way.isEmpty()) {
            //隊(duì)頭出隊(duì)
            WayData header = way.poll();
            //以header為中心，獲取周?chē)梢缘竭_(dá)的點(diǎn)（即未被占用，未標(biāo)記過(guò)的）（這個(gè)方法在獲取到可到達(dá)的點(diǎn)時(shí)，會(huì)標(biāo)記這個(gè)點(diǎn)為: 已走過(guò)）
            List<WayData> directions = getCanArrivePos(pattern, header);
            //創(chuàng)建臨時(shí)的footprints
            List<List<WayData>> footprintsTemp = new ArrayList<>();
            //遍歷可到達(dá)的點(diǎn)
            for (int i = 0; i < directions.size(); i++) {
                WayData direction = directions.get(i);

                for (List<WayData> tmp : footprints) {
                    //檢查是否可以鏈接
                    if (canLinks(header, tmp)) {
                        List<WayData> list = new ArrayList<>();
                        list.addAll(tmp);
                        list.add(direction);
                        footprintsTemp.add(list);
                    }
                }
                //檢查是否已達(dá)到邊界
                if (isEdge(verticalCount, horizontalCount, direction)) {
                    if (!footprintsTemp.isEmpty()) {
                        footprints.addAll(footprintsTemp);
                    }
                    //返回最短的出路
                    for (List<WayData> tmp : footprints) {
                        if (!tmp.isEmpty() && isEdge2(verticalCount, horizontalCount, tmp)) {
                            return tmp;
                        }
                    }
                }
                //本次未找到出路，入隊(duì)這個(gè)可到達(dá)的點(diǎn)
                way.offer(direction);

            }
            //準(zhǔn)備下一輪循環(huán)
            if (!footprintsTemp.isEmpty()) {
                footprints.addAll(footprintsTemp);
            }
        }
        //沒(méi)有出路，返回能走的最長(zhǎng)的一條路徑;
        return footprints.isEmpty() ? null : footprints.get(footprints.size() - 1);
    }

    /**
     尋找周?chē)?個(gè)方向可以到達(dá)的位置(不包括越界的,標(biāo)記過(guò)的,不是空閑的)
     */
    public static List<WayData> getCanArrivePos(int[][] items, WayData currentPos) {
        int verticalCount = items.length;
        int horizontalCount = items[0].length;
        List<WayData> result = new ArrayList<>();
        int offset = currentPos.y % 2 == 0 ? 0 : 1, offset2 = currentPos.y % 2 == 0 ? 1 : 0;
        for (int i = 0; i < 6; i++) {
            WayData tmp = getNextPosition(currentPos, offset, offset2, i);
            if ((tmp.x > -1 && tmp.x < horizontalCount) && (tmp.y > -1 && tmp.y < verticalCount)) {
                if (items[tmp.y][tmp.x] != Item.STATE_SELECTED && items[tmp.y][tmp.x] != Item.STATE_OCCUPIED && items[tmp.y][tmp.x] != STATE_WALKED) {
                    result.add(tmp);
                    items[tmp.y][tmp.x] = STATE_WALKED;
                }
            }
        }
        //打亂它，為了讓方向順序不一樣, 即每次都不同
        Collections.shuffle(result);
        return result;
    } 

    /**
     根據(jù)當(dāng)前方向獲取對(duì)應(yīng)的位置
     */
    private static WayData getNextPosition(WayData currentPos, int offset, int offset2, int direction) {
        WayData result = new WayData(currentPos.x, currentPos.y);
        switch (direction) {
            case 0:
                //左
                result.x -= 1;
                break;
            case 1:
                //左上
                result.x -= offset;
                result.y -= 1;
                break;
            case 2:
                //左下
                result.x -= offset;
                result.y += 1;
                break;
            case 3:
                //右
                result.x += 1;
                break;
            case 4:
                //右上
                result.x += offset2;
                result.y -= 1;
                break;
            case 5:
                //右下
                result.x += offset2;
                result.y += 1;
                break;
        }
        return result;
    }

    0   0   0   0   0   0   0   0   0
      0   0   0   0   0   0   0   0   0
    0   0   0   0   2   2   0   0   0
      0   0   0   2   1   2   0   0   0
    0   0   0   2   *   2   0   0   0
      2   0   2   *   2   0   0   0   0
    2   *   *   *   0   0   0   0   0
      *   2   2   2   2   0   0   0   0
    0   2   0   0   0   0   0   0   0