質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

2回答

620閲覧

整数座標に矩形を配置できる座標を求める高速なアルゴリズム

concern12

総合スコア18

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

1グッド

0クリップ

投稿2022/12/27 08:43

編集2022/12/29 11:51

矩形が配置されている座標には矩形を配置できないというルールの整数座標がある場合、矩形を配置できる座標を高速に調べる手法を探しています。

BitBoardを使うことで、bit演算だけで配置可能座標を調べることができると考え、BitBoardを用いて実装しています。

既に矩形が配置されていれば1、配置されていなければ0とする8x8のBitBoardに対して、配置したい矩形のbit列で片っ端からAND演算をし、結果が0の場合に矩形が配置できることがわかりますが、より速い手法を探しています。

イメージ説明
(例えば黒の矩形が配置済みで1として、3x4の矩形を新しく配置したい場合、片っ端からAND演算をしていくと、左下が43となる座標がAND演算の結果0となり、配置できることがわかる)

bit演算のテクニックを使えばもっと速くすることができると考えていますが、BitBoardの様々な文献を読んでもチェスやオセロの場合に使われるテクニックばかりで、このような矩形を配置できるかどうかのテクニックが見つかりませんでした。

愚直に片っ端からAND演算を試す以上の手法があれば教えていただきたいです。

また、BitBoardに対して、特定のサイズの矩形が配置できないことが高速にわかる手法がありましたら、AND演算で走査する必要がなくなるため、ご存知でしたら加えて教えていただきたいです。

melian😄を押しています

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Zuishin

2022/12/27 09:34

> 愚直に片っ端からAND演算を試す以上の手法があれば教えていただきたいです。 矩形を描いた履歴をとっていないのであれば全探索するより他ないと思いますが。 とっているのであれば座標から演算することも可能だと思いますが、領域の大きさがこの程度であれば素直に全探索する方が速いかもしれません。
fana

2022/12/27 10:18 編集

(正直,BitBoard なるものを知らないですが) 右側2人とORをとり,その結果を上3人とORをとり,結果が0ならいける,みたいな??? 座標 43 を例にすると… 自身と44と45でORをとっても0.(←シフトしてORしてシフトしてORして,みたいな手続きで?) (他の全マスも同時に同じことをしたとして,その結果の上で)自身と35,27,19 のORをとっても0なので矩形の左下になれる,っていう. (一律処理してれば,同時に座標 58 もOKだとわかる…のかな?)
concern12

2022/12/29 02:51

ありがとうございます。 履歴を取る方法も検討したいと思います。
guest

回答2

0

とりあえず[質問へのコメント]欄に書いた話:

(正直,BitBoard なるものを知らないですが)
右側2人とORをとり,その結果を上3人とORをとり,結果が0ならいける,みたいな???

座標 43 を例にすると…
自身と44と45でORをとっても0.(←シフトしてORしてシフトしてORして,みたいな手続きで?)
(他の全マスも同時に同じことをしたとして,その結果の上で)自身と35,27,19 のORをとっても0なので矩形の左下になれる,っていう.
(一律処理してれば,同時に座標 58 もOKだとわかる…のかな?)

を,すっごい雑に実装してみた.
("BitBoard" ってどんな型で表す物なのか? とか どういう演算を用いる物なのか? とかは知らないので,いろいろと適切ではないかもですが)

C++

1//BitBoard のつもり 2struct BB{ uint8_t Row[8]; }; 3 4//これは単なる表示 5void ShowBB( const BB &b ) 6{ 7 for( int iRow=0; iRow<8; ++iRow ) 8 { 9 uint8_t v = b.Row[iRow]; 10 for( int i=0; i<8; ++i ) 11 { 12 putchar( (v&0x80) ? '#' : '.' ); 13 v <<= 1; 14 } 15 putchar( '\n' ); 16 } 17} 18 19//これが処理.コメントとちょっと違っていて,矩形の「左上」を探している. 20void FindTopLeftPos( 21 int W, int H, //矩形のサイズ 22 const BB &b //現在の盤面 23) 24{ 25 BB buff = b; 26 //横方向 27 for( int i=0; i<W-1; ++i ) 28 { 29 for( int iRow=0; iRow<8; ++iRow ) 30 { buff.Row[iRow] |= ( ( buff.Row[iRow]<<1 )|0x01 ); } 31 } 32 //縦方向 33 for( int i=0; i<H-1; ++i ) 34 { 35 for( int iRow=0; iRow<8-1; ++iRow ) 36 { buff.Row[iRow] |= buff.Row[iRow+1]; } 37 buff.Row[7] = 0xFF; 38 } 39 //結果表示.(ここで '#' で表示されない場所が結果である) 40 ShowBB( buff ); 41} 42 43//main 44int main(void) 45{ 46 BB Curr = { { 0x03, 0x7F, 0x63, 0x00, 0x00, 0x00, 0xC7, 0xC7 } }; 47 std::cout << "---Input---\n"; 48 ShowBB( Curr ); 49 std::cout << "\n---Result---\n"; 50 FindTopLeftPos( 3,4, Curr ); 51 std::cout << std::endl; 52 return 0; 53}

動作結果:3箇所見つかった.

---Input--- ......## .####### .##...## ........ ........ ........ ##...### ##...### ---Result--- ######## ######## ###.#### ##.##### ##.##### ######## ######## ########

投稿2022/12/28 01:32

fana

総合スコア11632

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

concern12

2022/12/29 02:40

ご回答ありがとうございます。 配置可能な座標を取得したい場合はAND演算で走査した方が速そうですが、配置可能な座標をBitBoard上で表すならご回答していただいた手法が速くてとても役に立ちそうです。 矩形を動かすやり方ばかり考えていて、BitBoard自体を動かして配置できる座標を求める手法は全く思いついていなかったため、ハッとしました。 色々と応用が効きそうです。ありがとうございました!
guest

0

盤面がそれほど大きくない(100x100程度?)のであれば、二次元累積和が使えると思います。

二次元累積和は、碁盤状に並んだマスそれぞれに数値が書かれているとき、盤面上のある長方形の区画内の数値の合計を高速に求めることができる方法です。詳しい説明は下記のサイトでされているので読んでみてください。

具体的には、まず、BitBoardのときと同様に、矩形のある場所の数値が1, 無い場所の数値が0である二次元配列を用意します。次に、その配列の二次元累積和を取った配列を作ります。そして、二次元累積和を使って長方形の区画内の数値の合計を求め、それが0ならばその区画に配置可能、1以上なら配置できないと判断できます。

矩形の配置情報が更新されるときは、その度に累積和を取った配列も丸ごと更新する必要がありますが、盤面が小さいか更新回数が少なければ、あまり問題にはならないと思います。

投稿2022/12/27 14:59

luuguas

総合スコア492

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

concern12

2022/12/29 02:46

固定された盤面であればかなり高速な手法ですね。 二次元累積和を使った手法は考えていなかったため、考察しがいがありそうです。 ありがとうございました!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問