how to efficiently track the use of space on a map, both objects and free areas

Question

OK I start with a blank map, which is 512x512 = 262144 pixels/locations.

I need a way to efficiently draw some objects on it, and then be able to find the areas of free space, so that later more different objects can be added to these free areas. I cant figure out the best way to store this data, or algorithms to find the free areas.

I had a working solution, but it took forever to compute. I'm working with AS3, in case that impacts what would be the best solution.

Any Advice? thanks.

Answer 1

There is plenty of methods to work with bitmaps at Bitmap and BitmapData classes.

I've never done anything like that, but you could try. I believe the best approach is to draw the objects at the map. Then, use the method bitmapData.getColorBoundsRect() to get the areas that are not free. These AS3 native methods are very, very fast!

Here is the documentation: http://help.adobe.com/en_US/AS3LCR/Flash_10.0/flash/display/BitmapData.html

Cheers, CaioToOn!

Answer 2

Your problem is almost identical to the issue of memory allocation in operating systems - issues of fragmentation, cleanup, appropriate contiguous space usage all appear there as well. I'd read on up how this problem is solved in OS's: start on Wikipedia.

Answer 3

The first thing that comes to mind is to use polygon-filling techniques. Consider your space as a set of scan lines, one scan line per Y coordinate. On each scan line, store a list of X coordinates representing transitions between free and occupied space.