空间邻近度查询的数据结构

问：

局限性

• 内存不是问题，只要它适合普通 PC。我不是在这里尝试优化内存使用。
• 更新速度极其重要，其次是查询速度。

要解决的问题

我有一个任务世界，每个任务都与一个实际的世界对象相关联（即，砍伐这棵树，建造这堵墙，将这个资源存放起来，等等）。因此，任何资源丢弃都可能触发更新。

我也有演员会定期要求完成任务，他们选择做的任务是物理空间中最接近他们的任务，他们既可以做，也可以优先做。因此，最接近的任务并不总是答案，我需要一个正确排序的潜在任务流，以便我可以从中选择我的任务。

天真地，我可以（并且确实）将其实现为世界上每个任务的 for 循环，按与参与者的线性距离排序，过滤掉参与者无法实际完成的每个任务，并且我跟踪为每个任务类别找到的最佳任务，直到我找到优先级最高的任务， 或者我用完了任务，在这种情况下，我会选择我找到的最高优先级任务。

我正在寻找一种数据结构来帮助我避免根据每个周期中每个参与者的距离对整个任务世界进行排序。我考虑过并放弃的事情：

• 八棵树和朋友们。它非常擅长回答碰撞查询，即针对空间中特定点的查询。这不是我想要的，我想给它一分（我的演员），并得到离它最近到最远的任务，可能是所有的任务（但通常只是一小部分）。

• 无论如何，强迫八叉树和朋友。我考虑了以我的演员为中心的对八叉树的螺旋模式搜索，距离越来越远。我可以让它工作，但我不相信这是一个很大的改进，而且它绝对感觉很糟糕。我希望有更好的数据结构。