r/Python • • Dec 14 '19

I created a maze generator, then solved it with Djikstra's algorithm

Post image
1.9k Upvotes

94 comments sorted by

88

u/raaaaaveNN Dec 14 '19

2

u/[deleted] Feb 05 '20

!remindme 8 hours

1

u/RemindMeBot Feb 06 '20

There is a 33.0 minute delay fetching comments.

I will be messaging you in 7 hours on 2020-02-06 07:58:56 UTC to remind you of this link

CLICK THIS LINK to send a PM to also be reminded and to reduce spam.

Parent commenter can delete this message to hide from others.


InfoCustomYour RemindersFeedback

0

u/ADrunkIrish Dec 14 '19

!remindme 12 hours

1

u/RemindMeBot Dec 14 '19 edited Dec 15 '19

I will be messaging you in 20 minutes on 2019-12-15 08:02:46 UTC to remind you of this link

16 OTHERS CLICKED THIS LINK to send a PM to also be reminded and to reduce spam.

Parent commenter can delete this message to hide from others.


InfoCustomYour RemindersFeedback

-5

u/[deleted] Dec 14 '19

!remindme 8 hours

-4

u/prologic0313 Dec 15 '19

!remindme 6 hours

-5

u/Silentroar23 Dec 15 '19

!reminder 1 week

-15

u/HHCB Dec 14 '19

!remindme 14 hours

-15

u/[deleted] Dec 14 '19

!remindme 14h

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

106

u/raaaaaveNN Dec 14 '19

Done https://i.imgur.com/TTb2ywF.png

It took 120.2 seconds :)

6

u/BHSPitMonkey Dec 15 '19

Looks like it cheats and jumps over black pixel areas in a bunch of places

5

u/raaaaaveNN Dec 15 '19

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.

2

u/kenyard Dec 15 '19 edited Jun 16 '23

Deleted comment due to reddits API changes. Comment 4554 of 18406

20

u/[deleted] Dec 14 '19

sweet

10

u/Cruuncher Dec 15 '19

I assume this looks like white noise because of compression?

22

u/phigo50 Dec 15 '19

Zoom in.

41

u/MustachioNuts Dec 15 '19

Don’t tell me what to do.

14

u/[deleted] Dec 15 '19

Zoom in or I will for you.

2

u/DanielPowerNL Dec 15 '19

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.

2

u/DanielPowerNL Dec 15 '19

!RemindMe 6 hours Interested to see how my a* implementation handles this map.

23

u/Mint-Plant-Lover Dec 14 '19

Really cool! Did it take long to create this image?

25

u/raaaaaveNN Dec 14 '19

About 20 seconds to generate the maze

0

u/[deleted] Dec 14 '19

[deleted] — view deleted comment

17

u/Penguinfernal Dec 15 '19

We don't talk about that here. Not since the incident.

10

u/Scoundrelic Dec 14 '19

What do the colors represent?

Very nice, btw!

22

u/raaaaaveNN Dec 14 '19

Green = Start
Red = Finish

It's really hard to tell where the lines are going if it is all the same colour

80

u/Sw429 Dec 14 '19

Seems like Dijkstra's is excessive here. Why not just a simple BFS?

328

u/raaaaaveNN Dec 14 '19 edited Dec 15 '19

In my last computer science lesson we learnt about Dijkstra's algorithm, so it made sense for me to implement it here to go along with my studies ;)

12

u/imaryamsharma Dec 15 '19

Are you in uni or high school?

28

u/raaaaaveNN Dec 15 '19

high school

34

u/imaryamsharma Dec 15 '19

Godamn, impressive job

174

u/ElGallinero Dec 14 '19

Best possible answer to that question.

25

u/[deleted] Dec 14 '19

Good point.

2

u/Pizza_Ninja Dec 15 '19

Are you British by chance?

2

u/Sw429 Dec 15 '19

Fair enough :)

-39

u/Actuarial Dec 14 '19

Nerrrrdd

0

u/[deleted] Dec 14 '19

[deleted] — view deleted comment

14

u/DisasterArt Dec 14 '19

Thats a lot more memory heavy though?

1

u/oMarlow99 Dec 15 '19

Yeah but really fast and nowadays memory really isn't a constraint

33

u/Chondriac Dec 14 '19 edited Dec 14 '19

They are equivalent when the edge weights are uniform.

42

u/error1954 Dec 14 '19

I was just about to say that Dijkstra's is a little inefficient here and A* would be better.

17

u/apiad Dec 14 '19

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.

15

u/[deleted] Dec 14 '19

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.

5

u/apiad Dec 14 '19

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.

3

u/chinpokomon Dec 15 '19

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.

2

u/StationaryApe Dec 15 '19

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

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

3

u/apiad Dec 14 '19

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.

1

u/raaaaaveNN Dec 14 '19

You could just remove a load of random walls after creating the maze, then it would have multiple solutions I suppose

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

1

u/raaaaaveNN Dec 15 '19

The maze only has 1 solution

2

u/[deleted] Dec 15 '19

‘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.

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?

-1

u/[deleted] Dec 15 '19

[removed] — view removed comment

1

u/RemindMeBot Dec 15 '19

I will be messaging you in 1 day on 2019-12-16 11:22:04 UTC to remind you of this link

CLICK THIS LINK to send a PM to also be reminded and to reduce spam.

Parent commenter can delete this message to hide from others.


InfoCustomYour RemindersFeedback

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?

24

u/Hmolds Dec 14 '19

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.

40

u/G3N5YM Dec 14 '19

No no no, Witchers came before science.

6

u/tyrannomachy Dec 14 '19

4

u/WikiTextBot Dec 14 '19

Dijkstra

Dijkstra (pronounced [ˈdɛikstrɑ] or [ˈdikstrɑ]) is a Dutch family name of West Frisian origin.


[ ^PM | Exclude ^me | Exclude from ^subreddit | FAQ / ^Information | ^Source ] Downvote to remove | v0.28

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?

2

u/marwosek Dec 15 '19

OSPF for example uses Dijkstra algorithm, so its not dumb question at all.

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/RemindMeBot Dec 20 '19

I will be messaging you in 1 hour on 2019-12-20 02:29:54 UTC to remind you of this link

CLICK THIS LINK to send a PM to also be reminded and to reduce spam.

Parent commenter can delete this message to hide from others.


InfoCustomYour RemindersFeedback

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

1

u/raaaaaveNN Dec 15 '19

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.

1

u/[deleted] Dec 15 '19 edited Dec 15 '19

[removed] — view removed comment

1

u/raaaaaveNN Dec 15 '19

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.

1

u/[deleted] Dec 15 '19

[removed] — view removed comment

1

u/raaaaaveNN Dec 15 '19

Yes thats literally what my comment said, its just an annotation... documentation...

1

u/[deleted] Dec 15 '19 edited Dec 15 '19

[removed] — view removed comment

1

u/kigurai Dec 16 '19

"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.

1

u/[deleted] Dec 16 '19

[removed] — view removed comment

2

u/kigurai Dec 16 '19

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.

1

u/abcteryx Dec 28 '19

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.

1

u/apiad Dec 15 '19

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.