Monday, February 9, 2015

Cell labeling for bucketing positions on the grid

This idea is for cutting down on the number of items one has to check for possible interactions.
The cells can be labeled in this fashion (example: 4*j+i with i,j from 0..3):
An item on the plane within a square, like position 1567.5, 500 might be in cell 6 considering where it falls within the square on the plane. So one could check in cell 6-4 = 2 and cell 6+4 = 10 and 6-1 = 5 and 6+1 = 7 for possible interactions with the items in those cells, or counting diagonals also 6-3 and 6+3, 6-5 and 6+5. The +- 1, 3, 4, 5 is the same for any choice of cell except those on the edges.

So you might want to make your cell grid say 7x7 but only use the central 5x5 and cells number 0-6, 7*n+0, 41-48, and 7*n+6 would all be out of bounds ...To check a cells neighbors one would check it's cell number +- 1, 7, 6, 8

A "sparse" implementation could perhaps use something like a dictionary in python, and make new cells whenever there is a need for one with the specified number, and deleted when it is empty...

No comments:

Post a Comment