Implementing multiple irregular grids

A lot of building games cover the entire playable space with a regular grid, but Cities Skylines does this weird thing where grid squares are local to the road along which they’re built, like this:


Critically, the game is obviously able to check each grid square’s position against other grids to ensure that two squares never overlap.

If it were working with a single, regular grid that would be as simple as dividing the world coordinates you want to query by the grid size and using the result as the [x,y] coordinates in whatever array/container you store the grid in, but with multiple grids that are not axis- or position-locked it becomes a lot tricker. The big, dumb, obvious approach (which I’m convinced they aren’t using) would be to construct bounding volumes for each square and do literal collision checks, but that’s expensive and not suitable for a task that by accounts should only happen in data.

The next easiest thing that comes to mind would be storing each grid square’s center and dimensions, and checking if a proposed new square was positioned closer to any centerpoint than that square’s dimensions, but at any scale that’s quickly going to balloon into checking thousands upon thousands of coordinates every time the player does something, and scale poorly with size.

So what’s the alternative? There must by definition be some kind of central repository of grid information that lets prospective grids/squares see each other and external entities ask for a grid square and its data by coordinates, but I don’t see how that’s feasible without doing a ton of expensive coordinate checks.

You can quickly discard huge swathes of data points by considering each road’s individual cells as a single unit, one giant OBB, and check if that overlaps another road’s entire OBB before analyzing interior cells.

Ignoring my poor photo editing skills, you can see how you could discard all of the top road’s cells by only checking for a single overlap with the middle road. You can take this further by considering cardinal directions as well, e.g. checking the north side of the road, the south side of the road, etc. but that depends on how your roads work in general.

As for performance of evaluating all of the cell OBB’s against the other road’s overlapping cells, it should be fine. Overlap tests are generally quick, it’s the displacement calculations that are usually slow, and it only happens when the player is building things and not every single frame.

Oh derp, I never considered doing collision tests with the grid shape instead of individual squares… thank you for the suggestion, that sounds much more reasonable! :slight_smile: