java - 自动迷宫解决方案

Question

所以我正在创建一个迷宫应用程序(我从迷宫的字符串数组中读取，然后通过触摸事件引导球穿过它)。到目前为止设法创建了所有内容，该应用程序运行良好。但我想包括一个自动解决它的选项。

我正在使用此处找到的递归算法:https://en.wikipedia.org/wiki/Maze_solving_algorithm

基本上，我在 boolean 多维数组(具有迷宫大小)中获取路径。

试图实现类似 MWC 的设计，所以我有以下类:

LabyrinthView - 处理与绘制迷宫和绘制球相关的一切 LabyrinthModel - 初始化迷宫，处理球的运动，我也在此处检查迷宫的尽头，并在此处实现 recursiveSolve 以 LabyrinthActivity - 这是我将所有东西放在一起的地方

就像我说的那样，手动解决迷宫非常有效。 不知道如何为自动解决方案设置动画。 那么让我给你一个迷宫的例子:

<string-array name="labyrinthEasy">
    <item>0000000001</item>
    <item>0111110110</item>
    <item>0100000110</item>
    <item>0101111000</item>
    <item>0101000010</item>
    <item>0101011010</item>
    <item>0101011110</item>
    <item>0101000010</item>
    <item>0101111010</item>
    <item>0100000010</item>
    <item>0111111110</item>
    <item>1000000000</item>
</string-array>

它看起来像这样(E-Entry，F-finish):

解决方案:

这是我到目前为止的进展:

private void selectControlMode() {
    final CharSequence[] items = {"Human","Machine"};
    final AlertDialog.Builder alertDialog = new AlertDialog.Builder(this);
    alertDialog.setItems(items, new DialogInterface.OnClickListener() {
        @Override
        public void onClick(DialogInterface dialog, int which) {
            switch (which) {
                case 0:
                    dialog.dismiss();
                    break;
                case 1:
                    dialog.dismiss();
                    boolean temp;
                    temp = labyrinthModel.solveMaze();
                    if(temp){
                        new MazeSolver().execute();
                    }else{
                        AlertDialog.Builder builder = new AlertDialog.Builder(getApplicationContext());
                        builder.setMessage("The maze is unsolvable!");
                        builder.setPositiveButton("OK", new DialogInterface.OnClickListener() {
                            @Override
                            public void onClick(DialogInterface dialog, int which) {
                                switch (which) {
                                    case 0:
                                        dialog.dismiss();
                                        Intent intent1 = new Intent(LabyrinthActivity.this, MainActivity.class);
                                        intent1.addFlags(Intent.FLAG_ACTIVITY_CLEAR_TOP);
                                        startActivity(intent1);
                                        break;
                                }
                            }
                        });
                        AlertDialog alert = builder.create();
                        alert.show();
                    }
                    break;
            }
        }
    });

}

基本上，我会在对话中选择人工和机器解决问题。如果选择了 human，则处理对话框和无(应用程序继续并等待手动解决方案)。如果选择了机器，我会得到路径，如果可以解决，我想我应该在这里启动一个新线程，在那里我可以为自动解决方案设置动画，否则如果无法解决，我将返回到应用程序的主菜单。现在我的问题开始了，因为我真的不知道如何在我的 AsyncTask 类中实现它。

我在 doInBackgroung 方法中执行逻辑，但无法弄清楚如何遵循正确路径的逻辑。因为如果我逐行遍历数组，球会从一行跳到另一行，并且不会跟随路径的流动性。 此外，我认为我应该在每次迭代后使用 onProgressUpdate 方法重新绘制我的进度。

这就是我的手动逻辑的工作方式(移动和绘图):

    labyrinthView.setOnTouchListener(new View.OnTouchListener() {
        float x1 = 0, x2 = 0, y1 = 0, y2 = 0;
        float dx, dy;
        @Override
        public boolean onTouch(View v, MotionEvent event) {
            float MIN_DIST = 5;
            switch (event.getAction()){
                case (MotionEvent.ACTION_DOWN):
                    x1 = event.getX();
                    y1 = event.getY();
                    break;
                case (MotionEvent.ACTION_UP):
                    x2 = event.getX();
                    y2 = event.getY();
                    dx = x2-x1;
                    dy = y2-y1;
                    Log.v("log", dx + " " + dy);
                    if(Math.abs(dx) > MIN_DIST || Math.abs(dy) > MIN_DIST){
                        if (Math.abs(dx) > Math.abs(dy)){
                            if(dx > 0) {
                                labyrinthModel.right();
                                finishMessage();
                            }
                            else {
                                labyrinthModel.left();
                                finishMessage();
                            }
                        }else{
                            if(dy > 0) {
                                labyrinthModel.down();
                                finishMessage();
                            }
                            else {
                                labyrinthModel.up();
                                finishMessage();
                            }
                        }
                    }
                    break;
            }
            labyrinthView.invalidate();
            return true;
        }


    });

这是我到目前为止在我的异步任务中所做的:

private class MazeSolver extends AsyncTask<Void,Void,Void>{
    @Override
    protected Void doInBackground(Void... params) {
        for ( int row = 0; row < labyrinthModel.correctPath.length; row ++)
            for ( int col = 0; col < labyrinthModel.correctPath[0].length; col++ ){
                if(labyrinthModel.correctPath[row][col + 1]){
                    labyrinthModel.moveRight();
                }
//here to do the implementaion of the path following logic???

            }
        return null;
    }

    @Override
    protected void onProgressUpdate(Void... values) {
// here to redraw the progress ????
        super.onProgressUpdate(values);
    }

    @Override
    protected void onPostExecute(Void aVoid) {
        super.onPostExecute(aVoid);
    }
}

如果您能指出正确的方向，我将不胜感激。

Answer 1

鉴于您可以覆盖信号二维数组的路径，您只需要从头到尾跟随根:

travel(correctPath, 0, 0, 11, 8);

void travel(bool a[][], int row, int col, int finalRow, int finalCol) {
   // if we are already there stop
   if(finalRow == row && col == finalCol) return;

   // avoid comming back
   a[row][col]=false;

   // if the input is correct only on of this moves will be valid
   // try each of them and see which move we can make
   if(col - 1 >= 0 && a[row][col-1]) { left(); travel(a, row, col-1, finalRow, finalCol)};
   if(col + 1 < 8 && a[row][col+1]) { right(); travel(a, row,col+1, finalRow, finalCol)};
   if(row - 1 >= 0 && a[row-1][col]) { up(); travel(a, row-1, col, finalRow, finalCol)};
   if(row + 1 < 11 && a[row+1][col]) { down(); travel(a, row+1,col, finalRow, finalCol)};
}