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.
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
Problem
How do I reduce the search space when randomly generating the food?
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 Rectangle, and figuring out if the food's generated position is contained within a list of the rectangles that makes up the player.
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).
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.
After 7 months I have a solution. I have not tested this yet, because I still have to implement it.
The way I'm handling the snake body is by a list of rectangles defined by the top left X,Y coordinate, width, and height.
What I can do is create a tree of degree 8 starting with the whole board, and then place each snake part into the tree, with the top left corner offset by the size of the apple. When a part is placed, I can then split the board into 9 sections based on the 4 corners, 4 edges, and center of the snake. Ignoring board parts containing the snake, and board parts with dimensions <= 0, I can place these into the tree.
Since the snake parts were already adjusted for the apple size, any point within a non-occupied leaf node can be used to place an apple