2

しばらく前に四分木を使ったパスファインディングでプロジェクトを行いましたが、そのパフォーマンスを改善したいと思います。ノードの隣接関係を決定するためにテッセラル演算を使用すること（このページのように、ブリティッシュコロンビア大学の地理学部の厚意により）は、現在使用しているブルートフォース方式よりもはるかに高速であるようです（私はチェックしています共有エッジ。静的なクワッドツリーでは正常に機能しますが、マップが変更された場合はオーバーヘッドが大きくなりすぎます）。

隣接アルゴリズムのセクションで何が言われているのかは多かれ少なかれ理解していますが、どのように始めればよいのかよくわかりません。私は主にC＃に興味がありますが、言語に関係なく、私が見ることができるテッセラル算術を操作するためのソースがすでに浮かんでいるとしたら、それは素晴らしいことです。そうでなければ、誰かが私に足し算/引き算のキャリーに対処するためのいくつかの指針を与えることができますか？

4

2 に答える 2

4

これを効率的に行う方法はわかりませんが、通常の「ビット単位の演算で追加」アルゴリズムは、次のアルゴリズムを提案します（テストされていません）。

static int tesseral_add(int x, int y)
{
    int a, b;
    do
    {
        a = x & y;
        b = x ^ y;
        x = a << 2; // move carry up 2 places instead of the usual 1
        y = b;
    } while (b != 0);
    return b;
}

キャリーチェーンがある場合、これはおそらくかなり多くループします。

実際、これを行うにはもっと良い方法があります。

については、キャリーが再キャリーされるためz = interleave(a, -1); w = interleave(b, 0);、を追加zして直接部分的に正しい結果が得られることに注意してください（すべての「中間」ビットは1です）。w唯一の「問題」は、y座標が破壊されることです。

したがって、2つのテッセラル番号を追加するz = interleave(a, b); w = interleave(c, d);には、それを行うための簡単な方法があります。

int xsum = (z | 0xAAAAAAAA) + (w & 0x55555555);
int ysum = (z | 0x55555555) + (w & 0xAAAAAAAA);
int result = (xsum & 0x55555555) | (ysum & 0xAAAAAAAA);
于 2012-02-21T11:56:15.197 に答える
2

テッセラル算術を処理する最も簡単な方法は、数値を「ビット解凍」し、通常どおり任意の数の算術演算を実行し、テッセラル形式が必要なときにそれらを「ビット圧縮」することです。

z = bit_zip(bit_unzip(x) + bit_unzip(y));

（この例はunsignedのみ機能します。符号付き整数の場合、各数値を2つの変数に解凍し、両方の部分で別々に通常の算術演算を実行します）。

「bit-unzip」と「bit-zip」の高速実装は、「MattersComputational」の1.15 章「Bit-wisezip」にあります。

于 2012-02-21T17:09:35.423 に答える