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.
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.
