Clever Geek Handbook

グラフBoostの下のクラスをマスクします。 パート1：インターフェイスに触れないでください



プロローグ：ブーストコンセプト

パート2：コンセプトサポートの実装の完了



ゲームのパス検索アルゴリズムをやり直すのに時間がかかりました。 過去は完全に自作でした-側に一歩、そしてすべてが悪いです...私はそれを良い情報源から準備したかったです。 そのとき、ブーストにはグラフを操作する機能があることを思い出しました。 残念ながら、「関数を見つけて呼び出し、そしてそれがすべて機能する」というアプローチは行われませんでした。 ライブラリでは、使用の最大限の柔軟性に重点が置かれていますが、これは単純さに悪影響を及ぼしました。 同時に、致命的なことは何もありません。すべてをゼロから実行する（そして修正する）よりも優れています。 プロジェクトのブーストは長い間使用されていますが、他のライブラリに連絡することも望みませんでした...



与えられた-次の（この記事で重要な）インターフェースを持つ競技場のクラス 



class GameField { public: GameField(); bool canPass(int x, int y) const; int getWidth() const; int getHeight() const; };


フィールドは、正方形のセルの規則的なグリッドです。 隣接するセルに直接および斜めに移動できます。 GameField :: canPassメソッドを使用すると、特定のセルに入ることができるかどうかを確認できます （つまり、セルが存在し、その中に障害物がない）



最初のステップは、ブーストの概念を理解することでした- 以前の記事でそれらについて説明しました。 これがなければ、グラフのすべてのライブラリ要件はランダムに満たされ、永遠に読まなければなりません。 繰り返しはしませんが、前の記事への小さな追加にのみ焦点を当てます。 コンセプトを検証するために次の方法を提供しました。 



 BOOST_CONCEPT_ASSERT((SomeFuncAppropriate<SomeClass>));


また、目の二重装具が痛いという不満もありました。 彼らは私だけでなく、ブーストがより身近なオプションを提供することが判明しました 



 boost::function_requires<SomeFuncAppropriate<SomeClass> >();


将来使用するのはこの形式の録音です。



だから。 ブーストを受け入れるためのグラフとして偽装する必要があるソースクラスがあります。 同時に、私は競技場（GameField）のクラスを変更したくありません。ここでは、単純化したバージョンを示します。実際、クラスのインターフェースはすでにかなり大きく、タスクの非直接機能のために変更することは実用的ではありません。 パスを見つけるには、 A *アルゴリズム（AStar）を使用します。 ドキュメントには、boost :: astar_search関数がグラフを2つの概念（ 頂点リストグラフとインシデントグラフ）に準拠する必要があると書かれています。





さらに、グラフの概念には、クラスを操作できるブーストに基づいて、いくつかの特別なタイプの定義が必要です。 それらについて詳しく見ていきましょう。



vertex_descriptorは、頂点のタイプを定義します。 GameFieldクラスでは、頂点は2つのセル座標によって定義されます。 最初の考えは、構造または値のペア（std :: pair）を使用してこの定義を繰り返すことです。 ただし、 vertex_descriptorは 、グラフのタイプに応じて、さまざまな概念を満たす必要があります。つまり、演算子、コンストラクタなどを実装する必要があります。 非常に難しいとは言いませんが、頂点の2つの座標は私たちの競技場の実装の特徴にすぎないと考え、理解するのは簡単です。 それ自体では、グラフの表現はこの恩恵を受けません（この場合）。 そのため、グラフモデルでは、頂点に単純に番号を付けることにしました（（0、0）-> 0、（0、1）-> 1など）。 これにより、頂点タイプとして標準のintを使用できるようになり、必要な機能はすべてサポートされます。 もちろん、頂点インデックスをグラフの座標に変換するために、2つの関数を実装する必要があります。 



 std::pair<int, int> getCoordinates(const Vertex position, const GameField& graph) { return std::make_pair(position % graph.getWidth(), position / graph.getWidth()); }


そして戻る 



 Vertex getVertex(int x, int y, const GameField& graph) { return x + y * graph.getWidth(); }


頂点タイプの由来は次のとおりです。



edge_descriptor-エッジのタイプ。 エッジは2つの頂点であり、書き留めます：std :: pair <vertex_descriptor、vertex_descriptor>



directed_category-グラフが方向付けられているかどうかを決定する特別なタグタイプのいずれかに対応する必要があります（本質的に、これらはデータとメソッドのない構造です）。 私たちの場合、そうではないため、値boost :: undirected_tagを使用します



edge_parallel_categoryグラフで平行エッジを許可するかどうかを決定する別のタグタイプ（2つの頂点間に複数のエッジが存在できる場合）。 無効-ブーストを使用:: disallow_parallel_edge_tag



traversal_categoryタグも。 グラフトラバーサルメソッドを定義します。 ここではすべてが少し複雑です。 VertexListGraphの場合、これはそれぞれboost :: vertex_list_graph_tagであり、IncidenceGraphの場合はboost :: incidence_graph_tagです。 これは、両方のバイパスオプションを継承する新しいタグタイプを作成することで解決されます。 



 struct game_field_traversal_catetory: public boost::vertex_list_graph_tag, public boost::incidence_graph_tag { };


vertex_iterator頂点を横断するためのイテレーター。 この実装については、記事の次の部分で検討します。



out_edge_iterator上から来るエッジを走査するためのイテレータも将来実装されます。



degree_size_type頂点の次数（出力エッジの数）が表現されるタイプ。 整数



vertices_size_typeグラフの頂点の数が表現されるタイプ。 また、整数として取ります。



タグの種類について詳しく説明します（これはタグの正確なディスパッチと呼ばれます）。 これらは、モデルの1つまたは別の機能を利用するために、関数をオーバーロードするために使用されます。 たとえば、boost :: undirected_tagタグを定義することにより、グラフのエッジが方向付けられていないことをライブラリに伝えます。 その結果、発信エッジと着信エッジの個別の定義を必要としない関数を使用します。



次に、競技場のタイプを一致させる必要があります。 最初のバインディングオプションは、追加の定義をクラスに直接配置することです。 



 class GameField { public: typedef int vertex_descriptor; ...


ただし、GameFieldインターフェイスは変更しないでおきます。 幸い、ブーストはそのような機会を提供します。 必要なすべてのタイプは、ライブラリによってグラフクラスから直接抽出されません。つまり、そうではありません。 



 GameField::vertex_descriptor


代わりに、特殊なboost :: graph_traitsテンプレートが使用されます。 



 boost::graph_traits<GameField>::vertex_iterator


デフォルトでは、パラメータクラスから対応する型を取得するだけです。 次のことを行います 



  template <typename Graph> struct graph_traits { typedef typename Graph::vertex_descriptor vertex_descriptor; ...


GameFieldクラス用に独自の専門graph_traitsを書くことができます。これは私たちにとって便利なので、それで動作します。 競技場で必要なタイプを検索しようとしないでください。 タイプの選択については上で言葉で説明しましたが、最終的な実装を検討します。 boost名前空間に配置することを忘れないでください。 



 namespace boost { template <> struct graph_traits<GameField> { typedef int vertex_descriptor; typedef std::pair <vertex_descriptor, vertex_descriptor> edge_descriptor; typedef boost::undirected_tag directed_category; typedef boost::disallow_parallel_edge_tag edge_parallel_category; typedef game_field_traversal_catetory traversal_category; typedef VertexIteratorImpl vertex_iterator; typedef OutEdgeIteratorImpl out_edge_iterator; typedef int degree_size_type; typedef int vertices_size_type; typedef void in_edge_iterator; typedef void edge_iterator; typedef void edges_size_type; }; }


構造には、以前に言及されていないいくつかのタイプが含まれていることに注意してください。in_edge_iterator、edge_iterator、edges_size_type。 これらは、それぞれVertexListGraphとIncidenceGraphの概念を実装するために必要ではなく、それらを指定することはできません（ voidにします ）。



今後の作業では、必要に応じて定義を1か所で変更できるように、graph_traitsで型を参照することをお勧めします（つまり、頂点の場合はintではなく、vertex_descriptorを使用します）。 boost :: graph_traits <GameField> :: vertex_descriptorのフォームの構築は、書き込みと読み取りの両方で重いため、単純な型名を導入します。これは今後使用します 



 typedef boost::graph_traits<GameField>::vertex_descriptor Vertex; typedef boost::graph_traits<GameField>::edge_descriptor Edge; typedef boost::graph_traits<GameField>::vertex_iterator VertexIterator; typedef boost::graph_traits<GameField>::out_edge_iterator OutEdgeIterator; typedef boost::graph_traits<GameField>::degree_size_type DegreeSizeType; typedef boost::graph_traits<GameField>::vertices_size_type VerticesSizeType;


必要なすべてのタイプが定義されています。 VertexIteratorImplおよびOutEdgeIteratorImplはgraph_traits <GameField>で使用されました。これらの反復子の実装については、記事の次の部分で検討します。 サポートされている概念に必要なグラフ機能も実装されます。


More articles:


All Articles