[LAD] update: OT-ish: realtime 2d placement algorithms :-/

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-advice-needed
>
> 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.
>
>
>

_______________________________________________
Linux-audio-dev mailing list
Linux-audio-dev@email-addr-hidden
http://lists.linuxaudio.org/listinfo/linux-audio-dev
Received on Fri May 21 16:15:02 2010