按范围遍历大型数组或其他数据结构

想像贪吃蛇的游戏中，地图上有很多食物, 程序要检测蛇头是否与食物碰撞（根据地图上的坐标）。
如果用一个数组保存食物的信息，就要遍历这个数组。但如果有很多食物（数组很大），完全遍历是没必要的，因为只有一定范围里的食物可能发生碰撞。
问题是怎么实现不遍历整个数组，而根据坐标，找到可能发生碰撞的食物。

我能想到的是使用array_filter，但实质上还是遍历。
如果有使用其他数据结构(不用数组）的方法，也可以提供。
可能做过游戏的朋友会有好的解决方案。

回复内容：

想像贪吃蛇的游戏中，地图上有很多食物, 程序要检测蛇头是否与食物碰撞（根据地图上的坐标）。
如果用一个数组保存食物的信息，就要遍历这个数组。但如果有很多食物（数组很大），完全遍历是没必要的，因为只有一定范围里的食物可能发生碰撞。
问题是怎么实现不遍历整个数组，而根据坐标，找到可能发生碰撞的食物。

我能想到的是使用array_filter，但实质上还是遍历。
如果有使用其他数据结构(不用数组）的方法，也可以提供。
可能做过游戏的朋友会有好的解决方案。

redis的sort set类型 可以满足你的需求 http://redis.readthedocs.io/e...

我觉得是这个样子：

• 首先贪吃蛇中食物是一个球，那存食物的数组应该存的是<坐标, 半径>，在C++里有map可以用；

• 然后，你可以开一个数组就叫做Map，数组的大小就是地图的w h，假设有这么食物<(x,y), r>，那Map需要这么赋值：Map[wx + y] = r；记录一个maxR的东西，代表食物的最大半径，maxR=max(r).

• 最后，判断碰撞，设蛇头的位置为(a, b)，你需要做的是遍历以(a，b)为中心半径为maxR的圆的所有坐标(x，y)，然后取出r = Map[w*x + y]，与now_r = dis((a,b), (x,y))相比较，如果r>=now_r，说明蛇会吃到这个食物，如果小于，则说明吃不到，继续下一个坐标的判断。

• 实际上，我估计实际做的时候应该就是遍历所有的食物，毕竟贪吃蛇的食物没那么多吧。