一点に集合する場合の整列の仕方

質問

オブジェクが目的地に移動するプログラムを作っています。
このオブジェクは複数存在しています。目的地は一つなので全オブジェクがいずれ一点に集合します。
その際、目的地の座標に全オブジェクは集まるので被って一つしか見えなくなってしまいます。

これを回避する為に同じ座標にオブジェクが存在した場合、位置をずらしたいのです。
今はx軸y軸に+1ずらしています。数が少ない時はこれで十分でしたが数を増やすと斜めになって見づらくカッコ悪い状態です。

理想は目的座標を中心に円を描く様になって欲しいのです。

実装方法がわからないので、実装方法又は、実装方法に必要な方法の検索ワードを教えて下さい。

回答No.6

qwertfk

まだ正規化の式が間違えています
いきなり処理全体をつくろうとせずに各処理を確実１つずつ作ってみてください。
-オブジェクト型に直接座標値が入っているならそれはやめてベクトル型をつくってそのオブジェクトをメンバに持つようにしたほうがよいとおもいます
-そのうえでベクトルに四則演算を実装する
-正規化機能を実装する
上記を行いテストを行い正常に動作する事を確認する、ということをさきにやったほうが良いです。

あと、うまくいかない、とかかれていますがもう少し具体的に説明されたほうが解決に近づきやすうとおもいます。
現状で衝突判定は正常にできていますか?
回避だけがうまくいかないとは具体的にどういう結果になっているでしょうか?

補足

衝突判定は出来ています。
衝突して位置をずらす時に、画面左上。xに0,yにマイナスの値が入っています。

回答No.5

qwertfk

ベクトルの絶対値のあつかいが間違えていますので確認してみてください。

補足

２点の距離が円の直径より短ければ重なっているとし
処理を行う。
Cには2点の中心点の座標を収める。
Cから各座標の向き(正規化したベクトル)に円の半径を掛けてずらす。

この様な処理だと理解しています。

うまく行きません。一つ前の補足に書いたコードの処理を以下の様に変更しました。

オブ[i].x=(オブ[i].x-Cx)/sqrt((オブ[i].x-Cx)*(オブ[i].x-Cx))*radius;
オブ[i].y=(オブ[i].y-Cy)/sqrt((オブ[i].y-Cy)*(オブ[i].y-Cy))*radius;

オブ[j].x=(オブ[j].x-Cx)/sqrt((オブ[j].x-Cx)*(オブ[j].x-Cx))*radius;
オブ[j].y=(オブ[j].y-Cy)/sqrt((オブ[j].y-Cy)*(オブ[j].y-Cy))*radius;

回答No.4

qwertfk

質問について確認なのですが、

> 理想は目的座標を中心に円を描く

というのは、目的座標を中心として、オブジェクトがドーナツ状に並ぶということなのか、
オブジェクトが密集していて、全体の分布が円状になる、という意味のどちらでしょうか？

もう一点確認は、

> 位置をずらしたい

について、オブジェクトの形は円ということで良いと思いますが、位置をずらすというのは
オブジェクト同士が全く交差しないように配置する、という意味なのか、オブジェクトがちょっとでも
ずれがあるのならそれで良い、という意味のどちらでしょうか？

前回の回答は、
・オブジェクトが密集していて、全体の分布が円状になる
・オブジェクト同士が全く交差しないように配置する
という前提の内容なのですが、質問の意図と合っていますでしょうか？

その前提での回答の続きになりますが、

まず、先ほどのコードについて、色々間違いがあります。
半径rの円形のオブジェクトが2つあり、それらの中心座標をa,bとすると、それらが交差しているかどうかの判断は、

|a - b| < 2 * r

という評価式で行います。

それで、もし交差があるのであればそれらの円をちょうど接触する位置までずらします。
位置をずらす処理は、

c = (a + b) / 2.0

として、

a' = (a - c) / |a - c| * r
b' = (b - c) / |b - c| * r

という変換を行うと、2つの円がちょうど接触した状態になります。

それと、前回のアルゴリズムの若干の修正ですが、

foreach(全オブジェクト→a)
{
　aを目標地点に少しだけ近づける
}

foreach(全オブジェクト→a)
{
　foreach(全オブジェクト→b)
　{
　　if(a==b) continue;
　　aとbが交差するなら適当にaとbが接触するように位置をずらす
　}
}

オブジェクトを目標地点に近づける処理を入れなければ集まってくれません。

あとは、これをコードにするだけです。

補足

近づける処理

for(i=0;i<オブジェクト数;i++){
for(j=0;j<オブジェクト数;j++){
if(i==j)continue;

//|a - b| < 2 * r
if( abs( (オブ[i].x-オブ[j].x)*(オブ[i].x-オブ[j].x) + (オブ[i].y-オブ[j].y)*(オブ[i].y-オブ[j].y)) < (2*radius)*(2*radius) ){

//c = (a + b) / 2.0
Cx = (オブ[i].x + オブ[j].x)/2;
Cy = (オブ[i].y + オブ[j].y)/2;

//a' = (a - c) / |a - c| * r
オブ[i].x=(オブ[i].x-Cx)/abs(オブ[i].x-Cx)*radius;
オブ[i].y=(オブ[i].y-Cy)/abs(オブ[i].y-Cy)*radius;
//b' = (b - c) / |b - c| * r
オブ[j].x=(オブ[j].x-Cx)/abs(オブ[j].x-Cx)*radius;
オブ[j].y=(オブ[j].y-Cy)/abs(オブ[j].y-Cy)*radius;

}
}
}

この様に実装してみました。
結果は0やマイナスの座標が入ってしまいます。

回答No.3

qwertfk

座標は実数でしょうか？整数でしょうか？
整数であれば単純に、x軸y軸に+1ではなく、目的地に最も近い空き座標にオブジェクトを
順に配置していくだけでも良いかと思いますがどうでしょうか？

実数の場合、複数オブジェクトが出来るだけ指定点に密集する＋全体が円形になるような配置
を求める問題というのは、最密充填、英語ではPackingといわれる問題です。

オブジェクトの形が同じ大きさの真円であれば、20個までなら
http://en.wikipedia.org/wiki/Circle_packing_in_a_circle
に配置関数があります。

そうでない場合、たとえば、
foreach(全オブジェクト→a)
{
　foreach(全オブジェクト→b)
　{
　　if(a==b) continue;
　　aとbが交差するなら適当にaとbが接触するように位置をずらす
　}
}

このような非常に簡単な回避処理を数回繰り返す程度でもオブジェクト100個程度
でも殆ど問題なく交差なく円形に配置することが出来ます。

補足

for(i=0;i<オブジェクト数;i++){
for(j=0;j<オブジェクト数;j++){
while(オブジェクト[i].x == オブジェクト[j].x && オブジェクト[i].y==オブジェクト[i].y &&i!=j){
オブジェクト[i].x=cos(rad/180*PI)*dis;
オブジェクト[i].y=sin(rad/180*PI)*dis;
rad+=10;
if(rad>360){rad=0.0;dis+=size;}
}
}
DrawCircle( オブジェクト[i].x ,オブジェクト[i].y ,size);
}

”接触する様に位置をずらす”を実装して見ようと試みました。
うまく行ってません。
ずらすという処理を角度を変えて実装しようとしているのですが、正しいのでしょうか？

回答No.2

honor

単純な方法ですが、同じ座標にいるオブジェクの個数を数えて、(2π/オブジェクの数)だけ角度をずらして目標地点を中心とする円周上に置けばいいのでは。
個数が少ないと円にならないとか問題はありますけど。

回答No.1

anmochi

具体的なワードは出せないかも知れないが。

分かっているかも知れないがこれはかなり難しい。
もはやAIの領域と言ってもいい（と言ってもいわゆるゲームAIといって複雑な状況判断と行動決定をプログラムしたものだが）。
オブジェクが他のオブジェクと協調動作しないとこの動きはできない。
「自分の近くに他のオブジェクが居る。」
「自分と目的地と他のオブジェクとの位置関係が○○である。」
という判断を自分と目的地と近くに居る全ての他オブジェクについて毎回考えないといけない。

もっとも、最終的には自分自身の位置を決めるのが目的だというのが分かっていれば
アルゴリズムは考えやすいだろう。
AIではなく、個々のオブジェクとシステム全体の整合性で考えれば、
システムは目的地からの半径とオブジェク間の距離を保持。
個々のオブジェクはその半径と他オブジェクからの距離によって整列しようとするが、オブジェク間の距離を保てないと判断するとシステムに対して半径を増やす事を指示する。
システムが半径を増やしたら個々のオブジェクはまたその半径と距離にしたがって整列しようと試みる。
後から目的地にたどり着いたオブジェクがあればさらに半径が必要になる。

というのを繰り返しシミュレーションする事になる。
夏の第三角形に例えると、オブジェクAからみてオブジェクBが、目的地アルタイルに対してBがデネブでAがベガの位置にあるとするとBは動かさずにAの角度を調整するという動きにしてもいいし逆でもいい。可能なら両方で調整を行ってもいいが難しいかも。

これを、数が増えたら2列、3列にするとなるとさらに大変だ。