Inteligência Artificial
AI para Labirintos


Você está em: MarMSX >> Cursos >> AI   Este capítulo irá discutir algumas soluções para desenvolver inteligência artificial para controlar personagens em labirintos. O estudo terá como base labirintos do tipo Pac-man.

  No curso de Jogos em Basic, reproduzimos o labirinto do jogo Break-man, conforme mostra a figura abaixo. Ele será a base de nosso estudo.
  Na parte extra daquele curso, utilizamos um recurso para economizar tempo e linhas de código do programa principal. Assim, salvamos a área de memória de vídeo contendo o labirinto e os caracteres modificados. Dessa forma, através das duas tabelas salvas, utilizamos o programa a seguir para gerar o labirinto.
10 SCREEN 1:WIDTH 32
20 VPOKE 8192+16,32:VPOKE 8192+17,32
30 BLOAD"CARACT.TAB",S
40 BLOAD"NOME.TAB",S
  Dessa forma, é só baixar as tabelas no link acima e colocar no mesmo disco que o programa anterior, que o labirinto é desenhado. Assim, iremos somente nos preocupar com o controle do personagem dentro do labirinto.

  O seguinte trecho de código cria uma bola em sprite para representar um personagem, que servirá de exemplo para todos os testes desse capítulo. 
100 ' Cria personagem
110 X=16:Y=8: 'Local inicial do personagem
120 FOR I=1 TO 8
130 READ A$
140 S$=S$+CHR$(VAL("&H"+A$))
150 NEXT I
160 SPRITE$(0)=S$
170 DATA 3C,7E,FF,FF,FF,FF,7E,3C

  A seguir, iremos ver como criar e validar os movimentos de um personagem pelo labirinto.

  Primeiramente, devemos definir uma direção. Os códigos numéricos da figura abaixo definem a direção que iremos nos mover.   Após definirmos a direção, registramos nas variáveis temporárias XX e YY as novas posições do personagem, cuja posição atual é X,Y. Para validar o movimento, a nova posição deverá cair em uma região de caminho livre, nunca em uma parte do labirinto.
  Ao validar o movimento, atualizamos as variáveis X e Y com os valores XX e YY, respectivamente.
Estratégias para movimentar o personagem   Serão propostas as seguintes soluções: Movimento aleatório   Esta solução tem como objetivo escolher uma direção aleatoriamente. Caso não seja possível seguir em uma direção, aguarda a próxima iteração do loop principal.

  O código a seguir irá fazer a simulação para o movimento aleatório. Junte este código com os códigos do labirinto e da bolinha, apresentados anteriormente. 
500 ' Loop principal
510 PUT SPRITE 0,(X,Y-1),11,0
520 GOSUB 1000
530 GOTO 510
1000 ' Rotina que movimenta personagem, segundo uma direção
1010 DI=INT(RND(-TIME)*4)+1
1020 IF DI=1 THEN YY=Y-8:XX=X:GOSUB 1500
1030 IF DI=2 THEN XX=X+8:YY=Y:GOSUB 1500
1040 IF DI=3 THEN YY=Y+8:XX=X:GOSUB 1500
1050 IF DI=4 THEN XX=X-8:YY=Y:GOSUB 1500
1060 RETURN
1500 ' Verifica nova posição
1510 C=VPEEK(6144+XX/8+4*YY)
1520 IF C=32 THEN X=XX:Y=YY: 'Se espaço vazio, anda
1530 RETURN

  A bolinha se movimenta! Entretanto, ela se movimenta constantemente para frente e para trás e seus movimentos ficam circunscritos aos mesmos locais.
Andar em linha reta até encontrar um obstáculo   Nessa proposta, andamos sempre na mesma direção até encontrar um obstáculo. Dessa forma, decidimos aleatoriamente por onde seguir.

  O código a seguir irá fazer a simulação para o movimento proposto. Junte este código com os códigos do labirinto e da bolinha, apresentados anteriormente. 
490 DI=2 :' Direcao incial
500 ' Loop principal
510 PUT SPRITE 0,(X,Y-1),11,0
520 GOSUB 1000
530 GOTO 510
1000 ' Rotina que movimenta personagem, segundo uma direção
1010 IF DI=1 THEN YY=Y-8:XX=X:GOSUB 1500
1020 IF DI=2 THEN XX=X+8:YY=Y:GOSUB 1500
1030 IF DI=3 THEN YY=Y+8:XX=X:GOSUB 1500
1040 IF DI=4 THEN XX=X-8:YY=Y:GOSUB 1500
1050 RETURN
1500 ' Verifica nova posição
1510 C=VPEEK(6144+XX/8+4*YY)
1520 IF C=32 THEN X=XX:Y=YY: RETURN
1530 DI=INT(RND(-TIME)*4)+1:RETURN 1000

  A bolinha vai mais longe! Entretanto, ela salta os caminhos alternativos que existem no meio da trajetória reta que ela percorre. Em outras palavras, ela não analisa os desvios no meio do caminho dela, onde acaba nunca entrando em certas regiões.
Analisar em cada passo as direções possíveis   De forma a suprir a carência do algoritmo anterior, iremos analisar todas as direções possíveis e tomar uma decisão. A diferença para o primeiro algoritmo é que, agora, só devolvemos o controle para o loop principal quando andarmos efetivamente em uma direção.

  O código a seguir irá fazer a simulação para o movimento proposto. Junte este código com os códigos do labirinto e da bolinha, apresentados anteriormente. 
500 ' Loop principal
510 PUT SPRITE 0,(X,Y-1),11,0
520 GOSUB 1000
530 GOTO 510
1000 ' Rotina que movimenta personagem, segundo uma direção
1010 DI=INT(RND(-TIME)*4)+1
1020 IF DI=1 THEN YY=Y-8:XX=X:GOSUB 1500
1030 IF DI=2 THEN XX=X+8:YY=Y:GOSUB 1500
1040 IF DI=3 THEN YY=Y+8:XX=X:GOSUB 1500
1050 IF DI=4 THEN XX=X-8:YY=Y:GOSUB 1500
1060 RETURN
1500 ' Verifica nova posição
1510 C=VPEEK(6144+XX/8+4*YY)
1520 IF C=32 THEN X=XX:Y=YY: RETURN
1530 RETURN 1000

  Assim como no primeiro exemplo, a bolinha vai e volta na mesma reta! Entretanto, nesse caso, não perde tempo esperando o loop certo para seguir.
Analisar em cada passo as direções possíveis, sem voltar   Agora, iremos juntar todos os pontos positivos anteriores num algoritmo só. Dessa forma, vamos analisar todas as direções possíveis e tomar uma decisão sempre descartando a possibilidade de voltar. Para isso, devemos registrar a cada iteração, a última direção tomada.

  O código a seguir irá fazer a simulação para o movimento proposto. Junte este código com os códigos do labirinto e da bolinha, apresentados anteriormente. 
490 UD=0 :'Ultima direção
500 ' Loop principal
510 PUT SPRITE 0,(X,Y-1),11,0
520 GOSUB 1000:UD=DI
530 GOTO 510
1000 ' Rotina que movimenta personagem, segundo uma direção
1010 DI=INT(RND(-TIME)*4)+1
1020 IF DI=1 THEN IF UD<>3 THEN YY=Y-8:XX=X:GOSUB 1500 ELSE 1010
1030 IF DI=2 THEN IF UD<>4 THEN XX=X+8:YY=Y:GOSUB 1500 ELSE 1010
1040 IF DI=3 THEN IF UD<>1 THEN YY=Y+8:XX=X:GOSUB 1500 ELSE 1010
1050 IF DI=4 THEN IF UD<>2 THEN XX=X-8:YY=Y:GOSUB 1500 ELSE 1010
1060 RETURN
1500 ' Verifica nova posição
1510 C=VPEEK(6144+XX/8+4*YY)
1520 IF C=32 THEN X=XX:Y=YY: RETURN
1530 RETURN 1000

  Na linha 520, devemos armazenar a última direção em UD. O ELSE 1010 (linhas 1020-1050) é necessário, pois um valor DI atribuído aleatoriamente pode ser bloqueado no teste, se aquela direção for oposta a do movimento (voltar). Assim ele retorna ao loop principal sem se mover e com a direção DI errada. Aplicando o ELSE 1010, devolvemos a execução do programa para a linha 1010 para o sorteio de uma nova direção.

  Agora ficou legal, mas a bolinha dá umas travadas de vez em quando. Isso se deve ao fato dela ter que esperar o sorteio de uma direção cair em uma posição válida.
  De forma a otimizar este código, em vez de sortear novamente a direção, iremos passar para a direção seguinte em um movimento horário nas direções. Além disso, vamos calcular o endereço de vídeo no teste uma vez na linha 1010, e utilizar um deslocamento DE para alcançar as cercanias.

  O código a seguir apresenta a otimização desse algoritmo. 
490 UD=0 :'Ultima direção
500 ' Loop principal
510 PUT SPRITE 0,(X,Y-1),11,0
520 GOSUB 1000:UD=DI
530 GOTO 510
1000 ' Rotina que movimenta personagem, segundo uma direção
1010 DI=INT(RND(-TIME)*4)+1:E=6144+X/8+4*Y
1020 IF DI=1 THEN IF UD<>3 THEN YY=Y-8:XX=X:DE=-32:GOSUB 1500 ELSE DI=2
1030 IF DI=2 THEN IF UD<>4 THEN XX=X+8:YY=Y:DE=1:GOSUB 1500 ELSE DI=3
1040 IF DI=3 THEN IF UD<>1 THEN YY=Y+8:XX=X:DE=32:GOSUB 1500 ELSE DI=4
1050 IF DI=4 THEN IF UD<>2 THEN XX=X-8:YY=Y:DE=-1:GOSUB 1500 ELSE DI=1:GOTO 1020
1060 RETURN
1500 ' Verifica nova posição
1510 C=VPEEK(E+DE)
1520 IF C=32 THEN X=XX:Y=YY: RETURN
1530 DI=(DI MOD 4)+1:RETURN 1020

  Vixe! A bolinha está viva!

  Existe uma armadilha para a bolinha nesse algoritmo. Se ela cair no elemento central da tela, onde a única saída é retornando, ela ficará presa.   Para solucionar esse problema, podemos introduzir um contador nos testes de direção. Caso o contador estoure, faça com que a DI=UD e UD=0.
  Alterações: 
1010 DI=INT(RND(-TIME)*4)+1:CN=0
...
1510 C=VPEEK(6144+XX/8+4*YY):CN=CN+1
...
1525 IF CN=5 THEN DI=UD:UD=0:RETURN 1020
Um mapa de decisões   O jogo Pucky utiliza uma estratégia interessante. Ele cria o mapa do labirinto de cada fase na matriz T(j,i), onde armazena todos os pontos de decisão que os fantasmas precisam tomar. Os locais restantes, são preenchidos com o valor 0, que significa que o fantasma deve seguir seu curso normal.
  De acordo com o mapa acima, ele toma as seguintes decisões:   As demais decisões são baseadas na perseguição ao jogador e serão abordadas no próximo capítulo.
Perseguição   Até agora utilizamos algoritmos onde o personagem não tem um destino certo para ir. No caso da perseguição, o personagem terá uma direção a seguir, definida pelas coordenadas do jogador.

  No exemplo do jogo Puck da seção anterior, caso a decisão seja a 5, significa que o fantasma tem quatro direções para seguir. Assim, o cálculo da direção é feito com base nas coordenadas dele (AX,AY) e nas do Pucky (X,Y). 
YY=Y-AY
XX=X-AX
IF ABS(YY) >= ABS(XX) THEN 
  AB=SGN(YY)
  AA=0
ELSE
  AB=0
  AA=SGN(XX)
  Onde AA é o deslocamento do fantasma em X e AB o deslocamento em Y.

  Ele toma a direção do eixo da maior distância encontrada, seguindo para o sentido (sinal SGN) do Pucky.

  Para as demais decisões, temos:
Caso Direções possíveis Estratégia
6 ↑, ↓, → Se movimento for horizontal, sobe ou desce de acordo com a posição do Pucky.
Se vertical, caso esteja alinhado com o Pucky, toma o caminho vertical, senão, continua na horizontal.
7 ↑, ↓, ←
8 ↑, ←, → Se movimento for vertical, vai para esquerda ou direita de acordo com a posição do Pucky.
Se horizontal, caso esteja alinhado com o Pucky, toma o caminho horizontal, senão, continua na vertical.
9 ↓, ←, →
A voltar Inverte o sinal de AA e AB.
B passagens De acordo com o portal, passa para o portal correspondente.


<< Anterior   AI   Próxima >>