Animando o 8-puzzle (§5.2) usando gráficos de personagens

De Augusto Baffa Wiki
Ir para navegação Ir para pesquisar

Combinamos as seções 5.1 e 5.2 para produzir um solucionador para o 8-puzzle que gera soluções da forma [esquerda, para cima, ...] - isto é, listas de movimentos indicando em qual direção da peça vazio (espaço) deve ser movida. Esta seção mostra como "reproduzir" essa solução para animar graficamente a solução real. Para isso, usamos gráficos de caracteres no estilo VT100. Este programa deve funcionar para Quintus ou SWI Prolog (e muitos outros) sendo executado em uma sessão VT100 ou janela XTERM. Claro, um animador semelhante pode ser (e tem sido) desenvolvido usando gráficos X-Windows.


Independentemente do sistema gráfico específico, o método de representação de "dados" gráficos subjacentes e a representação de "ações" nos dados gráficos podem ser exemplificados com força usando programas Prolog simples, ou protótipos. Na programação orientada a objetos, os conceitos correspondentes são normalmente caracterizados como objetos (cujas variáveis de instância contêm valores para os dados gráficos), e os objetos são influenciados e alterados pelos métodos (ou funções) da classe.


Para a implementação do Prolog, usamos 'assert' e 'retract' para afetar ou alterar os dados básicos que representam o quebra-cabeça. (Isso é semelhante ao ponto de vista obtido na seção anterior 8.1, e na seção 2.19.) Para um quebra-cabeça inicial, as posições das peças são declaradas. Ações que movem as peças (esquerda, direita, para cima, para baixo) retraem as posições antigas das peças e afirmam novas posições apropriadas. O autor usou a experimentação para determinar o que parecia ser um efeito razoável dos movimentos gráficos. 

   %%% For Quintus Prolog
:- dynamic location/3.   %%% So that location of a tile 
                         %%%  can be retracted/asserted.
                         %%% Location(s) asserted and retracted
                         %%%  by puzzle animator 

initialize(A/B/C/D/E/F/H/I/J) :-
  cls,
  retractall(location(_,_,_)),    
  assert(location(A,20,5)),  
  assert(location(B,30,5)),  
  assert(location(C,40,5)),  
  assert(location(F,40,10)), 
  assert(location(J,40,15)), 
  assert(location(I,30,15)), 
  assert(location(H,20,15)), 
  assert(location(D,20,10)),
  assert(location(E,30,10)), draw_all. 

   %%% move empty tile (space) to the left
left :- retract(location(0,X0,Y0)),
        Xnew is X0 - 10,
        location(Tile,Xnew,Y0),
        assert(location(0,Xnew,Y0)),
        right(Tile),right(Tile),right(Tile),
        right(Tile),right(Tile),
        right(Tile),right(Tile),right(Tile),
        right(Tile),right(Tile).

up :- retract(location(0,X0,Y0)),
      Ynew is Y0 - 5,
      location(Tile,X0,Ynew),
      assert(location(0,X0,Ynew)),
      down(Tile),down(Tile),down(Tile),down(Tile),down(Tile).

right :- retract(location(0,X0,Y0)),
         Xnew is X0 + 10,
         location(Tile,Xnew,Y0),
         assert(location(0,Xnew,Y0)),
         left(Tile),left(Tile),left(Tile),left(Tile),left(Tile),
         left(Tile),left(Tile),left(Tile),left(Tile),left(Tile).

down :- retract(location(0,X0,Y0)),
        Ynew is Y0 + 5,
        location(Tile,X0,Ynew),
        assert(location(0,X0,Ynew)),
        up(Tile),up(Tile),up(Tile),up(Tile),up(Tile).

Nenhuma dessas cláusulas realmente desenha nada na tela. Para fazer isso, precisamos do seguinte ... 

   %%% Position the cursor at (X,Y) on the screen
   %%% X from left, Y from top
cursor(X,Y) :- put(27), put(91), %%% ESC [
               write(Y),
               put(59),          %%%   ;
               write(X),
               put(72).          %%%   M

   %%% clear the screen, quickly
cls :-  put(27), put("["), put("2"), put("J").

   %%% video attributes 
plain         :- put(27), put("["), put("0"), put("m").
reverse_video :- put(27), put("["), put("7"), put("m").

Para desenhar um bloco, use o seguinte padrão de caracteres ... 

character_map(N, [ [' ',' ',' ',' ',' ',' ',' '],
                   [' ',' ',' ', N ,' ',' ',' '],
                   [' ',' ',' ',' ',' ',' ',' '] ]).

Para desenhar e ocultar uma peça ... 

   %%% draw tile
draw(Obj) :- reverse_video, character_map(Obj,M),
             location(Obj,X,Y),
             draw(X,Y,M), plain.
   
draw(_,_,[]).
draw(X,Y,[R|G]) :- draw_row(X,Y,R),
                   Y1 is Y + 1,
                   draw(X,Y1,G).

draw_row(_,_,[]).
draw_row(X,Y,[P|R]) :- cursor(X,Y),
                       write(P),
                       X1 is X + 1,
                       draw_row(X1,Y,R).

   %%% hide tile
hide(Obj) :- character_map(Obj,M),
             location(Obj,X,Y),
             hide(X,Y,M).

hide(_,_,[]).
hide(X,Y,[R|G]) :- hide_row(X,Y,R),
                   Y1 is Y + 1,
                   hide(X,Y1,G).

hide_row(_,_,[]).
hide_row(X,Y,[_|R]) :- cursor(X,Y),
                       write(' '),
                       X1 is X + 1,
                       hide_row(X1,Y,R).

Anime os movimentos gráficos ... 

up(Obj)    :- hide(Obj),
              retract(location(Obj,X,Y)),
              Y1 is Y - 1,
              assert(location(Obj,X,Y1)), 
              draw(Obj).

down(Obj)  :- hide(Obj),
              retract(location(Obj,X,Y)),
              Y1 is Y + 1,
              assert(location(Obj,X,Y1)),
              draw(Obj).

left(Obj)  :- hide(Obj),
              retract(location(Obj,X,Y)),
              X1 is X - 1,
              assert(location(Obj,X1,Y)),
              draw(Obj).

right(Obj) :- hide(Obj),
              retract(location(Obj,X,Y)),
              X1 is X + 1,
              assert(location(Obj,X1,Y)),
              draw(Obj).

Agora, juntando tudo com o solucionador ... 

puzzle(P) :- solve(P,S), 
             animate(P,S),
             message.

animate(P,S) :- initialize(P),
                cursor(1,2), write(S), 
                cursor(1,22), write('Hit ENTER to step solver.'),
                get0(_X),
                play_back(S).

draw_all :- draw(1), draw(2), draw(3), draw(4),
            draw(5), draw(6), draw(7), draw(8).

   %%% play_back([left,right,up,...]).
play_back([M|R]) :- call(M), get0(_X), play_back(R).
play_back([]) :- cursor(1,24).  %%% Put cursor out of the way

message :- nl,nl,
   write('    ********************************************'), nl, 
   write('    *  Enter 8-puzzle goals in the form ...    *'), nl,
   write('    *     ?-  puzzle(0/8/1/2/4/3/7/6/5).       *'), nl,
   write('    ********************************************'), nl, nl.


:- message.

Para executar o animador gráfico de solução do 8-puzzle, use o seguinte tipo de objetivo ... 

?-  puzzle(0/8/1/2/4/3/7/6/5).

que, neste caso, representa começar com o objetivo 

0  8  1
2  4  3
7  6  5

A tela então limpa e o usuário pode definir a solução pressionando a tecla Enter. (O programa não verifica se o objetivo é alcançável desde o início que o usuário fornece.)


Exercício 8.2.1 Adicione a "verificação de acessibilidade" do Exercício 5.2.1 ao animador gráfico para o '8-puzzle'.


Exercício 8.2.2 Anime soluções para o Exercício 5.1.1, problema das rainhas.


Exercício 8.2.3 Anime soluções para o Exercício 5.1.2, problema do labirinto.


Veja Também

Disponível em “http://www.augustobaffa.pro.br/wiki/index.php?title=Animando_o_8-puzzle_(§5.2)_usando_gráficos_de_personagens&oldid=300”