   Icon Placement / Circle Packing
  I am writing a strategy game at the moment and came across an interesting problem which I've since been pondering about.In the game groups of units occupy no area; they are represented as the 'average' point of unit locations and as such two groups of units can have the same central point. An analogy of this is two hoops of different sizes arranged so that one sits exactly in the center of the other. The two hoops therefore have the same position, albeit a different radius.This is exactly how the game world functions, the problem is not in how these units are internally arranged, but how the icons the player sees which represent the units should be.Continuing the analogy of the hoops. If the hoop is the group of units then a solid circle or disk is the icon on the screen. If two units have the same central point then the icons' desired positions must be on top of each other which is undesirable as one will be obscured.In a real world situation the two disks would sit side-by-side so that the point at which the two disks touch is the desired location for both of them. The sum of their displacement from their desired position is equal to the diameter of the icon (all icons are the same size). This is the perfect solution for two icons and is easily implemented, but how do I describe the location of any subsequent icons which share the same desired location and any which might overlap, but do not necessarily share the same point? The ideal solution is one in which the sum of the distances each icon is away from its desired location is as small as possible.I have attempted two solutions so far:1. Place each icon at its desired location, regardless of overlaps.While at least one icon moved last loop    For each icon find any icons which overlap it.   Calculate the sum of the change in X and change in Y from this icon to the icons which overlap it   Move the icon one unit on the inverse of the vector produced by the change in x, change in Y calculated above    End ForEnd WhileProblem: This doesn't work at all if two or more icons share the same initial location as there is no resultant vector for one of the icons to move at unless there is another icon which overlaps it, but does not have the same location.2.Using a similar approach to above in that if two icons share the same location use the last different position of the unit as the center of the icon rather than the unit's current location. This solves the problem most of the time, but can be caught in an infinite loop if certain conditions are met. This solution seems a bit 'hacky' and isn't elegant or logically sound.So here is a logic challenge if you wish to accept it:Produce an algorithm which given infinite disks can arrange them in a manner which ensures the smallest possible sum of the displacements from desired positions whilst no disks overlap.Thanks to anyone who took the time to read this and replies.   
  Would it be fair to express your problem as solving the following optimization problem?argmin    [ ||x1-p1||^2 + ||x2-p2||^2 + ... ||xN-pN||^2 ]  x1,x2,...,xN   s.t.||xi - xj||^2 >= (Ri+Rj)^2  for all i,j in {1,...,N};  That looks about right if it means what I think it does. Forgive me, but I haven't come across the notation before (I know I should have done). How would this be implemented algorithmically?As far as I can tell whilst solving this problem if there are only two icons with the same central point there is no information about the icons which should indicate the direction or exact location that each icon should move to attain the minimum distance. Analogy: If two billiard balls are arranged one exactly on top of the other so perfectly that the arrangement balances then there is no way of calculating or 'non-randomly' picking a direction that each ball should move/roll off to find the positions. This also extends to infinite balls.Sorry if analogies annoy some people. I find they help me solve problems like this.I continue to ponder solutions to this, but if anyone has any ideas, even if it isn't a full solution and is just a point in a possible direction please post it here.Thanks   ;  you could have the icons float in the center of your group. if two groups overlap, so that their centers are identical, the icons would have to "fight" for the spot. this could be done by using an avoidance/collision system seen in flocking algorithms. icons would follow the groups center, the position would never be exact, but close enough. this would prevent the icons from jumping to a different spot suddently, just because the algorithm said so. just the first thing that came to mind ;)   ;  I understand what you mean and I agree it is a solution, could you provide a reference to a flocking algorithm or a collision reaction algorithm which would handle two circles having exactly the same location? I have seen this done before in games, but in a different context to this and there was no way to be sure that the objects had the same central point.An undesired effect of using your method (I think) would be that the icon would not always be as close as possible to the unit it represented. Here comes the analogy:When you use satellite navigation your car is represented on the map as close to your location as can be calculated, but when you drive through a tunnel (negating any projected position calculation) the representative on the map cannot go through the tunnel (the signal was lost so it just stays at the entrance), but upon exiting the tunnel the representative snaps to your new position. This relates to what would happen if there were a block of icons on the screen and the unit passed through the field of icons. As the icon representing the moving unit hit the edge of the field it would be blocked and would only move when the unit exited the field and the icon could be 'snapped' back onto its exact location as opposed to the icon switching to the other side as the unit passed the center of the field or better still the icon pushing its way through the field of icons.If I misunderstand how your suggestion would work please correct me.   ;Quote:Original post by EmergentWould it be fair to express your problem as solving the following optimization problem?argmin    [ ||x1-p1||^2 + ||x2-p2||^2 + ... ||xN-pN||^2 ]  x1,x2,...,xN   s.t.||xi - xj||^2 >= (Ri+Rj)^2  for all i,j in {1,...,N}Quote:Original post by HoodedOne:That looks about right if it means what I think it does. Forgive me, but I haven't come across the notation before (I know I should have done). How would this be implemented algorithmically?It means this:1 - You have a bunch of vectors x1,x2,...,xN that you can choose.2 - You're only allowed to choose them in such a way that satisfies the inequalities that I wrote after the "s.t." (which stands for "such that")3 - Subject to the constraint #2, you want to choose x1,x2,...,xN so that the function f(x1,...,xN), which we definef(x1,...,xN) = ||x1-p1||^2 + ||x2-p2||^2 + ... ||xN-pN||^2 ,is as small as possible.4 - I say "argmin" instead of "min" because you don't care about what value f(x1,...,xN) takes when it is as small as possible per-se --- that's what 'min' returns --- but rather what arguments x1,...,xN made it as small as possible --- and that's what "argmin" returns.  An example: min  (1 - x)^2 + 3   =   3  xbut argmin  (1 - x)^2 + 3   =   1 .   x5 - The basic notation I used is how people express constrained minimization problems.   ;  That is indeed what I thought it meant, but the explanation made it a lot clearer. ThanksSo how do people go about solving this sort of minimisation problem?   ;  How about just stacking the icons, people can see there are multiple icons available from that.Mouse-over causes the stack to explode; it could simply become a horizontal line.Or you could explode the stacked icons into a ring around the pointer. This minimises the movement necessary to click one them. If the pointer passes outside the ring, re-coalesce the icons into the stack.In order to ensure a consistent ordering for the icons, you could number the unit types (1=tanks, 2=infantry etc) and number each unit. Sort them by type first, then their individual serial number. This way the unit's icons will always stack to consistent places in the ring/line.In order to actually stack them, you now have a sequence for the icons, so they can just be drawn in a line extending up-and-right from the centre point slightly offsetting each one from the previous.;  What about this:for each unit  1) place unit at it's logical location, if there is no collision with an already placed & locked unit, if not...  2) if there is a collision, move in the direction of the units centre difference from that of the colliding unit's centre. (circle/circle collision, move so edges of discs touch)  3) if there is a collision AND the units have the same centre, move in an arbitrary, or randomly selected selected diretion.  4) Unit is now "placed and locked" and cannot be moved;Quote:Original post by HoodedOneThat is indeed what I thought it meant, but the explanation made it a lot clearer. ThanksSo how do people go about solving this sort of minimisation problem?That's what I was thinking about...For those cases when the problem can be solved analytically, people usually use the method of Lagrange multipliers.  These also appear in various algorithms.In terms of algorithms...If your cost and your constraints are all convex, then there are various convex optimization algorithms (most are basically variants of Newton's method) that guarantee convergence to a global optimum, and they're quite fast.  One method is the (Newton-) logarithmic barrier method; another is the "central path method..." Here, I should just refer you to Stephen Boyd's Convex Optimization Book which is available for free online as a PDF; it's very good.  There are some special cases for when your costs and constraints are all linear (these problems are called "linear programs"), or you have a quadratic cost and linear constraints ("quadratic program") which can be solved even faster than general convex problems.Unfortunately for you, it looks like your problem isn't convex, so you're stuck with a general-purpose optimization algorithm, I think, unless your problem has some geometric structure we haven't noticed that can be exploited...There are local optimizers and global optimizers.  Some require first derivatives, some require second derivatives, and some no derivatives at all.  And the fact is, the ad-hoc stuff people propose here will probably be competitive with some of these.--Local optimization---Gradient-free methods: Nelder-Mead simplex algorithmThe first-derivative based methods: Gradient descent, conjugate gradient descent, quasi-Newton methods (e.g., BFGS)Second-derivative based methods: Newton's method.--Global optimization---Brute force grid search.Stochastic hill-climbing (either gradient-based or gradient-free)Simulated annealingParticle Swarm OptimizationGenetic AlgorithmsBasically any combination of any of these, or variant on them, is also in use!   