Labirintos

Para brincar um pouco mais com Red, decidi criar um programinha para gerar labirintos. Por enquanto é só isso, não é um jogo ou coisa parecida.
editado: já é possível movimentar o personagem até a saída.

Ok. Achei alguns algoritmos e resolvi implementar três. Primeiro foi o Recursive Backtracking que por ser recursivo pode gerar estouro de pilha. O segundo foi o Binary Tree algorithm que pode gerar labirintos grandes sem se preocupar muito com a memória. O terceiro foi o Sidewinder algorithm que também não é recursivo mas se consegue alguns padrões interessantes alterando apenas uma variável.

Recursive backtracker
Binary tree
Sidewinder com peso 2
Sidewinder com peso 20

Os algoritmos foram convertidos de Ruby para Red com relativa facilidade (um pouco por estar meio desacostumado com Ruby e outro por não estar bem familiarizado com Red). Como incluí três algoritmos no mesmo contexto, em vez de carve_passages_from nomeei a função com o nome do algoritmo, no caso. recursive-backtracker

Ruby

N, S, E, W = 1, 2, 4, 8
DX         = { E => 1, W => -1, N =>  0, S => 0 }
DY         = { E => 0, W =>  0, N => -1, S => 1 }
OPPOSITE   = { E => W, W =>  E, N =>  S, S => N }

def carve_passages_from(cx, cy, grid)
  directions = [N, S, E, W].sort_by{rand}
  directions.each do |direction|
    nx, ny = cx + DX[direction], cy + DY[direction]
    if ny.between?(0, grid.length-1) && nx.between?(0, grid[ny].length-1) && grid[ny][nx] == 0
      grid[cy][cx] |= direction
      grid[ny][nx] |= OPPOSITE[direction]
      carve_passages_from(nx, ny, grid)
    end
  end
end

carve_passages_from(0, 0, grid)

Red

set [N S E W] [1 2 4 8]
DX:       #(E: 1 W: -1 N:  0 S: 0)
DY:       #(E: 0 W:  0 N: -1 S: 1)
OPPOSITE: #(E: 8 W:  4 N:  2 S: 1)

recursive-backtracker: func[cx cy /local nx ny directions][
    directions: random copy [n s e w]
    foreach direction directions [
        nx: cx + DX/:direction
        ny: cy + DY/:direction
        if all [(ny >= 1) (ny = 1) (nx <= width) (grid/:ny/:nx = 0)][
            grid/:cy/:cx: grid/:cy/:cx or get direction
            grid/:ny/:nx: grid/:ny/:nx or OPPOSITE/:direction
            recursive-backtracker nx ny
        ]
    ]
]

recursive-backtracker 1 1 

Tirando os detalhes da linguagem, ficou quase um por um. Algumas obervações:

  • Como blocos etc iniciam com um (1), não foi necessário incluir coisas como length-1. YMMV mas eu sempre achei que arrays e outras estruturas deveriam iniciar em 1 e não zero. Fora facilitar para a CPU, não acho natural pegar o item zero de uma lista de 10 elementos nem o nono elemento elemento (10-1) da lista para pegar o 10. Respeito se você acha o contrário, mas você está errado. 😀
  • Poderia ter feito as atribuições de nx e ny na mesma linha utilizando set [nx ny] reduce [cx + DX/:direction cy + DY/:direction]. Como Red é uma linguagem homoicônica, sem reduce nx ficara com o valor cx e ny com +.
  • Red não tem between?. Como significa apenas (n >= min) && (n <= max), basta utilizar all que retorna verdadeiro se todas as comparações resultarem verdadeiro (nem precisaria os parêntesis colocados acima e ficaria como all [(ny >= 1) (ny <= height) (nx >= 1) (nx <= width) (grid/:ny/:nx = 0)]).

As rotinas para o desenho dos labirintos ficam para uma outra vez.

Os fontes podem ser encontrados no Github.

Feliz novamente. :D

Meu primeiro contato com programação me deixou bastante feliz. Era BASIC e super fácil de fazer alguma coisa. Meu primeiro programa verificava se o usuário havia pressionado algo com inkey$ e movimentava um quadrado com print at l,c. Me senti um deus comandando a máquina. Com o próprio manual do computador aprendi o Assembly do […]

ZSH – Arquivo mais antigo

Basta seguir o que foi dito no post anterior mas trocando o o minúsculo por um maiúsculo O (sort order down). O arquivo mais antigo de um diretório é dado por:

print *(.Om[1])

De qualquer forma, o m (modification time) pode ser seguido de alguns parâmetros. Pode ser s (seconds), m (minutes), h (hours), d (days), w (weeks), M (months), (before), + (since).

Para um retorno de arquivos com mais de 30 dias usamos *(.md+30) e para arquivos com menos de 2 semanas usamos *(.mw-2). Para remover todos os arquivos com menos de 2 horas é possível fazer:

rm -f *(.mh-2)

ZSH – Arquivo mais recente

Basta utilizar o (sort order up), m (modification time) e [] (range os files) para retornar o primeiro arquivo. Para assegurar que não retornem diretórios utilizamos o (ponto) . (plain files). Para retornar o arquivo mais recente, o resultado seria:

ls *(.om[1])

Para editar o arquivo texto mais recente podemos utilizar:

nano *.txt(.om[1])

Você também pode excluir os 5 arquivos mais recentes utilizando:

rm *(.om[1,5])

O resto fica por conta da sua imaginação.