Algorítmo de Pathfinding

Criando Jogos com PhaserJS – Algorítmo de Pathfinding

O algorítmo

No tópico de hoje eu quero discutir com você sobre algoritmos de “PathFinding”. Mas o que é isso Jonatan? Você já se perguntou como um personagem acha o caminho mais curto para chegar à um determinado local? Bom, na maioria das vezes, é utilizado um algoritmo de PathFinding.

Este algoritmo vai realizar um mapeamento das possibilidades de caminho e vai retornar o caminho mais curto para uma determinada posição. Eu confesso que fiquei encantado com este conceito. Pra você entender melhor, dê uma olhada neste exemplo.

Neste exemplo você pode controlar qual o ponto de início e o ponto final, bem como adicionar bloqueios no meio do caminho. É bem interativo e intuitivo. A ideia é que seja possível visualizar algoritmos diferentes e os seus possíveis resultados.

Algorítmo AStar

Como eu falei no primeiro post desta série eu estou me baseando no BrowserQuest. Um jogo OpenSource de MMORPG criado com HTML, CSS, e JS. Analisando o código do Jogo eu me deparei com um arquivo chamado pathfinding.js que me chamou a atenção, e este arquivo fazia referência à uma LIB chamada AStar. Ao pesquisar mais à fundo, descobri que esta é uma biblioteca utilizada por este jogo para fazer o caminho mais curto à um determinado local. Então, decidi usar a mesma LIB no meu projeto.

O conceito é simples, preciso retornar uma Matriz do meu mapa para o AStar. Esta Matriz possui a referência dos meus Tiles ou bloquinhos que compoem o meu mapa, ou seja, as imagens que aparecem no meu mapa. Cada imagem tem um número de referência. Por Exemplo:

CódigoTransitável
1Não
2Sim

Neste caso eu digo para o AStar que eu só posso andar nas Tiles ou Imagens que tem a graminha representada pelo código 2. Sempre que ele encontrar o código 1 na minha matriz ele vai procurar um caminho alternativo que não passe por este.

O resultado é um Array com todas as posições que o meu personagem precisa passar para chegar ao seu destino.

Algoritmo em ação.

Bem, o meu algoritmo está um pouco zoado em virtude do meu mapa estar um pouco bagunçado. Ainda preciso descobrir como otimizá-lo. Provavelmente eu redesenhe o mapa, otimizando as colisões e etc. Também o tamanho do mapa é um problema, eu não consegui fazer ele andar no mapa todo ainda. Espero conseguir fazer isto na próxima semana.

this.input.on('pointerdown', function (pointer)
    {
        player.playAnimation('idle_down')

        let pathFindingManager = new Pathfinding.PathFinding();
        pathFindingManager.setWalkable(0) // or this.pathFindingManager.setWalkable(0, 10, 11); 
        let col = Math.floor(player.getPositionY() / mapDPosition);
        let row = Math.floor(player.getPositionX() / mapDPosition);
        pathFindingManager.setStart({ col: col, row: row });
        pathFindingManager.setEnd({ col: Math.floor(pointer.worldY / mapDPosition), row: Math.floor(pointer.worldX / mapDPosition) });


        let mapinha = [];
        console.log(game.cache.tilemap.get('zoltan').data.layers);

        let mapaColisao = game.cache.tilemap.get('zoltan').data.layers[1].chunks;

        let tmp = game.cache.tilemap.get('zoltan').data.layers[1].chunks.length;
        for (let i = 0; i < tmp; i++) {
            mapinha.push(mapaColisao[i].data);
        }

        let bestPath = pathFindingManager.find(mapinha);
        for (let i = 0; i < bestPath.length; i++) {

            setTimeout(function ()
            {
                player.setPositionX(bestPath[i].row * mapDPosition);
                player.setPositionY(bestPath[i].col * mapDPosition);
            }, 200 * i);
        }


    }, this);

Conclusão

O Código está bem bruto, mas tem todo o conceito que te falei. Se tiver alguma dúvida, você já sabe onde me encontrar. Por hoje nós ficamos por aqui. Se quiser ver o código na integra dá uma olhada aqui no BitBucket. Até mais 😀

Leave a comment

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Copyright © – Jonatan Pietroski