平面グラフを作るパズルゲームのアルゴリズム

質問

http://jayisgames.com/games/planarity/

にゲームがあります。

最終的には各辺同士が交差しない状態にすると完成です。

例えば、ふつうの迷路ゲームには、「右手(左手)で壁を触りながら前進すればいつかはゴールできる」という完成のためのアルゴリズムがありますが、このゲームのアルゴリズムを教えていただけないでしょうか。

回答No.9

stomachman

ついでに。問題をどうやって作るか、という話も書いておきます。

ひとつの方法は以下の通りです：
(1) 平面上にn個の点（頂点）をランダムにばらまき、それらの点に番号を付けておきます。
(2) 平面を、n個の領域に分割します。k番の領域内にある位置xは「位置xと最も近い点はkである」という性質を満たすようにする。その結果、点kを囲む凸多角形の領域ができます。領域の中には点が１個だけあるわけです。
　このように平面を分割した図は「ボロノイ図」と呼ばれており、領域の境界線を計算するためのアルゴリズムが知られています。ボロノイ図は、たとえば「東京都23区の地図を、最寄りの地下鉄の駅がどれであるか、によって色分けする」という問題を解くときに使えるわけで、実地にいろいろな応用があります。
(3) 境界線をはさんで隣接している領域k, jについて、点kと点jは直接に辺で結ばれる、ということにします。境界線の直線部分の個数と同数の辺が作られます。
(4) 領域の境界線を消すと、平面グラフになっています。
(5) この平面グラフの辺の途中に、新たに点を追加してもかまいません。しかし辺を追加するのはダメです。
(6) あとは、点の位置（座標）をランダムに書き換えるだけで、問題の出来上がりです。

添付図はボロノイ図の例（太い線が領域の境界線）と、それによって作られる平面グラフ（破線）です。

回答No.8

stomachman

ANo.7について、図を貼っておきます。分かりやすいように、あんまり点が多くないやつです。

(図左上) : 3つの点を選んで、右下に三角形を作り、他の点は三角形の外に移動したところ。三角形の中は「処理済み」の点、外は「未処理」の点の置き場という訳です。
(図右上) : 三角形の頂点に直接つながっている点を三角形の中に移動。三角形の中にある点同士を結ぶ線は交差しないようにする。三角形の外の点とつながる線は一切無視します。
(図左下) : 三角形の中にある点につながっている点を、１個ずつ三角形の中に入れて行く。ただし常に、三角形の中にある点同士を結ぶ線は交差しないようにレイアウトを調節する。（それができるまでは、三角形内に新しい点を入れては駄目。）
めんどくさいけどこまめにケチケチと場所を詰めなくては、スペースが足りなくなります。三角形内に「三角形の外にあるどの点とも直接つながっていない点」ができたら、その点の周囲にはもうスペースは不要だから、三角形の角近くに押し込めてかまわない。
(図右下) : あとひとつ。

「常に、三角形の中にある点同士を結ぶ線は交差しないようにする」ということが局所的なレイアウト調整だけでできるのは、問題として与えられるグラフが平面グラフで表せるものに限られているからです。結局、「こまめにケチケチと場所を詰める」という作業が、このパズルを解くのに掛かる時間のほとんどを占めます。

回答No.7

stomachman

ANo.6です。

今度はヒトが手でやる話にします。

(1)右下の引っ掻き回しボタンを使って、画面全体にノードを散らす。
(2)3つのノードから成るループ（であって、できればそれらのどのノードも３つ以上の辺を持っているもの）をみつけ、これらを画面の３つの隅ギリギリに置く。以後動かさない。
(3)この直角三角形の外に、ほかのノードを全部とにかく移動。このとき、ノード同士が重ならないように注意。
(4)三角形の頂点に直接つながっているノードすべてをその頂点の近くに持ってくる。そして、三角形の中にあるノード同士をつなぐ辺が交差しないようにレイアウトする。（当然のことながら、もし二つの頂点と直接つながってるノードがあった場合には、三角形の辺ギリギリのところに置く。もし三つの頂点と直接つながるノードがあった場合は、どれかの頂点のすぐ近くに置く。）
(5)三角形の中にあるひとつのノード（なるべく頂点に近いもの）に直接つながっているノードすべてをその近くに持ってくる。そして、三角形の中にあるノード同士をつなぐ辺が交差しないようにレイアウトする。
(5)を繰り返すのだが、途中でスペースが詰まってきたら、適宜三角形の中のノードの位置を調節して、必要なスペースを作る。

とやれば良さそうです。
　このパズルがパズルとして成立するのは、ひとえに、ノードを表す○が結構でかいのに使えるスペースが狭いということ、および、いくつかのノードをまとめて動かすということができない操作性の悪さ、に起因するクソメンドクササによってではないかな。Level 30を超えるあたりから、ノード同士が重なって、クリックしたノードにつながっている相手を探すのも難しくなる。
　操作性を改善する機能をいろいろ入れてやれば、だいぶ簡単になっちゃうと思います。

回答No.6

stomachman

アルゴリズムをお尋ねですから、ヒトが手でやる場合のヒューリスティックスじゃなく、機械で解く話を考えることにします。両者はかなり違う。というのは、ヒトにとってはグラフ上の距離が近いnode同士を平面上で近くにまとめて整理して行くことが重要だ（level15までやってみた感想に過ぎませんが）けれども、機械にとってはそれは問題にならんからです。（いや、もちろん、ヒトがやるためのヒューリスティックスを機械で模倣する、というのでもイイ線行くと思います。解いている途中段階を動画で見せようとすれば、こっちの方が面白いでしょうしね。この場合、nodeが集まりすぎて団子になったら全体をズームアップするように拡大する、ということが簡単にできるのも機械の有り難みです。）

　出題されるのは、平面グラフに限られている。しかもそれは、連結であって、切断点（そのnodeを除くとグラフが連結でなくなるようなnode)を持たず、かつ、両端が同じであるようなedgeがない（長さ2のサイクルがない）、という性質を持つグラフです。（出題されるときにnodeが円周上に並んでいる、ということは全くどうでも良い話であって、node同士がどうedgeで繋がっているか、という情報だけに着目するんです。）
　そこで、基本的には、そのグラフが実際に平面グラフであるということを、平面性判定アルゴリズム（これは既に知られている）を使って確認する作業をすればいいでしょう。判定アルゴリズムは要するに「なるべく長いサイクルを探して、その内側と外側に残りのノードを割り振る」ということを繰り返して行く。すなわち、サイクルがひとつ決まったら、それを構成するnodeたちをワッカ状に配列すると、他のノードは2種類に分類され、一方がサイクルの外、他方がサイクルの内に配置されることになる。これを再帰的に繰り返す訳で、最終的に平面が幾つかの部分領域に分割されます。（なので、同時に双対グラフも得られることになります。）
　で、これらの領域が、nodeを頂点、edgeを辺とする多角形になるようにグラフを描きたい。ここからが、ご質問の問題に特有の話になるかとおもいます。というのは、単に平面グラフというだけだと、edgeが曲線でも良い。nodeのレイアウトを調整してedgeが直線になるようにnodeの位置を微調整して行くことが必要ですね。
　平面性判定のプロセスで同定されたサイクルについて、同定されるたびに、それが丸っこくなるようにサイクルを構成するnodeをレイアウトしていく。これだけでも概ね正解に近い状態のグラフが描けるでしょう。もちろん、edgeを線分で描くと、交差が生じうる。しかし、この交差は、nodeを少し（edgeをまたがずに）動かすだけで解消できる筈のものです。なので、交差（あるいは、領域内を通過するedge）を検出して、nodeの位置を修正する、という作業を反復して行えば、正解に収束するでしょう。

回答No.5

QoooL

＃１～４です。今のところ回答を独占しているみたいで恐縮です。

＞　お金に関しては、お支払してもいいです。

　これは、私が　ＯｋＷａｖｅでの回答にお金を要求している、と受け取らないでくださいね。
そうじゃなくて私が言いたいのは、
　　　このゲームはこう考える
とここで明かしてしまったり、
　　　このゲームはこうやって作る
とここで明かしてしまったりすると、
そのノウハウを元にひともうけできる人が現れるから、ここで聞くのが残念ながら不適切ではないか、ということなのです。

　質問者さんと私がタッグを組んだとしますね、
で、本気で「これは日本で売り出そう」と考えたとします。
（無料ゲームとはいえ、儲けるカラクリがある、という前提でね。）
もちろん、「私も分け前が欲しい」　というのは本音ですよ。

それなりに、「このアルゴリズムをお答えするのは、無料の質問の範囲を超えていて、仕事になる」　と私は判断した

わけです。だって、

無料でこのゲームを作ってください、プログラムの方針を示してください

という投稿があったとしたらおかしいですよね。

　それ以上に私が懸念するのは、前から言う権利関係です。こうこうこうやればこれは作れる、ということをインターネットで公表してしまうと、いつなんどき誰が見ているかわかりませんから、我々がビジネスにする前に他人がビジネスにしてしまう可能性もあるわけです。そうなると、「一緒に儲けましょう」と言っていても、障害になりますよね。

　一方、細かく手の内を明かしてしまうと、「商品にならない」という両刃の剣の側面もあります。

　誇張ではなく、私としてはルール的なものはもう見えました。言葉で表すのはまだ難しいですが、
　　　同じ問題をランダムでプログラムに作らせる
　　　同じ問題を人間が解いた後にプログラムに正解かどうか判定させる
のは頭の中でできています。

　先に一筆書きのアルゴリズムのことを申し上げておきますが、
＞　スタートとゴールを見つけ出し一筆で・・・
というのはルールとしてもちろんなのですが、これには
　　点からでる線が奇数になっている点の数、
　　点からでる線が偶数になっている点の数、
というのを意識して、どの点から必ず始める、という必勝法のアルゴリズムがあります。
それさえ知っていれば、図を見た途端に、
　　「この図は一筆書きできる」
　　「この図は一筆書きが不可能」
ということが小学生でも即答できるのです。一部の中学受験生は（そんなに難関中学受験でもないですが）次の図から一筆書きできるものを選べ、というときにこの裏技を利用しています。

　今回のプラナリティでは、一筆書きそのものは関係ないですが、一筆書きのアルゴリズムは利用できる、という意味で申し上げたのです。頂点から出ている線の数を数えると、レベル８でもせいぜい４本ずつですから、５５個の点から出ている線の数も知れているのです。

　判定の式は実は極めて単純です。
（Ｘ1，Ｙ1）と（Ｘ2，Ｙ2）を結ぶ線分と、
（Ｘ3，Ｙ3）と（Ｘ4，Ｙ4）を結ぶ線分が、
交わるか否かを判定する、
これを有限回繰り返せばよい（Ｆｏｒ～Ｎｅｘｔのやること）というだけです。

　私はフラッシュゲームは作れませんが、内容的に全く同じゲームを作ることができますよ。例えばリトルビッグプラネットってご存知ですか？　私が今すぐプログラムするならそういうツールが手近ですね。エクセルＶＢＡでも作れるけど、「点を移動させる」というロジックがＶＢＡでは面倒くさいです。まあ、プレイヤーにはカット＆コピーで点を移動してもらえば、エクセルでも同じゲームは作れるか。

　こういう商品化の話なら、やっぱり私は無料じゃなくてお金に結び付けたいのですよ、できる見込みがはっきりしているのですし。
　でも、ただ単に「必勝法が知りたい」という意味でアルゴリズムとおっしゃっているなら、これはプログラムに解かせるのはまだまだ難しい段階ですね。人間が無意識的に解いている計算を、プログラム言語で書き表すのは手間がかかりますから。
　ただ、「必勝法を示す」こと自体は、私の解き方を動画に撮って見ていただくのが一番近いのかも知れません。当たり前ですけれど、皆そうやっているんでしょうけど、
　　　関連する点は近くへ寄せる、近くへ寄せる、
　　　特に４の点は内側へ、３の点は外側へ配置する、
　　　特定の４の点Ａに関連する点２つに、別の４の点Ｂが同時に関連しているときは、
　　　この点２つを結んだ線分ＣＤに関してＡとＢは逆側に配置する、
　　　２の点は基本的に無視する、
というような感じですね。あと
　　　直線的に配置する　＆　少しずつ鈍角のカーブを描いていく
という方が手では解きやすいですけど。

　めちゃくちゃに不規則に点どうしが結ばれているように見えて、めちゃくちゃでもないのですよ。
残念ながら左手の法則みたいに一言で言える法則ではないですが、ルービックキューブと同じように、ああしてこうしてそうして、みたいなお決まりの手順に近いものはあります（ただし「判定」に比べたら「解く」のはプログラムには大仕事、ということです）。

　また質問者さん自身が８問目より先に進んだら、画像は挙げなくてけっこうですから自己ベストを教えてくださいね！
　ビジネスのお話をしようとしてもここではどうやっても連絡先交換ができませんね。

回答No.4

QoooL

連続で失礼ですが、もう１枚解答例を示しておきます。

ご自身でアルゴリズムを考える際にもご参考になれば幸いです。

私のカンでは、「同じ問題を」複数回解いて（別に低いレベルで良い）、
お互い答えを見せ合って、「なるほど、そういう解答例もあるのか」　と見比べるのが、
アルゴリズムの突破口になると感じます。

できあがりだけをもらうのはずるい、だって手間がかかるのに！！
（しかもリアル報酬なし！？）

っていうのも本音ですが（笑）

回答No.3

QoooL

＃１，２です。
８問目まで解きましたが、もうつかれた。しんどい。

ギブアップ（９問目を見る気がしない）です。

確かに法則がありそうですね。
「問題を作る側」に立ってみたらいかがです？

「問題の解答例だけでいい」「答えは確かに存在するということがわかればいい」
ということだけなら、
権利関係も気にせずに答えやすいのですがね。

ご自身では何問目まで行ったのでしょうか？
ご自身の考えるアルゴリズム予想も示していただけませんか？
それが私にとっては、「どういう方向性で答えたら良いか」　の指針になりそうです。

数列やΣは理解なさっている、ということでよろしいですか？
さらにプログラム言語がわかりますか？

回答No.2

QoooL

言い忘れましたが、
私は中学１年生のときにポケットコンピュータＥ－５００で、
ＢＡＳＩＣを使って

迷路ランダム作成ゲーム（配列変数の都合上、確か最大１００ｘ１００）を作った

ことがありますよ。（完全独学。雑誌記事を参考にとかではありません。）

正に左手の法則を使って。
ポートピア連続殺人事件とか、ドルアーガの塔とか、ボンバーマンとか、もちろんドラクエＩIIIIIとか
の影響を強く受けていましたからね。

単に、早い解き方を知りたいだけですか？
でもこれって、日本でゲーム会社が商品化することも可能ですよね。
最近、「フリーのお手軽ゲーム」が以前と違う意味で流行っていますし。

ご事情を伺ってすみません。

回答No.1

QoooL

確かにおもしろいゲームですね。

それにしてもアルゴリズムとは、珍しいご質問ですね。

失礼ですが、
この「仕事」を私が解決した場合、私にいくらか入ることはあるのでしょうか？

なぜなら、例えフリーでも、
ゲームのアルゴリズム　には　知的財産権が存在する可能性がある、
と懸念するので・・・

日本での版権をお持ちかと思いまして。

まあ、このような回答のしかたをして人間くささを出すのは私としてもイレギュラーですが、単なる好奇心で普通に答えてはいけないか、という直感がいたしました。
プログラム的なアルゴリズムを　言葉に直すにはまだ日数もかかりますし。
４問目まではだいぶスムーズに解けましたけど（テレビ見ながら）
何問目まであるんでしょうかね？

示唆としては、
少なくとも一筆書きには、
　　　小学生の中学受験でも　覚えさせられるような、アルゴリズム
がありますよ。

お礼

ありがとうございます。
お金に関しては、お支払してもいいです。
一筆書きには、スタートとゴールを見つけ出し、スタートからゴールへいく一つの道を描き、通っていない道を何度も修正する、というアルゴリズムと思います。

平面グラフも、たぶん、境界になれるような頂点をとりあえず1つ見つけ出し、それと隣接する頂点を、辺に交わりがないように順に配置していけばいいとは思います。しかし、その際に修正が必要ですが、その修正が前回の頂点だけでなく、前々回の頂点、さらにその前などにおいても必要になりそうで、複雑です。

いまはあまり時間が取れません。