Você já se perguntou como o terreno em jogos como Minecraft é gerado? Há um antigo algoritmo chamado Diamond-Square Algorithm que é de uso comum. Acho que seria divertido implementar esse algoritmo usando TDD. Aqui está um exemplo de saída do resultado:
Então, eu pensei que você gostaria de ver os passos TDD que eu usei para construir esse algoritmo. Antes de começar, certifique-se de que entende o algoritmo lendo o link acima. Não se preocupe, é um algoritmo muito simples; e o artigo do link é extremamente fácil de ler.
Então, como você realiza um test-drive em um algoritmo como esse? No início, pode parecer simples. Para cada teste, crie um pequeno array de duplas, preveja os resultados e, em seguida, escreva o teste que compara os resultados previstos com a saída do algoritmo.
Existem vários problemas com essa abordagem. O primeiro é a sobrecarga de dados. Mesmo o menor array é um 3X3 com 9 valores diferentes para verificar. O próximo menor é 5X5 com 25 valores. Em seguida, 9X9 com 81 valores. Tentar escrever um conjunto abrangente de testes, mesmo para o caso 3X3, seria tedioso na melhor das hipóteses; e muito difícil para alguém entender.
O segundo problema é que a condução de test-drives a partir dos resultados brutos nos obriga a escrever todo o algoritmo muito cedo no processo de teste. Não há nenhuma maneira de proceder incrementalmente. Você pode se lembrar de textos anteriores que escrevi em que eu chamo isso de: “Getting Stuck”.
Outro problema é que esses testes não provam que o algoritmo está funcionando como deveria. Eles apenas provam que os valores resultantes estão certos. Agora, na maioria dos casos, isso não é um problema. Eu sou um forte adepto da Escola Clássica de TDD e eu tendo a não usar meus testes para inspecionar o funcionamento interno do software que estou escrevendo. Os valores de saída geralmente são bons o suficiente. Nesse caso, no entanto, o algoritmo é a preocupação primordial.
Agora, como eu sou um classicista, ainda quero verificar os valores. No entanto, os valores que eu quero verificar não são os valores de saída do algoritmo, mas os valores internos que o algoritmo usa. Especificamente as coordenadas das células que estão sendo manipuladas.
Considere: eu quero saber que as coordenadas do ponto médio do quadrado estão sendo calculadas corretamente. Eu também quero garantir que o valor do ponto médio é definido tomando a média dos quatro cantos. Então, estou muito interessado no cálculo das coordenadas desses quatro cantos. Por outro lado, uma vez que eu sei que essas coordenadas são calculadas corretamente, eu realmente não me importo com quais são os valores das células ou se a média é calculada corretamente. Quero dizer, as médias são bastante triviais para testar. Então, eu realmente não preciso testar o cálculo médio ainda.
Parte do algoritmo Diamond tem preocupações semelhantes. Eu quero ter certeza de que as coordenadas dos pontos do losango estão sendo calculadas corretamente e que as coordenadas para as entradas para essas médias são calculadas corretamente. Eu também quero ter certeza de que os losangos nas bordas do array só desenham a partir dos três pontos reais; e não tentem chegar fora do array para o quarto.
Então, aqui está o código para meus testes. Eu não vou te mostrar o código para o algoritmo real, porque não é particularmente interessante. Na verdade, sugiro que você use esses testes para conduzir sua própria implementação ;-).
O código
Começamos usando o maravilhoso HierarchicalContextRunner de Stephan Bechtold para nos ajudar a organizar nossos testes. Se você não estiver familiarizado com esse runner, que vergonha de você. <grin>
Observe a String nomeada actions. Esse vai ser o coração da nossa estratégia.
@RunWith(HierarchicalContextRunner.class)
public class TerrainInterpolatorTest {
private String actions = "";
private double[][] dummy;
private TerrainInterpolator interpolator;
Começamos com validações simples. Nossa configuração para esse conjunto de testes cria uma instância de TerrainInterpolatorSpy, que você verá no final do código. Esse teste duplo vai carregar a string actions com os valores que queremos testar.
Essa é uma inclinação bastante diferente e um teste duplo de espionagem. Em vez de nos dar booleanos e bandeiras para inspecionar sobre as chamadas de funções individuais, esse espião vai carregar a string actions com a sequência de coisas que aconteceram enquanto o algoritmo prosseguia.
Os primeiros três testes são apenas verificações muito simples para certificar que o algoritmo se comporta adequadamente quando recebidas entradas inválidas.
public class SimpleValidations {
@Before
public void setUp() throws Exception {
dummy = new double[1][1];
interpolator = new TerrainInterpolatorSpy();
}
Primeiro, testamos isso quando nos é dado um array que é muito pequeno, nenhuma ação ocorre.
@Test
public void terminalCondition_sizeOne() throws Exception {
interpolator.interpolate(dummy, 1);
assertThat(actions, isEmptyString());
}
Os próximos dois testes garantem que podemos detectar que o array tem um tamanho inválido.
@Test(expected = TerrainInterpolator.BadSize.class)
public void sizeMustBePowerOfTwoPlus1() throws Exception {
interpolator.interpolate(dummy, 2);
}
@Test
public void Check_isPowerOfTwo() throws Exception {
assertThat(interpolator.isPowerOfTwo(2), is(true));
assertThat(interpolator.isPowerOfTwo(4), is(true));
assertThat(interpolator.isPowerOfTwo(8), is(true));
assertThat(interpolator.isPowerOfTwo(1), is(false));
assertThat(interpolator.isPowerOfTwo(7), is(false));
assertThat(interpolator.isPowerOfTwo(18), is(false));
}
Agora, vamos ao trabalho real. Vamos analisar os cálculos das coordenadas. Começamos por certificar-nos de que o ponto médio de um quadrado 3X3 é calculado corretamente e que os pontos passados para a função média são os pontos corretos. Olhe para a string abaixo até entender o que significa. O código que constrói a string actions está no TerrainInterpolatorSpy abaixo.
public class SquareDiamondCoordinateCalculations {
@Test
public void simpleThreeByThree_SquarePass() {
interpolator.interpolate(dummy, 3);
assertThat(actions, startsWith(
"Square(0,0,3): A([0,0],[2,0],[0,2],[2,2])->[1,1]."));
}
Em seguida, asseguramos que os pontos do losango são calculados corretamente, que as entradas para a função média vêm dos locais corretos e que, uma vez que todos os losangos em um 3X3 estão nas bordas, que as médias são tomadas a partir de apenas três pontos.
@Test
public void simpleThreeByThree_DiamondPass() {
interpolator.interpolate(dummy, 3);
assertThat(actions, endsWith("Diamond(0,0,3): "+
"A([0,0],[2,0],[1,1])->[1,0]. " +
"A([1,1],[0,0],[0,2])->[0,1]. " +
"A([0,2],[2,2],[1,1])->[1,2]. " +
"A([1,1],[2,0],[2,2])->[2,1]. "));
}
Depois, vamos olhar para um 5X5 e nos certificar de que o quadrado inicial e as coordenadas do losango estão devidamente calculados.
@Test
public void DiamondSquare_FirstPass() throws Exception {
interpolator.interpolate(dummy, 5);
assertThat(actions, startsWith(
"Square(0,0,5): A([0,0],[4,0],[0,4],[4,4])->[2,2]. "+
"Diamond(0,0,5): " +
"A([0,0],[4,0],[2,2])->[2,0]. " +
"A([2,2],[0,0],[0,4])->[0,2]. " +
"A([0,4],[4,4],[2,2])->[2,4]. " +
"A([2,2],[4,0],[4,4])->[4,2]. "));
}
}
OK, agora temos que nos certificar de que o quadrado e os losangos estão devidamente repetidos, com tamanho e locais certos. Nesse ponto, não nos importamos mais com as médias porque sabemos que as coordenadas das entradas são calculadas corretamente. Tudo o que importa agora é que os pontos de partida e os tamanhos para os quadrados e losangos são calculados corretamente. Então, vamos usar um espião diferente. O TerrainInterpolatorDiamondSquareSpy carrega a string actions com apenas as ações de quadrado e losango, mas não as médias.
public class SquareDiamondRepetition {
@Before
public void setup() {
dummy = new double[1][1];
interpolator =
new TerrainInterpolatorDiamondSquareSpy();
}
@Test
public void FiveByFive() throws Exception {
interpolator.interpolate(dummy, 5);
assertThat(actions, is(
"" +
"Square(0,0,5) Diamond(0,0,5) " +
"Square(0,0,3) Square(0,2,3) Square(2,0,3) Square(2,2,3) " +
"Diamond(0,0,3) Diamond(0,2,3) Diamond(2,0,3) Diamond(2,2,3) "
));
} }
Agora, finalmente, podemos olhar para alguns valores reais. Isso nos ajudará a realizar o test-drive das coisas simples, como computar médias de uma lista de pontos.
public class Averages {
@Before
public void setup() {
dummy = new double[3][3];
interpolator = new TerrainInterpolator();
}
A chamada para interpolate com apenas dois argumentos desativa qualquer aleatorização. Assim, se começarmos com um array de todos os zeros, nosso resultado deve ser um array de todos os zeros.
@Test
public void zero() throws Exception {
interpolator.interpolate(dummy, 3);
assertThat(dummy, is(new double[][]
{{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}));
}
Claro que o mesmo acontece com todos os outros. Na verdade, um array de todos os X irá produzir um array de todos os X.
@Test
public void allOnes() throws Exception {
dummy[0][0] = dummy[2][0] =
dummy[0][2] = dummy[2][2] = 1;
interpolator.interpolate(dummy, 3);
assertThat(dummy, is(new double[][]{
{1, 1, 1},
{1, 1, 1},
{1, 1, 1}}));
}
Agora, alguma matemática real.
@Test
public void ramp() throws Exception {
dummy[0][0] = 0;
dummy[2][0] = 12;
dummy[0][2] = 12;
dummy[2][2] = 24;
interpolator.interpolate(dummy,3);
assertThat(dummy, is(new double[][]{
{0, 8, 12},
{8, 12, 16},
{12, 16, 24}}));
}
}
OK, finalmente, vamos nos certificar de que o fator aleatório e o offset estão sendo adicionados corretamente. O offset é minha própria criação, para que eu possa dirigir os valores para cima ou para baixo com um offset fixo. O terceiro argumento para a chamada interpolate é a amplitude aleatória. O quarto é o offset. O teste duplo TerrainInterpolatorWithFixedRandom simplesmente desliga a aleatoriedade e usa os valores absolutos da amplitude aleatória em vez disso.
Esse teste precisou de um monte mãos que calculam para criar. E, é claro, eu fiz o cálculo errado, no início. Então, eu tive que verificar os resultados do algoritmo e modificar o teste.
public class RandomsAndOffsets {
@Before
public void setup() {
dummy = new double[5][5];
interpolator =
new TerrainInterpolatorWithFixedRandom();
}
@Test
public void volcano() throws Exception {
interpolator.interpolate(dummy, 5, 2,4);
assertThat(dummy, is(new double[][]{
{0,8.5,8,8.5,0},
{8.5,8.5,10.75,8.5,8.5},
{8,10.75,6,10.75,8},
{8.5,8.5,10.75,8.5,8.5},
{0,8.5,8,8.5,0}
}));
}
}
}
O TerrainInterpolatorSpy carrega a variável actions com as ações square, diamond, set e average invocadas pelo algoritmo. Esse teste duplo simplesmente substitui aquelas funções do algoritmo principal por outras que carregam a variável actions.
private class TerrainInterpolatorSpy
extends TerrainInterpolator {
void doSquare(int x, int y, int size) {
actions += String.format("Square(%d,%d,%d): ",x,y,size);
super.doSquare(x, y, size);
}
void doDiamond(int x, int y, int size) {
actions += String.format(
"Diamond(%d,%d,%d): ",x,y,size);
super.doDiamond(x, y, size);
}
void set(int x, int y, double value) {
actions += String.format("->[%d,%d]. ", x, y);
}
double get(int x, int y) {
return -1;
}
double average(Integer... points) {
actions += "A(";
for (int i = 0; i < points.length; i += 2)
actions += String.format(
"[%d,%d],", points[i], points[i + 1]);
actions = actions.substring(0, actions.length()-1)+")";
return 0;
}
}
O teste duplo TerrainInterploatorDiamondSquareSpy simplesmente carrega a variável actions com as ações square e diamond, mas não com as ações set ou média.
private class TerrainInterpolatorDiamondSquareSpy
extends TerrainInterpolator {
void doSquare(int x, int y, int size) {
actions += String.format("Square(%d,%d,%d) ",x,y,size);
}
void doDiamond(int x, int y, int size) {
actions += String.format("Diamond(%d,%d,%d) ",x,y,size);
}
}
O teste duplo TerrainInterpolatorWithFixedRandom simplesmente substitui a função random para retornar o randomAmplitude fixo em vez de retornar um número aleatório entre + e -randomAmplitude.
private class TerrainInterpolatorWithFixedRandom
extends TerrainInterpolator {
double random() {
return randomAmplitude;
}
}
}
A partir desses testes, eu criei um algoritmo DiamondSquare em pleno funcionamento. Eu aposto que você também pode. Experimente.
***
Uncle Bob faz parte do time de colunistas internacionais do iMasters. A tradução do artigo é feita pela redação iMasters, com autorização do autor, e você pode acompanhar o artigo em inglês no link: http://blog.cleancoder.com/uncle-bob/2017/01/09/DiamondSquare.html.
De 0 a 10, o quanto você recomendaria este artigo para um amigo?