Estrutura de Dados
André Augusto Nogueira Alves
[email protected]
Colaborador: Alexandre Tolstenko Nogueira
Papel e caneta na mão!
REVISÃO
Revisão
1. Diferença entre IDE, Framework, Engine
e SDK;
2. Estrutura básica de um game em XNA;
3. Rectangle vs Vector2;
4. Desenhar uma imagem na tela;
5. Desenhar um texto na tela;
6. Colisão com com instersect.
4
OBJETIVOS
Objetivos
1. Entender um pouco de OO (Orientação
Objeto);
2. Apresentação de algumas das estruturas
de dados mais simples;
3. Um novo jogo ao fim da aula, mas dessa
usando os tópicos citados acima;
6
ORIENTAÇÃO OBJETO E ESTRUTURA
DE DADOS
Teoria
Prática
Teoria
História
Conceitos
POO
Listas
Árvores
Objetos
PongOO
Interação
Snake
Apêndice
Campeonatos
História
• Final da década de 60;
• Possibilitar compartilhamento de códigos
e desenvolvimento mais rápido;
10
Conceitos
• Desvendando os mistérios da Classe;
• Abstração: Abstração é o processo ou resultado de
generalização por redução do conteúdo da
informação de um conceito ou fenômeno observável;
• Classe x Objeto;
• Alocar memória (construtores);
• DNA(assinatura da classe) x Humano(objeto);
11
Objetos
• Alta coesão, baixo acoplamento;
• Tentativa de representar o mundo do ponto de
vista humano de forma computacional;
• Semelhanças com Structs;
• Visibilidade;
• Criando um objeto;
12
Pong OO - Bola
13
Pong OO - Raquete
14
Interação – Acoplamento(?)
•Juntando os objetos;
•Montando uma colisão;
15
Teoria
POO
Enum
Estruturas
Vetor
Snake
Listas
Apêndice
Campeonatos
Árvores
Enum
• Diferenças entre C e C#;
• Usos do Enum;
17
Vetor
• Prós e Contras;
18
Teoria
POO
Enum
Estruturas
Vetor
List
Snake
Listas
LinkedList
Apêndice
Campeonatos
Árvores
Pilha
Fila
Lista
• Exemplos de usos;
20
List
List<Tipo> myList;
Utilidade: agregar coisas sem garantir sequência
21
Lista Ligada
LinkedList<Tipo> listTipo;
LinkedListNode<Tipo> llnTipo;
Uso: llnTipo.Next, llnTipo.Previous
Utilidade: agregar coisas com com sequência.
22
Pilha
Stack<tipo> stkTipo;
Uso: stkTipo.Pop, stkTipo.Push
Utilidade: Armazenar coisas temporariamente (ex.
Gerência de tela, recursão)
23
Fila
Queue<tipo> qTipo;
Uso: qTipo.Pop, qTipo.Push
Utilidade: guardar coisas enquanto elas esperam para
serem executadas.
Ex:
24
Teoria
POO
Enum
Estruturas
Vetor
Snake
Listas
Binárias
Apêndice
Campeonatos
Árvores
Quadtree
Octree
BSP
Árvores
•
•
•
•
Definição
Árvore Binária;
Quadtree (Octree);
BSP;
26
...
Lista de outras estruturas
Splaytree
Btree
Red-black tree
Hash table
Grafos
Dicionários
27
Estrutura de dados e classes
• Classes que incluem vários objetos;
28
Teoria
Classe vs Struct
Listas
Árvores
História
Snake
Mecânica de
jogo
Apêndice
Campeonatos
Modelagem
Computacional
Códigos
Prática
• Prática:
– Programar um SNAKE;
• Opcional: transformar o Pong em um Breakout;
• Desafio:
– Mapear uma imagem usando uma
quadtree;
– Defender;
30
Snake Time
• Jogo do dia: Snake;
• Programado usando OO não estruturada;
31
Análise de Jogo
• Elementos?
• Como anda?
• Como interage?
32
Mecânica de jogo
• A cobra tem que “comer” os pontos que
aparecem na tela;
• A cada item comido, a cobra cresce de tamanho;
• A cobra anda somente para as direções Up, Left,
Right e Down;
33
Modelagem Computacional
• Classes a serem criadas;
• Métodos de cada uma dessas classes;
• Interação entre elas;
34
Teoria
Classe vs
Struct
Listas
Árvores
Snake
Apêndice
Campeonatos
XNA
Challenge
SBgames
Arena Info
Dreambuild
Imagine Cup
Struct
public struct RectangleFloatS
{
public float X, Y;
public RectangleFloatS(float X, float Y)
{
this.X = X; this.Y = Y;}
public Anda(Direcao dir)
{switch(dir){
case Direcao.Up:
//anda pra cima
break;
...}}
}
36
Class
public class RectangleFloatC
{
public float X, Y;
public RectangleFloatC(float X, float Y)
{
this.X = X; this.Y = Y;}
public Anda(Direcao dir)
{switch(dir){
case Direcao.Up:
//anda pra cima
break;
...}}
}
37
Diferenças
List<RectangleFloatS> rectStructList;
List<RectangleFloatC> rectObjList;
...
foreach(RectangleFloatS rect in
rectStructList)
rect.X += valor; // nao altera X do rectStructList
foreach(RectangleFloatR rect in rectObjList)
Rect.X += valor; // altera X do recObjList
38
Agradecimento
spriteBatch.DrawString(
Arial,
"Obrigado Pela Atenção!",
positionVect,
Color.Black);
39