Generowanie ścieżek na siatce n * n

Question

Mam siatkę n*n, gdzie na przykład n=10. Muszę wypełnić go czarno-białymi elementami. Każdy czarny element musi mieć jednego, dwóch lub trzech czarnych sąsiadów. Nie można zawierać czarnych elementów z czterema lub zerowymi sąsiadami.

Jak zbudować ten rodzaj siatki?

Edit:

Aby być bardziej szczegółowe, to tablica dwuwymiarowa zbudowany na przykład z dwóch for pętli:

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

Ten kod pseudo buduje somethind jak:

Oczekuję:

Answer 1

Oczywiście próbujesz wygenerować kształty "czarnej ścieżki" na siatce zapisu.

Po prostu zróbmy to.

• Zacznij od białej siatki.
• Losowo umieść na niej kilka żółwi.
• Następnie, w czasie, gdy sieć nie spełnia odpowiedniej proporcji komórek/czarny biały, wykonaj następujące czynności
  • Przenieś każdy żółw jedną komórkę w losowym kierunku i pomalować go na czarno, chyba że robi tak złamać „nie więcej niż trzy zasada czarnych sąsiadów ".

Answer 2

Z wielkości, aby pokazać tutaj, można łatwo przejść do kawałka brute force realizacji.

Napisz funkcję, która sprawdza, czy spełniasz wymagania, po prostu przez powtarzanie wszystkich komórek i liczenie sąsiadów.

Po tym, zrobić coś takiego:

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. 

Jeśli siatka jest duży (tysiące pikseli), powinieneś zajrzeć do bardziej wydajnego algorytmu, ale na siatce 10x10 zostanie to obliczone błysk.

Answer 3

Może ten kod Pythona może być przydatny. Jego podstawową ideą jest zrobienie pewnego rodzaju szerokości pierwszego przejścia przez siatkę, upewniając się, że poczerniałe piksele respektują ograniczenie, że mają nie więcej niż 3 czarne sąsiady. Wykres odpowiadający poczerniałej części siatki jest drzewem, jak się wydawało, pożądanym rezultatem.

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') 

Oto wynik ustawienie size = 50

i drugi ustawienie size = 1000

Można również grać z korzenia drzewa.