Onde encontrar algoritmo para criar peças de puzzles? - Dúvidas e Discussão de Programação - Portugal-a-Programar
Onde encontrar algoritmo para criar peças de puzzles?
Por Knitter, 9 de Agosto de 2008 em Dúvidas e Discussão de Programação
Criar linhas curvas em tempo real com uma linguagem de programação não é algo que alguma vez tenha feito ou tenha sequer ideia de como fazer, conhecem algum algoritmo que me permita criar peças de puzzles, pegando numa imagem e recortando dela peças que sejam válidas?
Queria fazer um pequeno puzzle mas falta a parte mais importante, conseguir cortar as peças e não estou a conseguir encontrar grande informação sobre o assunto.
Não conheço nenhum algoritmo, mas estive a pensar como podes fazer isso.
Divides o teu puzzle numa grelha. Depois para cada aresta de cada quadrado verificas se podes dividir as peças (se não forem peças nos limites do puzzle), e geras (esta parte talvez seja a mais difícil) uma curva de Bézier, com pelo menos 2 ponto de controlo entre o ponto médio da aresta, e os cantos do quadrado que fazem ligação com a respectiva aresta. Depois criando vários pontos de controlo na outra peça, utilizas as equações de Bézier para obter a curva. Para unir a superfície criada pela curva e a peça podes utilizar técnicas de CSG, embora não sei bem como funcionam, mas esta parte deve ser relativamente fácil.
Não sei se isto funciona, foi a primeira ideia que me veio à cabeça-
A ideia do Triton parece-me excelente.
A única alteração que sugeria talvez era, em vez de CSG, manteres a noção de grelha durante todo o tempo.
- Primeiro desenhavas a grelha de acordo com o modelo do Triton ou algo semelhante (poderias adicionar pequenos elementos aleatórios).
- Mantinhas em cache o puzzle completo.
- Cada peça era um objecto CPeca sendo que nem precisas de guardar em cache o Fill. Bastava teres a descrição do polyline object e as suas coordenadas, e durante o rendering ias buscar o Fill ao puzzle que está no buffer.
Não sei expliquei isto lá muito bem. Qual é a linguagem?
Uma questão muito interessante sim senhor ! vou gostar de ver os programas do pessoal a surgir!
Realmente não é necessário juntar a curva com as polyline da peça num polígono. Podes manter as duas separadas.
Mas talvez para detecção de colisões depois no jogo seja mais fácil teres a peça reprentada como um polígono completo em vez de curvas/linhas.
Marfig, não percebi bem o que querias dizer com o Fill. Estás a falar da imagem que constitui o puzzle, certo?
Penso que ele está a usar Java, com a biblioteca Slick2D, pelo menos foi o que li no blog dele.
Usar uma curva de Bézier é algo que já estava a tentar aplicar, neste caso o problema nem será tanto criar a curva mas sim recortar a imagem correctamente.
Na maioria das opções que vi, e só encontrei coisas em Flash, o que se faz é criar peças a partir de máscaras, tendo como base as peças já desenhadas, isto é, já ter as imagens que fazem as peças e depois colar e cortar a imagem a partir destes moldes. Isso é algo que não pretendia fazer uma vez que o resultado é muito igual de jogo para jogo. As imagens acabam por ser sempre recordadas da mesma maneira e de forma uniforme.
A linguagem a usar será Java mas desenhar uma grelha implica tornar o puzzle pouco realista e fácil, as peças irão ser demasiado uniformes. Não sei se manter toda a imagem em cache será uma boa opção, além de que estar a recortar a imagem cada vez que precisar de redesenhar o ecrã não me parece muito bom, mas como não tenho, até ao momento, qualquer implementação, não posso confirmar qual a melhor ou pior opção.
Para as colisões, para já não estou a pensar em nada muito complexo, um simples Box Collision deve chegar, depois vejo melhor, pelo que dá jeito ter a peça como uma imagem separada, ou pelo menos ter o tamanho da imagem.
Neste momento estou a trabalhar em vários pequenos jogos e aplicações ao mesmo tempo pelo que esta componente do projecto está ainda em fase de testes, ainda não decidi qualquer interface, uso de swing ou awt, etc. Para já queria apenas ser capaz de recortar uma imagem fornecida por mim, me peças de vários formatos.
Encontrei uma descrição em Lisp, vamos ver se percebo alguma coisa do que está lá escrito
Correcto. O objectivo será não manter a imagem em cada uma das peças. Cada peça descreve apenas a sua forma e coordenadas na grelha. E será responsabilidade do PAINT event prencher o fill do poligono com base na forma e coordenadas. Mas eu estava a pensar em C++... pouco sei de Java. Mas calculo que o processo não à de ser muito diferente(?).
Na maioria das opções que vi, e só encontrei coisas em Flash, o que se faz é criar peças a partir de máscaras, tendo como base as peças já desenhadas, isto é, já ter as imagens que fazem as peças e depois colar e cortar a imagem a partir destes moldes.
É como digo, não conheço Java muito bem. Mas o processo que descreves em Flash é basicamente o que queres. Estou neste momento com uma porcaria de conecção à internet na minha conta Clix ADSL (40kbps downstream! dá para acreditar? Aquilo é mesmo um b minúsculo. Já reportei a avaria) pelo que não consigo ver a documentação do Slick2D em tempo útil. Mas vejo que suporta clipping e alpha buffers. Ora é exactamente isso que tu queres. Com a descrição do poligono, usas estes métodos e outros para recortar a imagem a partir do source (o puzzle completo) em cache.
Bom, a grelha é a melhor opção no meu ponto de vista, uma vez que um puzzle não é mais do que uma grelha. Para evitares um puzzle demasiado uniforme usas elmentos aleatórios na construção das curvas bezier. O que, bem feito até podes ter se quiseres peças de diferentes tamanhos. O mundo estará a teus pés.
Mas tudo o resto é realmente discutível. Depende do tipo de interactividade que queres dar ao puzzle, quantas peças (quanto mais peças, mais tu vais querer ter a imagem completa em cache e desenhar peça a peça. Parece contraditório mas podemos discutir o porquê mais em pormenor depois), etc...
Para as colisões sinceramente não sei. Teria que pensar nisso com mais cuidado. Um Box Colision parece-me bem, mas isso poderá depender do algoritmo de criação das peças que poderia criar peças que não seriam lá muito compatíveis com esse modelo.
Assim à partida preferia não um collision detection, mas um modelo de snapping em que criavas pontos de snap em cada peça e activavas quando esses pontos estivessem a uma distância que tu definirias e os angulos de ambas as peças fossem aproximados. Ms como te digo... isso teria que ser melhor pensado.
Posso avançar com um algoritmo de criação da grelha se tu quiseres...
Tenho estado a ver o que o Java2D me oferece e posso usar um objecto que representa uma forma, um path, que poderá ser uma boa opção.
(...) pelo que não consigo ver a documentação do Slick2D em tempo útil.(...)
Slick2D é uma biblioteca para jogos feita em Java, estamos a falar do mesmo? Não quero usar essa biblioteca, não é multiplataforma como eu quero, estou a estudá-la mas para outras coisas, neste caso quero usar apenas Java/Java2D.
Bom, a grelha é a melhor opção no meu ponto de vista, uma vez que um puzzle não é mais do que uma grelha. Para evitares um puzzle demasiado uniforme usas elmentos aleatórios na construção das curvas bezier.(...)
Sim, estou a começar a virar-me mais para o lado da grelha.
Para já quero conseguir criar as peças, o resto vem depois. Este é um pequeno programa parte de um suite de aplicações que estou a criar para aprender/aprofundar alguns conceitos. Este é um dos vários pequenos jogos que estou a criar para aprofundar Java2D e para conhecer algumas bibliotecas de binding OpenGL, como o caso do Slick2D e outras.
Para já tenho um pequeno puzzle de 8 para rever o funcionamento de tabelas, e um pequeno jogo de 4 em linha para implementar um MinMax/MinMax com Desbaste Alpha-Beta.
Não obrigado, para já, queria ser eu a fazê-lo, o algoritmo não é muito importante mas mesmo assim queria ver consigo fazer isto.