Caminhante Auto-Evitante (Self-Avoiding Walker)

Um caminhante auto-evitante é uma caminhada aleatória onde a partícula nunca visita a mesma célula duas vezes. É um modelo importante em física estatística, usado para estudar polímeros e outras estruturas.

Algoritmo Principal

O algoritmo funciona assim:

1. Grid: Cria uma grade e marca células visitadas
2. Movimento: A cada passo, escolhe aleatoriamente entre células não visitadas adjacentes
3. Validação: Verifica se a célula já foi visitada antes de mover
4. Parada: Para quando não há mais células válidas para visitar
5. Rastro: Desenha o caminho percorrido

Equações Implementadas

No código:

// Opções de movimento
moveOptions = [
  {x: 1, y: 0},   // Direita
  {x: -1, y: 0},  // Esquerda
  {x: 0, y: 1},   // Baixo
  {x: 0, y: -1}   // Cima
]

// Filtra apenas movimentos válidos (não visitados)
validMoves = moveOptions.filter(move => {
  newX = x + move.x
  newY = y + move.y
  return !grid[newY][newX]  // Não visitado
})

// Escolhe movimento aleatório entre válidos
if (validMoves.length > 0) {
  move = random(validMoves)
  grid[y][x] = true  // Marca como visitado
  x += move.x
  y += move.y
}

Complexidade de Compreensão

Nível: Intermediário

• Conceitos necessários: Caminhada aleatória, grid, validação de movimento
• Matemática: Probabilidade, física estatística, teoria de polímeros
• Programação: Arrays bidimensionais, validação, algoritmos de caminhada

Referências e Recursos para Estudo

Artigos e Documentação

• Wikipedia - Self-Avoiding Walk - Visão geral completa
• MathWorld - Self-Avoiding Walk - Definição matemática
• Scholarpedia - Self-Avoiding Walk - Artigo acadêmico

Tutoriais e Código

• The Coding Train - Random Walker - Tutorial relacionado
• Rosetta Code - Self-Avoiding Walk - Implementações
• Processing Examples - Exemplos práticos

Aprofundamento Matemático

• Introduction to Probability - Blitzstein - Probabilidade
• Polymer Physics - Doi - Física de polímeros

Visualizações Interativas

• Self-Avoiding Walk Explorer - Explorador interativo
• Probability Visualizations - Visualizações