経路検索して歩くドット絵RPG風キャラ

昨日は[d_nishiyama85](http://qiita.com/d_nishiyama85)さんによるResources以下のファイル一覧取得についての投稿でした。
実用的でいいですね。

## 自己紹介

[HappyHoppyHappy](https://twitter.com/happyh0ppyhappy)の[Smith](https://twitter.com/do_low)です。
弊社のほとんどのアプリの開発をしています。[iOS](https://itunes.apple.com/jp/artist/happyhoppyhappy-co.-ltd./id770282567)/[Android](https://play.google.com/store/apps/developer?id=HappyHoppyHappy+Co.,Ltd.&hl=ja)
ちょうど一年前くらいからスマフォアプリのゲームを作り始め、cocos2d-xもその時から触れ続けています。
なので、2.x系の事は知りません。
脱出ゲームとか、育成ゲームとか、タワーディフェンスとか、貧乏暇なしです。


## お題について

実用的かどうかは置いておいて、ゲームを作っている誰もが通る道になると思うので、何かのヒントになれば幸いです。
なお、TileMapは使用していませんので悪しからず。

弊社アプリで使用している脱出ゲーム用フレームワークの構成を元に書いています。
というか、思った以上にcocos2d-xっぽい内容になりませんでした。さーせん。

## 経路検索して歩くドット絵RPG風キャラとは

タップした場所にアニメーションしながら歩いて行くキャラクターです。
この遊び方画像が全てを表していると思います。

![b.png](https://qiita-image-store.s3.amazonaws.com/0/42873/36061947-d4ef-4b6a-54e8-51a888cc6d1d.png)

一見、簡単そうなことでも、中身は結構面倒くさかったりします。
以降、これを実現する手順を示していきます。

### 1. マップをマス目状にする

マップのマスターデータを定義します。

* 1マスのSize
* 縦横のマス数
* 各マスの地形情報（通行可否）
* 各マスの背景画像
* 人やモノの情報

この時点で面倒くさいですね。
マスターデータの定義の方法は何でもいいのですが、弊社の場合は大体、外部plistで設定しています。
必要なときだけ、FileUtilsのgetValueMapFromFileなどで展開する感じです。

**マス目の座標**

前提として、マスの集合から特定のマスを扱えるようにするために、各マスに座標の概念を適用します。
座標は特に明示する必要はなく、配列やvectorのインデックスを流用すれば良いでしょう。
本稿ではマス座標の表現に2種類の型を用いていますが、これらは同義です。

* 左上からZ字順で数えるマスのインデックスのint (以下、indexと表記)

* 左上を基準としたXY座標のVec2(以下、addressと表記)

```
Vec2 address = Vec2(map.width % index, floor(map.width / index))
int  index   = address.y * map.width + address.x
```

例えば10 x 10のマップのマスには下記のように座標が割り当てられます。
0,および(0,0)が画面の一番左上です。

![f.png](https://qiita-image-store.s3.amazonaws.com/0/42873/cf2a0961-7f29-23e4-f3c9-a94b5f3078ea.png)


#### 1マスのSize

キャラクター移動の距離単位や、マスの背景画像サイズと等しいSizeです。

#### 縦横のマス数

地形情報などを一次元配列で取り扱う場合、Y座標を求めるために必要です。

#### 各マスの地形情報、背景画像

全てのマスに対して通行可能かどうかと、背景画像idを定めます。
boolやintの配列で扱えるようになっていれば十分だと思います。

下記画像のように隣接するマスの間に壁を儲けようと思った場合は、見た目に大して縦横2倍の地形情報を用意するなどの工夫が必要です。

![g.png](https://qiita-image-store.s3.amazonaws.com/0/42873/aa83964e-d794-f5db-4e38-31560dc797c8.png)

#### 人やモノの情報

人やモノは全てのマスについて定義するほど数が多くはないので、インスタンスに対してマスのindexやaddressを与えた方がよいと思います。

```lang:PersonSample.cpp
// あくまでも例なので、こんな実装マネしちゃダメよ
struct Person
{
    int personId, eventId, imageId;
    Vec2 address;
    
    Person();
};

// インスタンスに対してaddressを明示
Person gentleman = {1, 1, 2, Vec2(4,3)};
Person lady      = {2, 4, 3, Vec2(6,7)};

```

下記は実際のゲーム画面ですが、青いマスは地形として通行不可なマス、赤いマスは人やモノがあるために通行不可なマスとして定義されています。

![d.png](https://qiita-image-store.s3.amazonaws.com/0/42873/add564ae-74f4-53f9-2860-623b1bf6a74a.png)



### 2. 移動先をタップで指定する

タップした座標を経路検索の目的地として設定するためaddressに変換します。
大抵、マップ画像はマップ用のLayerなどに入れてたりするので、適宜convertToNodeSpaceしてあげましょう。
また、マス座標Yは画面の上から数えるように定義しているので、cocos2d-xの座標Yとは反対になります。

![e.png](https://qiita-image-store.s3.amazonaws.com/0/42873/1ae308d0-c69f-3b94-cb4b-418ddbd6f6a4.png)

```lang:MoveSample.cpp

Vec2 MoveSample::getDestinationByTouch(Touch* touch)
{
    // タップ座標の取得
    Director* director = Director::getInstance();
    Vec2   touchLocation = director->convertToGL(touch->getLocationInView());
    Vec2   localLocation = this->convertToNodeSpace(touchLocation); // thisはマップ画像を含むLayer
    
    // タップ座標をaddressに変換
    Size  gridSize = Field.gridSize();
    float addressX = floor(localLocation.x / gridSize.width);
    float addressY = this->_mapSize.height - floor(localLocation.y / gridSize.height);
    
    return Vec2(addressX, addressY);
}
```

### 3. 経路検索

移動開始地点をキャラクターのいるマスの座標、移動終了地点をタップしたマスの座標として経路検索を行います。
検索結果はindexのvector\<int\>で受取るようにしています。

例えば下記の画像の左上を0とし、噴水や人を通行できないとした場合。
勇者の現在位置(65)から右上の村人の上のマス(17)までの経路は

vector\<int\> route = {66,67,57,47,37,36,26,16,17}

となるでしょう。

![a.png](https://qiita-image-store.s3.amazonaws.com/0/42873/1342a5ed-6efc-928e-1d47-7a21f31129be.png)

余談ですが、経路検索は検索対象が広くなると処理コストが跳ね上がるので、広大なマップで経路検索をされる場合は画面内に表示されているマスのみを切り出して使うと良いです。
切り取った地形情報は0からindexを振り直し、検索結果は現在地を元に還元するなどの処理で対応できます。


#### A*

A*は経路検索アルゴリズムの一つです。
他にもダイクストラとかありますが、弊社ではA*を採用しています。

[c++でA*検索が行えるソース](https://github.com/justinhj/astar-algorithm-cpp)が公開されていますが、このままでは組み込みに適さないので改修を加えています。
具体的には、mainに引数でマップ情報を渡し、経路のindexのvector<int>を返すようにしています。



### 4. 移動Action実行

移動する方向に合わせたSpriteFrameを表示しながら、Spriteの座標を動かします。
キャラクターの画像は四方向x足踏みx3が用意されています。
動的なAnimationの作成を行えるように、画像ファイルには命名規則を定めています。

```
person_[画像id]_[方向id]_[足踏みid].png
```

![c.png](https://qiita-image-store.s3.amazonaws.com/0/42873/a9ef9095-0e30-0672-c5b8-46e909850358.png)

Actionは経路の検索結果から生成します。
下記は移動アクション生成/実行処理のサンプルです。

※ *ソース中で使われるGeoは、メソッド名通りの処理をしているだけなので詳細は割愛します。*


```lang:CharacterSample.cpp
void CharacterSample::move(vector<int> route, function<void (Node*)> callback) {
    Sequence* seq = Sequence::createWithTwoActions(
        Spawn::createWithTwoActions(
            this->_createWalkAnimate(route), // Animate
            this->_createWalkMove(route)),   // Sequence
        CallFuncN::create(callback)); // 移動後地点のイベントの開始などが指定される
    
    this->runAction(seq);
}

```

_createWalkAnimateでは、routeの移動順序を１つずつ調べて、使用する向きのSpriteFrameを決定します。
画像の決定は、歩数も考慮します。

```lang:CharacterSample.cpp

Animate* CharacterSample::_createWalkAnimate(vector<int> route)
{
    SpriteFrameCache* cache = SpriteFrameCache::getInstance();
    
    Animation* animation = Animation::create();
    animation->setDelayPerUnit(this->_moveDuration);
    
    Vec2 currentAddress = this->_address;
    
    // 足踏み画像idの表示順
    vector<int> stepFrames = {1, 2, 1, 3};
    
    int i = 0;
    for (int index : route) {
        // 次の経路のindexから画像の向きを決める
        Vec2 nextAddress  = Geo::indexToAddress(index);
        int  newDirection = Geo::directionBetweenAddresses(currentAddress, nextAddress);
        
        // 命名規則通りに画像ファイルを指定する
        char file[64];
        sprintf(file, "person_%d_%d_%d.png", this->_imageId, newDirection, stepFrames.at(i % stepFrames.size()));
        animation->addSpriteFrame(cache->getSpriteFrameByName(file));
        
        // 現在のアドレスを進める
        currentAddress = nextAddress;
        i++;
    }
    
    return Animate::create(animation);
}

```

_createWalkMoveでは座標の移動を連続したMoveToで行います。
MoveToが1マス毎に実行されるのは、1マス毎のコールバック処理を行うためです。
コールバックでは、キャラクターが持つaddressとZOrderを更新します。
ZOrderを更新する理由は、背の高いノードの背後に回り込んだ場合などに前後関係として不自然な表示にならないようにするためです。

```lang:CharacterSample.cpp

FiniteTimeAction* CharacterSample::_createWalkMove(vector<int> route)
{
    // MoveToを行う回数が動的なので、Vectorで用意する
    Vector<FiniteTimeAction*> actions = Vector<FiniteTimeAction*>();
    
    for (int index : route) {
        // 実際の座標に移動
        actions.pushBack(MoveTo::create(this->_moveDuration, Geo::indexToVec2(index)));
        // 一歩毎の処理
        actions.pushBack(CallFuncN::create(bind(&CharacterSample::_onEachStep, this, placeholders::_1, index)));
    }
    
    // std::vectorでcreate出来るようにして欲しいな
    return Sequence::create(actions);
}

void CharacterSample::_onEachStep(Node* sender, int index)
{
    CharacterSample* self = static_cast<CharacterSample*>(sender);
    // ノードの現在位置情報を更新
    self->_address = Geo::indexToAddress(index);
    // 画像の前後関係が正しく表現されるようにZorderを更新
    self->setZOrder(self->_address.y);
}

```

これでドット絵RPG風キャラを経路検索して歩かせることが出来ました。
移動終了後のコールバックには、キャラクターのその場での足踏み開始、及びイベント処理などが入ります。

## まとめ

ドット絵風キャラクターをタップした箇所まで経路検索して自動移動させるには・・・

* **歩いているキャラクター画像を作る**
* **マップの地形情報を作る**
* **キャラクターの位置情報を持てるようにする**
* **タップした箇所の位置情報を取得出来るようにする**
* **地形情報で経路検索できるようにする**
* **経路検索結果からActionを作れるようにする**

これらをやってあげれば形になると思います。

移動後は更に各種イベントの開始などが待ち受けているので、ゲーム全体としてはこれはまだ最初の一歩です。
正直、キャラクターの移動はやっつけ仕事ですので、その後のイベント処理の実装の方が作ってて面白いと思います。
今回のお題にしようとも思いましたが、設計とかデザインとかOOPとか、今回よりも更にcocos2d-xっぽくない話題なのでやめときました。


以上です、ありがとうございました。

イブイブの明日は[tkyaji](http://qiita.com/tkyaji)さんです。
お楽しみに。

　
　
　


### おまけ：弊社開発環境

**脱出ゲームフレームワーク**

最初にちょっと書きましたが、脱出ゲームのフレームワーク的なものがあったりなかったりします。
(別に脱出ゲームばっか作ってるってワケじゃないです)

フレームワークは、その役割を下記のように定め、実装しています。

* **マップ描画**
背景と人、モノの描画とアニメーション

* **イベント管理/操作**
イベントフローを管理してキチンと順番通りに処理するハンドラ

* **イベント処理モジュール群**
メッセージ表示、数字合わせのパズル、店舗画面等の各イベントの実体で、管理/操作用の共通インターフェイスを持ったモジュール
本稿のお題である経路検索と移動もこちらのモジュールに分類されます

* **イベントフロー登録**
あるオブジェクトを調べたら、x秒待ってxマス歩いて特定のメッセージを表示して・・・等の定義を任意で行えるインターフェイスの提供
RPGツクールのイベント作成を想像してもらえるとわかりやすいです
そのため、ここの部分は中学生でも実装できるようにする、をモットーにして作りました。

* **Scene等の外部へ向けたインターフェイス**
DB操作など、FWが直接関わらない処理に関するDelegateの提供等

cocos2d-xにべったり依存しているので、本家のアップデートの度にリファクタを要する素敵な存在です。

**全アプリ共通コンポーネント**

下記は弊社の全アプリ共通で用いる基盤として作っています。
いくつもアプリを開発されるようであれば、この辺りは用意しておくと色々と捗ります。

* sqlite操作
* DBレコードやplistの内容(マスターデータ)のORマッピング
* ネイティヴ連携(SDK操作など)
* HTTP通信
* タップ処理のラップ
* Sceneの機能強化

　
　
　

**注釈**

本稿に使用している画像は開発中のもので、製品版とはさっぱり関係ありませんが
、いちおう著作権は弊社HappyHoppyHappyにあります。
転用しても大丈夫ですが、辱めるような行為はお控え下さい。
また、記載されているソースは掲載用に適宜改変していますので、動かねーぞとか言わないでね。