Python Maze

Question

Lets say i have a maze on a 10x10 grid. And you can only visit blocks on the maze once. How can I check if there are dead ends?

example: (1s are walls, 0s are walkable squares, 3 is a finish )

1111111111111111111
0000000001
1111111111111111111

this is what a dead end looks like.

11111111111111111111
00000000031
11111111111111111111

this is not a dead end beacause you can reach the finish

Answer 1

Your entire grid (including char position) is stored inside of the array, so you can iterate through it and have it check that way. Just define what you consider to be a dead end. For example, is dead end any 1 that only has one 0 next to it and the rest 1s? Is a dead end any wall that you try to run in to? You could create a function that checks each direction from any given coordinate and see what's within 1 position proximity of it. So if it's all 1s, that means it's an inner wall that has no access to it at all. If it has only one 0 and the rest are 1s, then it's your typical maze dead end. If it has two 0s and rest are 1s, then maybe you're in a hallway. If it's nothing but 0s then maybe you're in an open area or outside. etc....

Get what I mean? Just iterate through the array and you can have it check the surrounding (as explained in my original post) tiles relative to the current iteration (coordinate). If you keep some sort of counter, you could calculate exactly how many dead ends exist in your maze. You could even create another array that stores the coordinates of each one it finds also, then you'll have a list of their locations as well.

Answer 2

Conceptually, since you didn't provide code and supplied just a general question, you'll just check to see if the coord in the direction you're trying to move is equal to 1. If it is, prevent movement, otherwise move your character there. Assuming your grid is stored in a 2D array, think of the first index as the row and second index as the column. So moving to the right is a +1 to the column, left is -1. Moving down is +1 to the row, moving up is -1. Using that concept you can check the surrounding possible positions and see what they contain so that you know which directions are possible to move in. As well, you can use same thing to check for any other condition, such as finish.

Answer 3

Btw, if you want to post up the code you're working on, we can help you more specifically than conceptually.

Answer 4

Jakko Jak that explanation was perfect, thank you, I could post the code but it's a bit long, and making it short would be quite hard cause of pygame and that sort of stuff, but if you don't mind looking into long codes iam all for it

Answer 5

Jakko Jak https://github.com/KirillVidov/AI-Snake.git this is the code, what iam trying to do is to visit every square exactly once on a grid, everything is working, is just that it takes way too long to complete, and i dont know how to reduce time

Answer 6

Okay, no worries. I'm at work right now, but when I get home I'll download it and see what I can do to help you out.

Answer 7

Jakko Jak its all good now, I solved the time complexity problem by assigning each square a weight every time a mistake happens and always choosing the neighbor with the lowest weight

Answer 8

Jakko Jak yeha I get that, but what if want to see if there are dead ends in the maze without moving my character

Answer 9

You're more than welcome Kirill. I sit around reading through long code all the time, so that's no problem. If it's something like that though, and you wanted me to help with any of it, just upload to Google Drive (or something like that) and I can just download it from there. Just let me know and happy to help/collab on whatever.

Answer 10

Jakko Jak is it fine if I post it here or github?

Answer 11

Kirill Vidov Yeah, that's fine. Post it up in whatever way you want and I'll check back shortly for it.

Answer 12

Jakko Jak sorry if the code is rough

Answer 13

Jakko Jak much appreciated, thank you