a grid 64 x 64, draw it out on graph paper.
now create a list of ten areas with random width and random height.
starting at the top of the list and working down, for each random width
and height do the following:
1) start at the top right of the grid, place the area (of width x height)
in the first area in the grid where it will fit. move your finger from
right to left along each row, before moving your finger down to the row
below. colour the area found in BLACK.
2) start at the bottom left of the grid, place the same area (of width x
height used in 1) in the first area in the grid where it will git. move
your finger from left to right along each row, before moving your finger
up to the row above. colour the area found in BLACK.
for a computer there are several ways of implementing such an algorithm.
1) create a data structure which holds the coordinates of the used-up
space. when it comes to finding freespace, iterate through the list of
coordinates and using mathematics, calculate where the next area can be
placed.
X-( far too slow for my requirements.
2) create a data structure which stores areas of unused space. the data
structure links to other areas of free space. when an area is used, the
areas of freespace must be adjusted or split such that certain
relationships are still maintained.
X-( far too complex for me to fully implement, suggested lots of recursion.
3) create an 2d array where each element in the array is either a 1 for
used space, or a 0 for freespace. searches are performed by inspecting
each element in the array.
X-( using a char array, only 1 bit out of 8 is used, so for a 128 x 128
array, that's a wastage of 14336 bits (unless my maths is wrong).
:-) faster than any other method investigated and quite easy to implement
all other placement strategies.
4) create a 2d array much like in 3 but this time directly use the
individual bits of whatever data type is used (ie 64/32/16/8 bit types).
X-( A PITA to implement, difficult to genericize the placement algorithm,
instead left-to-right and right-to-left are two seperate algorithms.
:-) faster still, and less memory wastage.
here's a 64 x 32 dimension grid, it uses 32bit array types.
////////////////////////////////|//////////////////////##########
////////////////////////////////|//////////////////////##########
////////////////////////////////|//////////////////////##########
////////////////////////////////|//////////////////////##########
////////////////////////////////|//////////////////////##########
////////////////////////////////|//////////////////////##########
////////////////////////////////|//////////////////////##########
////////////////////////////////|//////////////////////##########
////////////////////////////////|//////////////////////##########
////////////////////////////////|//////////////////////##########
////////////////////////////////|//////////////////////##########
////////////////////////////////|//////////////////////##########
////////////////////////////////|//////////////////////##########
////////////////////////////////|//////////////////////##########
////////////////////////////////|//////////////////////##########
////////////////////////////////|//////////////////////##########
##########//////////////////////|////////////////////////////////
##########//////////////////////|////////////////////////////////
##########//////////////////////|////////////////////////////////
##########//////////////////////|////////////////////////////////
##########//////////////////////|////////////////////////////////
##########//////////////////////|////////////////////////////////
##########//////////////////////|////////////////////////////////
##########//////////////////////|////////////////////////////////
##########//////////////////////|////////////////////////////////
##########//////////////////////|////////////////////////////////
##########//////////////////////|////////////////////////////////
##########//////////////////////|////////////////////////////////
##########//////////////////////|////////////////////////////////
##########//////////////////////|////////////////////////////////
##########//////////////////////|////////////////////////////////
##########//////////////////////|////////////////////////////////
-----------------------------------------------------------------
////////////////////////////////|////////////////################
////////////////////////////////|////////////////################
////////////////////////////////|////////////////################
////////////////////////////////|////////////////################
////////////////////////////////|////////////////################
////////////////////////////////|////////////////################
////////////////////////////////|////////////////################
////////////////////////////////|////////////////################
////////////////////////////////|////////////////################
////////////////////////////////|////////////////################
////////////////////////////////|////////////////################
////////////////////////////////|////////////////################
////////////////////////////////|////////////////################
////////////////////////////////|////////////////################
//////////######////////////////|////////////////################
//////////######////////////////|////////////////################
################////////////////|////////////////######//////////
################////////////////|////////////////######//////////
################////////////////|////////////////////////////////
################////////////////|////////////////////////////////
################////////////////|////////////////////////////////
################////////////////|////////////////////////////////
################////////////////|////////////////////////////////
################////////////////|////////////////////////////////
################////////////////|////////////////////////////////
################////////////////|////////////////////////////////
################////////////////|////////////////////////////////
################////////////////|////////////////////////////////
################////////////////|////////////////////////////////
################////////////////|////////////////////////////////
################////////////////|////////////////////////////////
################////////////////|////////////////////////////////
-----------------------------------------------------------------
////////////////////////////////|////////########################
////////////////////////////////|////////########################
////////////////////////////////|////////########################
////////////////////////////////|////////########################
////////////////////////////////|////////########################
////////////////////////////////|////////########################
////////////////////////////////|////////########################
////////////////////////////////|////////########################
////////////////////////////////|////////########################
////////////////////////////////|////////########################
////////////////////////////////|////////########################
////////////////////////////////|////////########################
////////////////////////////////|////////////////################
////////////////////////////////|////////////////################
//////////######////////////////|////////////////################
//////////######////////////////|////////////////################
################////////////////|////////////////######//////////
################////////////////|////////////////######//////////
################////////////////|////////////////////////////////
################////////////////|////////////////////////////////
########################////////|////////////////////////////////
########################////////|////////////////////////////////
########################////////|////////////////////////////////
########################////////|////////////////////////////////
########################////////|////////////////////////////////
########################////////|////////////////////////////////
########################////////|////////////////////////////////
########################////////|////////////////////////////////
########################////////|////////////////////////////////
########################////////|////////////////////////////////
########################////////|////////////////////////////////
########################////////|////////////////////////////////
-----------------------------------------------------------------
/////////////////////////////###|################################
/////////////////////////////###|################################
/////////////////////////////###|################################
/////////////////////////////###|################################
/////////////////////////////###|################################
/////////////////////////////###|################################
/////////////////////////////###|################################
/////////////////////////////###|################################
/////////////////////////////###|################################
////////////////////////////////|////////########################
////////////////////////////////|////////########################
////////////////////////////////|////////########################
////////////////////////////////|////////////////################
////////////////////////////////|////////////////################
//////////######////////////////|////////////////################
//////////######////////////////|////////////////################
################////////////////|////////////////######//////////
################////////////////|////////////////######//////////
################////////////////|////////////////////////////////
################////////////////|////////////////////////////////
########################////////|////////////////////////////////
########################////////|////////////////////////////////
########################////////|////////////////////////////////
################################|###/////////////////////////////
################################|###/////////////////////////////
################################|###/////////////////////////////
################################|###/////////////////////////////
################################|###/////////////////////////////
################################|###/////////////////////////////
################################|###/////////////////////////////
################################|###/////////////////////////////
################################|###/////////////////////////////
-----------------------------------------------------------------
///////////////////#############|################################
///////////////////#############|################################
///////////////////#############|################################
///////////////////#############|################################
///////////////////#############|################################
///////////////////#############|################################
///////////////////#############|################################
///////////////////#############|################################
///////////////////#############|################################
///////////////////##########///|////////########################
////////////////////////////////|////////########################
////////////////////////////////|////////########################
////////////////////////////////|////////////////################
////////////////////////////////|////////////////################
//////////######////////////////|////////////////################
//////////######////////////////|////////////////################
################////////////////|////////////////######//////////
################////////////////|////////////////######//////////
################////////////////|////////////////////////////////
################////////////////|////////////////////////////////
########################////////|////////////////////////////////
########################////////|////////////////////////////////
########################////////|///##########///////////////////
################################|#############///////////////////
################################|#############///////////////////
################################|#############///////////////////
################################|#############///////////////////
################################|#############///////////////////
################################|#############///////////////////
################################|#############///////////////////
################################|#############///////////////////
################################|#############///////////////////
-----------------------------------------------------------------
///////////////////#############|################################
///////////////////#############|################################
///////////////////#############|################################
///////////////////#############|################################
///////////////////#############|################################
///////////////////#############|################################
///////////////////#############|################################
///////////////////#############|################################
///////////////////#############|################################
///////////////////##########///|////////########################
////////////////////////////////|////////########################
////////////////////////////////|////////########################
////////////////////////////////|////////////////################
////////////////////////////////|////////////////################
//////////######////////////////|////////////////################
//////////######////////////////|////////////////################
################////////////////|////////////////######//////////
################////////////////|////////////////######//////////
################////////////////|////////////////////////////////
################////////////////|////////////////////////////////
########################////////|////////////////////////////////
########################////////|////////////////////////////////
########################////////|///##########///////////////////
################################|#############///////////////////
################################|#############///////////////////
################################|#############///////////////////
################################|#############///////////////////
################################|#############///////////////////
################################|#############///////////////////
################################|#############///////////////////
################################|#############///////////////////
################################|#############///////////////////
-----------------------------------------------------------------
///////////////////#############|################################
///////////////////#############|################################
///////////////////#############|################################
///////////////////#############|################################
///////////////////#############|################################
///////////////////#############|################################
///////////////////#############|################################
///////////////////#############|################################
///////////////////#############|################################
///////////////////##########///|////////########################
////////////////////////////////|////////########################
////////////////////////////////|////////########################
////////////////////////////////|////////////////################
////////////////////////////////|////////////////################
//////////######////////////////|////////////////################
//////////######////////////////|////////////////################
################////////////////|////////////////######//////////
################////////////////|////////////////######//////////
################////////////////|////////////////////////////////
################////////////////|////////////////////////////////
########################////////|////////////////////////////////
########################////////|////////////////////////////////
########################////////|///##########///////////////////
################################|#############///////////////////
################################|#############///////////////////
################################|#############///////////////////
################################|#############///////////////////
################################|#############///////////////////
################################|#############///////////////////
################################|#############///////////////////
################################|#############///////////////////
################################|#############///////////////////
-----------------------------------------------------------------
////////////####################|################################
////////////####################|################################
////////////####################|################################
////////////####################|################################
////////////####################|################################
////////////####################|################################
////////////####################|################################
////////////####################|################################
////////////####################|################################
////////////#################///|////////########################
////////////#######/////////////|////////########################
////////////#######/////////////|////////########################
////////////#######/////////////|////////////////################
////////////////////////////////|////////////////################
//////////######////////////////|////////////////################
//////////######////////////////|////////////////################
################////////////////|////////////////######//////////
################////////////////|////////////////######//////////
################////////////////|////////////////////////////////
################////////////////|/////////////#######////////////
########################////////|/////////////#######////////////
########################////////|/////////////#######////////////
########################////////|///#################////////////
################################|####################////////////
################################|####################////////////
################################|####################////////////
################################|####################////////////
################################|####################////////////
################################|####################////////////
################################|####################////////////
################################|####################////////////
################################|####################////////////
-----------------------------------------------------------------
////////////####################|################################
////////////####################|################################
////////////####################|################################
////////////####################|################################
////////////####################|################################
////////////####################|################################
////////////####################|################################
////////////####################|################################
////////////####################|################################
////////////#################///|////////########################
////////////#######/////////////|////////########################
////////////#######/////////////|////////########################
////////////#######/////////////|////////////////################
////////////////////////////////|////////////////################
//////////######////////////////|////////////////################
//////////######////////////////|////////////////################
################////////////////|////////////////######//////////
################////////////////|////////////////######//////////
################////////////////|////////////////////////////////
################////////////////|/////////////#######////////////
########################////////|/////////////#######////////////
########################////////|/////////////#######////////////
########################////////|///#################////////////
################################|####################////////////
################################|####################////////////
################################|####################////////////
################################|####################////////////
################################|####################////////////
################################|####################////////////
################################|####################////////////
################################|####################////////////
################################|####################////////////
-----------------------------------------------------------------
///#############################|################################
///#############################|################################
///#############################|################################
///#############################|################################
///#############################|################################
///#############################|################################
///#############################|################################
///#############################|################################
////////////####################|################################
////////////#################///|////////########################
////////////#######/////////////|////////########################
////////////#######/////////////|////////########################
////////////#######/////////////|////////////////################
////////////////////////////////|////////////////################
//////////######////////////////|////////////////################
//////////######////////////////|////////////////################
################////////////////|////////////////######//////////
################////////////////|////////////////######//////////
################////////////////|////////////////////////////////
################////////////////|/////////////#######////////////
########################////////|/////////////#######////////////
########################////////|/////////////#######////////////
########################////////|///#################////////////
################################|####################////////////
################################|#############################///
################################|#############################///
################################|#############################///
################################|#############################///
################################|#############################///
################################|#############################///
################################|#############################///
################################|#############################///
-----------------------------------------------------------------
fs->buf[0][0]: 00011111111111111111111111111111 ( 536870911 )
fs->buf[0][1]: 11111111111111111111111111111111 ( 4294967295 )
fs->buf[1][0]: 00011111111111111111111111111111 ( 536870911 )
fs->buf[1][1]: 11111111111111111111111111111111 ( 4294967295 )
fs->buf[2][0]: 00011111111111111111111111111111 ( 536870911 )
fs->buf[2][1]: 11111111111111111111111111111111 ( 4294967295 )
fs->buf[3][0]: 00011111111111111111111111111111 ( 536870911 )
fs->buf[3][1]: 11111111111111111111111111111111 ( 4294967295 )
fs->buf[4][0]: 00011111111111111111111111111111 ( 536870911 )
fs->buf[4][1]: 11111111111111111111111111111111 ( 4294967295 )
fs->buf[5][0]: 00011111111111111111111111111111 ( 536870911 )
fs->buf[5][1]: 11111111111111111111111111111111 ( 4294967295 )
fs->buf[6][0]: 00011111111111111111111111111111 ( 536870911 )
fs->buf[6][1]: 11111111111111111111111111111111 ( 4294967295 )
fs->buf[7][0]: 00011111111111111111111111111111 ( 536870911 )
fs->buf[7][1]: 11111111111111111111111111111111 ( 4294967295 )
fs->buf[8][0]: 00000000000011111111111111111111 ( 1048575 )
fs->buf[8][1]: 11111111111111111111111111111111 ( 4294967295 )
fs->buf[9][0]: 00000000000011111111111111111000 ( 1048568 )
fs->buf[9][1]: 00000000111111111111111111111111 ( 16777215 )
fs->buf[10][0]: 00000000000011111110000000000000 ( 1040384 )
fs->buf[10][1]: 00000000111111111111111111111111 ( 16777215 )
fs->buf[11][0]: 00000000000011111110000000000000 ( 1040384 )
fs->buf[11][1]: 00000000111111111111111111111111 ( 16777215 )
fs->buf[12][0]: 00000000000011111110000000000000 ( 1040384 )
fs->buf[12][1]: 00000000000000001111111111111111 ( 65535 )
fs->buf[13][0]: 00000000000000000000000000000000 ( 0 )
fs->buf[13][1]: 00000000000000001111111111111111 ( 65535 )
fs->buf[14][0]: 00000000001111110000000000000000 ( 4128768 )
fs->buf[14][1]: 00000000000000001111111111111111 ( 65535 )
fs->buf[15][0]: 00000000001111110000000000000000 ( 4128768 )
fs->buf[15][1]: 00000000000000001111111111111111 ( 65535 )
fs->buf[16][0]: 11111111111111110000000000000000 ( 4294901760 )
fs->buf[16][1]: 00000000000000001111110000000000 ( 64512 )
fs->buf[17][0]: 11111111111111110000000000000000 ( 4294901760 )
fs->buf[17][1]: 00000000000000001111110000000000 ( 64512 )
fs->buf[18][0]: 11111111111111110000000000000000 ( 4294901760 )
fs->buf[18][1]: 00000000000000000000000000000000 ( 0 )
fs->buf[19][0]: 11111111111111110000000000000000 ( 4294901760 )
fs->buf[19][1]: 00000000000001111111000000000000 ( 520192 )
fs->buf[20][0]: 11111111111111111111111100000000 ( 4294967040 )
fs->buf[20][1]: 00000000000001111111000000000000 ( 520192 )
fs->buf[21][0]: 11111111111111111111111100000000 ( 4294967040 )
fs->buf[21][1]: 00000000000001111111000000000000 ( 520192 )
fs->buf[22][0]: 11111111111111111111111100000000 ( 4294967040 )
fs->buf[22][1]: 00011111111111111111000000000000 ( 536866816 )
fs->buf[23][0]: 11111111111111111111111111111111 ( 4294967295 )
fs->buf[23][1]: 11111111111111111111000000000000 ( 4294963200 )
fs->buf[24][0]: 11111111111111111111111111111111 ( 4294967295 )
fs->buf[24][1]: 11111111111111111111111111111000 ( 4294967288 )
fs->buf[25][0]: 11111111111111111111111111111111 ( 4294967295 )
fs->buf[25][1]: 11111111111111111111111111111000 ( 4294967288 )
fs->buf[26][0]: 11111111111111111111111111111111 ( 4294967295 )
fs->buf[26][1]: 11111111111111111111111111111000 ( 4294967288 )
fs->buf[27][0]: 11111111111111111111111111111111 ( 4294967295 )
fs->buf[27][1]: 11111111111111111111111111111000 ( 4294967288 )
fs->buf[28][0]: 11111111111111111111111111111111 ( 4294967295 )
fs->buf[28][1]: 11111111111111111111111111111000 ( 4294967288 )
fs->buf[29][0]: 11111111111111111111111111111111 ( 4294967295 )
fs->buf[29][1]: 11111111111111111111111111111000 ( 4294967288 )
fs->buf[30][0]: 11111111111111111111111111111111 ( 4294967295 )
fs->buf[30][1]: 11111111111111111111111111111000 ( 4294967288 )
fs->buf[31][0]: 11111111111111111111111111111111 ( 4294967295 )
fs->buf[31][1]: 11111111111111111111111111111000 ( 4294967288 )
_______________________________________________
NetBehaviour mailing list
[email protected]
http://www.netbehaviour.org/mailman/listinfo/netbehaviour
