[jiggy2011]

You can fit at most 60 chat windows on the screen. So surely you can just start at the top left and wrap around every 10 windows? When you get to 60 you can't display any more.

Or is the problem different? For example you already have some arbitrary number of windows already displayed at arbitrary locations that you cannot move?

[btilly]

I would assume that you have an arbitrary number of windows already displayed that you cannot move.

[jiggy2011]

In that case, it's probably most space efficient to place each new window next to an already visible window or at an edge of the screen.

So keep a list of possible candidate positions. Each of these positions represents either an edge of the screen or a position directly above/below/to the left/to the right of an existing window. You will need to calculate different offsets for each of these circumstances to generate candidate positions. You easily eliminate ones that fall outside of the screen.

Each time you attempt to add a window you iterate the list of candidate positions. If a candidate position can fit a window (just use brute force 2D AABB collision detection against all windows, or a quadtree/spatial hash to optimise) then place the window there. If it cannot fit remove the position from the candidate list.

Once you have added the window, calculate all the candidate positions (for each side) and add these to the list of possible positions for later windows.

Well it's late and that's the best I can manage.. I know somebody will point out a flaw here :)

[chacham15]

You know, for people who have taken graphics classes, this seems like a much easier question because they know about AABB trees. That is the problem at the heart of the question. Also, your idea about candidate positions is wasteful. Just invert the tree so that it contains empty space instead of full space. Then, on insert, remove from the tree.

[jiggy2011]

I guess you still need to find empty spaces that would overlap between branches at various levels. Under some circumstances you could end up backtracking around the tree quite a lot to find somewhere to park when you have a lot of nodes with some free space but not enough.

[btilly]

All kinds of problems are easier for people who know how to solve them. :-)

[Evbn]

That is an example of a theoretical solution that may be overkill in practice, especially if you are stuck in JS. Unless you send window positions back to the server for analysis.

And can you code an AABB tree on a whiteboard? :-)

One could try placing the new window at (100x, 200y) for integer x,y, and check for intersection each time with all the existing windows. 3600 overlap tests in the worst case, but you get huge benefits in practice by hinting the location of the last new window.

Optimize a bit by sorting lists of windows by x and y, so you can binary search for the few candidates to overlap test, and you are down to about 1000 window checks. You miss some cases if windows are very maliciously aligned off grid, but you can mitigate that by using a slightly finer grid.

Or test the 8 neighbors (edges and corners) of each existing window (if any), as it is nearly impossible for available space to be not one of those positions.

(You can compute the next window position after the previous window creation or move, so there is no latency when rendering a new window.)