# Find grid cells in 2D grid based on object size and rotation

I am working on a game that uses a grid system that allows the player to place buildings in the world. Each cell in the grid is 64x64. All buildings will be a multiple of 64x64, so everything will evenly fit in the the grid.

Below shows an example of a building that is 128x64 and placed at grid position 64x64. The client sends the server the "base" cell, which in this case is 1,1 (@64x64), and knows the building that is being build is 128x64 so it sets both cells to the "occupied" state which means a building is placed in those 2 grids.

The problem I am having is allowing the client to rotate the building either 90, 180, or 270 degrees.

For example, if the client wanted to place the same building, but rotated 90 degrees, it would look like this:

Basically what I am asking is: Given the client sends to server the location to build 64x64, and sends 90 for the rotation, how can I (on the server) figure out which cells are going to be build on?

Currently I am using this code to get the grids, but it doesn't allow for rotation since I have no idea.

https://pastebin.com/UaaUa7jZ

Any help would be appreciated.

• Please include your code in the question itself, not in an external link that can rot. – DMGregory Mar 23 '20 at 2:42

I have previously implemented something similar for determining placement of items within a 2D grid and hope that sharing my ideas with you will provide some guidance.

It helps to normalise the coordinates for the items being placed into an offset around the origin as well as considering rotations as a fixed step rather than an angle (which you could convert to/from later if needed).

As an example, consider the following shape rotated in 4 different orientations:

The footprint of the object is defined by the offsets from the origin where 0,0 is the "base" cell as you described. To calculate the neighbouring cells for a given rotation, we can use a simple formula to convert from the original, non rotated footprint to the footprint of the rotated object.

For the original rotation (rot = 0), we simply do nothing and the footprint coordinates remain as is.

For each subsequent rotation we can follow these rules:

Rot = 1: First invert the x coordinate, then flip both the x and y coordinates.
Rot = 2: Invert both the x and y coordinates
Rot = 3: First invert the y coordinate, then flip both the x and y coordinates.


Here is an example for the footprints of the above shapes with the appropriate rotation:

To work through an example of this, given the footprint with rot = 1, we would convert the coordinates as such:

Rot = 1: First invert the x coordinate, then flip both the x and y coordinates.

0, 0 -> 0, -0
0, 1 -> 1, -0
1, 1 -> 1, -1


Hopefully this should be enough information to infer the remaining rotations with the aforementioned formulas.

Once you have calculated the new footprint coordinates for your given rotation, these can then be added to your world grid coordinates to determine which neighbouring cells need to be checked in relation to your base cell.

The server has to have the same knowledge of building types that the client has, and needs to know the current rotation and dimension(s).

To keep this information concise in your packets sent up to server, you can use 1 byte for the direction (this is really just an enum type that both client and server code have access to):

0=0 degrees
1=90 degrees
2=180 degrees
3=270 degrees


You can actually fit these 4 values into 2 bits i.e. 2^2=4, rather than 1 byte or 8 bits. But keeping it as a byte keeps it simple to start with.

Building shape could be either just length (say 1 unit wide x n units long), or length and width, both of which get sent to the server - you can use 1 byte for each of width and height, and later on, use fewer bits to save on bandwidth.

So your simplified packet layout might be e.g.:

[1 byte rotation factor|1 byte width| 1 byte height| other stuff you need to send]

When this arrives on the server, you multiple the rotation factor by 90 degrees or the equivalent radians, then figure out the direction the body length is going to go, and then check whether this collides with existing buildings on the server.

I would suggest for a more compressed layout (optimise only once the basic logic is working):

[2 bits rotation factor|3 bits width|3 bits height] totalling 8 bits or 1 byte

• It looks to me like OP could also use some help translating a packet like "Building A (3x2) at position 13, 4, rotated 90 degrees" into the corresponding tile coordinates that the footprint of the building will cover in that orientation. – DMGregory Mar 26 '20 at 14:04
• @DMGregory The assumption is that part is trivial. Do you not agree? Simple matrix transposition is one way to do this. OP - let us know if this is what has you confused. – Engineer Mar 26 '20 at 14:11
• I'd agree it's trivial for someone with your experience, but by my reading, I don't think OP is finding it so easy, so showing even a quick example of that could be a big help to them. – DMGregory Mar 26 '20 at 14:12
• Let's see if they come back and respond, in which case I will make good on your suggestion. – Engineer Mar 26 '20 at 14:14