title: Randomly generate entity on 2D board avoiding collisions
body: <p>I am attempting to make a snake clone, and I wanted the snake to be 5 or so pixels wide, and moves in 1 pixel increments.  This means the snake can be closer than one snake width to itself.  This complicates things when randomly generating food, which will be a 5x5 pixel square.  I need / want an algorithm that reduces the random generation to 5x5 squares that contain no pieces of the snake. </p>
  
  <p>Part of the problem is that, since the food is 5x5, the collision detection has to be checked for each pixel within the food to see if the snake is partially within the food. This leaves me with two problem</p>
  
  <p><strong>Problem</strong></p>
  
  <p><em>How do I reduce the search space when randomly generating the food?</em></p>
  
  <p>I've thought about doing a quad tree, subdividing the space until the divisions are smaller than the food I want to place.  I've also thought about using awt's <code>Rectangle</code>, and figuring out if the food's generated position is contained within a list of the rectangles that makes up the player.</p>
  
  <p>The best solution I can think of is to generate a 2D array, containing all possible rectangles, with their upper left corner as the index values.  Then generate another 2D array that maps each pixel to each rectangle that contains it, or even just starting points, the whole rectangle isn't needed (25 for each).  Then after each move, update the corner maps of the head and tail, marking each of the mapped rectangles that it is occupied.  Then do a simpler random search using the mapped corner array, (this reduces it down to a 1x1 pixel search space).</p>
  
  <p>The main problem I am trying to avoid is that when the snake fills 90% of the playable space, any basic search-fail-repeat system will take a noticeable amount of time to complete, and worst case, never generate a food square.</p>