Creating Array of Integers to store spaces in grid Java

Question

I am currently making a program which optimizes the placement of houses on a grid to gain the most profit.

The area plan is on a grid - all house details (dimensions etc) are entered by a user.

All houses must be placed next to a road - the roads have already been added to the grid by the user.

I am currently struggling to write a function which checks if the grid has any available space left to add another house (the stopping condition for my optimization algorithm).

The available space won't be the empty squares on the grid, but the empty squares adjacent to the road. (This road can go both horizontal and vertical)

The grid:

Coords[][] grid;

If a coordinate on the grid is a road:

grid[x][y].getRoad() == true

The following function finds all neighbouring squares of any coordinate: (cols - number of columns in grid) (rows - number of rows in grid)

public static Coords[] addNeighboursSquare(Coords coord, int x, int y, int cols, int rows)
{
   Coords[] neighbours = null;

   //right
   if (x < cols - 1)
   {
      neighbours[0] = AStarAlgorithm.grid[x + 1][y];
   }

   //left
   if (x > 0)
   {
      neighbours[1] = AStarAlgorithm.grid[x - 1][y];
   }

   //top
   if (y < rows - 1)
   {
      neighbours[2] = AStarAlgorithm.grid[x][y + 1];
   }

   //bottom
   if (y > 0)
   {
      neighbours[3] = AStarAlgorithm.grid[x][y - 1];
   }

   return neighbours;
}

How do I loop through all roads squares in the grid, and create an array of ints containing the size of all 'gaps' along the road?

user_13197027 · Answer

Assuming that your function addNeighboursSquare() will return array with coords of neighbours (you have to initialize array neighbours) and you can check if cell is empty (no house there yet) I would start with function that return me a number of gaps around one cell:

(psudocode):

getGapsNumber(x, y):
    gapsNumber := 0
    neighbours := addNeighboursSquare(x,y)
    for neighbour in neighbours:
        if neighbour is empty
            gapsNumber++
    return gapsNumber

Then just iterate through roads coords and call getGapsNumber() for them like:

(psudocode):

totalGapsNumber := 0
for cell in road:
    totalGapsNumber += getGapsNumber(cell.x, cell.y)
return getGapsNumber

If you don't have road coords in one place, loop through whole grid and add if statement, where you check if cell is a road.

(psudocode):

totalGapsNumber := 0
for cell in grid:
    if cell is road:
        totalGapsNumber += getGapsNumber(cell.x, cell.y)
return getGapsNumber

user_13197027 · Answer

How about this:

Iterate through houses and get all coords of neighbours of house vertices that are roads.
Verify number of adjacent coords (2 means that house has road on the one side only, 3 means 2 roads ...)
Iterate through this adjacent roads (check if road is vertical or horizontal)
Go right and left or up and down till next house or road appear. Check if this "houses pair" is already saved, if not save houses pairs to avoid repeating and add distance to gap size array.

Creating Array of Integers to store spaces in grid Java

2 Answers