🔒 Recursive Backtracking

[split cradle]

My A-Level project is going to be a Maze generator using recursive backtracking and then a pathfinder, but I've read so many docs about recursive backtracking but i can't seem to understand it properly.

[gleaming geode]

@split cradle

Python help channel opened

Remember to:

• Ask your Python question, not if you can ask or if there's an expert who can help.
• Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
• Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.

[formal prawn]

Do you understand recursion at all. Like have you ever used it before @split cradle

[split cradle]

yes

minimax algorithm and quick sort

[formal prawn]

Ah okay

And I don’t think either of those use backtracking

[split cradle]

yeah they don't, you asked if i've ever used recursion

[formal prawn]

I know what I asked I was just talking to myself

[split cradle]

oh oh okay

[formal prawn]

Backtracking is essentially just using recursion to go “all-in” on a solution, and then trying different solutions from the point where the old solution goes bad or could have failed

I’m guessing you need backtracking because your algorithm may generate an invalid maze or something and you need to correct that?

[split cradle]

i think its when the cell has no "unvisited neighbours"

[formal prawn]

How does the algorithm work, like how are you generating a maze

[split cradle]

choose a point, mark it as visited, choose a unvisited neigbiour and break the wall between them

[formal prawn]

So you start with a fully closed off grid

Walls between each cell

[split cradle]

yes

[formal prawn]

Yeah alright I see where the backtracking is

Once you find no unvisited neighbors, you will return from the most recent recursive call

Which will put you in the second to last recursive call

Where you now continue on a different path as if nothing happened

How are you representing this grid and walls

And what questions do you have

[split cradle]

1 being walls, and 0 being the empty places, and it's represented with a 2d array

[split cradle]

first of all the grid layout, do i just start with all walls(1's) or do i need the empty places there as well (0's)

[formal prawn]

I’d start with a single 0 in like the top left

[split cradle]

so that corner would look like this?

1 1
1 0```

[formal prawn]

Something important if you do that setup: you won’t be checking cells that are directly next to each other

[split cradle]

yeah would have to check 2 cells away

[formal prawn]

Yes if you want 1s surrounding the whole thing

[formal prawn]

Yup exactly

[split cradle]

yeah gonna have to

[formal prawn]

In this case your walks won’t be thin

They will be 1 tile thick

Which is fine

[split cradle]

how do you mean

[formal prawn]

One of these is a thin walled maze

Where the walls don’t take up a tile

Your maze will be like the green

[split cradle]

ohhh, okay, yeah that's not a problem

im going to represent it on turtle anyways, so i can change the width

[formal prawn]

But you can’t

[split cradle]

oh

[formal prawn]

The walls have to be as think as a tile

[split cradle]

alrightm either way, not a problem

[formal prawn]

Because your walls are not between times

Gotcha

Also you need to leave openings

[split cradle]

maze = [
        [1,1,1,1,1,1,1,1,1],
        [1,0,1,0,1,0,1,0,1],
        [1,1,1,1,1,1,1,1,1],
        [1,0,1,0,1,0,1,0,1],
        [1,1,1,1,1,1,1,1,1],
        [1,0,1,0,1,0,1,0,1],
        [1,1,1,1,1,1,1,1,1],
        [1,0,1,0,1,0,1,0,1],
        [1,1,1,1,1,1,1,1,1]
        ]
visited = [
        [1,1,1,1,1,1,1,1,1],
        [1,False,1,False,1,False,1,False,1],
        [1,1,1,1,1,1,1,1,1],
        [1,False,1,False,1,False,1,False,1],
        [1,1,1,1,1,1,1,1,1],
        [1,False,1,False,1,False,1,False,1],
        [1,1,1,1,1,1,1,1,1],
        [1,False,1,False,1,False,1,False,1],
        [1,1,1,1,1,1,1,1,1]
        ]```

this was my original setup

[formal prawn]

I would start with a single 0

And if a cell is a 0 it’s visited

You only need 1 2d array

[split cradle]

ohh right

[formal prawn]

See how your visited array matches your other array

[split cradle]

and for a 4x4 maze, the array would need to be 9x9 right

[formal prawn]

Yeah that’s why having thick walls can make your arrays quite big

But it’s alright

[split cradle]

so how can i make it with thin walls

[formal prawn]

Imagine your maze starts as a grid

With thin walls

A 4x4 maze starts as a 4x4 array

0s can represent cells completely surrounded with walls

1s can mean left side is open

2s can mean top is open

6s can mean top and bottom is open etc

More complicated, and I think thick wall is fine

[split cradle]

would thick walls get more complicated with user defined width and height

[formal prawn]

The arrays will still be small compared to what your computer can handle

No

[split cradle]

okay

[formal prawn]

It’s just a formula

x2 + 1

Like for a 4x4

4x2 +1 is 9

[split cradle]

oh yeah fair enough

thanks for your help

[formal prawn]

No problem you can dm if you have more questions

Or make another thread

[split cradle]

alright, appreciate it

[gleaming geode]

Python help channel closed for inactivity

This help channel has been closed. Feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.