Need help making a maze AI

SacredBlood

Hi! I need to code my sprite so that it can solve any maze with a click of a button. I can't control it with the arrow keys or anything. It has to automatically make it's way through any maze. The amount of time it needs to do this can be any time (preferably no longer than an hour).

I had this idea to make the sprite just follow the left or right wall through out the entire maze, but I can't seem to get it to work. I've tried other things like making another sprite with hidden sensors to help it navigate the maze but it would always get stuck whenever all 4 directions were open or when it hit a dead end.

I feel like making it follow the left or right wall would be the easiest, but how do I do that? I'm not looking for something too complex and perfect, I just want something that works and is simple. Any help is appreciated!

mstone326

I made a very primitive maze solver a while back, I'll try to find it. I threw it together quickly for fun so it isn't ideal but it would eventually work as long as the paths weren't angled.

I made a variable that had 4 directions. So the sprite would repeat in that direction until touching the wall. Then it would test all directions to see if it could move in that way, if it passed the test, it would repeat moving that direction until touching the wall. I didn't make any specific arguments or anything as far as not going in the direction it just went. I'll try to find it.

It really isn't a good method but works and simple.

Edit:

Here it is. Its ugly but will work. https://scratch.mit.edu/projects/100383463

Last edited by mstone326 (Feb. 5, 2017 21:32:25)

SacredBlood

mstone326 wrote:
I made a very primitive maze solver a while back, I'll try to find it. I threw it together quickly for fun so it isn't ideal but it would eventually work as long as the paths weren't angled.

I made a variable that had 4 directions. So the sprite would repeat in that direction until touching the wall. Then it would test all directions to see if it could move in that way, if it passed the test, it would repeat moving that direction until touching the wall. I didn't make any specific arguments or anything as far as not going in the direction it just went. I'll try to find it.

It really isn't a good method but works and simple.

How do you make a variable that can make the sprite read 4 directions (Left, Right, Up, Down)? Also, did you have it so that when it touches a wall it gets sent backwards a little then turns around and moves in the first direct it finds empty?

If you could find that maze solver you made previously, that would be greatly appreciated!

I need this for a bigger project I'm doing.

mstone326

Each path option 1,2,3,4 will stand for say right, left, up, down. Note that this maze has no backtracking going to the left so I eliminated that route for this simple project.

It also just picks random directions so the code is not ideal. It should test which is the best route to go and should not choose a route it just came from unless all other routes have been tested and then it could backtrack.

Last edited by mstone326 (Feb. 5, 2017 21:36:32)

SacredBlood

mstone326 wrote:
Each path option 1,2,3,4 will stand for say right, left, up, down. Note that this maze has no backtracking going to the left so I eliminated that route for this simple project.

It also just picks random directions so the code is not ideal. It should test which is the best route to go and should not choose a route it just came from unless all other routes have been tested and then it could backtrack.

I see what you mean. I'm just having a hard time figuring out how to code it, I have many concepts in mind, but just don't know how to apply them.

mstone326

Start small. Path finding isn't always simple. If you are new to scratch keep the scope of your project small and try many different types of projects that can enhance your skills.

What type of project are you trying to make?

gtoal

SacredBlood wrote:
Hi! I need to code my sprite so that it can solve any maze with a click of a button. I can't control it with the arrow keys or anything. It has to automatically make it's way through any maze. The amount of time it needs to do this can be any time (preferably no longer than an hour).

I had this idea to make the sprite just follow the left or right wall through out the entire maze, but I can't seem to get it to work. I've tried other things like making another sprite with hidden sensors to help it navigate the maze but it would always get stuck whenever all 4 directions were open or when it hit a dead end.

I feel like making it follow the left or right wall would be the easiest, but how do I do that? I'm not looking for something too complex and perfect, I just want something that works and is simple. Any help is appreciated!

https://scratch.mit.edu/projects/20727676/

SacredBlood

gtoal wrote:
https://scratch.mit.edu/projects/20727676/

Hi! Thank you for your reply. Your project is quite extraordinary, but I'm just a beginner to Scratch and coding as a whole and I don't understand the code behind it even after an hour or 2 of playing around with it and looking at it. Is there any way to maybe simplify your maze solver by making my sprite just follow the right or left wall throughout the entire thing? I'm looking for something simple first, then I'll expand on it from there as I further my understanding of Scratch.

mstone326

The simplest option is probably the random direction option I sent you earlier. I have some free time this morning around 11, it is 8am my time now. I'll see if I can throw something together quickly that is a little less random than my option above but is simple to understand.

gtoal

SacredBlood wrote:
gtoal wrote:
https://scratch.mit.edu/projects/20727676/

Hi! Thank you for your reply. Your project is quite extraordinary, but I'm just a beginner to Scratch and coding as a whole and I don't understand the code behind it even after an hour or 2 of playing around with it and looking at it. Is there any way to maybe simplify your maze solver by making my sprite just follow the right or left wall throughout the entire thing? I'm looking for something simple first, then I'll expand on it from there as I further my understanding of Scratch.

The algorithm for solving a maze that's used here is actually simpler than wall following. Look at the block called “Solve” - that's the only one in the project that is relevant and it is quite short.

create an empty list called ‘queue’, and create an array the size of the maze called ‘visited’ - one entry for each location - and set all the locations to 0.

You start at the first square (add its location to the queue), then repeat the code below until you are at the last square:

for each of the immediately adjacent squares, add the location of those squares to the end of the queue - IF it hasn't already been added to the queue. (You keep track of what has been added by marking an item in the ‘visited’ array with a 1 .)

now take the first item from the start of the queue, and go round this loop again.

This is called a ‘breadth first search’ as you are examining (at the head of the queue) the locations nearest you first and working your way out in a circle from there. As soon as the expanding circle of visited locations touches the target, you've found the maze exit with the shortest path.

There is a little bit of a trick to this implementation - it actually finds the path by starting at the exit and finishing at the start! That is because what I actually did was instead of marking the ‘visited’ array with 0's and 1's, I marked each item with the location of the previous item. So for example square 56 might point back to square 46. The reason for this is to record the path back from square to square (as well as recording if a square has been visited already, so we don't handle the same square twice). Fortunately there is no square 0 in Scratch (all the arrays start at 1) so making ‘visited’ 0 or non-0 works just as well as making it 0 or 1, and we get to store the path back to where we started almost for free. That's a bit tricky to follow I know, but it's worth the effort to simplify the program.

So by reversing the path we created (in the visited array) we backtrack from the goal to the start - which since I actually created the path back to front by starting the search from the exit, means it lists the path from the actual true start to the final target. (That's the little loop that does the glide)

I hope that explains how the program works, well enough for you to write one like it yourself. If not, have a look around with Google for “breadth first search algorithm” and see if someone else can explain it better for you.

G

titanscratch

This is the easiest script I can think of:

when [ v] key pressed // any key
forever
repeat until <touching color [#000000] ?> // the colour of the walls
move (1) steps
end
set [variable 1 v] to (pick random (1) to (2)) // you will have to create a variable
if <(variable 1) = [1]> then
turn left (90) degrees
else
turn right (90) degrees
end
end

Last edited by titanscratch (Feb. 7, 2017 19:20:09)

zuckoids

this was really helpful thanks boiz!

midnightfever47258

I agree

Wainggan

midnightfever47258 wrote:
I agree

Don't necropost.

thiccccmilk

bruh, I am doing this for a school project and the maze ai is too old. does anyone have the code with a website whose link actually works?I tried using the way back machine and pated the url the last archive of the url was june 13 2022 and no one has accessed it so whenever i try to load up information the code is in html and way too long to read.

Last edited by thiccccmilk (March 5, 2023 10:27:43)

ventoaurum

thiccccmilk wrote:
bruh, I am doing this for a school project and the maze ai is too old. does anyone have the code with a website whose link actually works?

just make the bot follow the left wall

thiccccmilk

i have tried and i am way too dumb to do this also easier said then done.

ventoaurum

thiccccmilk wrote:
i have tried and i am way too dumb to do this also easier said then done.

“easier said than done”?
yeah, for you it is. for me i literally cant help you in any other way but saying the algorithm because you didnt link the project bruhh

IOFUN2

mstone326 wrote:
I made a very primitive maze solver a while back, I'll try to find it. I threw it together quickly for fun so it isn't ideal but it would eventually work as long as the paths weren't angled.

I made a variable that had 4 directions. So the sprite would repeat in that direction until touching the wall. Then it would test all directions to see if it could move in that way, if it passed the test, it would repeat moving that direction until touching the wall. I didn't make any specific arguments or anything as far as not going in the direction it just went. I'll try to find it.

It really isn't a good method but works and simple.

Edit:

Here it is. Its ugly but will work. https://scratch.mit.edu/projects/100383463

the project dont exist

IOFUN2

titanscratch wrote:

This is the easiest script I can think of:

when [ v] key pressed // any key
forever
repeat until <touching color [#000000] ?> // the colour of the walls
move () steps // steps taken
end
if <(pick random (1) to (2) = [1]> then
turn left (90) degrees
else
turn right (90) degrees
end
end

tysm

Last edited by IOFUN2 (July 4, 2024 17:12:38)

Discuss Scratch