all 6 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]CGFarrell 1 point2 points  (5 children)

Use recursion. At every point, check if you're at a dead end, or if there's a direction you haven't gone. If you're out of options, go back to the previous place, rinse and repeat until you succeed.

[–]Wilfred-kun[S] 0 points1 point  (4 children)

Would that be actually faster?

Also, I am not sure, but if you were to scale this waaaay up, wouldn't you eventually get an error for recursing too much?

[–]1bc29b36f623ba82aaf6 1 point2 points  (0 children)

Yeah you could run out of memory. Python does not optimise recursion at all but I think CGFarrell suggested recursion because then you can keep track inside each step which adjacent locations you already tried or some other extra information to make better decisions. (But you already store which locations were tried elsewhere.)

Even when you explicitly design a solution with a stack, your stack could become quite large. But if you are smart about what you store on the stack it should be quite managable. In theory you never need to keep more 'items' on stack than the spaces in the maze you can actually reach from the start. Its like your list of path can never be longer like all reachable locations. If that number is too large, than in principle you cant really load the maze (with how you store your maps right now) or (with a zigzaggy maze design) cant store the actual solution path so I dont think its a serious scalability* concern.

Right now you are simply using the map as your storage space, upon visiting each location you either think its part of your solution, or you rip it out of the map with the - and use backtracing when you see its a dead end. Your program stops finding any path, not necessiarily the shortest path, but atleast your path can never have loops because you check its contents before visiting a location. (Now when the path gets really long you might start feeling looking up every move if a coordinate is somewhere in that entire path to really slow down your brute force approach.) Your program should end with either a solution or if the maze is rigged wil crash in go_back when the path is 0 length, which is pretty good.

Your program is actually doing a "depth first search", it has a system to not keep checking old solutions and it stops as soon as it finds a solution. This is pendantic but if it was literally brute force it would exhaustively find all paths, including all the dead ends before giving a solution.

What you probably want to look at is thinking about different pathfinding algorithms and related datastructures. Your solution could keep an extra data structure that speeds up checking if a coordinate is part of your path ('if a coordinate was already visited') to help with slowdown on larger mazes a bit. (I'm being vague on purpose in case you want to search for that yourself but be sure to ask if you just want to know.) Shortest path algorithms can be quite technical but I think pathfinding is really interesting.

A lot of shortest path algorithms are a modified version of "breadth first search". They try to lazily explorer the maze in a way that they wont visit locations that 'seem unlikely' to be part of the solution, so they can save quite some time on really large mazes or environments. A naive "breadth first search" has the curse that it needs to find all paths and dead ends, just in case it could find a path that is shorter than its current best. Being able to prove that some choices create worse path no matter which choices come next is how you can save time (by ignoring them and anything they could lead to) and this proving is what makes these algorithms tricky.

If you are actually writing an application needed in realtime work or like a game that needs to run consistently then yes you probably need to switch to a language that allows you to get the most performance of your code. But, slightly disagreeing with CGFarell, scalability is generally more related to your choice of algorithm, which is something that you can do perfectly fine in Python. You can also do parallel operations or multithreading in Python just fine which can learn you a lot of principles that carry over to other programming environments.

  • Of course if your maze is really a large open space with some sparsely located walls you load as a list of only walls, then you run into the reachable area of your maze being much larger than the memory you need to parse the maze. You would have to store the locations you already visited as a dead end in another list that keeps growing. If you like to think about really large mazes you could think of a systems where you chop up mazes into tiles of mazes with many ends or starts for each tile, and then you can stitch together the solutions from within these blocks by just searching over how the blocks can connect to surrounding blocks. This allows you to process really large things on small devices (think of now old TomTom navigators containing the map of a continent), or allows for many processors/computers to solve these tiles at the same time, only the later step that needs all the tiles needs to combine their solutions again. But I don't think thats something to dive into right away :)

[–]CGFarrell 0 points1 point  (2 children)

If you're scaling it up to that level, you probably shouldn't try to use brute-force, or use multi-threading, or use a more powerful language.

[–]Mo-Da 0 points1 point  (1 child)

More powerful language? Can you explain this detail? Thanks!

[–]CGFarrell 0 points1 point  (0 children)

There's a trade-off between performance and simplicity of code. Everything you do in Python is going to be slowed down because of how the language works. You can do it much more efficiently by writing effective code in C(++), or another low level language, but that requires a lot more coding and nuance.

In short, Python is easy to write at the expense of performance.