0

I am working on a game where you place buildings linked by connectors on a rectangular grid. Nothing can overlap. Buildings and connectors cannot change once they are on the grid; they can be destroyed any time. The grid is defined such that the bottom left corner is (0,0).

The buildings are rectangles, where each edge can be 1 - 4 units long; there are also a 5x5 squares.

Connectors have a start point and an end point. They cannot overlap, and are 1 unit wide. They can go in straight lines EDIT:(left, right, up and down) and bend wherever at 90 degrees. Unlimited length.

The grid would ideally be quite large (200x200 or greater) but that means there can be many thousands of these objects and connectors.

When an object gets built, I need to check whether or not it overlaps with anything. If I make a grid of bits, its size would be prohibitively large beyond 300x300. If I make a list of all objects, I could search within some limit, but how would I deal with connectors?

Seeing as a 2-D array of bits is not possible, I must index all buildings, and sort them by x coordinates, then by y coordinates. I could do a linear search for connectors, but that would be very tedious and painful.

Does anyone have a suggestion? P.S. I am doing this in C++

Daniel Widdis
  • 8,424
  • 13
  • 41
  • 63
ithenoob
  • 326
  • 1
  • 2
  • 11
  • 90kbits isn't that large. What are the constraints of your target platform? You should probably look at quadtrees. Connectors could be represented as a series of 1xN rectangles. – Alan Stokes Jul 20 '13 at 20:16
  • I guess I have been stuck in a rut trying to hyper-optimize memory overhead. Now that you mention it, I could use a bit array. (Since I like to think extremes) Would theoretically a 1000x1000 grid best be represented by an array or detect object collisions? BTW how would quadtree help? – ithenoob Jul 20 '13 at 20:25
  • Quadtrees are supposed to make queries like 'does this new shape intersect any existing shape'. Should be better than exhaustive linear search. – Alan Stokes Jul 21 '13 at 18:13

1 Answers1

1

Apart that 300x300 is not large, and if you really wanted you could pack your boolean values in bits within a byte (but I don not suggest that for speed reasons) you can check if connectors intersect with a simple function: https://stackoverflow.com/a/565282/2436175

Assuming that you have already checked that your new building does not intersect with any other building, what is left to check is that the side of your new building (segment) do not intersect with any of the connectors you have already in place.

Community
  • 1
  • 1
Antonio
  • 19,451
  • 13
  • 99
  • 197
  • Sorry, question wasn't clear. Connectors go parallel to x and y axis, can bend at any point on the grid. – ithenoob Jul 20 '13 at 20:39
  • @ithenoob Then your intersection function becomes very simple. Your connectors are not one segment, but composed of several segment. You have also to decide how to handle when a connector *overlap* with one of the sides of the building. – Antonio Jul 20 '13 at 20:41
  • I guess using a boolean array would be the easiest way to do things... Beyond that, I think doing a brute search along all connectors is the only way because they can theoretically take any shape. – ithenoob Jul 20 '13 at 20:46
  • @ithenoob Yes. :) Just be sure you define correctly how this grid gets filled and checked: lines/segments normally would have zero area. Instead of using booleans, you can use `char` (same memory occupation of boolean if you want efficiency) and encode more information, like not only if a grid location is occupied, but also by which kind of object. Furthermore, if you can afford to have for example an array of `unsigned int` you can store for each location a unique ID for each object, making extremely easy to access or delete an object based on its location – Antonio Jul 20 '13 at 20:48
  • I already have a class for linear bit array. I can easily adapt it for this purpose. Thanks! – ithenoob Jul 20 '13 at 20:50