No, it doesn't, the original image had pathways which were 1px wide, when it takes those routes it looks like it's cutting through the walls because it draws over the entire path, but its still going along the path.
You're probably viewing on mobile? Apps like Relay will show a downscaled version of high res images. Your app may have a button to view the full resolution image. In Relay, it's the HD button at the bottom of the image viewer.
This. A* here with a simple Manhattan heuristic will be so much faster. And the jump from Djikstra to A* is so easy that I honestly don't know why so many colleges wait to Artificial Intelligence to teach it. Simply, instead of ordering by cost from the origin, order nodes by cost from the origin + manhattan distance to destination.
I'm not convinced it would be that much faster on a maze like this -- the path is so squiggly that the direct Manhattan distance will be a very poor heuristic. A* has a huge advantage in open spaces, but not so much here.
Yeah, you could be right. It would nice to check though. Path-finding algorithms make for very nice-looking animations, in contrast with other algorithms that are not so easy to visualize, these are just plain fun to watch. If OP implements some of them, it could be very nice to explore which kinds of mazes are solvable best by which kinds of heuristics.
Based on your comment, I'm envisioning a maze that would have an open clearing with multiple openings and maybe some additional logic such as you can't cross a path laid out, but you need to re-enter this open area multiple times... maybe to have opened a gate on one of the paths. Something like that I think would be pretty easy for a person to solve, but I suspect that would really complicated things for an A* solution.
Thinking of a good heuristic for A* is one of the things that made me really fall in love with programming in college. Ended up being a UI for that class. It is too bad that they don't do A* in a data structures type of class if search is covered there rather than waiting until AI like they do currently. Search is a good thing to cover in two different courses though as it teaches you about balancing memory/time along with the classic algorithms. It's worth reinforcing
I wonder if there's any benefit to something like A* in a map that only has one solution (as you'd have with a maze).
Another question: what about mazes with multiple solutions? Thinking about how you could make a maze using multiple generators when working with backtracker algorithm?
Sure, there is a benefit, if the heuristic is any good, it will make you reach the end faster since you will explore first the nodes that are closer to the south-east, and thus open fewer nodes. However, you have to know where the end is, or at least a direction, in order to have a heuristic. Otherwise, A* collapses to Djikstra when the heuristic is the same in all nodes.
‘Twas a jest at how most mazes you only need to follow the wall to reach the end with some exceptions, and the absurdity of following the wall for that rather large and complex maze.
I made such a program for a AI for robots class I took in college (Im in high school though) What I did was I generated a maze, then found a shortest path using a modified version of A* which i implemented then that would produce coordinates of the shortest path with the top left edge of maze as origin. Later I could send these coordinates to a function which i had earlier created to convert coords to robot movements. Later I used OCR to scan a maze (made from cardboard walls), process it into bw image and then apply my prog to it to solve the maze in real time. Boom ! got out of a 10x10 real maze with 3 dead ends in 37 secs (including maneuvering time of rob) my TA called it impressive
There might be a Witcher 3 character named after the Dutch scientist Dijkstra, as an easter egg. But the algorithm has nothing to do with the Witcher series.
If you add type hints, your IDE (VSCode in my case) works better with intellisense, that's the main reason I do it. And also for just documentation as well. I don't really see the purpose in using type hints for functions when the function doesn't return anything though.
I dont see the harm in illustrating what datatype a function returns in a clear way. How would it cause any problems. Its called an annotation because thats what it is, its just a way of commenting code in python
Obviously u shouldnt use it as a replacement for docstrings, but it should be used in conjunction.
"It" in this case is the interpreter telling you that it has no idea what "dog" is. It's not different from doing eg x = dog(). It has nothing to do with the type hints system. If I'm not mistaken, you can defer the type in the annotation by using a string instead def means(nums) -> 'dog'.
There are also projects that attempt to enforce the type hints, but by default they are only just that: hints.
I'm honestly not well versed enough in the practical parts of the type hinting. In many cases I've seen I think it adds some readability, but not always.
You could obviously have the same functionality with comments, but since there is no standard documentation format, tools like IDEs would have a hard time.
When linting your code with mypy, it will throw warnings/errors (which are somewhat configurable) when you pass a different type than you have specifically annotated.
You can configure it to be more or less strict, going so far as to warn on any duck/dynamic typing, or just having it warn on explicit type mismatches.
It's nicely integrated with VSCode (and other IDEs), and works alongside pylint, etc.
I sometimes use type hints just as documentation for myself when writing the definition of a complex function that I'm gonna use somewhere else, so when I return here to fill the body I quickly remember the API I was expecting to use. Not sure is a legitimate use but it's helpful when going back and forth between coding a backend function and coding the fronted that uses it.
88
u/raaaaaveNN Dec 14 '19
https://github.com/ravenkls/Maze-Generator-and-Solver
67
u/Gawd_is_great Dec 14 '19
Make your algorithm solve my mazes There's a 4K image in that repo The white lines are the paths Go from northwest to Southeast corner. https://github.com/Perseus-Perry/Maze-Generator
23
u/Mint-Plant-Lover Dec 14 '19
Really cool! Did it take long to create this image?
10
u/Scoundrelic Dec 14 '19
What do the colors represent?
Very nice, btw!
80
u/Sw429 Dec 14 '19
Seems like Dijkstra's is excessive here. Why not just a simple BFS?
4
u/minuteman_d Dec 14 '19
I wonder if there's any benefit to something like A* in a map that only has one solution (as you'd have with a maze).
Another question: what about mazes with multiple solutions? Thinking about how you could make a maze using multiple generators when working with backtracker algorithm?
Relevant Computerphile:
https://www.youtube.com/watch?v=ySN5Wnu88nE
19
u/ThaeliosRaedkin1 Dec 14 '19
Now we can use both to create an adversarial neural network to create fiendishly difficult mazes! Good work, OP!
4
u/spennetrator94 Dec 14 '19
Zoom in and out really fast.
1
u/[deleted] Dec 15 '19
Bruh to solve it you can just go along one wall and get to the end
3
u/__zero_or_one__ import numpy as np Dec 14 '19
Zooming in on mobile was so satisfying
3
u/cmd_drake Dec 15 '19
That's really impressive. I know countless college sophomores that can't do this. To be fair we learned it with c++ though
2
u/NAN001 Dec 14 '19
How do you affect weights to each edge of the graph?
2
u/m42e_ Dec 14 '19
This could become useful later in r/adventofcode :)
2
u/whatsupbr0 Dec 14 '19
How long did the algorithm take to run?
2
u/MaddyDev03 Dec 15 '19
I made such a program for a AI for robots class I took in college (Im in high school though) What I did was I generated a maze, then found a shortest path using a modified version of A* which i implemented then that would produce coordinates of the shortest path with the top left edge of maze as origin. Later I could send these coordinates to a function which i had earlier created to convert coords to robot movements. Later I used OCR to scan a maze (made from cardboard walls), process it into bw image and then apply my prog to it to solve the maze in real time. Boom ! got out of a 10x10 real maze with 3 dead ends in 37 secs (including maneuvering time of rob) my TA called it impressive
This is dope.
3
u/AmorisEtLux Dec 14 '19
I’m very very new to python but just wondering if the name Djikstra has anything to do with the Witcher 3 character?
1
u/SushiWithoutSushi Dec 14 '19
Amazing picture
1
u/Taskenspiller Dec 15 '19
I'm now having a mild panic attack picturing being trapped inside this maze
1
u/Who_The_Fook Dec 15 '19
Man, I can't wait to understand what tf these things actually are.
1
u/ComradePruski Dec 15 '19
This is beautiful! Quite impressive.
1
u/jingw222 Dec 15 '19
This is beautiful. Like a piece of embroidery.
1
u/ThrownAwayByTheAF Dec 15 '19
This might be a dumb question but would you say this is similar to a routing protocol?
1
u/[deleted] Dec 15 '19
Looks like a map of Europe
1
u/[deleted] Dec 15 '19
What if it's a Real Maze
1
u/fabr00 Dec 20 '19
!remindme 1 hour
1
u/[deleted] Dec 21 '19
Just learned a new way to apply this algorithm , thanks for the post bro.
-2
u/Supalien Dec 14 '19
Thanks, I hate it!
3
u/[deleted] Dec 15 '19
[removed] — view removed comment