Automatic Maze Solution

Question

So, I’m creating an application for the maze (I read from the array of lines in the maze, and then directs the ball through it using touch events). I managed to create everything so far, the application works fine. But I want to enable the option for its automatic solution.

I use this recursive algorithm found here: https://en.wikipedia.org/wiki/Maze_solving_algorithm

Basically I get the path in a boolean multidimensional array (which has the size of a maze).

Tried to achieve MWC design, so I have the following classes:

LabyrinthView - handles everything related to drawing a maze and draws a ball LabyrinthModel - initializes the maze, controls the movement of the ball, I also check the end of the maze here and implemented the recursive series here LabyrinthActivity - this is where I put it all together

As I said, manually solving the maze works like a charm. I don’t know how to revive an automatic solution. So let me give you an example of a maze:

<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>

It will look something like this (E-Entry, F-finish):

And the solution:

Here's how I got so far:

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;
            }
        }
    });

}

. , ( ). , , , , , , , , . , , 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;
        }


    });

, assync-:

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)};
}