2.3 Algoritmo completo

Agora que você entendeu a ideia do algoritmo, já pode descrevê-lo em formato de pseudocódigo. A rotina recebe quatro valores inteiros (x₀, y₀, x₁ e y₁) que correspondem às coordenadas da posição na qual personagem se encontra e a posição a qual ele deseja ir. Algumas variáveis são declaradas no início da rotina para facilitar os cálculos. Inclinação, que é o coeficiente angular da reta definida pelos pontos passados, erro, que é o fator de erro que se adiciona para totalizar o valor da inclinação e caminho, que é uma sequência de pontos inicialmente vazia, mas que representa o caminho a ser construído. Antes de iniciar o laço do algoritmo, defina as variáveis x e y que ficarão armazenando a posição a ser inserida no caminho.

A cada iteração do laço, insira o ponto (x, y) no caminho e atualize o erro em função da inclinação da reta. Se o erro for maior ou igual a 1, então y é incrementado (chegou a hora de gerar uma mudança na rota ), o erro é reajustado e o ponto com o novo y é inserido no caminho. Por fim, após o término do laço, a posição do destino também é inserida no caminho, e este retornado.

        Função CaminhoReto (Int x0, Int y0, Int x1, Int y1)

            Real inclinação = (x1 – x0) / (y1 – y0);

            Real erro = -0.5;

            Arranjo caminho = [];

            Int x, y = y0;

            Para x de x0 a x1 - 1

                insere (x,y) em caminho

                erro = erro + inclinação

                Se erro ≥ 1 então

                    y = y + 1

                    erro = erro - 1

                    insere (x,y) em caminho

                Fim_se

            Fim_para

            insere (x1,y1) em caminho

            Retorna caminho

        Fim_procedimento

O último detalhe que resta é fazer esse algoritmo funcionar para os demais sete octantes que restam no plano. Como já dito, da forma que foi descrita, funciona apenas para o primeiro octante. Você precisará generalizar para que o personagem siga em qualquer direção. O primeiro passo é descobrir em qual octante o caminho se encontra. Veja a figura 14.

Se você se lembra, o primeiro octante era definido pelo conjunto de pontos tal que x > 0, y > 0 e x ≥ y, não é? Raciocine agora sobre o segundo quadrante, apresentado na Figura 14. Esse octante é definido pelos conjuntos de pontos tal que x > 0, y > 0 e y ≥ x. Aplicando a mesma ideia para os demais octantes, você terá as condições presentes no Quadro 02. Nele, abs(x) representa o valor em absoluto (valor positivo) de x.

Agora que você sabe identificar os diferentes casos, falta chamar o procedimento de forma adequada. A estratégia mais simples é “enganar” o algoritmo fazendo-o “pensar” que se trata do primeiro octante, mesmo que não seja. Para isso, inverta as coordenadas, tanto as que você passou para ele, quanto as que ele insere no caminho. Por exemplo, em vez de passar as coordenadas (x₀, y₀) e (x₁, y₁) para ele, você passou (y₀, x₀) e (y₁, x₁), e trocou de volta o caminho gerado fazendo com que as coordenadas (x₀, y₀) e (x₁, y₁) sejam consideradas (y₀, x₀) e (y₁, x₁).

Para levar em conta todos os quadrantes, você precisará realizar as seguintes trocas: