Pythonで〇×ゲームのAIを一から作成する　その97　ゲーム木の生成過程を表示するアニメーション

# 目次と前回の記事

https://qiita.com/ysgeso/items/2381dd4e3283cbed49a0

https://qiita.com/ysgeso/items/7b687d25a4ab300f5865

## これまでに作成したモジュール

以下のリンクから、これまでに作成したモジュールを見ることができます。

| リンク | 説明 |
|:--|:--|
| [marubatsu.py](https://github.com/ysgeso/marubatsu/blob/master/097/marubatsu.py)  | Marubatsu、Marubatsu_GUI クラスの定義|
| [ai.py](https://github.com/ysgeso/marubatsu/blob/master/097/ai.py)  |  AI に関する関数 |
|  [util.py](https://github.com/ysgeso/marubatsu/blob/master/097/util.py) |  ユーティリティ関数の定義。現在は `gui_play` のみ定義されている |
| [tree.py](https://github.com/ysgeso/marubatsu/blob/master/097/tree.py)  | ゲーム木に関する Node、Mbtree クラスの定義  |
| [gui.py](https://github.com/ysgeso/marubatsu/blob/master/097/gui.py)  |  GUI に関する処理を行う基底クラスとなる GUI クラスの定義  |

## ルールベースの AI の一覧

ルールベースの AI の一覧については、下記の記事を参照して下さい。

https://qiita.com/ysgeso/items/10d1d01192c014173e4b

# マウス操作による中心となるノードを移動する GUI の問題点と改良

[前回の記事](https://qiita.com/ysgeso/items/7b687d25a4ab300f5865#%E3%83%9E%E3%82%A6%E3%82%B9%E3%81%AE%E6%93%8D%E4%BD%9C%E3%81%AB%E3%82%88%E3%82%8B%E4%B8%AD%E5%BF%83%E3%81%A8%E3%81%AA%E3%82%8B%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E7%A7%BB%E5%8B%95)で実装した、マウス操作による、中心となるノードの移動には、問題があることがわかりましたので修正します。実際に操作してみればわかる問題点だと思いますので、どのような問題があるかについて少し考えてみて下さい。

## 問題点

[以前の記事](https://qiita.com/ysgeso/items/17b0438676f4a41a906c#%E4%B8%AD%E5%BF%83%E3%81%A8%E3%81%AA%E3%82%8B%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E7%A7%BB%E5%8B%95%E5%8F%AF%E8%83%BD%E3%81%AA%E7%AF%84%E5%9B%B2%E3%81%AE%E6%94%B9%E8%89%AF)で説明したように、__深さ 6 のノードを中心とする部分木__ は、__最も深い深さ 9 のノードまでを描画することができる__ ので、GUI の操作によって __深さが 7 以上のノードが中心とならない__ ようにする処理を行いました。

→ ボタンで中心となるノードを子ノードに移動する場合は、中心となるノードの __深さが 1 ずつしか深くならない__ ので、深さ 6 のノードが中心の場合に → ボタンを押した際に移動できなくしても特に問題はありませんでした。

一方、__マウスによって中心となるノードを移動__ する場合は、__2 つ以上深いノードに移動__ することができてしまうので、__深さが 7 以上のノードへ移動できなくする__ という処理には __問題があります__。言葉の説明では意味がわからないと思いますので、具体例を示します。

下図は、__深さ 5__ のノードを中心とする部分木です。下図で、一番右の列に表示される、__深さが 7__ のノードの上でマウスを押しても __中心となるノードは移動しません__。そのため、下図に表示されている __深さが 7 のノードの子ノードが表示される部分木__ を表示するためには、__深さが 6 のノードの上でマウスを押す必要があります__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/00544b2f-fc9f-af0c-9839-f94bb9ee0624.png" width="300">

具体的には、上図の深さが 7 の赤丸のノードの上でマウスを押しても表示は更新されず、赤丸の子ノードが表示される部分木を表示するためには、深さが 6 の青丸のノードの上でマウスを押す必要があります。下図は、上図で青丸のノードをマウスで押した場合の図で、赤丸のノードの子ノードが表示された部分木が表示されています。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/191214cc-7934-11e6-c1a6-35e198ee6261.png" width="300">

__赤丸の子ノードを表示するため__ に、__赤丸以外__ の青丸の __ノードをマウスで押さなければならない__ というのは、__わかりづらく不便__ です。

この問題を修正する方法について少し考えてみて下さい。

## 問題の修正方法

以下は、この問題を修正する方法の一つです。他にも良い方法があるかもしれないので、もっと良い方法を思いついた方はその方法を実装してみて下さい。

* 部分木の中で、__赤い枠を表示するノード__ を、__選択されたノード__ と表現することにする
* __すべてのノード__ を GUI の操作で __選択できる__ ようにする
* 選択されたノードの __深さが 6 以下__ の場合は、__これまでと同様__ に、選択されたノードを中心とした部分木を描画する
* 選択されたノードの __深さが 7 以上__ の場合は、その親ノードを辿った、__深さが 6 の親ノードを中心とする部分木を描画__ する

上記のように修正することで、深さが 7 以上のノードが選択された場合でも、深さが 6 から 9 までの部分木が描画されるようになります[^1]。

わかりづらいかもしれませんが、この修正で部分木の __中心となるノードがなくなるわけではありません__。また、選択されたノードの __深さが 6 以下の場合__ は選択されたノードと中心となるノードは __同じになります__。この修正は、GUI の 操作で中心となるノードではなく、赤枠で囲われた __選択されたノードを操作__ できるようにするというものです

なお、この修正は、今回の記事の後半で行う、ゲーム木の生成の過程のアニメーション処理を行う際にも必要となる修正です。

## `centernode` 属性の名前の修正

赤枠で表示されるノードは、これまでは中心となるノードと呼んでいたので Mbtree_GUI クラスの `centernode` 属性に代入していましたが、__選択された（selected）ノード__ と呼び方を変えることにしたので、代入する __属性の名前__ を __`selectednode`__ に変更することにします。

下記は、そのように `Mbtree_GUI` クラスを修正したプログラムです。なお、修正は VSCode の [シンボル名の変更](https://qiita.com/ysgeso/items/c2d569b1be171fbe4b31#vscode-%E3%81%AE%E3%82%B7%E3%83%B3%E3%83%9C%E3%83%AB%E5%90%8D%E3%81%AE%E5%A4%89%E6%9B%B4%E3%81%AE%E4%BD%BF%E3%81%84%E6%96%B9)の機能を使えば簡単なので、変更場所の説明は省略します。

<details><summary><strong>修正したプログラム（長いのでクリックして開いてください）</strong></summary>

```python
from gui import GUI
import matplotlib.pyplot as plt
import ipywidgets as widgets

class Mbtree_GUI(GUI):
    def __init__(self, mbtree, size=0.15):
        self.mbtree = mbtree
        self.size = size
        self.width = 50
        self.height = 64
        self.selectednode = self.mbtree.root
        super().__init__()
        
    def create_widgets(self):
        self.output = widgets.Output()  
        self.left_button = self.create_button("←", 50)
        self.up_button = self.create_button("↑", 50)
        self.right_button = self.create_button("→", 50)
        self.down_button = self.create_button("↓", 50)
        self.help_button = self.create_button("？", 50)
        self.label = widgets.Label(value="", layout=widgets.Layout(width=f"50px"))
        
        with plt.ioff():
            self.fig = plt.figure(figsize=[self.width * self.size,
                                            self.height * self.size])
            self.ax = self.fig.add_axes([0, 0, 1, 1])
        self.fig.canvas.toolbar_visible = False
        self.fig.canvas.header_visible = False
        self.fig.canvas.footer_visible = False
        self.fig.canvas.resizable = False        
        
    def create_event_handler(self):
        def on_left_button_clicked(b=None):
            if self.selectednode.parent is not None:
                self.selectednode = self.selectednode.parent
                self.update_gui()
                
        def on_right_button_clicked(b=None):
            if self.selectednode.depth < 6 and len(self.selectednode.children) > 0:
                self.selectednode = self.selectednode.children[0]
                self.update_gui()

        def on_up_button_clicked(b=None):
            if self.selectednode.parent is not None:
                index = self.selectednode.parent.children.index(self.selectednode)
                if index > 0:
                    self.selectednode = self.selectednode.parent.children[index - 1]
                    self.update_gui()
                
        def on_down_button_clicked(b=None):
            if self.selectednode.parent is not None:
                index = self.selectednode.parent.children.index(self.selectednode)
                if self.selectednode.parent.children[-1] is not self.selectednode:
                    self.selectednode = self.selectednode.parent.children[index + 1]
                    self.update_gui()            
                    
        def on_help_button_clicked(b=None):
            self.output.clear_output()
            with self.output:
                print("""操作説明

    下記のキーとボタンで中心となるノードを移動できる。ただし、深さが 7 以上のノードへは移動できない
    ←、0 キー：親ノードへ移動
    ↑：一つ前の兄弟ノードへ移動
    ↓：一つ後の兄弟ノードへ移動
    →：先頭の子ノードへ移動

    テンキーで、対応するマスに着手が行われた子ノードへ移動する
    ノードの上でマウスを押すことでそのノードへ移動する
    """)
                            
        self.left_button.on_click(on_left_button_clicked)
        self.right_button.on_click(on_right_button_clicked)
        self.up_button.on_click(on_up_button_clicked)
        self.down_button.on_click(on_down_button_clicked)
        self.help_button.on_click(on_help_button_clicked)

        def on_key_press(event):
            keymap = {
                "left": on_left_button_clicked,
                "0": on_left_button_clicked,
                "right": on_right_button_clicked,
                "up": on_up_button_clicked,
                "down": on_down_button_clicked,
            }
            if event.key in keymap:
                keymap[event.key]()
            elif self.selectednode.depth < 6:
                try:
                    num = int(event.key) - 1
                    x = num % 3
                    y = 2 - (num // 3)
                    move = (x, y)
                    if move in self.selectednode.children_by_move:
                        self.selectednode = self.selectednode.children_by_move[move]
                        self.update_gui()
                except:
                    pass            
                
        def on_mouse_down(event):
            for rect, node in self.mbtree.nodes_by_rect.items():
                if node.depth <= 6 and rect.is_inside(event.xdata, event.ydata):
                    self.selectednode = node
                    self.update_gui()
                    break               
                
        # fig の画像イベントハンドラを結び付ける
        self.fig.canvas.mpl_connect("key_press_event", on_key_press)
        self.fig.canvas.mpl_connect("button_press_event", on_mouse_down)    
            
    def display_widgets(self):
        hbox1 = widgets.HBox([self.label, self.up_button, self.label])
        hbox2 = widgets.HBox([self.left_button, self.label, self.right_button,
                            self.label, self.help_button])
        hbox3 = widgets.HBox([self.label, self.down_button, self.label])
        display(widgets.VBox([self.output, hbox1, hbox2, hbox3, self.fig.canvas]))   

    def update_gui(self):
        self.ax.clear()
        self.ax.set_xlim(-1, self.width - 1)
        self.ax.set_ylim(0, self.height)   
        self.ax.invert_yaxis()
        self.ax.axis("off")   
        
        if self.selectednode.depth <= 4:
            maxdepth = self.selectednode.depth + 1
        elif self.selectednode.depth == 5:
            maxdepth = 7
        else:
            maxdepth = 9
        self.mbtree.draw_subtree(self.selectednode, ax=self.ax, maxdepth=maxdepth)
        
        disabled = self.selectednode.parent is None
        self.set_button_status(self.left_button, disabled=disabled)
        disabled = self.selectednode.depth >= 6 or len(self.selectednode.children) == 0
        self.set_button_status(self.right_button, disabled=disabled)
        disabled = self.selectednode.parent is None or self.selectednode.parent.children.index(self.selectednode) == 0
        self.set_button_status(self.up_button, disabled=disabled)
        disabled = self.selectednode.parent is None or self.selectednode.parent.children[-1] is self.selectednode
        self.set_button_status(self.down_button, disabled=disabled)
```
</details>

## `draw_subtree` の修正

部分木の中で、__中心となるノード__ と、赤い枠を表示する __選択されたノード__ が __異なるノードになる場合が生じた__ ので、`draw_subtree` には、中心となるノードと、選択されたノードを代入する __異なる仮引数を用意する必要__ があります。また、`draw_node` を呼び出す際に __強調して表示するノードを選択されたノードに変更__ する必要があります。

下記は、そのように __`draw_subtree`__ を修正したプログラムです。

* __3 行目__：選択されたノードを代入する、デフォルト値を `None` とする仮引数 `selectednode` を追加する
* __6 行目__：`draw_node` で強調して表示するノードを、`selectednode` に変更する

```python
1  from tree import Mbtree
2  
3  def draw_subtree(self, centernode=None, selectednode=None, ax=None, size=0.25, lw=0.8, maxdepth=2):
元と同じなので省略
4              else:
5                  dx = 5 * node.depth
6                  emphasize = node is selectednode
7                  rect = node.draw_node(ax=ax, maxdepth=maxdepth, emphasize=emphasize, size=size, lw=lw, dx=dx, dy=dy)
元と同じなので省略
8            
9  Mbtree.draw_subtree = draw_subtree
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
from tree import Mbtree

def draw_subtree(self, centernode=None, selectednode=None, ax=None, size=0.25, lw=0.8, maxdepth=2):   
    self.nodes_by_rect = {}

    if centernode is None:
        centernode = self.root
    self.calc_node_height(maxdepth)
    width = 5 * (maxdepth + 1)
    height = centernode.height
    parent = centernode.parent
    if parent is not None:
        height += (len(parent.children) - 1) * 4
        parent.height = height
    if ax is None:
        fig, ax = plt.subplots(figsize=(width * size, height * size))
        ax.set_xlim(0, width)
        ax.set_ylim(0, height)   
        ax.invert_yaxis()
        ax.axis("off")        
    
    nodelist = [centernode]
    depth = centernode.depth
    while len(nodelist) > 0 and depth <= maxdepth:        
        dy = 0
        if parent is not None:
            dy = parent.children.index(centernode) * 4
        childnodelist = []
        for node in nodelist:
            if node is None:
                dy += 4
                childnodelist.append(None)
            else:
                dx = 5 * node.depth
                emphasize = node is selectednode
                rect = node.draw_node(ax=ax, maxdepth=maxdepth, emphasize=emphasize, size=size, lw=lw, dx=dx, dy=dy)
                self.nodes_by_rect[rect] = node
                dy += node.height
                if len(node.children) > 0:  
                    childnodelist += node.children
                else:
                    childnodelist.append(None)
        depth += 1
        nodelist = childnodelist
        
    if parent is not None:
        dy = 0
        for sibling in parent.children:
            if sibling is not centernode:
                sibling.height = 4
                dx = 5 * sibling.depth
                rect = sibling.draw_node(ax, maxdepth=sibling.depth, size=size, lw=lw, dx=dx, dy=dy)
                self.nodes_by_rect[rect] = sibling
            dy += sibling.height
        dx = 5 * parent.depth
        rect = parent.draw_node(ax, maxdepth=maxdepth, size=size, lw=lw, dx=dx, dy=0)
        self.nodes_by_rect[rect] = parent
    
        node = parent
        while node.parent is not None:
            node = node.parent
            node.height = height
            dx = 5 * node.depth
            rect = node.draw_node(ax, maxdepth=node.depth, size=size, lw=lw, dx=dx, dy=0)
            self.nodes_by_rect[rect] = node
            
Mbtree.draw_subtree = draw_subtree
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
from tree import Mbtree

-def draw_subtree(self, centernode=None, ax=None, size=0.25, lw=0.8, maxdepth=2):   
+def draw_subtree(self, centernode=None, selectednode=None, ax=None, size=0.25, lw=0.8, maxdepth=2):
元と同じなので省略
             else:
                dx = 5 * node.depth
-               emphasize = node is centernode
+               emphasize = node is selectednode
                rect = node.draw_node(ax=ax, maxdepth=maxdepth, emphasize=emphasize, size=size, lw=lw, dx=dx, dy=dy)
元と同じなので省略
            
Mbtree.draw_subtree = draw_subtree
```
</details>

上記の修正後に、下記のプログラムを実行することで、実行結果から __`draw_subtree`__ が __中心となるノード__ と、__選択されたノード__ が __異なる部分木を表示__ できるようになったことを確認できます。

なお、下記のプログラムでは、下記のような部分木を表示しています。

* ルートノードを中心とする、深さ 1 までの部分木
* 選択されたノードは、深さ 1 の最初のノード

```python
mbtree = Mbtree()
mbtree.draw_subtree(centernode=mbtree.root, 
                    selectednode=mbtree.nodelist_by_depth[1][0], maxdepth=1)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/7854e4cb-5ae4-dc0e-6cc3-83e86f80ddbb.png" width="100">

## `create_eventhandler` の修正

次に、`create_eventhandler` を下記のプログラムのように、深さ 7 以上のノードを選択状態にできるように修正します。

* __3、23、27 行目__：深さが 6 以下の場合に制限するという条件を、条件式から削除する
* __11 行目__：操作説明のメッセージを修正する

```python
 1  def create_event_handler(self):
元と同じなので省略
 2      def on_right_button_clicked(b=None):
 3          if len(self.selectednode.children) > 0:
 4              self.selectednode = self.selectednode.children[0]
 5              self.update_gui()
元と同じなので省略
 6      def on_help_button_clicked(b=None):
 7          self.output.clear_output()
 8          with self.output:
 9              print("""操作説明
10
11  下記のキーとボタンで中心となるノードを移動できる。
12  ←、0 キー：親ノードへ移動
13  ↑：一つ前の兄弟ノードへ移動
14  ↓：一つ後の兄弟ノードへ移動
15  →：先頭の子ノードへ移動
16
17  テンキーで、対応するマスに着手が行われた子ノードへ移動する
18  ノードの上でマウスを押すことでそのノードへ移動する
19  """)
元と同じなので省略
20      def on_key_press(event):
元と同じなので省略
21          if event.key in keymap:
22              keymap[event.key]()
23          else:
24              try:
元と同じなので省略
25      def on_mouse_down(event):
26          for rect, node in self.mbtree.nodes_by_rect.items():
27              if rect.is_inside(event.xdata, event.ydata):
28                  self.selectednode = node
29                  self.update_gui()
30                  break               
元と同じなので省略
31    
32  Mbtree_GUI.create_event_handler = create_event_handler
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
def create_event_handler(self):
    def on_left_button_clicked(b=None):
        if self.selectednode.parent is not None:
            self.selectednode = self.selectednode.parent
            self.update_gui()
            
    def on_right_button_clicked(b=None):
        if len(self.selectednode.children) > 0:
            self.selectednode = self.selectednode.children[0]
            self.update_gui()

    def on_up_button_clicked(b=None):
        if self.selectednode.parent is not None:
            index = self.selectednode.parent.children.index(self.selectednode)
            if index > 0:
                self.selectednode = self.selectednode.parent.children[index - 1]
                self.update_gui()
            
    def on_down_button_clicked(b=None):
        if self.selectednode.parent is not None:
            index = self.selectednode.parent.children.index(self.selectednode)
            if self.selectednode.parent.children[-1] is not self.selectednode:
                self.selectednode = self.selectednode.parent.children[index + 1]
                self.update_gui()            
                
    def on_help_button_clicked(b=None):
        self.output.clear_output()
        with self.output:
            print("""操作説明

下記のキーとボタンで中心となるノードを移動できる。
←、0 キー：親ノードへ移動
↑：一つ前の兄弟ノードへ移動
↓：一つ後の兄弟ノードへ移動
→：先頭の子ノードへ移動

テンキーで、対応するマスに着手が行われた子ノードへ移動する
ノードの上でマウスを押すことでそのノードへ移動する
""")
                        
    self.left_button.on_click(on_left_button_clicked)
    self.right_button.on_click(on_right_button_clicked)
    self.up_button.on_click(on_up_button_clicked)
    self.down_button.on_click(on_down_button_clicked)
    self.help_button.on_click(on_help_button_clicked)

    def on_key_press(event):
        keymap = {
            "left": on_left_button_clicked,
            "0": on_left_button_clicked,
            "right": on_right_button_clicked,
            "up": on_up_button_clicked,
            "down": on_down_button_clicked,
        }
        if event.key in keymap:
            keymap[event.key]()
        else:
            try:
                num = int(event.key) - 1
                x = num % 3
                y = 2 - (num // 3)
                move = (x, y)
                if move in self.selectednode.children_by_move:
                    self.selectednode = self.selectednode.children_by_move[move]
                    self.update_gui()
            except:
                pass            
            
    def on_mouse_down(event):
        for rect, node in self.mbtree.nodes_by_rect.items():
            if rect.is_inside(event.xdata, event.ydata):
                self.selectednode = node
                self.update_gui()
                break               
            
    # fig の画像イベントハンドラを結び付ける
    self.fig.canvas.mpl_connect("key_press_event", on_key_press)
    self.fig.canvas.mpl_connect("button_press_event", on_mouse_down)    
    
Mbtree_GUI.create_event_handler = create_event_handler
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
def create_event_handler(self):
元と同じなので省略
    def on_right_button_clicked(b=None):
-       if self.selectednode.depth < 6 and len(self.selectednode.children) > 0:
+       if len(self.selectednode.children) > 0:
            self.selectednode = self.selectednode.children[0]
            self.update_gui()
元と同じなので省略
    def on_help_button_clicked(b=None):
        self.output.clear_output()
        with self.output:
            print("""操作説明

-下記のキーとボタンで中心となるノードを移動できる。ただし、深さが 7 以上のノードへは移動できない
+下記のキーとボタンで中心となるノードを移動できる。
←、0 キー：親ノードへ移動
↑：一つ前の兄弟ノードへ移動
↓：一つ後の兄弟ノードへ移動
→：先頭の子ノードへ移動

テンキーで、対応するマスに着手が行われた子ノードへ移動する
ノードの上でマウスを押すことでそのノードへ移動する
""")
元と同じなので省略
    def on_key_press(event):
元と同じなので省略
        if event.key in keymap:
            keymap[event.key]()
-       elif self.selectednode.depth < 6:
+       else:
            try:
元と同じなので省略
    def on_mouse_down(event):
        for rect, node in self.mbtree.nodes_by_rect.items():
-           if node.depth <= 6 and rect.is_inside(event.xdata, event.ydata):
+           if rect.is_inside(event.xdata, event.ydata):
                self.selectednode = node
                self.update_gui()
                break               
元と同じなので省略
    
Mbtree_GUI.create_event_handler = create_event_handler
```
</details>

上記の修正後に、下記のプログラムを実行すると、実行結果のように赤い枠のノードが表示されなくなります。これは、`draw_subtree` を先程修正したにも関わらず、`draw_subtree` を呼び出す処理を修正していないからです。

```python
mbtree_gui = Mbtree_GUI(mbtree)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9be94bce-3efc-3a5f-7160-09aab40a35be.png" width="150">

## `update_gui` の修正

`draw_subtree` は、`update_gui` から呼び出しているので、__`update_gui`__ の中で、下記のような __中心となるノードを計算する必要__ があります。

* 選択されたノードの __深さが 6 以下__ の場合は、これまでと同様 に、__選択されたノードを中心__ とした部分木を描画する
* 選択されたノードの __深さが 7 以上__ の場合は、その親ノードを辿った、__深さが 6 の親ノードを中心__ とする部分木を描画 する

そのような中心となるノードは、下記のプログラムの 2 ~ 4 行目の処理で計算できます。

* __2 行目__：`centernode` に選択されたノードを代入する
* __3、4 行目__：`centernode` の深さが 6 より大きい場合に、`centernode` に親ノードを代入する繰り返しの処理を行う
* __5 行目__：計算された `centernode` を実引数に記述して `draw_subtree` を呼び出す

上記の処理を行うと、`centernode` に下記のようなノードが代入されます。

* 選択されたノードの深さが 6 以下の場合は、3 行目の条件式が __最初から `False` になる__ ため __4 行目の処理が行われない__。従って、__`centernode` には選択されたノードが代入__ される
* 選択されたノードの深さが 7 以上の場合は __`centernode` の深さが 6 になるまで__ 4 行目の処理が繰り返し行われる。そのため、`centernode` には、深さが 6 の選択されたノードの親ノードが代入される


```python
1  def update_gui(self):
元と同じなので省略
2      centernode = self.selectednode
3      while centernode.depth > 6:
4          centernode = centernode.parent
5      self.mbtree.draw_subtree(centernode=centernode, selectednode=self.selectednode, ax=self.ax, maxdepth=maxdepth)
元と同じなので省略    
6    
7  Mbtree_GUI.update_gui = update_gui
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
def update_gui(self):
    self.ax.clear()
    self.ax.set_xlim(-1, self.width - 1)
    self.ax.set_ylim(0, self.height)   
    self.ax.invert_yaxis()
    self.ax.axis("off")   
    
    if self.selectednode.depth <= 4:
        maxdepth = self.selectednode.depth + 1
    elif self.selectednode.depth == 5:
        maxdepth = 7
    else:
        maxdepth = 9
    centernode = self.selectednode
    while centernode.depth > 6:
        centernode = centernode.parent
    self.mbtree.draw_subtree(centernode=centernode, selectednode=self.selectednode, ax=self.ax, maxdepth=maxdepth)
    
    disabled = self.selectednode.parent is None
    self.set_button_status(self.left_button, disabled=disabled)
    disabled = self.selectednode.depth >= 6 or len(self.selectednode.children) == 0
    self.set_button_status(self.right_button, disabled=disabled)
    disabled = self.selectednode.parent is None or self.selectednode.parent.children.index(self.selectednode) == 0
    self.set_button_status(self.up_button, disabled=disabled)
    disabled = self.selectednode.parent is None or self.selectednode.parent.children[-1] is self.selectednode
    self.set_button_status(self.down_button, disabled=disabled)
    
Mbtree_GUI.update_gui = update_gui
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
def update_gui(self):
元と同じなので省略
+   centernode = self.selectednode
+   while centernode.depth > 6:
+       centernode = centernode.parent
-   self.mbtree.draw_subtree(self.selectednode, ax=self.ax, maxdepth=maxdepth)
+   self.mbtree.draw_subtree(centernode=centernode, selectednode=self.selectednode, ax=self.ax, maxdepth=maxdepth)
元と同じなので省略    
    
Mbtree_GUI.update_gui = update_gui
```
</details>

上記の修正後に、下記のプログラムを実行して深さ 7 以上のノードを選択状態にすると、実行結果のように、そのノードが赤い枠で表示され、そのノードの深さが 6 の親ノードが中心となる部分木が表示されるようになります。

```python
mbtree_gui = Mbtree_GUI(mbtree)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/04371755-c144-25be-3b57-d42c91afe1e0.png" width="350">

これで、ゲーム木を視覚化する GUI は完成ですが、他にも機能を付け加えたい人は実装してみて下さい。

# ゲーム木の作成の過程の視覚化

Mbtree クラスでは、[幅優先アルゴリズム](https://qiita.com/ysgeso/items/0bb9d7fd972636d470d5#%E5%B9%85%E5%84%AA%E5%85%88%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AB%E3%82%88%E3%82%8B%E3%82%B2%E3%83%BC%E3%83%A0%E6%9C%A8%E3%81%AE%E4%BD%9C%E6%88%90)によって、ゲーム木の作成を行いました。先程完成したゲーム木を視覚化する GUI では、__完成したゲーム木を視覚化__ することができますが、ゲーム木が __どのように作成されたか__ を知ることはできません。そこで、幅優先アルゴリズムによって、ゲーム木のノードがどのような順番で作成されるかを視覚化することにします。実は、本記事で、ここまで部分木の視覚化の実装を行ってきた一つの理由は、ゲーム木の作成の過程の視覚化を行いたかったからです。

どのような方法で視覚化すればよいかについて少し考えてみて下さい。


## 〇×ゲームのリプレイ機能と同様の方法による視覚化

視覚化の方法として、〇×ゲームの GUI のリプレイ機能のように、下図の <<、<、>、>> の 4 つのボタンと IntSlider のウィジェットで、ゲーム木が作成される過程を表示するという方法が考えられますが、この方法はあまり良い方法ではないでしょう。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/0f1ba975-181c-d272-1b5a-9dee7a3a5705.png" width="350">

その理由の一つは、上記の UI では、ゲーム木が作成される過程の __表示を進めるため__ には、__> ボタンをクリックする必要がある__ からです。〇× ゲームのゲーム木のノードは、[以前の記事](https://qiita.com/ysgeso/items/949d18e60939d510c931#%E6%AD%A3%E3%81%97%E3%81%84%E5%90%84%E6%B7%B1%E3%81%95%E3%81%AE%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E6%95%B0%E3%81%AE%E8%A8%88%E7%AE%97%E6%96%B9%E6%B3%95)で説明したように、__50 万以上もある__ ため、> ボタンをクリックして表示を進めるのは __現実的ではない__ でしょう。

また、他の理由としては、〇×ゲームのリプレイ機能の場合は、__ゲームの経過を 1 手ずつ前後に移動しながら確認したい__ ので上記のような UI を採用しましたが、ゲーム木が作成される過程を表示する際に < ボタンをクリックして __1 つ前に戻る必要はあまりない__ でしょう。

ゲーム木が作成される過程を表示する場合は、__自動的に表示が更新__ されるという、__アニメーション（動画）によって行うのが自然__ だと思いますので、本記事では __アニメーションによるゲーム木の生成の過程を表示する方法__ について説明します。〇× ゲームのリプレイと同じ UI が良いと思った方は、そちらを採用して下さい。

## Play ウィジェットによるアニメーション

アニメーションは、__一定時間おき__ に、__少しずつ内容が異なる画像を表示する__ ことで行います。原理的には、__パラパラ漫画と同じ__ です。ノートや教科書の端に、パラパラ漫画によるアニメーションを描いたことがある人は多いのではないでしょうか？

__一定時間おきに表示する画像__ のことを __フレーム（frame）__ と呼び、__1 秒間に表示するフレームの数__ を __fps__（frame per second）と呼びます。fps が高いほうが滑らかなアニメーションになり、テレビ番組や映画などでは約 30 fps、ゲームでは 60 fps が一般的なようです。

従って、プログラムでアニメーションを行うためには、__一定時間おきに表示を更新する処理を行う__ 必要があります。

### Play ウィジェット

ipywidgets には、アニメーションを行うために利用できる __Play__ というウィジェットが用意されています。Play ウィジェットは、下図のような表示が行われるウィジェットで、下記のように、__一定時間おき__ に __`value` 属性を変化させる機能__ を持ちます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/8aa805ca-b888-9d27-e8f6-10fb259bab1d.png" width="150">

* 上図のような、3 つのボタンで構成されるウィジェットである
* 三角形のボタンをクリックすると、一定時間おきに、Play ウィジェットの __`value` 属性の値が変化__ するようになる。その後、もう一度そのボタンをクリックすると `value` 属性の値が変化しなくなる
* __`value`__ 属性には、__初期値__、__最小値__、__最大値__、__加算される値__ を設定することができる
* 四角形のボタンをクリックすると、`value` 属性の値が最小値になり、時間経過で変化しないようになる
* 一番右のボタンをクリックして ON の状態にすると、`value` 属性の値が最大値を超えた場合に初期値に戻り、ループするようになる

Play ウィジェットの詳細については、下記のリンク先を参照して下さい。

https://ipywidgets.readthedocs.io/en/latest/examples/Widget%20List.html#play-animation-widget

https://ipywidgets.readthedocs.io/en/latest/reference/ipywidgets.html#ipywidgets.widgets.widget_int.Play

### Play ウィジェットの属性

Play ウィジェットには、主に下記の属性があります。

| 属性 | 意味 | デフォルト値 |
|:--|:--|:--|
| __`value`__  | 一定時間おきに値が変化する属性  | `0`  |
| __`min`__  | `value` 属性の最小値  | `0`  |
| __`max`__  | `value` 属性の最大値  | `100`  |
| __`step`__  | 時間経過による `value` 属性の変化量  | `1`  |
| __`interval`__  | `value` 属性が変化する間隔。単位はミリ秒  | `100`  |
| __`disabled`__ | `True` の場合にウィジェットを操作できなくなる | `False` |

### Play ウィジェットによるアニメーション処理

Play ウィジェットは、他のウィジェットと同様に __[`observe`](https://qiita.com/ysgeso/items/17c74178449148ad3ef7#%E3%82%A6%E3%82%A3%E3%82%B8%E3%82%A7%E3%83%83%E3%83%88%E3%81%AE%E3%82%A4%E3%83%99%E3%83%B3%E3%83%88%E3%83%8F%E3%83%B3%E3%83%89%E3%83%A9%E3%81%A8-observe-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89)__ メソッドを使ってその __属性が変化した際に実行するイベントハンドラを結び付ける__ ことができ、その __イベントハンドラに画像の表示を更新する処理を記述する__ ことで、アニメーションを行うことができます。

アニメーションの __fps__ は、1 秒間に表示する画像の数なので、「__1000 / `interval` 属性の値__」という式で計算できます。例えば __`interval` 属性に `100` を代入__ した場合のアニメーションは、1000 / 100 = __10 fps__ のアニメーションになります。

逆に、__fps から `interval` 属性の値を求める__ 場合は、「__1000 / fps__」 という式で計算できます。例えば __20 fps__ のアニメーションは、`inteval` 属性に 1000 / 20 = __50 を設定__ します

下記は、__赤い正方形の辺の長さを 1 から 10 まで増やしながら表示する__ というアニメーションを、__10 fps__ で行うプログラムです。実行すると、実行結果の左図のような表示が行われ、三角形のボタンをクリックすると、右図のようなアニメーションが表示されます。

なお、イベントハンドラは `value` 属性が変更された際に呼び出され、__`value` 属性の値__ は Play ウィジェットの __三角形のボタンをクリックするまでは変化しない__ ので、下記のプログラムを __実行した直後__ は、__Figure には何も表示されません__。

* __3 ~ 5 行目__：ヘッダ[^2]の無い Figure を作成し、Axes の軸を表示しないようにする
* __7 行目__：`value` 属性の初期値が 1、最小値が 1、最大値が 10、fps が 10 になるように `interval` 属性が `100` の Play ウィジェットを作成し `play` に代入する
* __9 ~ 17 行目__：Play ウィジェットの `value` 属性が変化した際に呼び出されるイベントハンドラを定義する
* __10 ~ 13 行目__：それまでに Axes に表示されていた内容をクリアし、Axes の表示範囲を設定し、軸を表示しないようにする
* __15 行目__：更新された Play ウィジェットの `value` 属性の値をローカル変数 `value` に代入する。なお、この部分には `value = play.value` を記述しても良い
* __16、17 行目__：(0, 0) を頂点とし、縦横の辺の長さが `value` の赤い正方形の Artist を作成し、Axes に登録して表示する
* __19 行目__：Play ウィジェットに、`value` 属性の値が変更された際に呼び出されるイベントハンドラを結び付ける

```python
 1  import matplotlib.patches as patches
 2
 3  fig, ax = plt.subplots(figsize=(3, 3))
 4  fig.canvas.header_visible = False
 5  ax.axis("off")
 6
 7  play = widgets.Play(value=1, min=1, max=10, intervale=100)
 8
 9  def on_play_changed(changed):
10      ax.clear()
11      ax.set_xlim(0, 10)
12      ax.set_ylim(0, 10)
13      ax.axis("off")
14    
15      value = changed["new"]    
16      rect = patches.Rectangle(xy=(0, 0), width=value, height=value, fc="red")
17      ax.add_artist(rect)
18    
19  play.observe(on_play_changed, names="value")
20
21  display(play)    
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
import matplotlib.patches as patches

fig, ax = plt.subplots(figsize=(3, 3))
fig.canvas.header_visible = False
a x.axis("off")

play = widgets.Play(value=1, min=1, max=10, intervale=100)

def on_play_changed(changed):
    ax.clear()
    ax.set_xlim(0, 10)
    ax.set_ylim(0, 10)
    ax.axis("off")
    
    value = changed["new"]    
    rect = patches.Rectangle(xy=(0, 0), width=value, height=value, fc="red")
    ax.add_artist(rect)
    
play.observe(on_play_changed, names="value")

display(play)    
```
</details>

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/676030a0-c0e9-fe71-86bc-1a0b3aef1e1f.png" width="200">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/d0d8a11e-489b-14a6-26e1-3d5bbf1c87b5.gif" width="200">

上記のプログラムを実行して、Play ウィジェットの三角形のボタンをクリックすると、下記のような処理が行われるため、上図右のようなアニメーションが行われます。なお、上図右では、アニメーションがリピートしますが、__実際に表示されるアニメーション__ では、三角形のボタンを押しただけでは __アニメーションのリピートは行われません__。Play ウィジェットの右のボタンをクリックしてから三角形のボタンをクリックすることでアニメーションがリピートするようになります。

* `play.value` が 100 ミリ秒おきに 1 増えるようになる。
* `value` 属性の値が変更されると、`on_play_changed` が呼び出される
* `on_play_changed` では、`value` 属性の値を辺の長さとする赤い正方形を描画する
* 上記から、1000 / 100 = 10 fps のアニメーションが表示される

:::note
matplotlib を利用したアニメーションは、matplotlib の __ArtistAnimation__ や __FuncAnimation__ を使って作成することもできます。ただし、これらを使ってアニメーションを作成する場合は、アニメーションの __すべてのフレームの画像を用意する必要__ があります。〇×ゲームのゲーム木には 50 万以上のノードが存在するので、〇×ゲームのゲーム木の生成過程を表すアニメーションを作成するためには、50 万以上のフレームの画像を作成する必要があるため、__アニメーションを開始する前__ に、__かなりの時間が必要__ になります。そのため、本記事ではそれらは採用しません。

なお、ArtistAnimation などには、アニメーションの作成に時間がかかるという欠点がありますが、動画ファイルとして保存することができるなどの利点があります。

matplotlib の ArtistAnimation や FuncAnimation を使ったアニメーションに興味がある方は、下記のリンク先を参照して下さい。本記事でも、必要があればそれらの使い方を今後紹介するかもしれません。
:::

https://matplotlib.org/stable/users/explain/animations/animations.html#animations-using-matplotlib

:::note
具体的な手順は長くなるので説明しませんが、本記事の中で先程表示したアニメーションの画像は、FuncAnimation を使って作成した mp4 の動画を、アニメーション GIF の形式に変換したものです。アニメーション GIF に変換した理由は、Quiita には、mp4 の動画ファイルをアップロードすることができないからです。

なお、ArtistAnimation や FuncAnimation は、Figure のアニメーションを作成するためのものなので、Play ウィジェットや IntSlider ウィジェットなどをアニメーションに含めることはできません。以後の記事のアニメーション画像に Play ウィジェットなどを表示しないのはそのためです。
:::

### Play ウィジェットと IntSlider ウィジェットのリンク

__Play ウィジェットだけ__ では、アニメーションの __どのフレームが現在描画されているか__ が __わからない__ という問題があります。この問題を解決する方法の一つに、__Play ウィジェット__ と __IntSlider ウィジェット__ を __リンク__ して連動させるというものがあります。

ipywidgets のウィジェットは、__`jslink`__ という関数によって、__複数のウィジェットの属性をリンクして連動する__ ことができます。具体的には、下記のプログラムのように記述することで、リンクさせた片方のウィジェットの __属性の値が変更される__ と、__自動的にもう片方の属性の値がその値に変更される__ ようになります。

```python
widgets.jslink((ウィジェット1, 属性名1), (ウィジェット2, 属性名1))
```

下記は、先程のプログラムに IntSlider を加え、Play ウィジェットと IntSlider の __`value` 属性をリンク__ して連動させるようにしたものです。

* __3 行目__：Play と同じ `value`、`min`、`max` 属性の値を設定した IntSlider を作成する
* __4 行目__：Play と IntSlider の `value` 属性をリンクする
* __7 行目__：Play と IntSlider を HBox を使って横に並べて配置して表示する

```python
元と同じなので省略
1
2  play = widgets.Play(value=1, min=1, max=10, interval=100)
3  slider = widgets.IntSlider(value=1, min=1, max=10)
4  widgets.jslink((play, "value"), (slider, "value"))
5
元と同じなので省略
6
7  display(widgets.HBox([play, slider]))    
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
fig, ax = plt.subplots(figsize=(3, 3))
fig.canvas.header_visible = False
ax.axis("off")

play = widgets.Play(value=1, min=1, max=10, interval=100)
slider = widgets.IntSlider(value=1, min=1, max=10)
widgets.jslink((play, "value"), (slider, "value"))

def on_play_changed(changed):
    ax.clear()
    ax.set_xlim(0, 10)
    ax.set_ylim(0, 10)
    ax.axis("off")
    
    value = changed["new"]    
    rect = patches.Rectangle(xy=(0, 0), width=value, height=value, fc="red")
    ax.add_artist(rect)
    
play.observe(on_play_changed, names="value")

display(widgets.HBox([play, slider]))    
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
元と同じなので省略

play = widgets.Play(value=1, min=1, max=10, interval=100)
+slider = widgets.IntSlider(value=1, min=1, max=10)
+widgets.jslink((play, "value"), (slider, "value"))

元と同じなので省略

-display(play)    
+display(widgets.HBox([play, slider]))    
```
</details>

実行結果（Figure の部分は省略します）

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/5fe5c5a9-69ff-7552-b7d0-13a5300cfb4d.png" width="200">

上記のプログラムを実行すると、下図のように Play ウィジェットの右に IntSlider が表示されるようになます。また、Play ウィジェットと IntSlider ウィジェットが下記のように連動するようになります。

* Play ウィジェットの三角形のボタンをクリックすると、IntSlider が Play ウィジェットの `value` 属性の値に連動して変化するようになる
* IntSlider をドラッグして変更すると、Play ウィジェットの `value` 属性の値が連動して変更されてイベントハンドラが呼び出されるようになり、Figure の表示が更新される

:::note
さらに、< ボタンや > ボタンを加えることで、〇×ゲームのリプレイ機能のように、アニメーションのフレームを 1 つずつ前後にずらすことができるようになります。
:::

:::note
`jslink` による属性のリンクは、イベントハンドラの仕組みを使って行うこともできます。例えば、Play の `value` 属性が変更された際に呼び出されるイベントハンドラと、Slider の `value` 属性が変更された際に呼び出されるイベントハンドラに下記のように記述します。なお、イベントハンドラとウィジェットの結び付けは省略します。

```python
def on_play_changed(changed):
    slider.value = changed["new"]

def on_slider_changed(changed):
    play.value = changed["new"]
```

ただし、イベントハンドラの仕組みを使った連動には、以下のような欠点があるので、__属性の値を連動するだけ__ の場合は、__`jslink` を利用したほうが良い__ でしょう。

* イベントループからイベントハンドラが呼び出されるという仕組みから、連動が瞬時に行われず、ほんの少し時間が経過してから連動が行われる
* `jslink` による属性のリンクは、イベントハンドラの仕組みを利用していないので、属性の値が変更された瞬間にもう片方の属性の値が変更される
* `jslink` による属性のリンクは、2 つのイベントハンドラを定義する必要がなく、1 行で簡潔に記述できる

ただし、__`jslink`__ で行うことができるのは、__属性の値の連動だけ__ です。属性の値が変更した際に、画像の表示などの、属性の値の連動以外の処理を行いたい場合は、イベントハンドラを利用する必要がある点に注意して下さい。
:::

:::note
`jslink` は、2 つの属性を双方向にリンクしますが、片方向のみのリンクを行う `jsdlink`[^3]という関数もあります。

双方向と片方向の違いがわらない人がいるかもしれないので、具体例を挙げます。

双方向のリンクでは、属性 A と B があった時に、以下のような連動が行われます。

* 属性 A が変化した場合に、属性 B の値が変化する
* 属性 B が変化した場合に、属性 A の値が変化する

片方向のリンクでは、属性 A と B があった時に、以下のような連動が行われます。

* 属性 A が変化した場合に、属性 B の値が変化する
* 属性 B が変化した場合に、属性 A の値は変化しない

なお、イベントハンドラの仕組みで属性のリンクを記述する場合は、片方のウィジェットのイベントハンドラのみを記述することで片方向のリンクになります。
:::

`jslink`、`jsdlink` の詳細については、下記のリンク先を参照して下さい。

https://ipywidgets.readthedocs.io/en/latest/examples/Widget%20Events.html#linking-widgets-attributes-from-the-client-side

## アニメーションの仕様

アニメーションを行う方法がわかったので、ゲーム木の生成の過程の __アニメーションの仕様を決める__ ことにします。どのような仕様が良いかについて少し考えてみて下さい。

一つの方法として、__ルートノードのみのゲーム木から始め__、Play ウィジェットの __`value` 属性の値が 1 増える__ ごとに、幅優先アルゴリズムと同じ順番で __ゲーム木にノードを追加__ し、それを表示するという方法が考えられるでしょう。ただし、本記事ではこの方法は、下記の理由から採用しないことにします。

* 上記のアニメーションを行うためには、`value` 属性の値が 1 増えた際に、ゲーム木に対して、幅優先アルゴリズムと同じ順番で、__ノードを 1 つだけ追加するという処理__ を行う必要がある。そのような処理を、これまでに説明した方法で行うのは困難である
* 上記の方法でアニメーションを行った場合に、__IntSlider の値を大きく増やす__ と、__処理に時間がかかってしまう__。例えば、IntSlider の値を __0 から 約 50 万__ に増やした場合、__50 万個のノードをゲーム木に追加__ する必要があるため、__かなりの時間が必要__ になる。このことは、ゲーム木を作成する際に 30 秒以上の時間が必要になることから明らかである
* __IntSlider の値を減らした場合__ に、ゲーム木を __一から作り直す__ 必要が生じる

もう一つの方法としては、__完成したゲーム木__ に対して、Play ウィジェットの `value` 属性の値が 1 増えるごとに、幅優先アルゴリズムと __同じ順番__ でゲーム木に __追加したノード__ を、__赤い枠で選択状態にして表示する__ という方法が考えられます。具体的には、下記のような方法でアニメーションを表示します。

* アニメーションのフレームを 0 番から数えることにする
* 0 番のフレームには、ルートノードが選択状態になった部分木を描画する

* n 番のフレームには、ゲーム木に n 番目に追加されたノードが中心かつ、選択状態になった部分木を描画する

このアニメーションでは、表示される __部分木の赤い枠のノードを見る__ ことで、__どのような順番でゲーム木にノードが追加されていくか__ を知ることができます。

また、この方法では、ゲーム木を __新しく作り直す必要はない__ ので、IntSlider でアニメーションのフレームを大きく増やしても、表示に大きな時間がかかるようなことはありません。

ただし、上記の方法で本当にわかりやすいアニメーションが表示できるという保証はありませんので、上記の方針でアニメーションを実装した結果、わかりづらいことが判明した時点で、必要に応じて仕様を修正することにします。

### `Mbtree` クラスの修正

上記のようなアニメーションを行うためには、ゲーム木の __各ノード__ が、__ゲーム木に追加された順番を記録__ する必要があります。そのような情報は、__list の要素__ に、ゲーム木に __追加された順番でノードを代入__ することで表現することができます。

そこで、Mbtree クラスに、その情報を代入する __`nodelist`__ という属性を追加することにします。そうすることで、Play ウィジェットの __`value` 属性__ の値を __`nodelist` のインデックス__ とすることで、__`value` 番のフレーム__ に表示する部分木の __選択されたノードを計算__ することができるようになります。

幅優先探索では、__深さが浅い順にノードを追加__ し、__各深さのノードの情報__ は、ゲーム木に __追加された順番__ で Mbtree クラスの __`nodelist_by_depth` 属性に代入__ されています。そのため、__`nodelist`__ は、下記のプログラムのように記述することで計算できます。

* __5 行目__：`nodelist` 属性を空の list で初期化する
* __8 行目__：`nodelist` に、深さが浅い順に `nodelist_by_depth` に記録されたノードの list を `+=` 演算子で __[拡張](https://qiita.com/ysgeso/items/59e51d983a32ac4bc5db#-%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%AB%E3%82%88%E3%82%8B-list-%E3%81%AE%E7%B5%90%E5%90%88)__ する

```python
 1  from marubatsu import Marubatsu
 2
 3  def create_tree_by_bf(self):
元と同じなので省略
 4      self.nodenum = 0
 5      self.nodelist = []
 6      for nodelist in self.nodelist_by_depth:
 7          self.nodenum += len(nodelist)
 8          self.nodelist += nodelist
 9      print(f"total node num = {self.nodenum}")
10    
11  Mbtree.create_tree_by_bf = create_tree_by_bf
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
from marubatsu import Marubatsu

def create_tree_by_bf(self):
    # 深さ 0 のノードを、子ノードを作成するノードのリストに登録する
    nodelist = [self.root]
    depth = 0
    # 各深さのノードのリストを記録する変数を初期化する
    self.nodelist_by_depth = [ nodelist ]
    
    # 深さ depth のノードのリストが空になるまで繰り返し処理を行う
    while len(nodelist) > 0:
        childnodelist = [] 
        for node in nodelist:
            if node.mb.status == Marubatsu.PLAYING:
                node.calc_children()
                childnodelist += node.children
        self.nodelist_by_depth.append(childnodelist)
        nodelist = childnodelist
        depth += 1
        print(f"{len(nodelist):>6} depth {depth} node created")
        
    self.nodenum = 0
    self.nodelist = []
    for nodelist in self.nodelist_by_depth:
        self.nodenum += len(nodelist)
        self.nodelist += nodelist
    print(f"total node num = {self.nodenum}")
    
Mbtree.create_tree_by_bf = create_tree_by_bf
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
from marubatsu import Marubatsu

def create_tree_by_bf(self):
元と同じなので省略
    self.nodenum = 0
+   self.nodelist = []
    for nodelist in self.nodelist_by_depth:
        self.nodenum += len(nodelist)
+       self.nodelist += nodelist
    print(f"total node num = {self.nodenum}")
    
Mbtree.create_tree_by_bf = create_tree_by_bf
```
</details>

上記の修正後に、下記のプログラムで Mbtree クラスのインスタンスを作成しなおし、2 行目で __`nodelist` 属性の要素の数__ を表示すると、__total node num の行で表示された値と同じ値が表示__ されることが確認できます。また、3 行目から __`nodelist` の先頭の要素__ に、__ルートノードが代入されている__ ことが確認できます。

```python
mbtree = Mbtree()
print(len(mbtree.nodelist))
print(mbtree.nodelist[0] is mbtree.root)
```

実行結果

```
     9 depth 1 node created
    72 depth 2 node created
   504 depth 3 node created
  3024 depth 4 node created
 15120 depth 5 node created
 54720 depth 6 node created
148176 depth 7 node created
200448 depth 8 node created
127872 depth 9 node created
     0 depth 10 node created
total node num = 549946
549946
True
```

## `Mbtree_Anim` クラスの定義

__アニメーションの処理__ は、Play ウィジェットや IntSlider ウィジェットを利用した __GUI のプログラム__ なので、Mbtree_GUI クラスと同様に、__GUI クラスを継承__ した __Mbtree_Anim__ というクラスを定義して実装することにします。

下記は Mbtree_Anim クラスの定義です。__Mbtree_Anim__ では __ゲーム木の部分木を描画する__ ので、__`__init__`__ メソッドには、下記のプログラムのように、__Mbtree_GUI__ クラスの `__init__` メソッドと __ほぼ同様の処理__ を記述します。

ただし、Mbtree_Anim クラスで表示する部分木の __選択されたノード__ は、後述の __`update_gui`__ メソッドの中で、アニメーションの __フレームの番号__ を表す Play ウィジェットの __`value` 属性から計算する__ ことになるので、__Mbtree_GUI__ クラスの `__init__` メソッドで行っていた、`selectednode` 属性にルートノードを代入する `self.selectednode = self.mbtree.root` という処理を __記述する必要ありません__。

`__init__` メソッド以外のメソッドの定義は、この後で行います。

```python
class Mbtree_Anim(GUI):
    def __init__(self, mbtree, size=0.15):
        self.mbtree = mbtree
        self.size = size
        self.width = 50
        self.height = 64
        super().__init__()
        
    def create_widgets(self):
        pass
    
    def display_widgets(self):
        pass
    
    def create_event_handler(self):
        pass
    
    def update_gui(self):
        pass
```

<details><summary><strong>Mbtree_GUI クラスの <code>__init__</code> メソッドからの修正箇所</strong></summary>

```diff_python
    def __init__(self, mbtree, size=0.15):
        self.mbtree = mbtree
        self.size = size
        self.width = 50
        self.height = 64
-       self.selectednode = self.mbtree.root
        super().__init__()
```
</details>

### `create_widgets` メソッドの定義

Mbtree_Anim クラスでは、Play ウィジェット、IntSlider ウィジェット、Figure を表示するので、`create_widgets` メソッドは下記のように定義します。その際に、アニメーションの fps を決める必要がありますが、今回の実装ではアニメーションがあまり速くなりすぎないように、2 fps に設定しました。

* __2 行目__：ゲーム木の __ノードの数__ は __`self.mbtree.nodenum`__ に代入されているので、Play ウィジェットの __`value` 属性の最大値__ を表す __`max`__ 属性には __その値から 1 を引いた値を代入__ する。list のインデックスが 0 から数え始めるので 1 を引く必要がある点に注意する事。また、fps が 2 のアニメーションを行うために、`interval` に 500 を代入した
* __3 行目__：IntSlider ウィジェットは Play ウィジェットとリンクさせるので、__`max` 属性に同じ値を代入__ する。また、__Intslider の左に frame という文字列が表示__ されるようにするために、__`description` 属性に `"frame"` を代入__ した
* __4 行目__：Play と IntSlider ウィジェットの __`value` 属性をリンク__ させる
* __6 ~ 13 行目__：Figure を作成する。この部分は Mbtree_GUI と全く同じである

```python
 1  def create_widgets(self):
 2      self.play = widgets.Play(max=self.mbtree.nodenum - 1, interval=500)
 3      self.slider = widgets.IntSlider(max=self.mbtree.nodenum - 1, description="frame")
 4      widgets.jslink((self.play, "value"), (self.slider, "value"))  
 5
 6      with plt.ioff():
 7          self.fig = plt.figure(figsize=[self.width * self.size,
 8                                          self.height * self.size])
 9          self.ax = self.fig.add_axes([0, 0, 1, 1])
10      self.fig.canvas.toolbar_visible = False
11      self.fig.canvas.header_visible = False
12      self.fig.canvas.footer_visible = False
13      self.fig.canvas.resizable = False 
14    
15  Mbtree_Anim.create_widgets = create_widgets
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
def create_widgets(self):
    self.play = widgets.Play(max=self.mbtree.nodenum - 1, interval=500)
    self.slider = widgets.IntSlider(max=self.mbtree.nodenum - 1, description="frame")
    widgets.jslink((self.play, "value"), (self.slider, "value"))
    
    with plt.ioff():
        self.fig = plt.figure(figsize=[self.width * self.size,
                                        self.height * self.size])
        self.ax = self.fig.add_axes([0, 0, 1, 1])
    self.fig.canvas.toolbar_visible = False
    self.fig.canvas.header_visible = False
    self.fig.canvas.footer_visible = False
    self.fig.canvas.resizable = False 
    
Mbtree_Anim.create_widgets = create_widgets
```
</details>

:::note
`value`、`min`、`step` 属性は、デフォルト値である `0`、`0`、`1` で良いので上記では記述しませんでしたが、それらの属性の値を明確にしたい人は下記のプログラムのように記述して下さい。

```python
    self.play = widgets.Play(value=0, min=0, max=self.mbtree.nodenum - 1,
                             step=1, interval=500)
    self.slider = widgets.IntSlider(value=0, min=0, max=self.mbtree.nodenum - 1, 
                             step=1, description="frame")
```
:::

### `display_widgets` メソッドの定義

__`display_widgets`__ メソッドは下記のプログラムのように定義します。

* __2 行目__：Play と IntSlider ウィジェットを横に配置した Hbox を作成する
* __3 行目__：上記の Hbox と Figure を縦に配置して表示する

```python
def display_widgets(self):
    hbox = widgets.HBox([self.play, self.slider])
    display(widgets.VBox([hbox, self.fig.canvas]))
    
Mbtree_Anim.display_widgets = display_widgets
```

### `update_gui` メソッドの定義

__`update_gui`__ は下記のプログラムのように、Play ウィジェットの __`value` 番目にゲーム木に挿入されたノード__ を __中心かつ選択されたノードとする部分木__ を描画するように定義します。

* __2、3 行目__：__`value` 番目にゲーム木に挿入されたノード__ は、Mbtree クラスの __`nodelist` 属性__ に代入された list の `value` 番のインデックスの要素に代入されているので、`self.mbtree.nodelist[self.play.value]` で計算できる。それを `selectednode` 属性と `centernode` 属性に代入する

```python
 1  def update_gui(self):
元と同じなので省略   
 2      self.selectednode = self.mbtree.nodelist[self.play.value]
 3      self.centernode = self.selectednode
 4      if self.selectednode.depth <= 4:
 5          maxdepth = self.selectednode.depth + 1
 6      elif self.selectednode.depth == 5:
 7          maxdepth = 7
 8      else:
 9          maxdepth = 9
10      self.mbtree.draw_subtree(centernode=self.centernode, selectednode=self.selectednode, ax=self.ax, maxdepth=maxdepth)
11
12  Mbtree_Anim.update_gui = update_gui
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
def update_gui(self):
    self.ax.clear()
    self.ax.set_xlim(-1, self.width - 1)
    self.ax.set_ylim(0, self.height)   
    self.ax.invert_yaxis()
    self.ax.axis("off")   
    
    self.selectednode = self.mbtree.nodelist[self.play.value]
    self.centernode = self.selectednode
    if self.selectednode.depth <= 4:
        maxdepth = self.selectednode.depth + 1
    elif self.selectednode.depth == 5:
        maxdepth = 7
    else:
        maxdepth = 9
    self.mbtree.draw_subtree(centernode=self.centernode, selectednode=self.selectednode, ax=self.ax, maxdepth=maxdepth)
    
Mbtree_Anim.update_gui = update_gui
```
</details>

<details><summary><strong>修正箇所（Mbtree_GUI からの修正箇所です）</strong></summary>

```diff_python
def update_gui(self):
元と同じなので省略   
+   self.selectednode = self.mbtree.nodelist[self.play.value]
+   self.centernode = self.selectednode
    if self.selectednode.depth <= 4:
        maxdepth = self.selectednode.depth + 1
    elif self.selectednode.depth == 5:
        maxdepth = 7
    else:
        maxdepth = 9
    self.mbtree.draw_subtree(centernode=self.centernode, selectednode=self.selectednode, ax=self.ax, maxdepth=maxdepth)
    
Mbtree_Anim.update_gui = update_gui
```
</details>

:::note
上記のプログラムでは、`selectednode` 属性と、`centernode` 属性に値を代入しましたが、それらの属性の値は __`update_gui` メソッドの中でしか利用しない__ ので、__ローカル変数に代入してもかまいません__。ただし、そのようにすると `Mbtree_GUI` クラスの `update_gui` メソッドをコピーして `Mbtree_Anim` クラスの `update_gui` クラスを定義する際に、修正箇所が増えてしまうので、本記事では採用しませんでした。
:::

### `create_event_handler` メソッドの定義

`create_event_handler` には、下記のプログラムのように、__Play ウィジェットの `value` 属性の値が変更された場合__ に呼び出される __イベントハンドラを定義__ し、Play ウィジェットに結びつけます。また、このイベントハンドラが行う処理は、__Figure の表示の更新だけ__ なので、`update_gui` を呼び出す処理のみを記述します。

```python
def create_event_handler(self):
    def on_play_changed(changed):
        self.update_gui()
        
    self.play.observe(on_play_changed, names="value")
    
Mbtree_Anim.create_event_handler = create_event_handler
```

### 処理の確認

上記の修正後に、下記のプログラムを実行すると、実行結果の左図のように __ルートノード__ が __中心かつ、選択された部分木__ が表示されます。また、三角形のボタンをクリックすると、右図のようにゲーム木に __登録された順__ で、__赤い枠のノードが表示__ される __アニメーション__ が行われることと、__IntSlider をドラッグ__ することで、アニメーションの __任意のフレームの表示に移動できる__ ことを確認して下さい。

```python
mbtree_anim = Mbtree_Anim(mbtree)
```

実行結果（右図は 0 ~ 19 フレームまでのアニメーションの繰り返しです）

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/d9dbc19a-2aef-bdc7-0f2e-4087ad324b07.png" width="350">

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/55149a5e-26cb-8438-2614-d9f19625146d.gif" width="350">

:::note
上記のプログラムでアニメーションを行う際に、たまに表示が固まる場合があり、そのような場合は、しばらくすると固まっていた間のフレームの表示が飛ばされて、その先のフレームが表示されます。

この現象はおそらく、[以前の記事](https://qiita.com/ysgeso/items/c6d4a2da7b8118a5a143#fnref-2)のノートで説明した、利用できなくなったオブジェクトのデータをメモリから削除する、ガーベジコレクションという処理を Python が行っていることが原因である可能性が高いのではないかと思います。

Play ウィジェットは、interval で指定した時間が経過した際に、ガーベジコレクションなどの理由でイベントハンドラが実行できなかった場合は、その時の `value` の値に対するイベントハンドラの __呼び出しの処理が飛ばされる__ ようになっているようです。そのため、ガーベジコレクションが発生した場合は、その間のフレームの表示が飛ばされて、その先のフレームが表示されます。

ガーベジコレクションは、いつ、どれくらいの長さで行われるかが予測できないので、アニメーションの処理の最中に行われると、アニメーションのフレームのいくつかが飛んでしまうことになります。

なお、Python のガーベジコレクションの仕様が良くわからなかったので、上記のガーベジコレクションに関する説明は間違っているかもしれません。間違っている場合は、コメントで指摘していただけると嬉しいです。
:::

# 今回の記事のまとめ

今回の記事では、マウス操作による中心となるノードの移動に関する処理の修正と、ゲーム木の作成の過程を表示するアニメーションの実装を行いました。

ただし、今回作成したアニメーションにはいくつかの問題点があるので、ゲーム木の生成過程があまりわかりやすく表示されません。次回の記事ではそれらを修正することにします。余裕がある方は、どのような問題点があるかについて考えてみて下さい。

# 本記事で入力したプログラム

| リンク | 説明 |
|:--|:--|
| [marubatsu.ipynb](https://github.com/ysgeso/marubatsu/blob/master/097/marubatsu.ipynb)  | 本記事で入力して実行した JupyterLab のファイル |
| [tree_new.py](https://github.com/ysgeso/marubatsu/blob/master/097/tree_new.py)  |  今回の記事で更新した tree.py |

# 次回の記事

https://qiita.com/ysgeso/items/10449c1d8e1465de1ed1

[^1]:深さが 8 以下のノードで決着がついたため、深さが 9 のノードが存在しない場合は除きます
[^2]:Figure の上部に表示される Figure のタイトルのことです
[^3]:`jsdlink` の `d` は、おそらく方向を表す directional の d だと思います。