在问AI除了四叉树之外，还有什么碰撞检测算法，发现了一个网格分割不错，比四叉树简单多了。

就是将整个平面空间分割成网格，这个可以适用于无限扩展的平面空间。

但是分割的间距要相等。全都是小正方形。

还是老样子，给出API：

1
2
3
addItem(object)
removeItem(object)
getCollished(object, type) -> object[]

内部维护两个哈希表，一个是从网格坐标映射到对象集合的表，一个是对象映射到它所有接触到的网格的坐标的集合。

1
2
3
4
{
(1, 5): {obj1, obj2, ...},
(1, 6): {obj1},
}
1
2
3
4
{
obj1: {(1, 5), (1, 6)},
obj2: {(1, 5)}
}

例如上面这样。

在addItem的时候，传入的是对象。

  1. 会根据这个对象，例如是圆形对象，根据它的圆心位置和半径，瞬间计算出来它占了哪些网格。
  2. 然后进行双向绑定，增加两个表里的内容

removeItem的时候：

  1. 首先根据一个表，拿到这个圆形所占住的所有格子。
  2. 删除两个表里的所有相关内容
  3. 如果其中一个key对应的value空了，连同key一起删除。

getCollish的时候

API 解释一下：存入碰撞检测体系的时候，可以分个类，比如子弹单独成一个类，敌人单独成一个类。所以参数里有一个type，只获取和它碰撞的并且类型为type的物品。

  1. 首先拿到该物体所占住的所有格子
  2. 遍历所有格子里的，类型==type的东西。看是否碰撞，注意排除所有重复的比较，因为跨格子的时候可能会有两个一样的物品。也就是一个东西可能占了两个及以上的格子。

所以，所有存入碰撞检测体系的物体，必须有一个唯一的key，或者能被哈希化，因为它将作为key。

这个相比四叉树，不会出现一旦某个物体接触到屏幕最大的十字线的时候就会和所有物品比较一次的缺点了。

但依然物体过大的时候，可能会导致性能下降。

如何计算一个物体所占住的格子，这个判断可能会小麻烦一点。