Organizational system for moving tiles in grid-based level

Question

conceptual problem here.

I have an array which will be rendered to display tiles in a grid. Now, I want these tiles to be able to move - but not just around in the grid. Per-pixel. It does need to be a grid, because I need to shift whole rows of tiles, and be able to access tiles by their position, but it also needs to have per-pixel adjustment, while still keeping the "grid" up to date. Picture a platforming game with moving tiles.

There are a few organizational systems with which I could do this, and I'll outline a few I thought of as well as their pros and cons (XY-style) in case it helps you understand what I'm saying. I'm asking if you think one of these is best, or think of a better way.

1. One way would be to place objects in the array with the properties xOffset and yOffset. I would then render them in their tile position plus their offset. (x * tileWidth + tile.xOffset). Pros: maintains vanilla grid-system. Cons: Then I would have to adjust each tile to its actual grid location once it moved. Also, the "grid" position would become a bit confused as tiles are moving. (Side note: If you think this is a good way, how would I handle collisions? It wouldn't be as simple as player.x / tileWidth anymore.)

2. Another would be to place lots of objects with xs and ys and render them all. Pros: Simple. Cons: Then I would have to check each one to see if it's in the row I want to shift before doing so. Also, collisions could not simply check the one tile a player is on, they would have to check all entities.

3. Another I thought of would be a sort of combination of the two. Tiles would be in the original array and get render as x * tileWidth normal tiles. Then, when they move, they are deleted from the grid and placed in a separate array for moving tiles, where their x and y are stored. Then the collisions would check the grid the fast way and the moving tiles the slow way.

Thanks!

PS: I'm using JavaScript, but it shouldn't be relevant.

PPS: Forgive me if it's not Stack Overflow material. This was the best fit, I thought. It's not exactly code review, but it's not specific to GameDev. Also I needed a tag, so I picked one somewhat relevant. If you guys recommend something else I'll be happy to switch it right over and delete this one.

PPPS: Sorry if repost, I have no idea how to google this question. I tried to no avail.

Answer 1

(Side note on handling collisions: Your obstacles are moving. Therefore, comparing the player's position to grid is no longer ever sufficient. Furthermore, you will always have to draw based on the object's current position. Both of these are unavoidable, but also not very expensive.)

You want the objects to be easy to look up, while still being able to draw them efficiently and, more importantly, quickly checking for collisions. This is easy to do: store the objects in the array, and for the X and Y positions keep indexes which allow for 1) efficiently querying ranges and 2) efficiently moving elements left and right (as their x and y positions change).

If your objects are going to be moving fairly slowly (that is, on any one timestep, it is unlikely for an object to pass very many other objects), your indexes can be arrays! When an object moves past another object (in X, for instance), you just need to check its neighbor in the X index array to see if they should swap places. Keep doing this until it does not need to swap. If they're moving slowly, the amortized cost of this will be very close to O(1). Querying ranges is very easy in an array; binary search for the first greater element, and also for the last smaller element.

Summary/Implementation: (Fiddle at https://jsfiddle.net/LsfuLo9p/3/)

Initialize (O(n) time):

1. Make an array of your objects called Objs.
2. Make an array of (x position, reference to Objs) pairs, sorted in X, called Xs.
3. Make an array of (y position, reference to Objs) pairs, sorted in Y, called Ys.
4. For every element in Xs and Ys, tell the object in Objs its index in those arrays (so that Xs has indexes to Objs, and Objs has indexes to Xs.)

When an object moves up in Y (O(1) expected time per moving object, given that they're moving slowly):

1. Using Objs, find its index in Ys.
2. Compare it to the next highest value in Ys. If it's greater, swap them in Ys (and update their Y indices in Objs).
3. Repeat step 2 until you don't swap.

(It's easy to apply this to the other three directions.)

When the player moves (O(log n + k²) time, where k is the maximum number of items that can fit in a row or column):

1. Look in Xs for small, the smallest X above Player.X, and large, the largest X+width below Player.X. If large ≤ small, return the range [large, small].
2. Look in Ys for small, the smallest Y above Player.Y, and large, the largest Y+height below Player.Y. If large ≤ small, return the range [large, small].
3. If there are any intersections between these two ranges, then the player is colliding with that object.

(You can improve the time of this to O(log n + k) by using a hashmap to check for set intersections.)