Maze - Artificial Intelligence

Mathematics ScratchVeryHard

In this lesson we will program a sprite to figure out how to navigate a maze using random decision making and we will time the beetle to see how fast it can complete the maze.

1

Create a new Scratch project

Create a new Scratch project and delete the cat.


2

Add the maze sprite

Save the maze picture in this step to your computer and upload it into Scratch as a new sprite. Once it appears, drag it into the center of the stage area.


3

Add the beetle sprite

Add the beetle
Add the 'Beetle' sprite from the sprite library. Drag the beetle to the start of the maze (the gap at the left of the maze).

Shrink the beetle
As the beetle sprite is too large to fit in the corridors of the maze, we'll need to add the following code to the beetle to shrink it:

when green flag clicked set size to (15) %

Position and point the beetle
Once you have added this code, click the green flag to shrink your beetle and then drag it to the start of the maze (near the bottom left of the maze). Now add the following code to your existing code block so that the beetle always starts in this location and is pointed in the right direction.

when green flag clicked set size to (15) % //add new code under here go to x(0) y(0)//set these to the start of the maze point in direction (0)



4

Edit the maze sprite

We need something at the exit of the maze that we can detect when our beetle sprite gets there, so we're going to add a small green circle by editing the maze. 

Click on the maze sprite in the sprite list below the stage area and then click on the 'Costumes' tab, this will open the sprite editor. To add a green circle follow these steps:

  1. Click on the Ellipse tool
  2. Click on the fill option button (this draws a shape that's filled in with the colour)
  3. Click on green in the color palette
  4. At the exit of the maze draw a circle by:
    - holding down the Shift button
    - and holding down the left click button
    - and dragging across to draw a circle
  5. Drag the circle to the exit of the maze

If you make a mistake just click the back button (a rounded arrow pointing left).


5

Create a steps variable

We're going to create and use a 'steps' variable for the amount of steps the beetle will take each time it moves. Create a new variable called 'steps' and add the following code:

when green flag clicked set size to (15) % go to x [0] y [0] point in direction (0)//add the code under here set [steps v] to (5) hide variable [steps v]

6

Set the pen colour

While our beetle is moving through the maze, we're going to get it to leave a trail behind to show what path it has taken.

We'll add the code for leaving the trail in a later step but right now we will set what colour the trail will be and also clear any trail from a previous go. 

First add the Pen extension to your toolbox.

Add the following code to your beetle at the bottom of the 'when green flag clicked' code block:

when green flag clicked set size to (15) % go to x [0] y [0] point in direction (0) set [steps v] to (5) hide variable [steps v]//add the code under here set pen color to [#FF0000] erase all

7

Start the beetle

Now we've setup everything we can start programming the beetle to move through the maze. First let's get it to move forward until it touches a wall. We'll start the beetle using the space bar button and also reset the timer (to 0).

Add the following code to the beetle:

when [space v] key pressed reset timer forever if < touching [maze v] >then else move (steps) steps pen down end end

Once you've added this code, click on the green flag and then press the space bar. Your beetle should move forward until it touches a wall and it should also draw a red line of it's path.


8

Turn a random direction

If the beetle walks into a wall, then it needs to choose a direction to turn and start walking again. We're going to program it to randomly choose either left (-90 degrees) or right (+ 90 degrees).

To make our code a bit easier to read we're going to create a custom 'turn' block that will have the code to choose the random direction.

Create a custom block called 'turn'. Once you've created it you will notice a large block called 'define turn' appears in the code area and a 'turn' block appears in the My Blocks palette. 

Add the following code to the 'define turn' block:

define turn if < (pick random (1) to (2)) = (1) > then // randomly turn left or right point in direction ((direction) - (90))// turn left else point in direction ((direction) + (90))// turn right end

9

Use the 'turn' block

Now that we have defined the instructions for our custom 'turn' block, we need to use the block somewhere in our code. We're going to add it to the 'if then else' block that detects if the beetle touches the maze.

Before we turn, we'll need to program the beetle to move backwards a small bit first and then turn, otherwise it will be constantly touching the wall.

To make the beetle move backwards, we will make it move:
steps x -2
If steps is set to 5 then the sum is:
5 x -2 = -10

Add the following code so that it runs if the beetle touches the maze:

when [space v] key pressed reset timer forever if < touching [maze v] >then // add code into here move ((steps) * (-2)) steps turn else move (steps) steps pen down end end

Once you've added this code, click the green flag and press the space bar again. If your beetle touches a wall, it should now move back a bit and then randomly turn before moving forward again. You've now programmed the beetle to work it's way through the maze!


10

Show the finishing time

In a previous step we started the timer by using the 'reset timer' block when we pressed the space bar. This sets the timer, which is running in the background, back to 0.

Now we want to add some code that detects if the beetle touches the green circle at the exit and shows us the finishing time for completing the maze.

Add the following to the bottom of the when green flag clicked block:

when green flag clicked set size to (15) % go to x [0] y [0] point in direction (0) set [steps v] to (5) hide variable [steps v] set pen color to [#FF0000] erase all//add the code under here forever if < touching color [#31B404] ? > then // the green of your green finishing circle move ((steps) * (-2)) steps say (join [woohoo I did it in ] (timer)) stop [other scripts in sprite v] end end

That's it, you've completed all the steps for the project. Click on the green flag and press the space bar to start your beetle. How quickly can it solve the maze?

11

Improve the intelligence of the beetle

It can take the beetle several minutes to complete the maze as it's not very intelligent. All it's doing to randomly turning left or right when it comes to a wall so it's just as likely to choose the wrong way as the right way.

Can you think of any ways you could program it to be more intelligent and solve the maze faster?

End of lesson
Copyright Notice
This lesson is copyright of Coding Ireland. Unauthorised use, copying or distribution is not allowed.

Scratch is developed by the Lifelong Kindergarten Group at the MIT Media Lab. It is available for free at https://scratch.mit.edu