Efficient Position Search

[sunjay]

This is probably only necessary to do once we start getting a lot of entities.

Using a VecStorage for storing positions is pretty inefficient to search. Would be better if we implemented a kd tree 2D grid of points within each cell. Basically a bucket hash map implementation at that point.

TODO: Look into R trees

https://stoeoef.gitbooks.io/spade-user-manual/content/

Some considerations:

• All nodes can be stored in a Vec and can refer to siblings using indices
• Needs to support the storage API: https://docs.rs/specs/0.14.0/src/specs/storage/storages.rs.html#49
  • add, remove, get, get_mut
  • To implement get_mut, we can keep a queue of items that may need to be reinserted and then do that at the start of other operations
• Must allow duplicates in case multiple entities are at the same position (could use a Small Vec at each point in the grid to optimize cache usage)
• Use the num crate to be generic over the element type
• Insert anything that can be converted into (T, T)