Ricerca di possibili posizioni per il rettangolo in una matrice 2-d

Question

Ricerca di possibili posizioni per il rettangolo in una matrice 2-d

#1 da (2 voti)

1

Bene, il titolo non è molto appropriato, per favore continua a leggere (non potrei averne uno migliore)

Nota: utilizzo di Python 2.7, ma sarà utile anche un algoritmo.

Sto facendo un gioco a scorrimento laterale, in cui sto generando gli ostacoli al volo. Il problema che sto avendo è capire come generare gli ostacoli. o_O
Ho una specie di logica, ma poi ho problemi a capire l'intera logica.

Quindi ecco il mio problema da una prospettiva di implementazione:
Ho un Surface , in cui ho messo un po 'di Element s, che sono tutti rettangoli.
Pensala come:

0 0 0 0 0 0 0
0 0 0 0 1 1 0
0 0 0 0 1 1 0
0 0 0 0 1 1 0
0 0 0 0 0 0 0
0 1 1 0 0 1 1
0 0 0 0 0 1 1

Come nella struttura sopra, come posso determinare se un rettangolo axb può essere aggiunto senza sovrapporre un altro rettangolo (di 1 secondo) e dove tutto. Inoltre, con il mantenimento di una distanza di x elementi (anche diagonalmente) da tutti gli altri oggetti, significa che l'intero rettangolo è (x + 3, x + 4). Qualcosa come se x=1, a=3, b=4 , c'è solo un possibile accordo:
(2s rappresenta il nuovo oggetto)

2 2 2 0 0 0 0
2 2 2 0 1 1 0
2 2 2 0 1 1 0
2 2 2 0 1 1 0
0 0 0 0 0 0 0
0 1 1 0 0 1 1
0 0 0 0 0 1 1

Fondamentalmente, ho bisogno di trovare tutti i punti, da cui un rettangolo di lati a e b può avere, per esempio, un angolo in alto a sinistra. Come si può ottenere?

Nota: apri a idee migliori per generare gli ostacoli al volo!

PS: non sono chiaro?

game-development python logic

posta pradyunsg 28.07.2013 - 09:00

fonte

1 risposta

Leggi altre domande sui tag game-development python logic

pre aggregazione di documenti mongodb Determinazione degli aggregati in questo dominio

score 2 · Answer 1

Quanto segue dovrebbe funzionare abbastanza bene:

def find_valid_locations(grid, z, a, b):
    seen = set()
    check = [(0, 0, 0, 0)]
    w = z + b
    h = z + a
    while check:
        x, y, ox, oy = check.pop()
        if (x, y) in seen:
            continue
        seen.add((x, y))
        if x + w >= len(grid) or y + h >= len(grid[0]):
            continue
        for i, row in enumerate(grid[x+ox:x+w+1], x+ox):
            for j, val in enumerate(row[y+oy:y+h+1], y+oy):
                if val:
                    break
            else:
                continue
            check.extend([(i+1, y, 0, 0), (x, j+1, 0, 0)])
            break
        else:
            yield (x, y)
            check.extend([(x+1, y, w-1, 0), (x, y+1, 0, h-1)])
            continue

Il metodo forza bruta qui sarebbe quello di controllare tutte le posizioni in ogni potenziale posizione del rettangolo e restituire solo posizioni in cui la rectange non ha incontrato una posizione diversa da zero. Questo è essenzialmente ciò che facciamo qui, con le seguenti ottimizzazioni:

Se abbiamo trovato una posizione valida (x, y), possiamo controllare facilmente le posizioni (x + 1, y) e (x, y + 1), semplicemente controllando le nuove posizioni aggiunte al rettangolo spostandolo in basso oa destra.
Se incontriamo un ostacolo in posizione (i, j) mentre controlliamo la posizione (x, y), possiamo saltare il controllo di qualsiasi altra posizione che include (i, j) iniziando i nostri prossimi controlli a (i + 1, y ) e (x, j + 1).

Nota che ho rinominato il parametro x in z in modo che potrei usare x come indice di riga nel codice.