POV-Ray : Newsgroups : povray.advanced-users : Recursive Backtracker Maze Algorithm Server Time
19 Apr 2024 08:31:36 EDT (-0400)
  Recursive Backtracker Maze Algorithm (Message 1 to 3 of 3)  
From: Bald Eagle
Subject: Recursive Backtracker Maze Algorithm
Date: 11 Sep 2023 17:00:00
Message: <web.64ff7f7e33513f7c1f9dae3025979125@news.povray.org>
So, since I got the A* pathfinding algorithm to function, I figured that I ought
to have a maze generator to go along with it.

I got most of the thing coded and sort of working by last night, and then spent
~3h today after work trying to puzzle out where the rest of it was going wrong.

1. The &'s and |'s in POV-Ray's #if statements ALL get evaluated, so if you want
#if something
(then)
#if something else

then it needs to be coded that way instead of #if (S & SE)

2. I think I missed a few lines of code, because the guy's live-coding screen
real estate sucks, and he's really loosey-goosey with RT explanations, and
moving forward at a pretty good clip with the copy-paste

3. I believe that maybe the bitwise_and and bitwise_or may work differently in
POV-Ray than in c++, since I seemed to be getting cross-talk in the logic he was
using with the values 1, 2, 4, 8, and 10.
So I switched the last to 16 and all was well.

AFAIK, we don't have any base-conversion functions, keywords, or macros in the
distribution, and I could swear that I wrote some decimal to binary and back
conversion macros - but I can't find them and had to write another one from
scratch to verify the behaviours of the bitwise operators.

4. I had to write my own stack to push and pop from, and thankfully there wasn't
any dynamic resizing of the c++ "vector" he was using.
I also had trouble with the modulo method he was using to select a random
element of the vector, so I used RRand from rand.inc.

5. I'm still not sure how the algorithm "erases" walls, and if that's the issue
I'm having with the "islands" in the maze - drawing on a canvas and
instantiating primitives in 3D space are fundamentally different operations.

https://www.youtube.com/watch?v=Y37-gB83HKE
https://github.com/OneLoneCoder/Javidx9/blob/master/ConsoleGameEngine/SmallerProjects/OneLoneCoder_Mazes.cpp


Anyway, here's a maze in a 50 x 50 grid.  Enjoy.

- BW


Could be cool to do some movie/video scenes featuring mazes
Labyrinth
Harry Potter and the Goblet of Fire
Hellbound: HellRaiser II
Katy Perry - Wide Awake
The Shining
Pan's Labyrinth

etc.


Post a reply to this message


Attachments:
Download 'mazemaker.png' (116 KB)

Preview of image 'mazemaker.png'
mazemaker.png


 

From: Bald Eagle
Subject: Re: Recursive Backtracker Maze Algorithm
Date: 11 Sep 2023 21:50:00
Message: <web.64ffc31714defef41f9dae3025979125@news.povray.org>
"Bald Eagle" <cre### [at] netscapenet> wrote:

> 5. I'm still not sure how the algorithm "erases" walls, and if that's the issue
> I'm having with the "islands" in the maze - drawing on a canvas and
> instantiating primitives in 3D space are fundamentally different operations.

Because I'm STOOOOPID.
It's really easy to invert the meaning of things, and look at the inverse of a
maze.
After watching the relevant portion and paying very careful attention to the all
to brief explanation, I did a few experiments that highlighted the issue, and
let me unravel everything so that I now have proper, algorithm-correct,
fully-internally-connected mazes.

Here's 100 by 100.  I've already tried a 500 x 500, which is 250,000 cells, and
it works, but I'd have to render it a bit bigger than usual to have it show up
clearly.


Post a reply to this message


Attachments:
Download 'mazemaker.png' (22 KB)

Preview of image 'mazemaker.png'
mazemaker.png


 

From: Bald Eagle
Subject: Re: Recursive Backtracker Maze Algorithm
Date: 11 Sep 2023 22:30:00
Message: <web.64ffccbc14defef41f9dae3025979125@news.povray.org>
"Bald Eagle" <cre### [at] netscapenet> wrote:

> Here's 100 by 100.

"Maybe I'll solve this tomorrow..."
Pffft.  We all know better than that, right?

A* solver took 4 min 5 sec to solve the maze.

- BW


Post a reply to this message


Attachments:
Download 'a-star image.png' (81 KB)

Preview of image 'a-star image.png'
a-star image.png


 

Copyright 2003-2023 Persistence of Vision Raytracer Pty. Ltd.