Tesseral算术/四叉树 [英] Tesseral arithmetic/quadtree

问题描述

我做过一个关于四叉树路径查找的项目，我想改善它的性能.似乎使用镶嵌算法确定节点邻接关系(按照

I did a project a while back on path finding with quadtrees and I would like to improve on its performance. It seems that using tesseral arithmetic to determine node adjacency (as per this page, courtesy of the Geography department of the University of British Columbia) would be much faster than the brute force method I'm using at the moment (I'm checking for shared edges, which works fine for a static quadtree but would be too much overhead if the map were changing).

我或多或少都了解邻接算法"部分的内容，但是我不确定如何开始.我主要是对C#感兴趣，但是如果已经有了一些我可以研究的使用细分算法的资料，而不论使用哪种语言，那就太好了.否则，有人能给我一些处理加/减进位的提示吗?

I more or less understand what's said in the Adjacency Algorithm section, but I'm not really sure how to begin. I'm primarily interested in C#, but it'd be awesome if there's already some source floating around for working with tesseral arithmetic that I could look at, regardless of language. Otherwise, could anyone give me some pointers on dealing with the addition/subtraction carries?

推荐答案

我认为，最简单的处理tesseral算术的方法是解压缩"数字，正常执行任意数量的算术运算，以及"bit-zip" 当需要镶嵌形式时，它们会返回:

I think, the easiest way to deal with tesseral arithmetic is to "bit-unzip" numbers, perform any number of arithmetical operations normally, and "bit-zip" them back when tesseral form is needed:

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

(此示例仅适用于unsigned.对于有符号整数，请将每个数字解压缩为两个变量，然后分别对这两个部分进行常规算术运算.)

(This example works for unsigned only. For signed integers, unpack each number into two variables and do normal arithmetic on both parts separately).

您可以在"要点计算中找到"bit-unzip"和"bit-zip"的快速实现. "，第1.15章按位zip".

You can find fast implementations for "bit-unzip" and "bit-zip" in "Matters Computational ", chapter 1.15 "Bit-wise zip".

这篇关于Tesseral算术/四叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！