I am making a 2D sport with simulation of water and gases. To retailer pixels, I exploit a modification of the RLE algorithm, the place I encode the pixels by x and y, leading to rectangles. In my case, that is the simplest strategy to scale back reminiscence utilization.
However I would like to seek out out which rectangle accommodates the x and y I am searching for. This must be achieved as rapidly as potential (this operation happens each body), sadly I’ve not discovered a means to do that. Is there such an algorithm?
What I attempted:
- Go left alongside x from the present x and y till I hit the pixel I would like.
- Create a graph of all rectangles, the place every vertex represents a rectangle, and an edge represents the neighborhood of two rectangles. And in addition retailer begin and finish factors of every rectangle.
The primary strategy could be very gradual. The second strategy kinda works, however consumes a variety of reminiscence.
That is scheme of what i would like:
- Similar colours right here don’t imply identical pixels sorts. They’re for simplicity of the scheme.
- Quantity in left high nook of rectangles, signify index of this pixel in 1D array. Array seems like this: [{x size, y size, matherial}, …]
- The dots are random factors on the grid with specified coordinates.
- The arrows present which pixels these factors belong to.
- Any grid level will all the time be occupied by some rectangle; empty areas can’t exist.
- The grid measurement is presently 65536 by 65536 pixels. And this is only one chunk. The grid is all the time sq.
Is there a option to get the index of a pixel by the coordinate it accommodates? Is it potential to someway modify this construction to realize this consequence? Thanks for any assist.
