Archived

This topic is now archived and is closed to further replies.

Kung Fu Coder: Season 1

This topic is 5672 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello all, My latest foe is a graphics algorithm I am trying to render. Paraphrased from Interactive Computer Graphics by Edward Angel: generate a simple NxM maze with a rectangular array of cells. Each cell has four sides. Remove the sides (except from the perimeter of all the cells), until all the cells are connected. Then create an entrance and an exit by removing two sides from the perimeter. Write a program that takes as input the two integers N and M and draws an NxM maze. Do I create a path-finding algorithm for the maze, or do I step through the 2d array within a while/for loop? How do I check to see that every cell is connected to each other? Trust me... this program will throw you for a loop. I''m just looking for a way to bring it to pass. No spoilers please - this kung fu coder must learn himself. But I need illumination. Thanks in advance for any help. -slippersk2

Share this post


Link to post
Share on other sites
I haven''t made line-mazes, but block-mazes. There is a good old algorithm by someone from the DOS-days, I cannot remember his name ... any remarks are appreciated.

The thing is to "grow" walls. Walls are originated from seeds, which allows the walls to grow in only one direction. Scatter some seeds around the walls of the maze and perhaps a few in the maze. Then let them grow one step. At the end of the wall, seed three new seeds and let them grow. The growing continues until a wall is in the way.
Note that you can only seed walls at even coordinates. If you seed a wall in an odd coordinate, the walls might grow just beside each other. Not good...

Well, that''s the basic principle, and that''s what you wanted, right?

Share this post


Link to post
Share on other sites
Hey guys... his maze-generation algorithm is already established... that''s not the question.

>Do I create a path-finding algorithm for the maze? How do I
>check to see that every cell is connected to each other?

I''m not sure what you meant by stepping through the array, so I ignored that. But for the above two questions, I can tell you that question #1 is just a specialized case of question #2. This is an area where recursive algorithms can be elegant solutions. Also, do a little research on graph theory and graph traversal in particular. Your maze can be represented as a graph with MxN nodes.

I can also think of a very easy way to solve question #2 (and hence, #1 also) which is based on well-known maze generation algorithms and doesn''t involve any sort of hefty graph theory or recursion for that matter. I think in general if you just do a little more reading on maze generation and path-finding you will figure it all out. This is a very old topic in computer science!

Let me know if you need more hints than that.

-Bryan



Share this post


Link to post
Share on other sites