[Python] 一次元配列で迷路の生成

## 迷路の構築（@一次元配列）

棒倒し法による迷路生成コードを1次元配列で書いた(Python)ので、以下覚書  

- [1. 空の迷路の生成、壁の構築](#1-空の迷路の生成壁の構築)
- [2. 棒を刺す](#2-棒を刺す)
- [3. 棒を見て倒していく](#3-棒を見て倒していく)
- [4. 迷路の描画](#4-迷路の描画)
- [5. まとめ](#5-まとめ)
- [補遺1 - ソースコード全文](#補遺１-ソースコード全文)
- [補遺2 - Pythonの新知識](#補遺２-pythonの新知識)
    - [-1. リストの宣言と初期化](#-1-リストの宣言と初期化)
    - [-2. 範囲指定した乱数の作成](#-2-範囲指定した乱数の作成)
    - [-3. リスト操作](#-3-リスト操作)
- [6. 最後に](#6-最後に)
- [7. 参考サイトページ](#7-参考サイトページ)

----

### 1. 空の迷路の生成、壁の構築

``` Python:1dmaze.py
# 迷路の一辺の大きさを入力
N = int(input(MAZE SIZE: ))
# 迷路本体のサイズ
siz = N * N
# 空で埋まった迷路本体（リスト）を作成
mazeBody = [' '] * siz

# 壁を立てる
for i in range(siz):
	if i < N or i > siz - N - 1 or i % N == 0 or (i - (N - 1)) % N == 0:
		# 条件式は左から: 
		# [上辺] or [下辺] or [左辺] or [右辺]を表す
		mazeBody[i] = '■' 
```

まず壁を構築するのだが、二次元配列を用いた場合と比べて少しひねりを効かせて条件式を構築する必要がある。
上で書いた式の具体的な意味は

- インデックス0 ~ N - 1までの要素 => 上辺
- (迷路本体のサイズ - N - 1) より大きいインデックスの要素 => 下辺
- Nで割り切れるインデックスの要素 => 左辺
- 自身から(N - 1)を引いた数がNで割り切れるようなインデックスの要素 => 右辺

という感じ。

----

### 2. 棒を刺す

``` Python:1dmaze.py
for i in range(siz):
	if i % N != 0 and (i - (N - 1)) % N != 0 and N < i < (N * (N - 1)) - 1:
		# こっちのifは壁より内側の走査用
		if (i % N) % 2 == 0 and ((i - (i % N)) / N) % 2 == 0:
			# こっちは偶数座標のみに棒を刺すための条件式
			mazeBody[i] = '■'
```

壁の内側を走査して偶数座標に棒を刺していく。
内側 **のみ** を走査する条件式を確立するのに少々困難を伴った。
また棒を刺す位置についても、二次元配列であれば単に二重ループを回して

``` Python
# mazeBodyが2次元配列だった場合
for i in range(y):
	for j in range(x):
		if i % 2 == 0 and j % 2 == 0:
			#...
```

のようにすればよいが、一次元配列の場合はそうもいかない。
いろいろと計算していくうちに、
`i = yn + x`という式が成り立つことを発見したのでそこから色々と考えて最初のソースの条件式に至った。

---

### 3. 棒を見て倒していく

棒倒しでの迷路生成はこれが本体のようなもの。
まず要件の確認として:

- 最上列の棒のみ上に倒せる
- 既に棒が倒れている方向には倒さない

以上を念頭に入れてソースを書いた。

``` Python:1dmaze.py
for i in range(siz):
	if i % N != 0 and (i - (N - 1)) % N != 0 and N < i < (N * (N - 1)) - 1:
	# 内側の走査
		if (i % N) % 2 == 0 and ((i - (i % N)) / N) % 2 == 0:
		# 偶数座標(=棒を刺したところだけ)見る
			direction = [1, N, -1, -1 * N] #上下左右
			if ((i - (i % N)) / N) != 2:
			# 最上列の棒ではない場合は上には倒さないので...
				direction.pop()
			while(len(direction) > 0):
				idx = math.floor(random.random() * len(direction))
				if mazeBody[i + direction[idx]] == ' ':
					mazeBody[i + direction[idx]] = '■'
					break
				else:
					del direction[idx]
```

内側の走査のため、最初に棒を刺すときと同じ条件式を書く。
また、次も棒を刺すときと同じく偶数座標を見るための条件式。
ちなみにこの時、偶数座標を見るための条件式を単に

``` Python
		if mazeBody == '■':
			# ...
```

と書いてしまっていたために、
**下に倒れた棒も見てしまう**というミスを犯した。
具体的には迷路の殆どが■で埋まってしまう自体に陥ったのだが、原因を見つけるのに少々時間がかかってしまった。

次はdirectionというリストを作成、上下左右方向を格納する。
これも二次元配列の場合は

``` Python
			direction = [
				[0, 1],
				[1, 0],
				[0, -1],
				[-1, 0]
			]
			# ...
```

となるが、一次元なので少し変わる。
つまり左右は単純に-1, +1でいいが、上下は-N, +Nとなる。
ちなみに格納してある順番が「右、下、左、上」となっているのは、
**「上」を使わないときはpop()で吐いて捨てるのが楽そう** ということで「上」を一番最後に持ってきたというだけで、それ以外の理由はない。

directionの下に最上段の棒でなければ`direction.pop()`が動くようにしている。

その次のwhile文はdirectionのリストとしての長さが1以上の間ループが回るようになっている。
その中身はまずidxに0~3のランダムな数値（最上段の棒でない場合は0~2）を格納しており、これはどの方向（direction）を見るかというのをランダムで選ぶために生成した乱数である。
そして確認した方向に倒れた棒がなければ、その方向に棒を倒してループを抜ける。
倒れている棒があればその方向はダメなので、directionリストから確認した方向を削除する。

ここの処理の設計自体はそこまで難儀ではなかったが、乱数生成の処理を間違えて

``` Python
				idx = math.floor(math.random() * #...
```

のようにJavaScript式で書いてしまった。
JavaScriptではrandom()はMathクラスのメソッドだが、**Pythonではrandomクラスのメソッド** なので注意が必要である。

迷路本体の生成コードはここまでになる。

----

### 4. 迷路の描画

迷路の **生成** 自体は以上までで完了したが、あとはコンソール上なりなんなりに迷路を描画してやる必要があるので、そのコードについても書き残しておく。
とはいえここに関しては書くこともほとんど二次元配列のものと変わらない。

``` Python:1dmaze.py
for i in range(siz):
	if i != 0 and (i + 1) % N == 0:
		print(mazeBody[i], end = '\n')
	else:
		print(mazeBody[i], end = ' ')
```

以上は「迷路の一辺の長さ分出力したら改行をはさんで、それ以外は間にスペースを挟む」というだけのことである。
ただ、`print()`の引数で行末文字を指定するということに慣れていなかったということと、ifの後の行末かどうかを区別する式ではiが0のときも当てはまってしまうため0も明示的に除外してやる必要があるということに少し躓いた。

----

### 5. まとめ

以上、一次元配列を用いた迷路生成のコードに関する覚書となる。
最初はC++でやろうと思ったが、行き詰まってしまったのでPythonで書くことにした。
まあ、Pythonでは完成まで持っていくことができたので改めてC++でも再挑戦してみても良いかもしれない。
あとは以下に、ソースコード全文と、Pythonで書くにあたって新しく学習した仕様やメソッドの使い方などを補遺として置いておこうと思う。

----

### 補遺１: ソースコード全文

``` Python: 1dmaze.py
# coding: utf-8
# geschrieben von Beliar698ma

import math
import random

N = int(input('MAZE SIZE:'))
siz = N * N
mazeBody = [' '] * siz

for i in range(siz):
    if i < N or i > siz - N - 1 or i % N == 0 or (i - (N - 1)) % N == 0:
        mazeBody[i] = '■'

for i in range(siz):
    if i % N != 0 and (i - (N - 1)) % N != 0 and N < i < (N * (N - 1)) - 1:
        if (i % N) % 2 == 0 and ((i - (i % N)) / N) % 2 == 0:
            mazeBody[i] = '■'

for i in range(siz):
    if i % N != 0 and (i - (N - 1)) % N != 0 and N < i < (N * (N - 1)) - 1:
        if (i % N) % 2 == 0 and ((i - (i % N)) / N) % 2 == 0:
            direction = [1, N, -1, -1 * N]
            if ((i - (i % N)) / N) != 2:
                direction.pop()
            while (len(direction) > 0):
                idx = math.floor(random.random() * len(direction))
                if mazeBody[i + direction[idx]] == ' ':
                    mazeBody[i + direction[idx]] = '■'
                    break
                else:
                    del direction[idx]

for i in range(siz):
    if i != 0 and (i + 1) % N == 0:
        print(mazeBody[i], end='\n')
    else:
        print(mazeBody[i], end=' ')
```

----

### 補遺２: Pythonの新知識

#### -1. リストの宣言と初期化

これはどちらかというと新知識ではないが、リストを使うたびに調べるのもいい加減面倒なのでまとめておく。

##### 空リストの作成

``` Python
my_list = []
print(my_list) 
# []

print(len(my_list)) 
# 0
```

##### 任意の要素数で初期化

``` Python
my_list = [0] * 10
print(my_list)
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
print(len(my_list))
# 10
```

これは、1個の要素を10回格納するという書き方なので、下のような書き方をすれば:

``` Python
my_list = [0, 1, 2] * 3
print(my_list)
# [0, 1, 2, 0, 1, 2, 0, 1, 2]
print(len(my_list))
# 9
```

というふうに3個の要素が3回格納されることになる。

また、2次元配列を宣言する場合は注意が必要。例えば：

``` Python
my_2dlist = [[0] * 4] * 3
print(my_2dlist)
# [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
```

これをやった場合、一見意図した配列が生成されているように見えるが、この場合は
**3つある各配列はすべて同じオブジェクトである** ため、例えば以下のように要素を変更しようとすると全てが書き換わってしまう。

``` Python
my_2dlist[0][0] = 5
print(my_2dlist)
# [[5, 0, 0, 0], [5, 0, 0, 0], [5, 0, 0, 0]]
```

このような場合は、リスト内包表記を用いて次のように書く。

``` Python
my_2dlist = [[0] * 4 for i in range(3)]
print(my_2dlist)
# [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
```

こうすればリストの各要素は異なるオブジェクトとして扱われる。

``` Python
my_2dlist[0][0] = 5
print(my_2dlist)
#[[5, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
```

同一のオブジェクトか否かを確認するためには、 **オブジェクトID** を確認するのが良い。たとえば：

```Python
my_2dlist_ng = [[0] * 4] * 3
# [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] <= 全て同一オブジェクト。
print(id(my_2dlist_ng[0]) == id(my_2dlist_ng[1]) == id(my_2dlist_ng[2]))
# True <= Trueなので全て同一オブジェクトであることがわかる。

my_2dlist_ok = [[0] * 4 for i in range(3)]
# [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] <= 互いに異なるオブジェクト。
print(id(my_2dlist_ok[0]) == id(my_2dlist_ok[1]) == id(my_2dlist_ok[2]))
# False <= Falseなので互いに異なるオブジェクトであることがわかる。
```

ということ。

#### -2. 範囲指定した乱数の作成

JavaScriptに慣れているとこれは
`Math.floor(Math.random() * N)` と書いてしまいがちであるが、
Pythonでは`floor()` はmathクラスのメソッド、`random()` は**randomクラスのメソッド**なので、
次のように書く必要がある。

``` Python
import math
import random 
# ...

randomNum = math.floor(random.random() * N)
```

ここで引っかかってもエラーに「randomはmathのメソッドではありません」的なことを言われるので時間をとられることはあまりなさそう。

#### -3. リスト操作

リストを操作するメソッドもついでに書いておこうかな、と思った。
**要素の追加** と **要素の削除** について参照できるように残しておく。

##### 要素の追加

###### .append(e)

`.append()`メソッドは引数に渡した要素（ここではe）をリストの末尾に追加する。
他の言語での`.push()`とか`.push_back()`と同じ？

例：

``` Python
my_list = [1, 2, 3]
my_list.append(4)
print(my_list)
# [1, 2, 3, 4]
```

###### .insert(idx, e)

`.insert()`メソッドは、リストに、第一引数で渡されたインデックスへ第二引数で渡された要素を挿入する。
こういうメソッド使える言語って他に何があったかな...?

例：

``` Python
my_list = [1, 2, 3]
my_list.insert(1, 4)
print(my_list)
# [1, 4, 2, 3]
```

###### .extend(list)

`.extend()`メソッドは、引数に渡されたリストを元のリストの末尾に連結する。
JavaScriptの`.concat()`ですかね。

例：

``` Python
my_list = [1, 2, 3]
my_list.extend([4, 5])
print(my_list)
# [1, 2, 3, 4, 5]
```


なお加算演算子`+`を使うことでもリストは連結できる。

例：

``` Python
my_list = [1, 2, 3]
my_list = my_list + [4, 5]
print(my_list)
# [1, 2, 3, 4, 5]
```

##### 要素の削除

###### del文

del文は`del my_list[idx]`のように書き、指定したインデックスの要素を削除する。

例：

``` Python
my_list = [1, 2, 3]
del my_list[1]
print(my_list)
# [1, 3]
```

###### .pop()/.pop(idx)

調べてて初めて知ったんですが、Pythonの`.pop()`って引数取れるんですね、知らなかったそんなの...。

`.pop(idx)`とすると指定したインデックスの要素を削除し、`.pop()`と引数を取らなければ末尾の要素を削除するようです。

例：

``` Python
my_list = [1, 2, 3]
my_list.pop(1)
print(my_list)
# [1, 3]

# あるいは

my_list2 = [1, 2, 3]
my_list.pop()
print(my_list)
# [1, 2]
```

###### .clear()

`.clear()`メソッドはリスト内の全要素を削除する。

例：

``` Python
my_list = [1, 2, 3]
my_list.clear()
print(my_list)
# []
```


とりあえず参考として書いておくのはこれくらいで、sortとかはまた使うときになったら調べて書けばいいかな...と思います。

----

### 6. 最後に

何がやりたくて1次元配列で迷路生成のコードを書いたのかというと、最終的に迷路の経路探索をやるためです。
棒倒し法による迷路生成をもともと2次元配列でやっていたのですが、「経路探索までやるなら1次元配列で作るか、2次元座標を1つの数字にまとめた方が楽かも」と助言をいただきました。
どっちにせよ2次元座標を1次元的に考える頭を作っておいたほうがよいのは確かなので、それならいっそ1次元配列で迷路作っちゃうか～～～と思って出来上がったのがこれになります。
次に覚書として記事を残す際は再帰関数についての話がメインになりそうですね。

### 7. 参考サイト・ページ

[【Python】リスト操作まとめ - Qiita](https://qiita.com/ell/items/8057198ef33e554e54a2 "【Python】リスト操作まとめ - Qiita")
[Pythonのリスト（配列）を任意の値・要素数で初期化](https://note.nkmk.me/python-list-initialize/)