CODEWITHSUNDEEP
algorithmgridspatial-index
kikito
kikito

Reputation: 52698

Optimize "diff" movement over spatial grid

I'm trying to find an efficient way to update a spatial grid which contains information about which object is on which grid cell. The objects move. For example:

···AAA···
···AAA···
···AAA···
·········

The object A occupies 9 cells in the grid. Now it moves down and to the right one position:

·········
····AAA··
····AAA··
····AAA··

The "brute force" approach would remove object A from all cells and then it would add A to the new cells. This however is very inefficient because 4 of the cells involved already contain A. What I would like to do instead is only to operate on the "diff":

···---···
···-··+··
···-··+··
····+++··

This is, adding "A" to the cells with a + and remove it from the cells with a -. Leaving the rest as they are.

A can be considered to be defined by its left,right,top and bottom coordinates:

The movement can occur in any direction, not just always left and bottom. The object can change in size as it moves, so the "After" could become bigger or smaller than the "Before". "Before" and "After" don't always overlap, the objects can "teleport" around.

I would like to avoid even iterating over cells that are not part of the diff, it at all possible.

I'm implementing this in Lua, but I would appreciate an efficient algorithm in any language that I can translate.

Upvotes: 0

Views: 40

Answers (2)

kikito
kikito

Reputation: 52698

I think I got it. Back to this image:

···---···
···-··+··
···-··+··
····+++··

The - and the + in the figure above both are "uppercase L" shapes. Depending on how the rectangles intersect the updated areas can take many "shapes". Most of them are rectangles. The Ls can take 4 "orientations" (⌜,⌝,⌞,⌟). Some Ls will have thick or thin "necks" and "bases". Optimally though, all you need to draw any uppercase L shape is two rectangles.

If one of the rectangles is bigger than the other ones, there can be some "C" shapes or even an "O" shape (one rectangle fully contains the other, which is smaller). So in the worst possible case we need 2 to "update" 4 rectangles.

Getting those rectangles calculated is tricky. I did ask ChatGPT, which put me on the right track, although I did have to massage and test the code quite a lot. Here's the result:

  -- "old" and "new" are intersecting
  if l1<=r2 and l2<=r1 and t1<=b2 and t2<=r2 then
    if l1<l2 then removecells(l1,t1,l2-1,b1) end
    if r1>r2 then removecells(r2+1,t1,r1,b1) end
    if t1<t2 then removecells(max(l1,l2),t1,min(r1,r2),t2-1) end
    if b1>b2 then removecells(max(l1,l2),b1,min(r1,r2),b2+1) end

    if l2<l1 then addcells(l2,t2,l1-1,b2) end
    if r2>r1 then addcells(r1+1,t2,r2,b2) end
    if t2<t1 then addcells(max(l1,l2),t2,min(r1,r2),t1-1) end
    if b2>b1 then addcells(max(l1,l2),b1+1,min(r1,r2),b2) end
  
  -- "old" and "new" are not intersecting. Apply the "brute force"
  -- option unless they are exactly the same, in which case we don't need
  -- to do any updates
  elseif l1~=l2 or r1~=r2 or t1~=t2 or b1~=b2 then
    removecells(l1,t1,r1,b1)
    addcells(l2,t2,r2,b2)
  end

From outside-in:

  • There's a special case where the "old" and "new" don't intersect. In that case you want to use the "brute force" approach and just add to all and delete from all cells. Even this has a special case; if "old" and "new" are the same you don't need to do anything.
  • When they intersect, you draw at most 2 small rectangles for deleting and adding. They can take any shape.
  • There's several call to min and max that ensure there's no "overlap" between the rectangles. You never delete or add more than once from the same rectangles.
  • There's several +1s and -1s in key places. This is mostly done to preserve the "common zone" between "old" and "new". Without those 1s we would end up "unnecessarily deleting/adding one extra column/row" from the common zone.

Upvotes: 0

ravenspoint
ravenspoint

Reputation: 20616

Your data structure becomes very expensive if the grid is large ( more than 100 by 100 ) and inefficient if the number of objects is low compared to the size of the grid ( i.e. sparse ).

I would suggest NOT storing the grid at all. Instead maintain a vector of objects. Each object would store it's 'center' location ( row and column ) and a method isInside(r,c) to return true or false depending on whether the row, column parameters are 'inside' the object.

Iterating over the vector of objects will be fast and independent of the grid size.

The challenge is to optimize the isInside(r,c) method. Each object should store, instead of the 'center' location as suggested above but the bounding rectangle. A quick check allows a fast return of FALSE for any r,c that is outside the bounding rectangle. If inside, more detailed code can determine whether the object covers particular location.

To your question: how to optimize a diff movement. This becomes trivial, you only have to adjust the bounding rectangle parameters.

I am guessing that you might be concerned about the performance of displaying the result of a diff movement. You describe attempts to avoid repainting locations that remain inside the object when it moves. Are you certain this is the real concern? With modern graphics cards this is blazingly fast. If you find that the display refresh lags, you most likely are not using the graphics card efficiently: do not update each location individually but use a double buffering technique where you update the display in a memory buffer and then write the entire buffer to the graphics card in one call.

Note about collision detection: This can be done quickly by first checking for an overlap of bounding rectangles, and only then checking if the objects have overlapping locations.

Upvotes: -1

Related Questions