21 May
2010
21 May
'10
12:30 p.m.
Just a quick update. I eventually settled on a 64bit 2D array, with each
64bit element in the array representing 64 spaces in the grid merely for
tracking the state of space being used or unused. Turns out much faster
this way. There will still be a list of blocks (or windows if it was a
window manager) placed but this is an entirely separate issue. For example
in the test code I keep track of the coordinates (returned by the
algorithm) and dimensions of placed blocks in an array.
code/demo here: http://jwm-art.net/boxyseq/freespace_grid.tar.bz2
video/demo here: http://jwm-art.net/art/freespace_grid.ogv
running 'make' in the src, builds a demo/test program which produces
similar output to the video - this is where the good old xterm wins - set
font to 'tiny' and maximize vertically and widen it to atleast 128 chars
and xterm displays fast enough it looks like an animation.
I'm hoping this will work well enough for real-time placement, though the
worst case scenario has changed from just being 255 windows placed, to
something like.... placing a 1x1 block in a non-empty grid full of (any
dimensioned window... it's difficult to work out the worst case here.
james.
On Fri, April 30, 2010 23:10, James Morris wrote:
Hello,
I'm still trying to develop my boxy-sequencer idea. Basically, I've tried
out a couple of algorithms for window-manager-like box placement within a
grid and run into big problems.
Because I need help/advice/ideas, I'm posting here as it has some
relevance, and I've also posted to
http://stackoverflow.com/questions/2746590/fast-block-placement-algorithm-a…
A quick run down of what's happened so far, the two algorithms:
The first I directly based on Fluxbox's Row Smart placement algorithm.
Testing only the data structures, (and with gcc -O0) jack kicked out my
client after around 200 boxes were placed in a 128x128 grid. I then
counted how many times the algorithm looped through the entire list of
boxes and discovered (not in RT for this) that the 256th box placement
required around 14000 scans through the list of 255 previously placed
boxes (i've decided 256 boxes will be the worst-case-scenario).
The second algorithm consists of a freebox data structure which represents
a rectangular area of free unused space. It also forms a node in a doubly
linked list, as well as four directional links to other freeboxes touching
it (with a maximum of one freebox touching each side of a freebox)...
turns out rather complex to implement fully: 700+ loc for a partial
implementation of row-smart left-to-right top-to-bottom placement - theres
also col-smart, r-to-l, b-to-t and all combinations.
Through stackoverflow, I've come across spatial hashing.
I wondered if anyone here uses this technique for the display of data
(would scrollable window views use such a thing?). worth it for a 128x128
grid etc?
I'm just after any general thoughts/insights you might have as to what
might or might not work. Anything worth pursuing.
I'm afraid there's all sorts of little things to be considered so if you
do have something to suggest, please read the stackoverflow post first.
Cheers for any help, if possible,
James.