| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 18.14 MB | Adobe PDF |
Authors
Advisor(s)
Abstract(s)
Path search algorithms, i.e., pathfinding algorithms, are used to solve shortest path problems
by intelligent agents, ranging from computer games and applications to robotics. Pathfinding
is a particular kind of search, in which the objective is to find a path between two nodes. A
node is a point in space where an intelligent agent can travel. Moving agents in physical or
virtual worlds is a key part of the simulation of intelligent behavior. If a game agent is not able
to navigate through its surrounding environment without avoiding obstacles, it does not seem
intelligent. Hence the reason why pathfinding is among the core tasks of AI in computer games.
Pathfinding algorithms work well with single agents navigating through an environment. In realtime
strategy (RTS) games, potential fields (PF) are used for multi-agent navigation in large
and dynamic game environments. On the contrary, influence maps are not used in pathfinding.
Influence maps are a spatial reasoning technique that helps bots and players to take decisions
about the course of the game. Influence map represent game information, e.g., events and
faction power distribution, and is ultimately used to provide game agents knowledge to take
strategic or tactical decisions. Strategic decisions are based on achieving an overall goal, e.g.,
capture an enemy location and win the game. Tactical decisions are based on small and precise
actions, e.g., where to install a turret, where to hide from the enemy.
This dissertation work focuses on a novel path search method, that combines the state-of-theart
pathfinding algorithms with influence maps in order to achieve better time performance and
less memory space performance as well as more smooth paths in pathfinding.
Algoritmos de pathfinding são usados por agentes inteligentes para resolver o problema do caminho mais curto, desde a àrea jogos de computador até à robótica. Pathfinding é um tipo particular de algoritmos de pesquisa, em que o objectivo é encontrar o caminho mais curto entre dois nós. Um nó é um ponto no espaço onde um agente inteligente consegue navegar. Agentes móveis em mundos físicos e virtuais são uma componente chave para a simulação de comportamento inteligente. Se um agente não for capaz de navegar no ambiente que o rodeia sem colidir com obstáculos, não aparenta ser inteligente. Consequentemente, pathfinding faz parte das tarefas fundamentais de inteligencia artificial em vídeo jogos. Algoritmos de pathfinding funcionam bem com agentes únicos a navegar por um ambiente. Em jogos de estratégia em tempo real (RTS), potential fields (PF) são utilizados para a navegação multi-agente em ambientes amplos e dinâmicos. Pelo contrário, os influence maps não são usados no pathfinding. Influence maps são uma técnica de raciocínio espacial que ajudam agentes inteligentes e jogadores a tomar decisões sobre o decorrer do jogo. Influence maps representam informação de jogo, por exemplo, eventos e distribuição de poder, que são usados para fornecer conhecimento aos agentes na tomada de decisões estratégicas ou táticas. As decisões estratégicas são baseadas em atingir uma meta global, por exemplo, a captura de uma zona do inimigo e ganhar o jogo. Decisões táticas são baseadas em acções pequenas e precisas, por exemplo, em que local instalar uma torre de defesa, ou onde se esconder do inimigo. Esta dissertação foca-se numa nova técnica que consiste em combinar algoritmos de pathfinding com influence maps, afim de alcançar melhores performances a nível de tempo de pesquisa e consumo de memória, assim como obter caminhos visualmente mais suaves.
Algoritmos de pathfinding são usados por agentes inteligentes para resolver o problema do caminho mais curto, desde a àrea jogos de computador até à robótica. Pathfinding é um tipo particular de algoritmos de pesquisa, em que o objectivo é encontrar o caminho mais curto entre dois nós. Um nó é um ponto no espaço onde um agente inteligente consegue navegar. Agentes móveis em mundos físicos e virtuais são uma componente chave para a simulação de comportamento inteligente. Se um agente não for capaz de navegar no ambiente que o rodeia sem colidir com obstáculos, não aparenta ser inteligente. Consequentemente, pathfinding faz parte das tarefas fundamentais de inteligencia artificial em vídeo jogos. Algoritmos de pathfinding funcionam bem com agentes únicos a navegar por um ambiente. Em jogos de estratégia em tempo real (RTS), potential fields (PF) são utilizados para a navegação multi-agente em ambientes amplos e dinâmicos. Pelo contrário, os influence maps não são usados no pathfinding. Influence maps são uma técnica de raciocínio espacial que ajudam agentes inteligentes e jogadores a tomar decisões sobre o decorrer do jogo. Influence maps representam informação de jogo, por exemplo, eventos e distribuição de poder, que são usados para fornecer conhecimento aos agentes na tomada de decisões estratégicas ou táticas. As decisões estratégicas são baseadas em atingir uma meta global, por exemplo, a captura de uma zona do inimigo e ganhar o jogo. Decisões táticas são baseadas em acções pequenas e precisas, por exemplo, em que local instalar uma torre de defesa, ou onde se esconder do inimigo. Esta dissertação foca-se numa nova técnica que consiste em combinar algoritmos de pathfinding com influence maps, afim de alcançar melhores performances a nível de tempo de pesquisa e consumo de memória, assim como obter caminhos visualmente mais suaves.
Description
Keywords
Influence Maps Inteligencia Artifical Pathfinding Spatial Reasoning