Constructing Maze by Clustering Algorithm

Japanese / English

Introduction

We introduce a method to construct maze which solution looks a picture.

Notice: The "Clastring" described here is not "Cluster analysis" in machine learning or data mining.


What is Clustering?

We often want to know properties of some network, such as webs or relation in Facebook, etc. Especially, the following properties are of interests.

The clustering algorithm is necessary to obtain such properties.

The clustering is some kinkds of grouping with equivalence relationships. The friend relationship consists a equivalence class with the folliwing definition,

"my friend's friend is also my friend."
For instance, if we know the following relations, we can obtain the following relation.
A clustering is a procedure to group from some relations. It is often applied to investigate critical phenomena such as percolation, etc.


Algorithm

While there are several algorithms for clustering, we will describe a simple method using one-dimensional array. Suppose we have N elements.

This procedure is a construction of a linked list. The diagram below shows that two groups are identified in the linked list with size 6. Initially, the link of each elements points to itself. After clustering, the links always points to left (lower index). Following the links and the last link pointing itself gives a cluster index.

Here is a sample code of clastering. Suppose equivalence relations are stored in two arrays, pair1 and pair2, then we can perform clustering by calling a function "clustering." The function "get_cluster_number" gives you a cluster index of each element. You can obtain any properties of the network, such as the size of the largest cluster, the number of unconnected clusters, etc.

//---------------------------------------------------------------------------
int cluster[N];
int pair1[N_PAIR],pair1[N_PAIR];
//---------------------------------------------------------------------------
int
get_cluster_number(int index){
  int i = index;
  while(i != cluster[i]){
    i = cluster[i];
  }
  return i;
}
//---------------------------------------------------------------------------
void
clustering(void){
  for(int i=0;i < N;i++){
    cluster[i] = i;
  }
  for(int i=0;i < N_PAIR;i++){
    int i1 = pair1[i];
    int i2 = pair2[i];
    i1 = get_cluster_number(i1);
    i2 = get_cluster_number(i2);
    if(i1 < i2){
        cluster[i2] = i1;
    }else{
      cluster[i1] = i2;
    }
  }
}
//---------------------------------------------------------------------------


Applying to Construction of Maze

Now we can apply the clustering algorithm to construction of maze. There are two properties a maze must satisfy. First, a maze should be a tree, that is, there are no loops in the maze. Next, a maze should be a spanning tree, that is, there are no closed space in the maze. A maze constructed by the clustering algorithm is guranteed to be a spannning tree.

The algorithm to construct a maze by clustering is as follows.

Finaly, we have a maze without closed paths and loops.


Example

Using the algorithm described above, we can make a maze which solution becomes some picture. First, draw a picture with a single stroke which is a solution of the maze. Then remove walls in the same manner. Since there are no loops, the given solution is guaranteed to be unique. Here is a sample maze made by the clustering algorithm. The left maze have the solution denoted by the right figure.


Summary

We describe the clustering algorithm and its application to maze. We can make a maze which solution is a picture. The clustering algorithm is very usefull and you can implement it easily (just 20 lines).


Sample Code (Ruby)

Here is a sample code written with Ruby. If you execute it, then it will export a following maze with EPS format.


Author: Hiroshi Watanabe

トップページへ戻る