Timeline for Maze generator (backtracking algorithm)
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 17, 2022 at 7:56 | comment | added | scripter2021 | That's interesting... But I thought the my messy version was faster because I hardcoded some parts. I mean I had {'y': -2, 'half': 1} already in a memory, while calculating dig(row - dr // 2, col - d // 2) on every iteration takes some extra time. And other small things like this also decrease the speed. Btw I also made a super repetative version of my own code where I didn't use functions and rewrite the whole logic for every case (up, down, left, right). And such procedural-style code was the fastest. It took 12 seconds while the code I posted took 16 | |
| Aug 17, 2022 at 6:01 | comment | added | AJNeufeld | Using actual backtracking speeds things up substantially, but changes the flavour of the generated maze, so you may not want to use that. | |
| Aug 17, 2022 at 6:00 | history | edited | AJNeufeld | CC BY-SA 4.0 |
Added actual backtracking
|
| Aug 17, 2022 at 5:42 | comment | added | AJNeufeld | Unfortunately, I concur: rev6 (tuples, set, & removing dead-ends) is slower. As I said, that change needed to be profiled to determine if it held any improvement ... and it seems it does not. At least stopping at rev5, you got cleaner code which should be no slower than the original. | |
| Aug 17, 2022 at 5:32 | comment | added | AJNeufeld |
I'm surprised you find the cleaner code slower. I've run 300x300 ten times with the original code, and revisions 1 through 5, using the same random.seed() for each run, and found the best time over ten trials is consistently 2.8 seconds on my nothing-special laptop. With 500x500, the original ran at 9.8 seconds and revision 5 hit 9.3 seconds. With 600x600, both the original and rev5 ran at 16.4 seconds. The cleaned code is definitely not slower than the original. (Without setting the random seed, the algorithms run in non-deterministic times & cannot be compared.)
|
|
| Aug 16, 2022 at 10:21 | comment | added | scripter2021 | thank you for such a detailed answer! Now my code looks much cleaner. But... a bit slower :D 300x300 now takes ~6.1 seconds (was 4.52) and 500x500 takes ~20.85 (was 13.5). Using tuples and removing deadends from paths takes even more time - 150x150 takes ~4.4 seconds and 300x300 takes ~63 seconds. By the way I noticed that the less structured the code the faster it is. A very straight-forward and repetative code (not using functions, hardcoding values) gave e the best results :D | |
| Aug 14, 2022 at 20:09 | vote | accept | scripter2021 | ||
| Aug 14, 2022 at 18:05 | history | answered | AJNeufeld | CC BY-SA 4.0 |