ランダムなサイズと位置の長方形を含む長方形のキャンバスを考えてみましょう。これらの長方形の間を移動するには、ユーザーは上、下、左、右の 4 つの矢印を使用できます。
かなり単純なユーザー エクスペリエンスを生成するナビゲーションのアルゴリズムに精通していますか?
いくつかの解決策に出くわしましたが、どれも適切ではありませんでした。「理想的」な解決策はないことは承知しています。ただし、私が探しているアルゴリズムの種類は、矢印キーのみを使用してデスクトップ上のアイコン間を移動するために使用される種類です。
次のように移動グラフを作成するのはどうですか。
次に、グラフを保存し、それだけを使用してナビゲートします。セッションの途中で方向を変えたくありません。
graphこの問題は問題としてモデル化でき、algorithm of navigationとして使用できますshortest path routing。
モデリングはこちら。
各長方形は、グラフの頂点です。各頂点 (長方形) には、上、下、左、右の 4 つのオプションがあります。したがって、4 つの異なる長方形に到達できます。つまり、この頂点には 4 つの隣接点があり、これらのエッジをグラフに追加します。
これが問題の一部であるかどうかはわかりません-「特定のアクション（上など）を使用して、長方形から複数の長方形に到達できます」。そうでない場合は、上記のモデリングで十分です。はいの場合、この頂点の隣接点としてそのような頂点をすべて追加します。したがって、4-regular グラフにならない場合があります。それ以外の場合は、問題を 4-regular グラフにモデル化します。
さて、問題はhow do you define your "navigation" algorithm。アクションを区別したくない場合、つまり上、下、左、右がすべて等しい場合、すべてのエッジに 1 の重みを追加できます。
特定のアクションに他のアクションよりも優先順位を付けることに決めた場合、たとえば、他のアクションよりもup優れている場合は、上への動きから生じるエッジを 1 として重み付けし、残りのエッジを 2 として重み付けできます。アイデアは、異なる重みを割り当てることです。移動するエッジを区別します。
すべてのupエッジが等しくないと判断した場合、つまり A と B の間のアップ距離が C と D の間のアップ距離よりも短い場合、それに応じて、グラフ作成プロセス中にエッジに重みを割り当てることができます。
ルーティングはこちら
ルートを見つける方法 -- を使用dijkstra's algorithmして、指定された頂点のペア間の最短経路を見つけることができます。複数の最短経路に関心がある場合は、アルゴリズムを使用してノードのペア間の最短経路k-shortest pathを見つけ、最適な経路を選択できます。k
最終的に得られるグラフは有向グラフである必要はないことに注意してください。有向グラフを好む場合は、エッジを作成するときにエッジに方向を割り当てることができます。それ以外の場合は、エッジを使用して別の頂点に到達するだけなので、無向グラフを使用することをお勧めします。さらに、 fromrectAを使用して Rectangle に到達できる場合upは、 fromrectangleBを使用しrectangle Bて到達できます。したがって、他の理由でそれらが必要ない場合、指示は実際には重要ではありません。先ほどの仮定が気に入らない場合は、有向グラフを作成する必要があります。downA
お役に立てれば。