1.1. 概略

迷路を作るときには、以下に注意します。

• 部屋と部屋が重なっていないこと。

• すべての部屋が通路でつながっていること。

  図 1-1. すべての部屋が通路でつながっていない例

  

アルゴリズムの方針は、こうなります。

1. 区画わけをします。

2. 各区画に１つずつ部屋を作ります。こうすることで、部屋が重なりません。

3. 部屋を通路でつなぎます。

区画のことをrectと書きます。同様に、区画の分割線をcouple、部屋のことをroomと書きます。

1. 図 1-2. まずは全体がrect[0]です。

   

2. 図 1-3. rect[0]を、分割します。rect[0]とrect[1]ができました。

   

3. 図 1-4. rect[0]を、分割します。rect[0]とrect[2]ができました。

   

4. 図 1-5. rect[2]を、分割します。rect[2]とrect[3]ができました。

   

5. 更に分割は進みますが、このへんでやめておきます。この分割の終了条件は、乱数による場合に加えて、区画の縦横のサイズが細かくなりすぎる場合です。

6. 図 1-6. 各区画にひとつずつ部屋を作ります。

   

7. 図 1-7. 各分割線ごとに部屋を通路でつなぎます。

   

   完成です。

• 分割するときには、以下の場合に備えた注意をします。

  1. 図 1-8. まずは全体がrect[0]です。

     

  2. 図 1-9. rect[0]を、横に分割します。rect[0]とrect[1]ができました。

     

     横に分割しています。ここまでは同じです。

  3. 図 1-10. rect[0]を、横に分割します。rect[0]とrect[2]ができました。

     

     さらに横に分割しています。

  このようにrect[0]を2回横に分割すると、あとでcouple(rect[0],rect[1])を使って通路を作るときに、rect[2]をまたぐことになり、困ります。2回縦に分割しても同様の問題が起こります。

  図 1-11. rect[2]をまたぐことになり、困ります。

  

  そこで、各区画の分割は、横に１回と縦に１回しかできないようにしています。

  あるいは、このように賢く分割するようにしてもいいです。最初の横分割ではrect[0]を左にしていますが、次の横分割では、couple(rect[0],rect[1])を意識して、rect[0]を右にしています。

  図 1-12. このように賢く分割するようにしてもいいです。