No lazer, meu filho e eu estudamos eletrônica digital. Recentemente, chegamos ao capítulo sobre máquinas de estados finitos. Este tópico está repleto de tarefas típicas, como um semáforo ou uma máquina de venda automática. Mas todos eles são monótonos e simples demais, e alguns são geralmente francos. Depois de estudar exemplos simples, eu queria fazer algo mais interessante e complexo. O jogo clássico “cobra” chamou minha atenção (meu filho jogou no telefone), e eu sugeri fazê-lo em máquinas de estado. Afinal, o estado do jogo é bastante final (especialmente se você se limitar a um campo pequeno) e, a partir das entradas, existem apenas 4 botões. E é isso que conseguimos.O jogo Snake (ela é uma cobra, python, jibóia, etc.) é amplamente conhecido por todos. Ela vem dos distantes anos 70, mas não vou repetir a história dela, que você pode ler na Wikipedia ou em muitos artigos sobre Habré. O jogo tem regras bastante simples e, ao mesmo tempo, jogabilidade viciante)) Graças a isso, é frequentemente usado para tutoriais ou exemplos de código . Nas linguagens de programação de alto nível, fazer um jogo desses é bastante fácil. Porém, em condições mais limitadas, o mais interessante começa, por exemplo, uma implementação no LabVIEW . Existem também muitas opções no FPGA: link 1 , link 2 , link 3, Link 4 . Mas não houve uma única opção em chips TTL separados das séries padrão. Então é isso que faremos.Parece que as soluções FPGA são as mais próximas de nós, e você pode pedir muito emprestado a partir daí? Mas em todas as opções que eu observei, elas são facilmente espalhadas nos registros esquerdo e direito. Por exemplo, muitas vezes um bit ou número separado é alocado para cada célula de campo. Não podemos fazer isso com pó solto, porque cada novo registro é um microcircuito separado que precisa ser colocado em algum lugar e depois conectado. Portanto, cruzamos toda a experiência acumulada por outros desenvolvedores e faremos tudo do zero. Como bônus, coletaremos tudo sobre os chips domésticos (e melhores - soviéticos) da série k555 / kr1533, com exceção das ROMs, que deverão ser atualizadas.Formulação do problema
Teremos essas restrições: um campo de tamanho 8 × 8 células ( matriz chinesa de LED ), um comprimento de cauda de 8 células. Uma cobra pode atravessar paredes, mas não processaremos a interseção com a cauda no início (para não complicar o design, você pode adicioná-lo mais tarde). Para descrever todo o estado do jogo, precisamos:- Posição da cabeça (X = 0..7, Y = 0..7, 6 bits)
- Direção do movimento (↑ ↓ ← →, 2 bits)
- Posição da Apple (X, Y, 6 bits)
- Comprimento da cauda (0..7, 3 bits)
- A posição das células da cauda (de 0 a 7 pedaços de 6 bits cada)
No total, são obtidos 65 bits, mesmo que registremos 8 bits cada, apenas 8 microcircuitos (e mais um gatilho) são necessários para armazenar o estado, isso é bastante.Mas a cauda não pode ser localizada onde quer que ela "cresça" da cabeça. Portanto, podemos armazenar não as coordenadas completas de cada seção da cauda, mas apenas a direção em que direção da célula anterior (ou cabeça) ela precisa ser desenhada. Então, em vez de 6 × 8 = 48 bits, precisamos de 4 × 8 = 16 bits, e isso economiza até quatro casos de registro!Máquinas automáticas
Vamos tentar fazer tudo em máquinas semelhantes a Moore ou Miles. Para implementar esse autômato, basta ter um pouco de memória de estado (registro) e lógica combinacional para alternar entre eles. Wikipedia
pictureGeralmente, uma máquina de estados é descrita como um gráfico de estados e transições entre eles. Às vezes, é mais conveniente criar uma tabela de transições para um novo estado, o exemplo mais simples (da Wikipedia):
você pode encontrar mais informações e imagens bonitas, por exemplo, neste artigo em HabréPequena digressão, , . , ROM , ROM.
( , ).
, , .
, « » .
Uma cobra de vários estados (se você não levar em consideração a posição da maçã) pode ter 2 ^ 8 + 2 ^ 10 + ... + 2 ^ 24 ≈ 32 milhões. Não é possível escrevê-los na tabela e ainda mais desenhar um gráfico de transição. Mas a maioria das transições é a mesma (a cabeça move apenas uma célula adjacente e a cauda move uma seção por turno). Nesse caso, não podemos descrever cada estado individual, mas formular um novo estado em função do estado anterior. Além disso, podemos dividir o jogo inteiro em vários autômatos paralelos: 1) uma máquina automática de direção, 2) uma máquina automática de posição da cabeça, 3) uma máquina automática para a cauda. E para definir cada um deles como será mais conveniente:1) , │
────────────────────┼───────────────────
← ←/↓/↑ │ ←
← → │ →
↑ ↑/←/→ │ ↑
↑ ↓ │ ↓
...... │
2) , │
─────────────────────┼──────────────
← (x,y) │ (x-1, y)
→ (x,y) │ (x+1, y)
↑ (x,y) │ (x, y-1)
↓ (x,y) │ (x, y+1)
3) , │
─────────────────────────────────────────┼──────────────────────────
← (t1,t2,t3,t4,t5,t6,t7,t8) │ (←,t1,t2,t3,t4,t5,t6,t7)
...... │
Direção
Vamos começar com a máquina direcional. Se você pensar com cuidado, poderá montá-lo em uma lógica separada. Mas, como a tarefa como um todo já é bastante grande, decidi que seria mais fácil criar uma tabela de pesquisa da EEPROM e escrever a tabela de transição manualmente. Ele terá 6 entradas, o que significa apenas 64 valores, que podemos simplesmente inserir no editor hexadecimal.
Cabeça
Para uma máquina de posição da cabeça, escrever uma mesa assim será muito mais difícil. Mas contém essencialmente apenas 2 operações: +1 e -1. Eles podem ser implementados em um somador K155IM6 de 4 bits. Para +1, adicionaremos nossa coordenada com b'0001 e para -1 com b'1111 (que na verdade é -1 no código adicional ). Vamos precisar de dois somadores (para xey), um pouco de lógica, e armazenaremos o estado no registro de 8 bits IR27 (ainda precisamos de muitos):
Vamos montá-lo na placa e, para verificação, conectaremos imediatamente a matriz de LEDs com dois decodificadores. O decodificador com saídas inversas é ID7 e, para o direto, seria possível usar o K561ID1 (CD4028), mas eu não o tinha à mão. Outra opção é levar 8 transistores como chaves, mas eu não queria fazer isso, então tive que gastar estupidamente outra EEPROM (escrevendo apenas 8 células lá). A lógica da nova posição da cabeça em uma placa separada no topo Outra digressão
Vamos fazer uma pequena pausa e salvar a tábua de pão (e alguns estojos de chips). Voltaremos a aproveitar o fato de que qualquer circuito combinado pode ser substituído por um LUT, escrevendo a tabela na ROM. Mas como fazer isso para uma mesa tão grande? Vamos usar outro truque - faremos o oposto: substitua a EEPROM pelo nosso circuito lógico e coloque-o no programador. As pernas não utilizadas são conectadas ao solo através de resistores. (Isso não poderia ser feito se você se aprofundar nas configurações do programador)
Agora, leremos nosso diagrama lógico como ROM e obteremos uma tabela. Nós o escrevemos com o mesmo programador em uma EEPROM real, que colocamos em vez de um circuito de elementos separados.
Rabo
A cauda tem um comprimento (em nossas limitações) de 2 a 8 células. Para armazenar esse comprimento, você pode usar um contador convencional com uma entrada de resolução de conta. De fato, será a mesma máquina de estados finitos, na qual o novo estado S 'será igual a S + 1 ou apenas S (se a conta for proibida). A própria cauda (ou melhor, a direção em que cresce), armazenaremos em dois registros de 8 bits. Teoricamente, era possível fazer registros de turno prontos (por exemplo, IR8), mas eles não estavam disponíveis, então o mesmo IR27 foi usado. A cada passo, a direção atual do movimento da cabeça é escrita no primeiro bit do registro e o valor do anterior no segundo e no próximo. Para obter a direção do crescimento da cauda, basta inverter um pouco. Você pode fazer isso imediatamente ao gravar, mas decidi que era melhor deixar o inverso para o circuito restante.Esquema
No total, nossa máquina do próximo passo assume esta forma: Esta imagem (como todos os outros) é clicável. Essa é uma parte bastante "pura" (do ponto de vista teórico) do esquema. Exemplo quase perfeito para máquinas Moore codificadas de saída . U1 é responsável pela nova direção, U2 pela posição da cabeça, que é armazenada em U5. U3 e U4 são usados para a cauda e seu comprimento é armazenado (e aumentado) em U6. Em seguida, precisaremos exibir tudo o que temos na tela e também haverá uma espaçonave, apenas de forma mais suja. Além de um gerador de números aleatórios primitivo, uma transição entre circuitos com um sinal de relógio diferente e outros hacks.
Subtotal
Espero que este artigo tenha lhe interessado e tentarei terminar rapidamente a segunda parte.E se você já está envolvido na batalha, abastecido com placas de ensaio, microcircuitos e telas de pontos, um arquivo com o circuito ROM e o firmware é anexado a este artigo. Mini-spoiler: para repetir o design, serão necessários cerca de 6 protótipos, 4 EEPROM 28C16 e um pouco mais de duas dúzias de outros chips.Bem, como deve ser: curtir, compartilhar, retwittar, inscrever-se, pressionar a campainha, etc. ...)) E por hoje tudo, obrigado pela atenção! Continua…
Arquive com firmware ROM e o esquemaUPD geral : a segunda parte está disponível aqui .