Labirintos com Delphi

Uma das coisas boas da programação é a diversão que ela proporciona. Só o ato de desenvolver sistemas já é, muitas vezes, divertido, e desenvolver aplicações que geram momentos marcantes é muito bom.

Em determinado momento tive a curiosidade de pesquisar sobre algorítmos de criação de labirintos (em inglês, mazes). Fiquei surpeso com a quantidade de algorítmos diferentes existentes para isso. Percebi que existem, aliás, diferentes tipos de labitintos, dos quais nunca havia ouvido falar a respeito.

Fui levado a diferentes literaturas, das quais, indico Mazes for Programmers, de Jamis Buck. Para aqueles que de alguma forma não conseguem adquirir o livro, sugiro a leitura do conteúdo no site do próprio autor, que já elucidará o suficiente o neófito de criação de labirintos – http://weblog.jamisbuck.org/under-the-hood.

Abaixo vamos desenvolver labirintos utilizando-se três diferentes tipos de algorítmos – e acredite, existem muito mais tipos.

Antes de começarmos

Existem diferentes tipos de labirintos. O labirinto tradicional consiste de um quadrado ou retângulo, cujo interior é divido de forma a criar as passagens do labirintos. Todavia, existem diversos outros tipos, como labirintos circulares, triangulares, hexagonais, multidimensionais, etc. Estaremos aqui nos referindo apenas aos labirintos tradicionais.

Assim, trataremos cada labirinto como uma matriz de dimensões N x N, com todas as paredes em todas as células, conforme a figura abaixo:

Binary Tree

O algorítmo de árvore binária para desenvolvimento de labirintos é talvez o mais simples de todos. Ele baseia-se no conceito:

  • Escolha duas direções que não sejam opostas. Ex: Norte e Leste. Poderia ser Norte e Oesta, como Sul e Leste. O importante é não se oporem.
  • Todas as céulas encostadas nas paredes dessas direções devem possuir uma passagem entre sí. Imagine que a escolha tenha sido Norte e Leste. Nesse caso, todas as células encostadas nas paredes Norte e Leste deverão estar ligadas:

  • Uma vez isso feito, para cada célula do labirinto, que não sejam essas células já abertas, faça uma escolha entre essas duas direções, e crie uma passagem nela.

Pronto, está criado seu labirínto. Você terá algo como:

Devido essa simplicidade e uniformidade, sem a existência de nenhuma dependência para a operação de cada célula, esse algorítmo é facilmente portado em uma lógica para processamento paralelo, além de utilizar o mínimo de memória, visto que não armazena nenhuma informação.

Sidewinder

O seu entendimento é um tanto confuso, mas depois que “pegamos o jeito”, vemos a sua engenhosidade.

A primeira coisa é entendermos que para o funcionamento desse algorítmo, vamos precisar criar diferentes “ambientes”. Chamo aqui de ambiente um dado corredor, dentro do labirinto.

Considere o labirinto 3 x 3 abaixo:

Um ambiente, é um corredor, conforme pode ser observado abaixo, grifado em vermelho:

Não importa se esse corredor possui apenas 1 casa, ou várias casas. Essa diferenciação é o que dará a “sensação” de um labirinto.

Partindo da posição inicial (0, 0 – primeira célula na esquerda, no topo), vamos linha a linha, de cima para baixo, com a seguinte lógica:

  • Se for a primeira linha, abra passagem por ela toda. Isso mesmo, a primeira linha inteira é um único ambiente. Isso é necessário para que seja possível interligar todos os ambientes.
  • Para as próximas linhas, sorteie um número, que seja entre 1 ao total de células disponíveis da linha, e abra o caminho entre essas células. Como é? Isso mesmo. Entre 1 ao total de células disponíveis da linha.

Vamos partir do segunda passo, quando já temos a primeira linha aberta:

Temos que a segunda linha possui 3 células disponíveis. Assim, vou fazer um sorteio entre 1 à 3, pois 3 é o total de células disponíveis. Vamos dizer que o número sorteado foi 2. Assim, tenho que as duas primeiras células terão passagem:

  • A próxima etapa a ser feita, é criar uma passagem para a linha de cima. Para isso, vamos sortear novamente, mas agora apenas entre as células do ambiente criado, ou seja, entre a primeira e segunda célula. Vamos dizer que, novamente, o número sorteado foi 2 – não se preocupe agora com quais números são sorteados. Isso realmente não importa. Depois você verá que qualquer número daria certo, embora produza um desenho de labirinto diferente.

Assim, como a segunda célula foi sorteada, fazemos uma passagem na segunda célula para a linha de cima:

Pronto. Agora vamos para o próximo passo.

  • Faça novamente a primeira e segunda etapa, para as células restantes da mesma linha.

Hein?

Ok, vou explicar. No nosso exemplo, temos apenas 3 colunas, por isso não é tão perceptível isso, mas o labirinto poderia ser de uma dimensão, 10 x 10 por exemplo. Nós tratamos apenas a primeira e segunda célula. Ainda faltam todas as outras células para a mesma linha. Como no nosso exemplo temos apenas 1 coluna restante, o sorteio vai entre 1 e 1. Assim, temos que a terceira coluna apenas – a única que restou – é a sorteada, e ela também recebe a abertura da passagem para a linha de cima, porque é a única célula a ser sorteada. Assim:

Perceba que o nosso labirinto já está ganhando forma.

  • Repita o mesmo passo inicial da linha 2 para os restantes das linhas. Vamos imaginar que, conforme o sorteio, na terceira linha a primeira célula seja a única escolhida, e depois, as dúas últimas células foram escolhidas. O desenho ficaria mais ou menos assim:

Pronto!

Está finalizado o labirinto, através do algorítmo sidewinder.

Recursive Backtracking

Na minha opnião, o melhor dos três labirintos. Seu desenho é muito mais agradável, e parece-se muito com aqueles labirintos dos almanaques da turma da Mônica – você sabe do que estou falando!.

Ele é um pouco mais complexo, mas nada que seja fora do comum.

  •  Escolha qualquer célula do labirinto randomizamente. Essa passa a ser a célula  ativa. Marque ela como uma célula visitada.
  • Partindo da posição da célula ativa, escolha um lado. Se esse lado ainda não foi visitado, cave uma passagem para ele. Essa célula imediata ao lado escolhido passa a ser a célula ativa.
  • Comece novamente o processo para a célula ativa.
  • Na escolha dos lados, se a célula do lado escolhido já foi visitada, escolha outro lado. Se todos os lados foram visitados, volte para a célula anterior. Ela se torna a célula ativa.
  • Continue o processo até que não existem mais lados disponíveis quando a célula ativa for a primeira célula escolhida, randomicamente.

Um ponto a prestar atenção aqui é que, como ele utiliza-se da recursividade, é possível que ele cause um estouro na stack caso suas dimensões sejam muito grande, então fique muito com isso. Uma possibilidade é alterar a directiva $MAXSTACKSIZE, para interferir na forma como o Delphi solicita a memória. Para saber mais a respeito, click aqui.

Legal, mas cadê a porta?

Já tinha percebido que não havíamos criado nenhuma porta de entrada ou de saída em nossos labirintos? Pois bem, isso é de fácil solução, mas deixo aqui como um exercício para você pensar um pouco.

Conclusão

Espero que você tenha gostado de aprender sobre desenvolvimento de labirintos – mazes – no Delphi, tanto quanto gostei de compartilhar isso com você.

Abaixo está um link para o projeto que desenvolvi para a geração de labirintos.

Link

Obtenha o exemplo do projeto aqui!

Projeto Migration for Delphi (M4D)

M4D

No final do ano passado comecei a desenvolver um projeto open-source, que disponibilizasse à comunidade Delphi a mesma facilidade que os desenvolvedores PHP possuem com frameworks como Laravel e Zend, e mesmo o pessoal de Rails, em realizar atualizações de sistemas controladas por migrações.

Não trata-se de migração de versões do Delphi, mas sim de controle de atualizações de seus próprios sistemas.

Assim, foi criado o projeto M4D (Migration for Delphi), que está disponível gratuitamente a todos que tiverem interesse em usufruir de seus recursos em: https://bitbucket.org/migration4d/m4d

Dentro do site do projeto existem links com vídeos explicativos a respeito do que é uma migração, como instala-la dentro do Rad Studio e como  utilizar os seus recursos. Existe também uma breve documentação com as classes existentes no projeto. Além disso, fiz questão de gravar os mesmos vídeos em português para a comunidade BR de desenvolvedores.

Espero que todos gostem do projeto, assim como gostei de desenvolvê-lo.

Abraços, e boas migrações!

Alta Performance com Busca Binária

Um dos métodos mais comum de realizar uma busca em uma lista de opções, é procurar item a item, até encontrar a opção que corresponde à aquela que está sendo procurada. Essa metodologia de busca é conhecida como bubble search. Embora funcional, ela é horrível para a performance, porque faz com que cada elemento dentro do conjunto a ser procurado, precise ser testado, até que a opção correta seja encontrada. Assim, em uma lista de 100.000 opções por exemplo, caso a última opção seja a correta, todas as 100.000 opções precisam ser testadas.

Em uma implementação Delphi, isso geralmente está vinculado a um laço de repetição como “for” ou “while”:

 

Embora esse seja um caso necessário em alguns cenários, obviamente não é algo a ser desejado.

Quando os valores de uma lista possam ser ordenados de alguma forma, é possível criarmos alguns algorítmos otimizados para a busca desses valores. Existem diversos algorítmos recomendados para cada situação. Falaremos agora um pouco da busca binária.

Busca Binária

Binary Search
Mecanismo de uma busca binária

Quando pudermos ordenar uma lista de elementos, é possível utilizarmos a busca binária. Ela possui esse nome porque sempre que a condição do retorno é testada, ela descarta metade da lista em cada teste. Assim, ela considera que existam dois lados: o lado correto, e o lado errado (2 = BInário).

Vamos entender melhor.

Imaginemos um conjunto de números dispersos que vão de 1 a 100. A primeira coisa a ser feita, é ordenar esses números de alguma forma. No nosso exemplo, vamos ordená-los de forma crescente (1, 5, 7, 10…100). A ordenação é o passo mais importante, porque ela que cria a condição necessária para o funcionamento da busca binária.

Uma vez com a lista ordenada, vamos utilizar a seguinte lógica para buscarmos nossos valores. Sempre que formos procurar um valor, iremos sempre ao meio da lista de verificaremos se o valor do meio é o valor que procuramos. Se for, está finalizado. Caso não for, verificaremos, conforme a ordenação dada (no nosso caso, ordem crescente de números), se o número que procuramos está antes ou depois do meio. Caso esteja antes, sabemos que podemos descartar da busca a metade para frente. Caso esteja depois, sabemos que podemos descartar o início da lista até a metade. Agora, teremos apenas metade da lista para procurar novamente.

Esse trecho da metade da lista restante forma uma nova lista, menor, é verdade, mas a qual podemos aplicar a mesma lógica. Assim, para essa nova lista, resultado da lista anterior, aplicamos o mesmo princípio: vamos à metade dessa nova lista e verificamos se o valor do meio é o valor que procuramos. Se for, encontramos o elemento. Se não for, verificamos se o número que procuramos está antes ou depois do meio. Se estiver antes, a metade posterior é descartada. Se estiver depois, a metade anterior é descartada.

Essa lógica é aplicada continuamente  às novas “sublistas” até encontrarmos o resultado.

O interessante desse algorítmo é que, não importa o tamanho da lista, o valor será encontrado em até 8 etapas. Isso mesmo. Mesmo que a lista tenha 1.000.000 de elementos, em até 8 etapas, o resultado correto é retornado. Isso é fantástico quando falamos em desempenho, porque 8 etapas de processamento é muito pouco para qualquer computador processar e
retornar o valor correto.

Implementando uma busca binária

Podemos implementar uma busca binária em Delphi facilmente, utilizando o recurso da recursividade. Como teremos ao máximo 8 chamadas para o mesmo método, não haverá risco de estouro de pilha (stack overflow). Veja o código abaixo:

 

 

A primeira coisa a fazermos é checar se o valor a ser encontrado está é algum dos limites da lista. Se não for, encontramos o meio e verificamos se o elemento do meio é o elemento que procuramos. Se não for, verificamos se está para frente ou para trás da lista. Conforme o caso, chamamos novamente a função BuscaBinaria, mas alterando o “range” do valor inicial e valor final da lista. Essa é a forma de limitarmos as buscas para a metade anterior ou posterior da lista.

Lembrando que a chamada inicial da busca ocorre passando o valor inicial como o primeiro elemento da lista, e o valor
final como o último elemento da lista.

Em poucas linhas você tem uma excelente ferramenta de busca de alta performance.

Busca Binária nativa no Delphi

Documentação: http://docwiki.embarcadero.com/Libraries/Tokyo/en/System.Generics.Collections.TArray.BinarySearch

O Delphi possui uma ferramenta nativa para buscas binárias. Utilizando-se do método BinarySearch da classe TArray, é possível chegar ao mesmo resultado.

Veja o código abaixo:

 

A primeira coisa que fizemos aqui foi criar uma lista aleatória de 0 à MAX (ou 100.000). Depois definimos qual seria o valor a ser encontrado na lista. A variável “Indice” é alimentada pelo terceiro parâmetro do método, um parâmetro out que retorna o índice em que está o elemento (ou o índice mais próximo a ele). O último parâmetro do método é um método anônimo para a definição da ordenação da lista (lembra que a ordenação é muito importante para a busca binária?).

O método retorna “true” se encontrou o elemento ou “false” se ele não foi encontrado.

Muito simples não é?

Conclusão

A busca binária é uma execelente ferramenta para encontrar valores dentro de um conjunto que possa ser ordenado de alguma forma. O Delphi possui essa ferramenta implementada de forma nativa e bem flexível, pois implementa a
funcionalidade com o uso de genérics, dando a possibilidade de alterar o tipo e a metodologia de busca conforme o caso necessário. Todavia, ainda sim existem alguns casos mais complexos onde será necessário o desenvolvimento de uma busca binária própria para o problema em questão, então é importante conhecer o mecanismo de funcionamento dessa busca, para conseguir extrair o máximo de proveito de sua utilização.

Lançamento do Delphi Tokyo Release 1 (10.2.1) e Embarcadero Roadmap 2018

Acabou de ser anunciado pela Embarcadero o lançamento do primeiro release esperado para o Delphi Tokio. Abaixo encontra-se o link para a notícia:

https://community.embarcadero.com/blogs/entry/delphi-tokyo-release-1-or-10-2-1-is-now-available?utm_source=dlvr.it&utm_medium=twitter

Para os mais curiosos, existe também o roadmap para as futuras liberações e versões:

https://community.embarcadero.com/article/news/16519-rad-studio-roadmap-may-2018

 

Diagnóstico de Perfórmance com TStopWatch e TTimeSpan

Documentação: http://docwiki.embarcadero.com/Libraries/Tokyo/en/System.Diagnostics.TStopwatch

O Delphi possui uma função de diagnóstico muito últil para medir a performance do sistema. No momento de melhorar a performance de um trecho de código, geralmente o desenvolvedor faz algo como:

Isso basicamente pega a data antes da execução, pega a data depois da execução, e depois mostra a diferença dos tempos entre as datas.

Isso funciona na maioria dos casos.

Caso você precise de uma maior precisão na medida do tempo, você pode utilizar GetTickCount: https://reisthales.wordpress.com/2016/03/30/delphi-medindo-o-tempo-de-execucao-de-um-processo/

Contudo, o Delphi possui uma classe preparada para esse tipo de diagnóstico, chamada TStopWatch. Sua utilização segue abaixo:

Embora TStopWatch seja um record, ele precisa ser inicializado, seja pelo método Create, seja pelo método StartNew. Ambos criam e inicializam o StopWatch. A diferença é que Create cria com o contador de tempo parado, e StartNew já cria com o contador de tempo girando.

StopWatch.Start inicia a contagem do tempo e StopWatch.Stop para a contagem do tempo. Isso feito, você consegue obter os valores em:

StopWatch.ElapsedMilliseconds – Retorna o total de tempo em milesegundos.

System.Diagnostics.TStopwatch.ElapsedTicks – Retorna o total de tempo em milesegundos (também).

System.Diagnostics.TStopwatch.Elapsed – Retorna o total de tempo em formato TTimeSpan – o melhor a ser usado.

Existem ainda outras funcionalidades como StopWatch.Reset, que reinicia o contador do StopWatch.

TTimeSpan

Documentação: http://docwiki.embarcadero.com/Libraries/Tokyo/en/System.TimeSpan.TTimeSpan

TTimeSpan é um record com funcionalidades específicas para tratamento de tempo. Assim que ele é retornado pelo método “Elapse”, você pode utilizar um de seus métodos:

Assim, você pode obter o retorno dessas informações facilmente em milesegundos, segundos, minutos, horas, dias, etc.

Pronto para melhor diagnosticar seu código?

Novo endereço

Resolvi melhorar o layout do site e migrei do Blogger para o WordPress. Além disso, optei pelo domínio próprio http://www.edgarpavao.com, ao invés de utilizar um subdomínio como estava antes. Espero que vocês gostem!