Graduando

Universidade Federal de Santa Maria
Departamento de Eletrônica e Computação
Prof. Cesar Tadeu Pozzer
Disciplina: Estruturas de Dados [e-mail] 10/06/2010

1. Teoria dos Grafos
Grafo é ma ferramenta muito comum em jogos. Podem ser utilizados para permitir um personagem viajar de um ponto a outro de modo eficiente, para decidir a próxima estratégia em um jogo ou para resolver um puzzle. O uso mais comum de grafos é para representar a rede de caminhos que um personagem pode navegar no ambiente. Na Figura 1 são apresentados vários exemplos de grafos. Os grafos podem ser conexos (Figuras A, B, C e D) ou não conexos (Figuras E e F). Um grafo é dito conexo quando se pode traçar um caminho que parte de qualquer nó e chega a qualquer outro. Um grafo é dito completo quando há uma aresta entre cada par de seus vértices. Se as arestas do grafo são orientadas, o grafo é chamado orientado. Para uma lista completa de definições, consulte
[1].

(a)

(d)

(b)

(c)

(e)

(f)

Figura 1: Exemplos de Grafos. Somente os grafos A, B, C e D são conexos

1.1. Notação Formal
Um grafo G pode ser formalmente definido como um conjunto de nós ou vértices, V, ligados por um conjunto de arestas A. Isso é geralmente escrito na forma:
G = {V, A}
Se os nós de um grafo forem numerados com um valor inteiro em um intervalo de 0 a (N-1), uma aresta pode ser referenciada pelos nós que ela conecta, como por exemplo 3-5.

1

Muitos grafos possuem pesos associados às arestas. Esse peso pode representar o custo necessário para mover de um ponto a outro do grafo. Esse custo pode ser dado em função da distância entre os vértices ou pela dificuldade de locomoção. Em jogos, regiões montanhosas ou que são mais propensas a ataques de inimigos podem ter um custo maior que regiões planares e com abrigo contra ataques de inimigos. Durante a fase de criação de cada cenário, o próprio game designer pode atribuir pesos diferenciados a cada região do mapa, ou
mais