Going through a set number of methods in a random order without repeating any

Newbie & Debugging Questions
#1

Hello!

I’m trying to make a program that generates a random labyrinth, I do this by using a Randomized Depth-First (se wikipedia, http://en.wikipedia.org/wiki/Maze_generation_algorithm , for the basic idea). I have just one problem, I want to be going in randomized directions but I don’t want the program to check the same direction twice. So I want it to pick a random direction and if that “cell” has already been visited (meaning there can’t be a path going from the current cell to that cell) then I want the program to check another direction from the current cell without ever checking the same direction again (since we know it’s unavailable).
One suggestion I was considering is to create a collection and mixing it with Collection.shuffle but I’ve never used collections before and I don’t know how to use that to make the program call 4 methods in a random order that way.
Anyone have a recommendation or a good trick I can use?

Thank you!

#2

I don’t know how you are representing directions, or check directions, etc, so here is a code sample, but read it for the algorithm, not the actual code. This is a simple methodology I employ for these type of problems. There are doubtlessly more efficient ways, but I wrote this for clarity:


enum Dirs {up,down,left,right;}
ArrayList<Dirs> availDirs = new ArrayList<Dirs>();
Random rand = new Random();

//Add available choices to the selection pool
if(upAvailable()) availDirs.add(Dirs.up);
if(downAvailable()) availDirs.add(Dirs.down);
if(leftAvailable()) availDirs.add(Dirs.left);
if(rightAvailable()) availDirs.add(Dirs.right);

//grab random element from available directions, assumes that there is at least one available 
Dirs dirToGo = availDirs.get(rand.nextInt(availDirs.size()));

//check dirToGo and proceed accordingly
...
#3

The algorithm you cited says to make a list of neighbors. I’m going to assume each location in the maze is a Cell object. So, how about an ArrayList of neighbor cells?.

ArrayList<Cell> neighborCells = new ArrayList<Cell>();

Once all the neighbor cells are added to the collection. It is very easy to randomize their order. Just use the following single line of code:


Collections.shuffle(neighborCells);

Then, to run methods in the random order, iterate through the list or use a for-each loop, e.g.:

for (Cell c: neighborCells)
{
    checkDirection(c);
}

I wanted to demonstrate how convenient Collections.shuffle() is to use.

#4

I’m not sure how fitting this is, but this iterates in a random order and is ridiculously fast even with 8000 elements (2.5 ms). I’m not the author.

#5

That doesn’t look efficient at all. Collections.shuffle() runs in linear time while the one you suggested looks, to me, to run at BEST in linear time.

#6

Well I can’t tell but it’s said to be tested with 8000 elements and finished in 2.5 ms.

#7

If you look at the code, it gets increasingly slower the further you get into calling next().

#8

You’re right. I’ll tell the author. Probably I shouldn’t throw around pieces of code that are just said to be fast as well.

#9

You are over complicating things. Just get every unvisited neighbor and Push them onto a Stack in a random order. You will only have four neighbors maximum (or three if you start on an edge) so you can use a fixed size array to hold elements before putting them on the Stack. Use Knuth’s Array Shuffling Algorithm to randomize the order.

You use a Stack because it is a First-In-First-Out structure and a Depth-First-Search explores the most recently expanded nodes before going back to the old ones. Do this once at the starting point and over and over again in a loop until the Stack is empty.

Consult Wikipedia if you do not recognize these terms.