1

从这个问题Detecting mouse coordinates withprecision开始，我在过去几天里学到了很多东西。以下是我挑选的关于该主题的最佳学习资源：

  1. http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/
  2. http://www.gamedev.net/page/resources/_/technical/graphics-programming-and-theory/quadtrees-r1303
  3. http://jsfiddle.net/2dchA/2/

(3) 中的代码在 JSFiddle 中有效，但在我的测试环境 (VS2012) 中的本节中断：

var myTree = new Quadtree({
  x: 0,
  y: 0,
  width: 400,
  height: 300
});

带有消息 Quadtree 在 IE 中未定义。FF & Chrome 只是掩盖它并显示一个空白页面。我没办法解决。问题1：有人可以帮忙吗？

我的主要问题：我有一个区域（像地图一样的地块），其中大约 1500 个地块是用 html5 绘制的，而不是 jpg 或 png 图像。完成它需要很多代码行，但渲染很棒，所以我保持这种方式。我打算让鼠标悬停事件告诉我当鼠标停止时我站在哪个包裹上。正如您将在上一个问题中看到的那样，我之前的尝试并不令人印象深刻。根据我一直在做的学习，并且感谢 Ken J 的回答/评论，我想采用这种新方法，将我的画布切成 15 个四边形，每个四边形 100 个对象。但是，在我以错误的方式进行另一次疯狂潜水之前，我需要一些指导。

问题 2：我应该在创建时将其切片，还是应该在鼠标悬停在某个区域上时进行切片，即跟踪鼠标？后者对我来说听起来更好，但我认为我可以提供一些建议，如果可能的话，一些开始的代码。四叉树的概念对我来说是全新的。谢谢。

4

3 回答 3

1

对问题 1 无能为力。

您绝对应该尽早构建树，因为目标是让页面在用户单击某处后尽快响应。

只要用户与 2d 区域交互，就保留树。更新四叉树应该不会太难，因此即使该区域更改了内容，您也应该能够重用现有的树（只需更新它）。

于 2013-07-21T14:02:19.047 回答
1

鉴于您的绘图区域众所周知，我认为 QuadTree 与空间散列函数相比没有优势。此函数将为您提供 (x,y) 点的整数。 

var blocWidth   = 20;
var blocHeight  = 20;
var blocsPerLine = ( 0 | ( worldWidth / blocWidth) ) + 1 ; 
function hashPoint(x,y) {
   return ( 0 | (x/blocWidth)) + blocsPerLine*(0|(y/blocHeight));
}

构建完成后，将所有地块散列在一个数组中：

parcelHash = [];

function addHash(i,p) {
   if (!parcelHash[i]) { parcelHash[i]=[ p ]; return; }
   if (parcelHash[i].indexOf(p) != -1 ) return;
   parcelHash[i].push(p);
}

function hashParcel (p) {
     var thisHash = hashPoint(p.x,p.y); // upper left
     addHash( thisHash, p);
     thisHash = hashPoint(p.x+width, p.y); // upper right
     addHash(thisHash, p);
     thisHash = hashPoint(p.x, p.y+p.height); // lower left
     addHash(thisHash, p);
     thisHash = hashPoint(p.x+width, p.y+p.height); // lower right
     addHash(thisHash, p);         
};

for (var i=0; i<allParcels.length; i++) { hashParcel(allParcels[i]) };

现在，如果您有鼠标位置，则可以使用以下命令检索同一块中的所有包裹：

  function getParcels(x,y) {  
       var thisHash = hashPoint(x,y); 
       return parcelHash[thisHash]; 
    }
于 2013-07-21T14:03:08.033 回答
0

除了其他人所说的之外，我只会给你一些提示。

...有一个鼠标悬停事件告诉我我站在哪个包裹上...

从您的其他消息中，我得出结论，包裹将具有不规则的形状。四叉树通常使用矩形，因此您必须计算围绕地块形状的边界矩形并将该矩形插入四叉树中。然后是当你想确定鼠标是否在一个包裹上时，你会查询四叉树，它会给你一组可能在鼠标下的包裹，但是你必须自己做一个更精确的检查看看是不是真的。

...当鼠标停止时。

从您的其他问题中，我看到您尝试检测鼠标何时“停止”。也许你应该这样看：鼠标光标从不移动，它在屏幕上从上一个点传送到下一个点。它总是停下来，从不移动。这可能看起来有点哲学，但它会让你的代码更简单。您绝对应该能够在没有任何 setTimeout 检查的情况下实现您的目标。

... 将我的画布切成 15 个四边形，每个四边形 100 个对象。
...我应该在创建时将其切片还是应该在鼠标悬停在某个区域上时进行切片

您不会（也不能）进行切片，当您从中插入或删除项目时，四叉树实现会自动执行此操作（这就是它的目的）（请注意，移动项目实际上是删除然后重新插入它）。

我没有研究您正在使用的四叉树的实现，但这里有两个 MX-CIF 四叉树实现，以防万一不适合您：

问题 1 中的问题可能是因为 jsfiddle (http) 页面正在尝试访问 https 上的 quadtree.js

于 2013-07-27T12:50:12.110 回答