CODEWITHSUNDEEP
algorithmmultidimensional-array
hsz
hsz

Reputation: 152206

Generate paths on n*n grid

I have n*n grid, where for example n=10. I have to fill it with black and white elements. Every black element has to have one, two or three black neighbors. It is not allowed to contain black elements with four or zero neighbors.

How should I build this kind of grid ?

Edit:

To be more specific, it is two-dimensional array built for example with two for loops:

n = 10
array = [][];
for ( x = 0; x < n; x++ ) {
    for ( y = 0; y < n; y++ ) {
        array[x][y] = rand(black/white)
    }
}

This pseudo code builds somethind like:

current

And what I expect is:

expected

Upvotes: 8

Views: 1579

Answers (3)

Vincent Nivoliers
Vincent Nivoliers

Reputation: 468

Maybe this python code could be of some use. Its basic idea is to do some sort of breadth first traversal of the grid, ensuring that the blackened pixels respect the constraint that they have no more than 3 black neighbours. The graph corresponding to the blackened part of the grid is a tree, as your desired result seemed to be.

import Queue
import Image
import numpy as np
import random

#size of the problem
size = 50

#grid initialization
grid = np.zeros((size,size),dtype=np.uint8)

#start at the center
initpos = (size/2,size/2)

#create the propagation queue
qu = Queue.Queue()

#queue the starting point
qu.put((initpos,initpos))

#the starting point is queued
grid[initpos] = 1


#get the neighbouring grid cells from a position
def get_neighbours(pos):
  n1 = (pos[0]+1,pos[1]  )
  n2 = (pos[0]  ,pos[1]+1)
  n3 = (pos[0]-1,pos[1]  )
  n4 = (pos[0]  ,pos[1]-1)
  return [neigh for neigh in [n1,n2,n3,n4] 
                  if neigh[0] > -1 and \
                     neigh[0]<size and \
                     neigh[1] > -1 and \
                     neigh[1]<size \
         ]


while(not qu.empty()):
  #pop a new element from the queue
  #pos is its position in the grid
  #parent is the position of the cell which propagated this one
  (pos,parent) = qu.get()

  #get the neighbouring cells
  neighbours = get_neighbours(pos)

  #legend for grid values
  #0 -> nothing
  #1 -> stacked
  #2 -> black
  #3 -> white

  #if any neighbouring cell is black, we could join two branches
  has_black = False
  for neigh in neighbours:
    if neigh != parent and grid[neigh] == 2:
      has_black = True
      break

  if has_black:
    #blackening this cell means joining branches, abort
    grid[pos] = 3
  else:
    #this cell does not join branches, blacken it
    grid[pos] = 2

    #select all valid neighbours for propagation
    propag_candidates = [n for n in neighbours if n != parent and grid[n] == 0]
    #shuffle to avoid deterministic patterns
    random.shuffle(propag_candidates)
    #propagate the first two neighbours
    for neigh in propag_candidates[:2]:
      #queue the neighbour
      qu.put((neigh,pos))
      #mark it as queued
      grid[neigh] = 1

#render image
np.putmask(grid,grid!=2,255)
np.putmask(grid,grid<255,0)
im = Image.fromarray(grid)
im.save('data.png')

Here is a result setting size = 50

black tree over grid, width 50

and another one setting size = 1000

black tree over grid, width 1000

You can also play with the root of the tree.

Upvotes: 2

Wouter van Nifterick
Wouter van Nifterick

Reputation: 24086

With the size that you show here, you could easily go for a bit of a brute force implementation.

Write a function that checks if you meet the requirements, simply by iterating through all cells and counting neighbors.

After that, do something like this:

Start out with a white grid.
Then repeatedly:
    pick a random cell
    If the cell is white:
        make it black
        call the grid checking routine.
        if the grid became invalid:
            color it gray to make sure you don't try this one again

do this until you think it took long enough, or there are no more white cells.
then make all gray cells white.

If your grid is large (thousands of pixels), you should probably look for a more efficient algorithm, but for a 10x10 grid this will be calculated in a flash.

Upvotes: 1

Nicolas Repiquet
Nicolas Repiquet

Reputation: 9255

Obviously, you're trying to generate "black path" shapes on a write grid.

So let's just do it.

  • Start with a white grid.
  • Randomly position some turtles on it.
  • Then, while your grid doesn't meet a proper white/black cell ratio, do the following
    • Move each turtle one cell in a random direction and paint it black unless doing so break the "no more than three black neighbors" rule.

Upvotes: 5

Related Questions