Explorer クラス

#include <Explorer.h>

Explorer 連携図

公開メンバ関数
	Explorer ()
void	createBlockArea ()
void	resetBlockArea ()
void	setHasBlockIn (std::int8_t blockID)
bool	hasBlock (std::int8_t id)
std::vector< int >	searchRoute (std::int8_t start, std::int8_t end)
Node *	calculateNeighborCost (Node *parent, std::vector< Node * > *around, std::int32_t realCost, std::int8_t end)
std::vector< Node * > *	getBlockAreaNodeList ()

詳解

ルート探索クラス

ETロボコン2018における、ブロック並べエリアのブロック置き場をノードとしたルート探索を行います。 斜め移動は考慮していません。

このクラスを利用して、別のブロック並べエリアを作成する場合は、次の4つの変数値を編集してください。

• 隣接ノードIDのリスト (デフォルトコンストラクタ内における

  neighborsIDList_ 

  の初期化値)
• 相対的なノード位置のリスト (デフォルトコンストラクタ内における

  currentPosition 

  の初期化値)
• ブロック並べエリアにおけるノード総数 (TOTAL_NODE_COUNT)
• ブロック並べエリアにおける各ブロック置き場が隣接するブロック置き場の最大数 (MAX_NEIGHBOR_COUNT)

Example

Explorer explorer;
explorer.createBlockArea();

explorer.resetBlockArea(); // 内部のフラグを初期化
explorer.setHasBlockIn(8);
explorer.setHasBlockIn(9);
explorer.setHasBlockIn(11);
explorer.setHasBlockIn(15);
auto route = explorer.searchRoute(8, 10); // == {8, 12, 13, 14, 10}
 

Explorer.h の 52 行目に定義があります。

構築子と解体子

Explorer::Explorer ( )

inline

デフォルトコンストラクタ

各ブロック置き場における隣接ノードIDのリスト、およびノード位置リストを作成し、そのサイズを元にノードリストを初期化しています。

Explorer.h の 76 行目に定義があります。

    : blockAreaNodeList(nullptr), neighborPtrs(TOTAL_NODE_COUNT), neighborsIDList(TOTAL_NODE_COUNT)
  {
    // 隣接ノードIDのリスト
    std::vector<std::array<std::int8_t, MAX_NEIGHBOR_COUNT>> neighborsIDList_{
      { { 1, 4, EMPTY_ID, EMPTY_ID },
        { 0, 2, 5, EMPTY_ID },
        { 1, 3, 6, EMPTY_ID },
        { 2, 7, EMPTY_ID, EMPTY_ID },

        { 0, 5, 8, EMPTY_ID },
        { 1, 4, 6, 9 },
        { 2, 5, 7, 10 },
        { 3, 6, 11, EMPTY_ID },

        { 4, 9, 12, EMPTY_ID },
        { 5, 8, 10, 13 },
        { 6, 9, 11, 14 },
        { 7, 10, 15, EMPTY_ID },

        { 8, 13, EMPTY_ID, EMPTY_ID },
        { 9, 12, 14, EMPTY_ID },
        { 10, 13, 15, EMPTY_ID },
        { 11, 14, EMPTY_ID, EMPTY_ID } }
    };

    // 相対的なノード位置のリスト
    std::vector<std::array<std::int8_t, 2>> currentPosition
        = { { 0, 0 }, { 1, 0 }, { 2, 0 }, { 3, 0 },

            { 0, 1 }, { 1, 1 }, { 2, 1 }, { 3, 1 },

            { 0, 2 }, { 1, 2 }, { 2, 2 }, { 3, 2 },

            { 0, 3 }, { 1, 3 }, { 2, 3 }, { 3, 3 } };

    //
    // 以降は触れなくてよい
    //

    for(unsigned int i = 0; i < neighborsIDList_.size(); i++) {
      neighborsIDList[i] = neighborsIDList_[i];
    }

    for(unsigned int i = 0; i < neighborsIDList.size(); i++) {
      Position position;
      position.x = currentPosition[i][0];
      position.y = currentPosition[i][1];
      positionList.push_back(position);
    }
  }

関数詳解

Node * Explorer::calculateNeighborCost	(	Node *	parent,
		std::vector< Node * > *	around,
		std::int32_t	realCost,
		std::int8_t	end
	)

ブロック置き場における隣接ノードのコストを計算します

これはA*アルゴリズムで用いる再帰的な内部処理です。 searchRoute(std::int8_t, std::int8_t) でのみ利用しています。

引数

parent	親ノードのポインタ
around	周辺ノード
realCost	実コスト
end	終端ノードのノードID

戻り値

終端ノードのポインタ

Explorer.cpp の 85 行目に定義があります。

{
  auto currentItr = blockAreaNodeList->begin() + parent->getNodeID();
  auto endItr = blockAreaNodeList->begin() + end;

  parent->setBeClosed(true);

  for(auto itr = (*currentItr)->getNeighbors()->begin();
      itr != (*currentItr)->getNeighbors()->end(); itr++) {
    if((*itr)->isClosed() || (*itr) == parent->getParentNode()) continue;

    int estimatedCostX = std::abs((*endItr)->getPositionX() - (*itr)->getPositionX());
    int estimatedCostY = std::abs((*endItr)->getPositionY() - (*itr)->getPositionY());
    int score = realCost + estimatedCostX + estimatedCostY;
    if((*itr)->hasBlock() && (*itr)->getNodeID() != end) score += 99;

    (*itr)->setScore(score);
    (*itr)->setRealCost(realCost);
    (*itr)->setParentNode(parent);
    around->push_back((*itr));
  }

  std::int32_t min = 999;
  std::int32_t minCost = 999;
  Node* minNode = nullptr;

  for(auto itr = around->begin(); itr != around->end(); itr++) {
    if((*itr)->isClosed() || (*itr) == parent->getParentNode()) continue;

    int score = (*itr)->getScore();
    if(score > min || (score == min && (*itr)->getRealCost() >= minCost)) continue;

    min = score;
    minCost = (*itr)->getRealCost();
    minNode = (*itr);
  }

  if(minNode->getNodeID() != end) {
    std::int8_t cost = 0;
    Node* node = minNode;
    while(node->getParentNode() == nullptr) {
      cost++;
      node = node->getParentNode();
    }
    minNode = calculateNeighborCost(minNode, around, realCost + 1, end);
  }

  return minNode;
}

呼び出し関係図:

被呼び出し関係図:

void Explorer::createBlockArea

(

)

ブロックエリアのノードリストを作成します

作成方法は、 Node クラスのドキュメントを参考にしました。

Explorer.cpp の 3 行目に定義があります。

{
  int nodeCount = neighborsIDList.size();

  // ノードのポインタのリストを作成
  for(int i = 0; i < nodeCount; i++) {
    Node node;
    node.setNodeID(i);
    nodeList.push_back(node);
    nodePtrs.push_back(&nodeList[i]);
    //nodePtrs.push_back(&node);
  }
  // 隣接ノードのポインタのリストをノード分リスト化
  for(int i = 0; i < nodeCount; i++) {
    for(int nodeID : neighborsIDList[i]) {
      if(nodeID == EMPTY_ID) break;
      neighborPtrs[i].push_back(nodePtrs[nodeID]);
    }
  }

  // 隣接ノードのポインタのリストを格納
  for(int i = 0; i < nodeCount; i++) {
    nodePtrs[i]->setNeighbors(&neighborPtrs[i]);
    nodePtrs[i]->setPosition(positionList[i].x, positionList[i].y);
  }

  // 各ノードのポインタを格納
  blockAreaNodeList = &nodePtrs;
}

呼び出し関係図:

被呼び出し関係図:

std::vector< Node * > * Explorer::getBlockAreaNodeList

(

)

ブロック置き場のノードのポインタのリストのポインタを取得します

戻り値

ブロック置き場のノードのポインタのリストのポインタ

Explorer.cpp の 136 行目に定義があります。

{
  return blockAreaNodeList;
}

被呼び出し関係図:

bool Explorer::hasBlock

(

std::int8_t

id

)

ブロック置き場のノードがブロックを保持している場合は真を返す真偽値判定を行います

引数でブロックの数以上の数値を入力した場合、何かしらのエラーが発生します。 それに関する責任をこの関数は持ちません。

引数

id	ブロック置き場のノードID

戻り値

ブロック置き場のノードがブロックを保持している場合は真を返す真偽値

Explorer.cpp の 50 行目に定義があります。

{
  auto itr = blockAreaNodeList->begin() + id;
  return (*itr)->hasBlock();
}

被呼び出し関係図:

void Explorer::resetBlockArea

(

)

ブロックエリアのノードリストにおける探索時のフラグなどを初期化します

Explorer.cpp の 33 行目に定義があります。

{
  for(auto itr = blockAreaNodeList->begin(); itr <= blockAreaNodeList->end(); itr++) {
    (*itr)->setBeClosed(false);
    (*itr)->setHasBlock(false);
    (*itr)->setScore(0);
    (*itr)->setRealCost(0);
    (*itr)->setParentNode(nullptr);
  }
}

被呼び出し関係図:

std::vector< int > Explorer::searchRoute	(	std::int8_t	start,
		std::int8_t	end
	)

ブロック置き場エリアにおける移動ルートを探索します

スタート位置と向かいたい位置を入力すると、

std::vector<int> 

型のリストを返します。 これは、ブロック置き場の位置コードのリストであり、隣接ノードが連なっています。 たとえば、位置コード8から位置コード10に移動したい場合は、

{8, 9, 10} 

を返します。 もし位置コード9にブロックが存在している場合は、

{8, 12, 13, 14, 10} 

を返します。 斜め移動は未対応です。

引数

start	スタート位置の位置コード
end	向かいたい位置の位置コード

戻り値

ブロック置き場の位置コードのリスト

Explorer.cpp の 56 行目に定義があります。

{
  auto startItr = blockAreaNodeList->begin() + start;
  auto endItr = blockAreaNodeList->begin() + end;

  int estimatedCostX = std::abs((*endItr)->getPositionX() - (*startItr)->getPositionX());
  int estimatedCostY = std::abs((*endItr)->getPositionY() - (*startItr)->getPositionY());
  int score = estimatedCostX + estimatedCostY;
  if((*startItr)->hasBlock()) score += 99;

  (*startItr)->setScore(score);
  (*startItr)->setRealCost(0);
  (*startItr)->setParentNode(nullptr);

  std::vector<Node*> around;
  Node* endNode = calculateNeighborCost((*startItr), &around, 1, end);

  std::vector<int> route = { endNode->getNodeID() };
  Node* parent = endNode->getParentNode();
  while(parent != nullptr) {
    route.push_back(parent->getNodeID());
    parent = parent->getParentNode();
  }

  std::reverse(route.begin(), route.end());

  return route;
}

呼び出し関係図:

被呼び出し関係図:

void Explorer::setHasBlockIn

(

std::int8_t

blockID

)

ブロックが存在するブロック置き場の位置コードを設定します

引数

blockID

ブロック置き場の位置コード

Explorer.cpp の 44 行目に定義があります。

{
  auto itr = blockAreaNodeList->begin() + blockID;
  (*itr)->setHasBlock(true);
}

被呼び出し関係図:

---

このクラス詳解は次のファイルから抽出されました:

• str/apps/include/Explorer.h
• str/apps/src/Explorer.cpp