title: Clustering 2d integer coordinates into sets of at most N points
body: <p>I have a number of points on a relatively small 2-dimensional grid, which wraps around in both dimensions. The coordinates can only be integers. I need to divide them into sets of at most N points that are close together, where N will be quite a small cut-off, I suspect 10 at most.</p>
  
  <p>I'm designing an AI for a game, and I'm 99% certain using minimax on all the game pieces will give me a usable lookahead of about 1 move, if that. However distant game pieces should be unable to affect each other until we're looking ahead by a large number of moves, so I want to partition the game into a number of sub-games of N pieces at a time. However, I need to ensure I select a reasonable N pieces at a time, i.e. ones that are close together.</p>
  
  <p>I don't care whether outliers are left on their own or lumped in with their least-distant cluster. Breaking up natural clusters larger than N is inevitable, and only needs to be sort-of reasonable. Because this is used in a game AI with limited response time, I'm looking for as fast an algorithm as possible, and willing to trade off accuracy for performance.</p>
  
  <p>Does anyone have any suggestions for algorithms to look at adapting? K-means and relatives don't seem appropriate, as I don't know how many clusters I want to find but I have a bound on how large clusters I want. I've seen some evidence that approximating a solution by snapping points to a grid can help some clustering algorithms, so I'm hoping the integer coordinates makes the problem easier. Hierarchical distance-based clustering will be easy to adapt to the wrap-around coordinates, as I just plug in a different distance function, and also relatively easy to cap the size of the clusters. Are there any other ideas I should be looking at?</p>
  
  <p>I'm more interested in algorithms than libraries, though libraries with good documentation of how they work would be welcome.</p>
  
  <p><strong>EDIT</strong>: I originally asked this question when I was working on an entry for the <a href="http://ants.aichallenge.org/problem_description.php" rel="nofollow">Fall 2011 AI Challenge</a>, which I sadly never got finished. The page I linked to has a reasonably short reasonably high-level description of the game.</p>
  
  <p>The two key points are:</p>
  
  <ol>
  <li>Each player has a potentially large number of ants</li>
  <li>Every ant is given orders every turn, moving 1 square either north, south, east or west; this means the branching factor of the game is O(4<sup>ants</sup>).</li>
  </ol>
  
  <p>In the contest there were also strict time constraints on each bot's turn. I had thought to approach the game by using minimax (the turns are really simultaneous, but as a heuristic I thought it would be okay), but I feared there wouldn't be time to look ahead very many moves if I considered the whole game at once. But as each ant moves only one square each turn, two ants cannot N spaces apart by the shortest route possibly interfere with one another until we're looking ahead N/2 moves.</p>
  
  <p>So the solution I was searching for was a good way to pick smaller groups of ants at a time and minimax each group separately. I had hoped this would allow me to search deeper into the move-tree without losing much accuracy. But obviously there's no point using a very expensive clustering algorithm as a time-saving heuristic!</p>
  
  <p>I'm still interested in the answer to this question, though more in what I can learn from the techniques than for this particular contest, since it's over! Thanks for all the answers so far.</p>