シンプルなBehaviour Treeを実装してみる

2015/06/26

chobi_e

みなさまこんばんは。ちょびえです。
今日はちょっと趣向を変えてゲームのAIの勉強、なかでもBehaviour Treeについてすこし勉強してみましょう。

ゲームの世界のAIってなんだっけ？

ゲームの世界のAIといえばよくある経路探索や、特定状況下におけるNPC等のふるまいをよしなにやってくれるようなものです。AIっていわれてしまうとなんだか難しいように感じてしまいますが、ゲームという枠組みの中では時間経過や環境の変化を自立して判断したり・判断してるようにみせかけて楽しめるような仕組みとなっていれば良いと思います。

Behaviour Treeにチャレンジしてみる

細かい説明はググっていただくと色々と記載あるのでなんとなくビヘイビアツリーってわかるような、うーん・・・文章で書かれてもよくわからないですね！ということでお決まりの通りコードで書いてみましょう。

いきなりコード書いてもまったくわからないのでざっくりな説明をしますと、Behaviour Treeは木構造でノードとリーフでルールとアクションを評価・実行していきます。

ノードの種類としては大きく分けてSelectorとSequencerという2つの種類があるようです。おおまかに説明すると

Selectorはリーフが成功するまで下位ノードを実行し続ける。
Sequencerはリーフが成功し続けるか終端に行くまで下位ノードを実行し続ける。

と、いうことになっています。とりあえず実装してみましょうか。

まずは最小で実装してみよう

適当なコードを書くときにはやっぱりPHP便利なのでPHPでかいてみます。
Treeまで考えると少し長くなってしまいますので、まずは各ノードのふるまいをなんとなく書いてみましょう。

ノードの結果がtrueであれば成功、falseであれば失敗ということにしておきます。

単純なSelector

Selectorは自身が持っているノードを成功し続けるまで評価していくノードです。

<?php

$selector = array();
$selector[] = function() {echo "Hello"; return false;};
$selector[] = function() {echo "World"; return true;};

foreach ($selector as $node) {
  if ($node()) {
     echo PHP_EOL;
     exit;
  }
  echo " ";
}

<?php

$selector = array();

$selector[] = function() {echo "Hello"; return false;};

$selector[] = function() {echo "World"; return true;};

foreach ($selector as $node) {

if ($node()) {

echo PHP_EOL;

exit;

}

echo " ";

}

Helloに失敗してしまっているので、Worldが実行されます。

単純なSequencer

Sequencerは自身が持っているノードを失敗するまで評価していくノードです。

<?php

$sequencer= array();
$sequencer[] = function() {echo "Hello"; return true;};
$sequencer[] = function() {echo "World"; return false;};
$sequencer[] = function() {echo "Chobie"; return true;};

foreach ($sequenceras $node) {
  if (!$node()) {
     echo PHP_EOL;
     exit;
  }
  echo " ";
}

<?php

$sequencer= array();

$sequencer[] = function() {echo "Hello"; return true;};

$sequencer[] = function() {echo "World"; return false;};

$sequencer[] = function() {echo "Chobie"; return true;};

foreach ($sequenceras $node) {

if (!$node()) {

echo PHP_EOL;

exit;

}

echo " ";

}

上記の例ではWorldで失敗しているのでChobieまで実行されていないのがわかります。

組み合わせ

今の実装だと木構造が作れないのでとても単純なタスクしかできません。
とりあえずのTree構造が取れるように、実装の楽さ優先で書いてみます。

とりあえず各リーフでHello,World,I,am,chobieという単語だけを出力できるように書いてみます。

<?php
class Action {
     public $cb;
     function __construct($cb) {$this->cb = $cb;}
     function __invoke() {$cb = $this->cb;return $cb();}
}
class Base {
     public $array = array();
     static function Create() {return new Selector();}
     function Add($node) {$this->array[] = $node;return $this;}    
}
class Selector extends Base {
     function __invoke() {
          foreach ($this->array as $node) {
               if ($node()) {
                    echo PHP_EOL;
                    return true;
               }
               echo " ";
          }
          return false;
     }
}
class Sequencer extends Base {
     function __invoke() {
          foreach ($this->array as $node) {
               if (!$node()) {
                    echo PHP_EOL;
                    return false;
               }
               echo " ";
          }
          return true;
     }
}

$selector = new Selector();
$selector->Add(Selector::Create()
     ->Add(new Action(function() {echo "Hello"; return false;}))
     ->Add(new Action(function() {echo "World"; return false;}))
);
$selector->Add(Selector::Create()
     ->Add(new Action(function() {echo "I"; return false;}))
     ->Add(new Action(function() {echo "am"; return false;}))
     ->Add(new Action(function() {echo "chobie"; return true;})) // ここまででおわろう！
     ->Add(new Action(function() {echo "san"; return false;}))
);
$selector->Add(Selector::Create()
     ->Add(new Action(function() {echo "Nyaaan"; return false;})) // これは実行されない
);
$selector();

<?php

class Action {

public $cb;

function __construct($cb) {$this->cb = $cb;}

function __invoke() {$cb = $this->cb;return $cb();}

}

class Base {

public $array = array();

static function Create() {return new Selector();}

function Add($node) {$this->array[] = $node;return $this;}

}

class Selector extends Base {

function __invoke() {

foreach ($this->array as $node) {

if ($node()) {

echo PHP_EOL;

return true;

}

echo " ";

}

return false;

}

class Sequencer extends Base {

function __invoke() {

foreach ($this->array as $node) {

if (!$node()) {

echo PHP_EOL;

return false;

}

echo " ";

}

return true;

}

$selector = new Selector();

$selector->Add(Selector::Create()

->Add(new Action(function() {echo "Hello"; return false;}))

->Add(new Action(function() {echo "World"; return false;}))

);

$selector->Add(Selector::Create()

->Add(new Action(function() {echo "I"; return false;}))

->Add(new Action(function() {echo "am"; return false;}))

->Add(new Action(function() {echo "chobie"; return true;})) // ここまででおわろう！

->Add(new Action(function() {echo "san"; return false;}))

);

$selector->Add(Selector::Create()

->Add(new Action(function() {echo "Nyaaan"; return false;})) // これは実行されない

);

$selector();

これを実行してみると

Hello World  I am chobie

1 2	Hello World I am chobie

期待通り実行出来ましたね！図で書いてみるとこんな感じです。

数字は評価順。赤い枠はtrueを返している（成功している）、灰色は実行されていない、黒色は失敗を表しています。
今回はSelectorだけで組んでいるので、失敗してほしいノードを先に持ってきておいて調節しています。

上記例では実行条件チェックがなく、実際の行動とごっちゃになっていますが例えばこんな風に書いてノードにつっこんでおけばとりあえず色々なルールが書けると思います。

new Action(function() {
  if (!お昼メイツがいる) {
    return false;
  }
  一緒にランチを食べる();
  return true;
})

new Action(function() {
  if (!お小遣いが千円ある) {
    return false;
  }
  ラーメンを食べに行く();
  return true;
})

new Action(function() {
  if (!お小遣いが500円ある) {
    return false;
  }
  お弁当を買いに行く();
  return true;
})
new Action(function() {
  水を飲む();
  return true;
})

new Action(function() {

if (!お昼メイツがいる) {

return false;

}

一緒にランチを食べる();

return true;

})

new Action(function() {

if (!お小遣いが千円ある) {

return false;

}

ラーメンを食べに行く();

return true;

})

new Action(function() {

if (!お小遣いが500円ある) {

return false;

}

お弁当を買いに行く();

return true;

})

new Action(function() {

水を飲む();

return true;

})

こういう事前条件チェックの大半は他でやるべきことなのでアクションの実行と一緒にしてしまうと使い回し面倒なんですけどネ。

おわりに

Behaviour Treeのファーストステップとしてはこれぐらいでいいんじゃないでしょうか?

Decoratorや実行状態管理等がなく、このまま巨大なルールを構築するとひたすらつらいだけですが、とりあえず遊んでみるのには十分な実装だとおもいます。

これぐらいの単純な例だとif分で素直に書けばいいじゃないとか色々あると思いますが、こんなふうなルールを設定ファイル等から組めるようにしておけば色々なパターンをコード書かずに試せるのでおもしろいのですよ。ということで今日も楽しんでいきましょう