While I was working on the "National Grid Floe" project (yes, that was last year! come on I'm slowly catching up with my posts.) I was facing the problem, that I had to place a massive amount of differently sized elements in a certain area on the site, with the problem being that the elements were not supposed to overlap with each other. A very basic approach - that's actually used more often than you would think - is to just place an object at a random place and test if it overlaps with any other object. If it does, place it somewhere else and test again, if it does not overlap with anything move on to placing the next object. As you can see this procedure is highly inefficient. Since you're working with randomly generated positions, it could easily happen that you place the object at the same position over and over again, wasting a lot of performance on something completely useless. The more objects you are placing, the more likely it is that this method makes your computer freeze and the browser crash. Since "National Grid Floe"'s community works with a ton of "user bubbles" that are not supposed to overlap each other I had to find a way to get an available spot on the first placement, otherwise the site would run into massive performance problems...

My solution works with a simple two-dimensional array. I create a grid of many rectangles and store in the array which of the rectangles are still available. Whenever I am about to place an object I look at the object's size and figure out how many rectangles next to each other in the grid I will need for this object and search for the nearest empty blob of free rectangles, big enough for the object. Since I keep checking each cell until I found a place for the object, the worst case scenario for repeated calculations with my system would be the amount of cells in the grid. That is still quite a few recursions but definitely beats the possibility of infinity with the common basic method. I created this solution in around a day or two, because I was under a really tight deadline back then and couldn't afford to research if there are even more efficient methods, but my class proved to be more than fast enough for what I needed it for.



2 Responses to “Array Grid”

  1. Juan Bermudez:
    May 13th, 2009 at 1:32 am

    What if you added itusing the tratitional messache and if it was on top of another moved it before adding to the displa list?

    Is tht more than using the multidimensional array?

  2. Jens:
    May 13th, 2009 at 9:42 am

    The main problem with the traditional method is not the part where you add it to the display list, it’s the fact that randomly generated positions are very likely to overlap with each other. It’s a huge performance problem, if you have a few hundred objects placed already and you have to call the “find a spot” function over and over again because the object is always placed on top of others. Imagine the placement calculation for a single object has to be executed 100,000 times. That means Flash has to make all those calculations before it will execute any of your other code. It’ll slow down the whole application massively and pretty soon, you’ll reach the moment where Flash will throw a “Stack Overflow” error…

    That doesn’t happen with the two dimensional array grid. It’s really a much, much faster solution.

Leave a Reply