cocos,A*,クオータービュー

適当に作った。

SDAsterNode::findPath()を呼び出せば、ゴールからの経路のVectorがかえってくる。
そのままコピーでは使えないが、以下を変えれば動く。
・MapPositionはx,y,zの座標とマップ名が入ってる。ので適宜x,yなどのcocos2d::Refのサブクラスにする。
・キャラクタは段差1を登り、2を降りることができるようにz座標の重み付けをしている。
・SDMapNode::makeTagは、x+y100+z10000のstringを返す。

```C++:SDAstar.h`
#pragma once
#include "SDMapPosition.h"
#include "SDGameParts.h"

namespace sevendays {

class SDAstarNode : public cocos2d::Ref{

public:
    SDAstarNode(MapPosition *pos, int heuristic):m_mpos(pos), m_heuristic(heuristic) {
        m_parent = nullptr;
    };
    int m_heuristic;
    MapPosition *m_mpos;
    SDAstarNode *m_parent;
    static cocos2d::Vector<MapPosition *> findPath(
                                                   MapPosition *start,
                                                   MapPosition *end,
                                                   const cocos2d::Map<std::string, SDGameParts *> jungleGym);
};

};

```C++:SDAstar.cpp`
//
// Created by Akinori ADACHI on 2014/07/09.
// Wikipediaを参考にA*アルゴリズムを実装した


#include "SDAstar.h"
#include "SDMapPosition.h"
#include "SDMapNode.h"
#include "SDGameParts.h"

using namespace sevendays;
using namespace cocos2d;

static int _gAster(MapPosition *pos, MapPosition *start);

static int _hAster(MapPosition *pos, MapPosition *end);

static SDAstarNode *littleHeuristic(
        MapPosition *start,
        MapPosition *end,
        Map<std::string, SDAstarNode *> nodes);

Vector<MapPosition *> SDAstarNode::findPath(
        MapPosition *start,
        MapPosition *end,
        const cocos2d::Map<std::string, sevendays::SDGameParts *> jungleGym) {

    Map<std::string, SDAstarNode *> opens;
    Map<std::string, SDAstarNode *> closes;

    std::vector<SDAstarNode *> path;

    SDAstarNode *startNode = new SDAstarNode(start, _hAster(start, end));
    SDAstarNode *endNode = nullptr;
    opens.insert(SDMapNode::makeTag(start->m_x, start->m_y, start->m_z), startNode);

    while (true) {
        //OpenListが空なら探索失敗
        if (opens.empty()) {
            break;
        }

        //ヒューリスティックが最小のノードを取り出す
        auto node = littleHeuristic(start, end, opens);

        //ゴールと一致なら探索終了
        if (node->m_mpos->equalTo(end)) {
            endNode = node;
            break;
        }
        

        closes.insert(SDMapNode::makeTag(node->m_mpos->m_x, node->m_mpos->m_y, node->m_mpos->m_z), node);
        opens.erase(SDMapNode::makeTag(node->m_mpos->m_x, node->m_mpos->m_y, node->m_mpos->m_z));

        SDGameParts *currentCube = jungleGym.at(
                SDMapNode::makeTag(node->m_mpos->m_x,
                        node->m_mpos->m_y,
                        node->m_mpos->m_z));
        int currentHigh = currentCube->getHarf() ? 1 : 2;

        //隣接ノードに対する操作
        for (int xoffs = -1; xoffs <= 1; xoffs++) {
            for (int yoffs = -1; yoffs <= 1; yoffs++) {
                int cost = 1;
                if (yoffs == xoffs) {
                    continue;
                }
                if (xoffs && yoffs) {
                    continue;
                }
                if((node->m_mpos->m_x + xoffs) < 0 or (node->m_mpos->m_x + xoffs) > 13){
                    continue;
                }
                if((node->m_mpos->m_y + yoffs) < 0 or (node->m_mpos->m_y + yoffs) > 13){
                    continue;
                }
                for (int zoffs = -1; zoffs <= 1; zoffs++) {
                    if(node->m_mpos->m_z + zoffs < 0){
                        continue;
                    }
                    SDGameParts *cube = jungleGym.at(
                            SDMapNode::makeTag(node->m_mpos->m_x + xoffs,
                                    node->m_mpos->m_y + yoffs,
                                    node->m_mpos->m_z + zoffs));
                    
                    if (!cube) {
                        continue;
                    }
                    if (!(cube->getWalkable())) {
                        continue;
                    }
                    int high = (cube->getHarf() ? 1 : 2) + zoffs * 2;
                    if (high - currentHigh > 1) {
                        continue;
                    }
                    if (high - currentHigh < -2) {
                        continue;
                    }

                    //int gAster = _gAster(node->m_mpos, start);
                    int gAster = node->m_heuristic - _hAster(node->m_mpos,end);
                    int hAster = _hAster(MapPosition::createWithParams(
                            node->m_mpos->m_mapId,
                            (node->m_mpos->m_x + xoffs),
                            (node->m_mpos->m_y + yoffs),
                            (node->m_mpos->m_z + zoffs)), end);
                    int heuristic = gAster + hAster + cost;

                    SDAstarNode *nodeInOpen = opens.at(
                            SDMapNode::makeTag(node->m_mpos->m_x + xoffs,
                                    node->m_mpos->m_y + yoffs,
                                    node->m_mpos->m_z + zoffs));
                    if (nodeInOpen) {
                        if (heuristic < nodeInOpen->m_heuristic) {
                            nodeInOpen->m_heuristic = heuristic;
                            nodeInOpen->m_parent = node;
                        }
                        continue;
                    }

                    SDAstarNode *nodeInClose = closes.at(
                            SDMapNode::makeTag(node->m_mpos->m_x + xoffs,
                                    node->m_mpos->m_y + yoffs,
                                    node->m_mpos->m_z + zoffs));
                    if (nodeInClose) {
                        if (heuristic < nodeInClose->m_heuristic) {
                            nodeInClose->m_heuristic = heuristic;
                            nodeInClose->m_parent = node;
                            opens.insert(SDMapNode::makeTag(node->m_mpos->m_x + xoffs,
                                    node->m_mpos->m_y + yoffs,
                                    node->m_mpos->m_z + zoffs), nodeInClose);
                            closes.erase(SDMapNode::makeTag(node->m_mpos->m_x + xoffs,
                                    node->m_mpos->m_y + yoffs,
                                    node->m_mpos->m_z + zoffs));
                        }
                        continue;
                    }
                    SDAstarNode *newNode = new SDAstarNode(MapPosition::createWithParams(
                            node->m_mpos->m_mapId,
                            (node->m_mpos->m_x + xoffs),
                            (node->m_mpos->m_y + yoffs),
                            (node->m_mpos->m_z + zoffs)),
                            heuristic);
                    newNode->m_parent = node;
                    opens.insert(SDMapNode::makeTag(node->m_mpos->m_x + xoffs,
                            node->m_mpos->m_y + yoffs,
                            node->m_mpos->m_z + zoffs), newNode);
                }
            }
        }
    }

    //
    Vector<MapPosition *> answer;
    if (!endNode) {
        return answer;
    }
    while (endNode->m_parent) {
        answer.pushBack(endNode->m_parent->m_mpos);
        endNode = endNode->m_parent;
    }
    return answer;
}

//g*(n)
int _gAster(MapPosition *pos, MapPosition *start) {
    int gAster = abs(pos->m_x - start->m_x)
            + abs(pos->m_y - start->m_y)
            + abs(pos->m_z - start->m_z);
    return gAster;
}

//h*(n)
int _hAster(MapPosition *pos, MapPosition *end) {
    int hAster = abs(end->m_x - pos->m_x)
            + abs(end->m_y - pos->m_y)
            + abs(end->m_z - pos->m_z);
    return hAster;
}

//最小の f*(n)をもつノードを取り出す
SDAstarNode *littleHeuristic(
        MapPosition *start,
        MapPosition *end,
        Map<std::string, SDAstarNode *> nodes) {
    int min = INT_MAX;
    SDAstarNode *littleHeuristic = nullptr;
    for (std::pair<std::string, SDAstarNode *> pair: nodes) {
        SDAstarNode *node = pair.second;
        int heuristic = _gAster(node->m_mpos, start) + _hAster(node->m_mpos, end);
        if (min > heuristic) {
            min = heuristic;
            littleHeuristic = node;
        }
    }
    return littleHeuristic;
}