Scan / filter 2d Array

[kevin]

  Scan / filter 2d Array

     A lot of game effects use various filtering methods applied across a 2D data set or 2D array.   For the sake of this example, we'll call a filter the process of reading the 8 surround cells of any cell within our array.     The problem is if we run through  a large 2d array and read the 8 cells around every cell, that's 8 times (at least) the array accesses than we generally need.   Often we can cache data in integer an value(s) and scroll the data. 

     Bellow the FIlter_Grid() routine runs through the GRID() array and tally's the 9 cells together into a single value. You'll noticed it doesn't read all 9 values every time, rather it just reads 3.   If you think about what such routines do they're a sliding window.  Each time we move across a row, the column of values in front and aligned to the last cell, now move across and behind.    So it's generally best to keep this stuff in variables and just move the variables, rather than try and pull stuff out of array all the time.   

    Now Since there's 9 cells and each cells is 1 bit, that gives us a 2^9 =512 possible combinations.  So we can pre-compute our behaviors.    In this example, I'm building a table on startup that counts the number of the cells (set bits) that are active around and including this current cell.    So the render routine screens this value against 4, cells with more than 4 bits set are drawn red and the other are drawn in the default grey/blue colour.   

PlayBASIC Code: [Select]

` *=---------------------------------------------------------------------=*
`                   >> Grid Scan / Filtering Example V0.01 <<
` *=---------------------------------------------------------------------=*
`
`                             By: Kevin Picone  
`
`                              (22nd,Jan,2014)
`
` *=---------------------------------------------------------------------=*
`
`    In  this demo we're looking a way to reduce amount of work required
` when we need to apply a filter to a 2D grid. 
      
`   The filter rule here will read 9 values, those being our source value and
` the 8 values around the source.   These values are packed into a single
` integer.  We can then use this value to lookup our behavior from each
` position.
`
` *=---------------------------------------------------------------------=*
` *=---------------------------------------------------------------------=*
`

   openscreen 900,700,32,1

   Size=20

   ; our grid of 'flags' 
   Dim GRid(Size,Size)

   ; the tally grid.  This holds the bit tally of each position in the grid.
   ; 
   Dim GRidTally(Size,Size)


   ` fill grid with 1 bit options
   For ylp=0 to Size-1
      For xlp=0 to Size-1
         ; use a rnd range of 100 to give a reasonable even distribution 
         grid(xlp,ylp) = rnd(100)>=50
      next
    next




   ` the filter routine packs nine (1 bit) values into a single 32 integer,
   ` giving us 512 possible combinations.  Since each bit represents the state
   ` of a grid item around the current item, we could use a table to tell us how many
   ` items around the current cell are set for example.. or pretty much anything
   ` really, the idea is to pre-compute the work house stuff out so we can
   ` simply lookup the answer, rather than compute it for eahc cell.
   
   Dim BitCount(512)
   
   
   For lp =0 to 512

      ` Count the number of set bits in this this value
      BitCount  = (lp and 1)   >0
      BitCount += (lp and 2)   >0
      BitCount += (lp and 4)   >0
      BitCount += (lp and 8)   >0
      BitCount += (lp and 16)   >0
      BitCount += (lp and 32)   >0
      BitCount += (lp and 64)   >0
      BitCount += (lp and 128)>0
      BitCount += (lp and 256)>0
   
      BitCount(lp)=BitCount
   
   next



   ` Convert the default font to a bitmap (CRF) font 
   MakeBitmapFont 1,-1,8


   ` -------------------------------------------------------------------------
   Do      ` MAIN LOOP
   ` -------------------------------------------------------------------------

         ; clear the screen to it's default colour black (rgb(0,0,0)
         cls 
      
         ; run the filter routine over the grid() to compute what's around each cell
         Filter_Grid()

         ; draw the grid to the screen so the user can get some idea of what's going on
         DrawGrid(60,10)


         ; flip the front and back buffers (show the screen to the user)      
         Sync


   loop esckey()
   end
   



` *=---------------------------------------------------------------------=*
` *=---------------------------------------------------------------------=*
` *=---------------------------------------------------------------------=*
`                                >> Draw GRid <<
` *=---------------------------------------------------------------------=*
` *=---------------------------------------------------------------------=*
` *=---------------------------------------------------------------------=*

Function DrawGrid(BaseXpos,BaseYpos)
   SizeY=40
   SizeX=40
   th=GetTextHeight("|")
   
   Ypos=BaseYpos
   lockbuffer
   For ylp=1 to GetArrayElements(Grid(),2)-1
      Ypos2=Ypos+SizeY
      Xpos=BaseXpos
      For xlp=1 to GetArrayElements(Grid(),1)-1

            ; Get the bit tally at this location
            ; this is the value of this point and the 8 points around it
            BitTally=GridTally(xlp,ylp)

            ; check if the middle bit is set
            if BitTally and 16

               ; choose a colour based upon how many bits around it (including us)
               ; are set
               C=$208080
               if BitCount(BitTally)>4 then C=$ff0000
               boxc xpos,ypos,xpos+SizeX-1,ypos2-1,true,c
            endif


            ; the show the bit tally grid at this location as 3 rows of text
            b$=right$(bin$(BitTally),9)
            text xpos,ypos         ,right$(b$,3)            
            text xpos,ypos+th      ,mid$(b$,4,3)            
            text xpos,ypos+th*2   ,left$(b$,3)            
            Xpos+=SizeX
      next
      Ypos=Ypos2
      if Ypos>GetScreenHeight() then exit
   next
   unlockbuffer

Login required to view complete source code