EP4

EP4

por Susanna Rezende -
Número de respostas: 24
Não tenho certeza se o enunciado da parte de ED está completo. Eu reli várias vezes e estou com alguma dúvidas:

1 - "Visando aumentar a eficiência de nosso joguinho, [...] em sua posterior impressão na tela [...]" - Dado que em cada instatne preciso imprimir todos os, digamos n, objetos, e como estamos usando uma biblioteca gráfica isto já leva ONão. Não vejo como a ED "sugerida" sorriso pode tornar isto mais eficiente.

2 - "Existem dois principais tipos de pontos em S, asteróides e cristais." - Isto não quer dizer que os phasers e as naves não fazem parte da árvore, certo?

3 - "Evento 1: um ponto p1 de S é x-menor que um ponto p2 no instante ti, porém, é x-maior no instante ti+1 (supondo uma árvore limite, somente a árvore principal deverá ser reajustada - consumo de tempo O(log n))." - Não vejo porque não seria necessário atualizar também algumas das estruturas associadas. No exemplo da figura: não precisamos atualizar, por exemplo, a estrutura associada ao nó interno que contém p2 da árvore principal? Antes esta árvore associada continha os pontos p2 e p3, mas agora deve conter os pontos p2 e p7, certo?

4 - E o evento "saiu da tela"? devo implementar algo semelhante ao evento 3, mantendo um fantasma?

5 - E o evento "surgiu na tela"? devo implementar inserção? Não foi dito que árvores limites não são uma boa estrutura para se implementar inserção?

6 - Supondo que mantenho os meus pontos fantasmas, após um certo tempo praticamente todos os meus objetos inicialmente na tela foram trocados por novos. Então posso ter duplicado o número de objetos na árvore, sendo que metade deles são "dummies". Isto não torna o algoritmo cada vez mas ineficiente?

7 - Como os objetos tem raio, devo armazenar 2 pontos para cada objeto? (centro +/- raio)

Obrigada!
Em resposta à Susanna Rezende

Re: EP4

por Alvaro Junio Pereira Franco -
Oi Susanna,

1 - Você não vai escrever todos os pontos na tela. Você deve escrever somente os que estão na tela (em uma janela). Todos os pontos estão na sua ED mas alguns estão na tela.

2 - Acho que a nave e os tiros (por serem poucos - uma nave e, sei lá, cinco tiros, por exemplo-) podem ser tratados fora da ED.

3 - Você tem razão. A árvore associada que você cita deve ser alterada. Ainda outras devem ser alteradas. Me cobre (no sentido de cobrança, não sei se escrevi certo) isso em um plantão.

4 - Um ponto sai da tela quando ele não está em uma janela (tela). Este ponto não deve sair da ED. Ele já estava lá e deve continuar lá.

5 - Um ponto entra na tela quando ele está em uma janela (tela). Este ponto não deve entrar na ED. Ele já está lá.

6 - Os pontos fantasmas deixarão as buscas cada vez mais ineficiente. Estes pontos não existirão se você implementar uma AVL ou Rubro-Negra.

7 - Acho que não.

Se eu não respondi alguma questão, por favor, me procure no plantão.
Em resposta à Alvaro Junio Pereira Franco

Re: EP4

por Eduardo Apolinário -

Olá,

Gostaria de saber quando vai estar disponivel o enunciado do EP4 e qual a previsao de entrega das notas do EP2?

Obrigado!

Em resposta à Alvaro Junio Pereira Franco

Re: EP4

por Francisco Zigmund Sokol -
O tratamento daqueles eventos descritos no enunciado do EP4 só servem para a estrutura da árvore limite?
As mudanças que eu teria que fazer numa AVL para tratar aqueles eventos não iguais, pois o "vizinho" de um ponto no plano não necessariamente é seu irmão, ou é?
Em resposta à Francisco Zigmund Sokol

Re: EP4

por Alvaro Junio Pereira Franco -
Olá,
Serve para qualquer árvore de busca binária desde que todos os pontos do conjunto estejam armazenados nas folhas.

Em uma AVL,as mudanças para tratar um evento são iguais, desde que todos os pontos estejam armazenados nas folhas.

As mudanças ocorrem em folhas "vizinhas" não necessariamente irmãs.
Em resposta à Susanna Rezende

Re: EP4

por André Casimiro -
Temos na descrição do EP como tratar os possíveis eventos entre dois pontos consecutivos. Mas como vamos detectar a ocorrência desses eventos?
Se ao fazer isso tivermos de checar todos os pontos então teremos a eficiência da estrutura limitada pelo número de pontos O(n lg n), certo?

No momento, temos uma matriz esparsa implementada e conseguimos simular com uns 500 asteróides a uma taxa de 40 FPS tranguilamente.
Na real? Ficamos muito desmotivados em ter de implementar uma ED nova para nem ao menos ver o ganho de eficiência (pois vamos simular algo "jogável", algo como 50 objetos na tela) e pior, mudar as regras do jogo para se adequar a isso.

Então, quais as consequências de não usarmos a ED proposta? Em termos de nota mesmo? E se o jogo se mostrar robusto, jogável, e "super legal"?

Com relação a ED, teríamos de fazer o EP-Sub?


Sinceramente,
André.
PS: postei a mesma imagem no fórum de Labprog.
Em resposta à André Casimiro

Re: EP4

por Carlos E. Ferreira -
Olá André e demais,

A ideia da ED é tornar a busca de pontos que se mexem que estão dentro de uma janela mais eficiente. Imagine que você tem um espaço muito maior do que cabe na tela, e quer determinar que asteroides estão no espaço perto de sua nave. É para esse problema que a ED faz sentido. Se vocês vão ter de verificar todos os 500 pontos para imprimir, como disse a Susanna, não tem graça implementar essa estrutura complicada.

Ou seja, para fazer sentido o espaço tinha de ser basicamente infinito (como aliás é), e ter alguns milhões de asteroides se movendo. Aí você podia dividir sua tela entre as duas naves (cada uma enxerga um pedaço do espaço).

Montada a árvore você pode verificar quando vai acontecer o próximo evento (você pode colocar, por exemplo num heap os tempos em que vão acontecer os próximos eventos). Quando esse evento ocorre você o trata, calcula os novos eventos relacionados com estes objetos e inclui na lista (heap). Note que tudo anda bem eficiente dessa forma. Se vocês quiserem, podem aparecer na monitoria do Alvaro na terça e ele explica direitinho, ou então me perguntem durante a aula.

Com relação à sua pergunta sobre "nota mesmo", sem problemas. O EP sub estará no ar em breve. Se vocês acharem mais fácil fazer o Ep sub do que fazer a ED sugerida para o projeto de LabProg, fiquem à vontade.

Abraços,

--
carlinhos
Em resposta à Carlos E. Ferreira

Re: EP4

por André Casimiro -
Entendi. De fato nesse caso a estrutura de árvore limite seria muito interessante.

Acontece que as regras do nosso jogo foram definidas de forma diferente.
As naves não iriam mais colidir com a borda (já que o espaço é infinito) e também seria ncessário que cada jogador tivesse sua própria tela (afinal cada jogador pode mover a nave para onde bem entender).

A pergunta é: devemos mesmo sacrificar as várias horas de programação e teste das outras fases alterando as regras do jogo na última fase para utilizar uma ED eficiente?
Essa resposta cabe ao pessoal de Labprog (que ainda não respondeu no outro fórum, estamos no aguardo)


Abraços,
André.

PS: sei que a intenção foi dar "uma aliviada", mas no geral parece não valer a pena (queremos fazer um joguinho legal!)
Em resposta à André Casimiro

Re: EP4

por Felipe Torres -

André,

acredito que a nave continuaria colidindo com a borda da tela, pois a idéia do espaço "infinito" seria implementada através de uma tela virtual.

A tela que nós veriamos (e as navezinhas voariam) seria, no final das contas, uma "janela" de um espaço muito maior, onde os asteróides já estariam inseridos.

Abraços!

PS.: também estou relutante em mudar minha estrutura... =/

Em resposta à Felipe Torres

Re: EP4

por André Casimiro -
Acho que não, Felipe.

A forma que está proposta (pelo menos foi como a Ana me explicou após ela ter conversado com o próprio carlinhos) é que o espaço seria "infinito" (muito grande) e a tela iria se mover de acordo com a movimentação da nave, saca?


Abraços.
Em resposta à André Casimiro

Re: EP4

por Carlos E. Ferreira -
Sim, é essa a idéia: cada nave só enxerga o pedaço do espaço perto dela.

Respondendo ao Fernando, quem não está fazendo LabProg pode fazer só a parte da estrutura (em grupos de até 3) ou escolher fazer o EP sub.

--
carlinhos
Em resposta à Susanna Rezende

Re: EP4

por William Gnann -
Dado que os asteróides e outros corpos celestes quaisquer se movimentam, supondo um quadro onde todos acabem se movimentando, terei, basicamente, de reconstruir a árvore?
Em resposta à Susanna Rezende

Re: EP4

por Ricardo Oda -
Se eu tenho uma árvore indexada pela coordenada x com fios nas folhas, consigo facilmente uma lista de pontos entre x1 e x2 do retângulo.

Por que preciso de uma árvore indexada por y, se eu vou precisar percorrer essa lista que obtive para separar os pontos no retângulo (x1, y1), (x2, y2)?

Não seria esperto pegar outra lista com pontos entre y1 e y2, e comparar com a primeira lista. Posso simplesmente percorrer a lista, checar a coordenada y de cada ponto, e interagir com ele.

Gostaria de saber se posso usar somente 1 árvore indexada pelo x.
Em resposta à Ricardo Oda

Re: EP4

por Alvaro Junio Pereira Franco -
Oi Ricardo,

Eu acho que você está falando da segunda versão do quarto ep. Nessa versão todos os pontos que estão na árvore estão também no retângulo. Você usará as árvores para descobrir com quais eventos um ponto está envolvido. Para descobrir os eventos relacionados a $x$-coordenada você usa a árvore da $x$-coordenada. Para descobrir os eventos relacionados a $y$-coordenada você usa a árvore da $y$-coordenada.
Em resposta à Alvaro Junio Pereira Franco

Re: EP4

por William Gnann -
Na prática, isso não restringiria o espaço a todo intervalo de x ou todo intervalo de y (em vez de restringir somente à intersecção do intervalo de x e do intervalo de y)?
Em resposta à Susanna Rezende

Re: EP4

por Ricardo Oda -
Quando tenho estruturas uma apontando para a outra, tenho que usar ponteiros voids + casting.

Em vez disso, posso fazer um arquivo x.h, por todos typedefs nele, e incluir nos outros headers?
Ou isso seria algo muito estranho e/ou uma má pratica de programacao?
Em resposta à Ricardo Oda

Re: EP4

por William Gnann -
Um módulo com as estruturas parece bastante conveniente. (eu fiz algo parecido no EP2 de Lab e o monitor não reclamou) =P
Em resposta à William Gnann

Re: EP4

por William Gnann -
Tem alguma forma de eu provar que o último elemento de uma sequência crescente e de tamanho K subtraído de um E (algo menor K/50) continua maior que a maioria dos outros elementos acrescidos de um E dessa sequência. Ah sim! A distância mínima entre a( n) e a(n-1) é maior que E/K.

Ou isso é falso?
Em resposta à Susanna Rezende

Re: EP4

por André Casimiro -
Oi, sou eu de novo!

Fizemos a implementação de uma "arvore limite não balanceada" (pontos nas folhas e arvores de segundo nível para todos os nós da árvore) para o EP4 mas estamos com dificuldade (leia-se sem tempo também) para integrar essa ED ao jogo.

Professor, para a parte de MAC323 podemos entregar uma simulação visual (na allegro) onde todos os objetos são círculos e cada um tem um tipo (cor)? Os objetos se movimentam, as mudanças na estrutura são tratadas quando ocorrem eventos entre eles (tiro, nave, asteróide e cristal...). Na prática, a diferença é não ser jogável.Ok?

Aí não iríamos unir isso ao código do jogo propriamente dito, visto que não haverá descontos por parte de Labprog se não usarmos a ED.


Abraços.

Em resposta à Susanna Rezende

Re: EP4

por Vitor Onuchic -
Olá,

O que é um campo desintegrador? Podemos fazer simplesmente que se a nave se chocar com um asteroide os dois são removidos e a nave é inicializada novamente na árvore?
Eu não estou fazendo labprog, então eu tabem não sei quando é fim de jogo... Posso simplesmente avisar que a nave foi destruida quando isso acontecer e recolocá-la na estrutura depois?