Archive for the ‘EGa2Dengine’ Category

Desarrollo: Dividiendo el espacio

Una de los problemas que aún sigo teniendo, es el problema de rendimiento ya que no puedo conseguir bien los 60 FPS especialmente cuando tengo muchas entidades (itemes, objetos, enemigos, triggers,etc..) creadas en el juego debido a que tengo actualizarlas una por una, aunque estás no se vean en pantalla lo cual implica un costo de tiempo.

Buscando en Internet la mejor alternativa que se podía implementar fácilmente  (o en apariencia)  era implementar un QuadTree. Bueno aunque no seguí al pie de la letra los algoritmos que salen en Wiki pero, el concepto no era tan difícil de comprender.

Así que implementé 3 tipos de clases: la clase QuadTreeNode y sus dos clases hijas QuadTreeNodeLeaf(hoja) y QuadTreeNodeBranch(rama). Puede que no haya seguido la nomenclatura usada comúnmente en la literatura pero me sirve para distinguir bien a las clases 🙂

El QuadTreeNode es una clase abstracta en las cuales defino algunas cosas necesarias como los métodos en común Insertar(Insert),  Preguntar(Query) y Relocalizar(Reallocate) y datos necesarios como la dimensión o el área que representa el nodo y un  puntero de la variable puntero que tiene el padre(El cual lo explicaré más adelante).

[cpp collapse=”true”]
template<typename T>
class QuadTree{
protected:
private:
class QuadTreeNodeLeaf; //class foward
class QuadTreeNode{
protected:
private:
public:
QuadTreeNode **me;
AABB dimension;
QuadTreeNode(QuadTreeNode **m,const AABB &aabb):me(m),dimension(aabb){}
virtual void Insert(Vector2i point, T t) = 0;
virtual bool Query(const AABB &aabb,List<T> &out) = 0;
virtual void Reallocate(QuadTreeNodeLeaf *nodo) = 0;
};
[/cpp]

La clase QuadTreeNodeLeaf es la encargada de guardar un punto(más el dato claramente) que estará distribuido sobre el área del juego.  Esta clase es importante también porque es la encargada de expandir el árbol ya que puede decirse que se transforma en un Nodo interno (QuadLeafNodeBranch) aumentando la altura del árbol.

[cpp collapse=”true”]
class QuadTreeNodeLeaf : public QuadTreeNode{
protected:
private:
public:
T data;
Vector2i point;
QuadTreeNodeLeaf(QuadTreeNode **me,const AABB &aabb,T _data,Vector2i _point):QuadTreeNode(me,aabb) {
data = _data;
point = _point;
}
void Reallocate(QuadTreeNodeLeaf *nodo)
{
//pues que mala suerte, tengo que relocalizar esto ….
QuadTreeNodeBranch *branch = new QuadTreeNodeBranch(me,dimension);
*me = branch; //hacer que me apunte a la nueva rama
branch->Reallocate(this);
branch->Reallocate(nodo);
}
void Insert(Vector2i point, T t)
{
//entonces debemos agregar un nuevo nodo….
//debemos convertir este nodo en un nodo rama
QuadTreeNodeBranch *branch = new QuadTreeNodeBranch(me,dimension); //hacemos que el puntero que me apunta a mí, ahora apunte a este nuevo nodo interno
*me = branch;
branch->Insert(point,t);
branch->Reallocate(this);
}
bool Query(const AABB &aabb,List<T> &out){
if(aabb.containsPoint(point)){
//pues… ya estamos acá, entonces me agrego 😀
out.add(data);
return true;
}else{
return false;
}
}
};
[/cpp]

Y finalmente queda la clase QuadTreeNodeBranch (que es un nodo interno) que es la culpable de dividir el area en 4 partes iguales.

[cpp collapse=”true”]
class QuadTreeNodeBranch: public QuadTreeNode{
protected:
private:
public:
QuadTreeNode *quadrants[4];
QuadTreeNodeBranch(QuadTreeNode **me,const AABB &aabb):QuadTreeNode(me,aabb){
quadrants[0] = NULL;
quadrants[1] = NULL;
quadrants[2] = NULL;
quadrants[3] = NULL;
}
void Insert(Vector2i point, T t){
//dividir el dimension
Vector2i p = dimension.p;
Vector2i e = dimension.e;
Vector2i x(e.x * 0.5, e.y * 0.5);
AABB quad[4] = {
AABB(p+Vector2i( x.x,-x.y), x),
AABB(p+Vector2i( x.x, x.y), x),
AABB(p+Vector2i(-x.x, x.y), x),
AABB(p+Vector2i(-x.x,-x.y), x)
};

for(int i=0; i<4; i++){
if(quad[i].containsPoint(point)){
if(quadrants[i] == NULL){
quadrants[i] = new QuadTreeNodeLeaf(&quadrants[i],quad[i],t,point);
}else{
quadrants[i]->Insert(point,t);
}
break;
}
}
}
void Reallocate(QuadTreeNodeLeaf *nodo){
//dividir el dimension
Vector2i point = nodo->point;
Vector2i p = dimension.p;
Vector2i e = dimension.e;
Vector2i x(e.x * 0.5, e.y * 0.5);
AABB quad[4] = {
AABB(p+Vector2i( x.x,-x.y), x),
AABB(p+Vector2i( x.x, x.y), x),
AABB(p+Vector2i(-x.x, x.y), x),
AABB(p+Vector2i(-x.x,-x.y), x)
};
for(int i=0; i<4; i++){
if(quad[i].containsPoint(point)){
if(quadrants[i] == NULL){
quadrants[i] = nodo;
nodo->me = &quadrants[i];
nodo->dimension = quad[i];
}else{
quadrants[i]->Reallocate(nodo);
}
break;
}
}

}
bool Query(const AABB &aabb,List<T> &out){
if(dimension.overlaps(aabb))
{
bool r = false;
for(int i=0; i<4; i++)
{
if(quadrants[i])
{
r |= quadrants[i]->Query(aabb,out);
}
}
return r;
}
else
{
return false;
}
}
};
[/cpp]

En mi afán de ahorrar memoria, yo agregué un método adicional que lo que hace es relocalizar un nodo y para eso necesité un puntero a la variable que tiene el nodo padré que es a su vez un puntero al nodo hijo (lo llamé me y es un QuadTreeNode**). El asunto es que cada vez que un nodo hoja(QuadTreeNodeLeaf) se convertía en un nodo interno(QuadTreeNodeBranch), tenia que volver a reinsertar el punto que contenía el actual nodo pero, si usaba el método Insert iba a utilizar innecesariamente más memoria(aunque sea poquita). Así que cree una variante de Insert y la llamé Reallocate que lo único que hace es buscar una nueva posición(dentro del árbol) y actualizar los datos del nodo hoja que tuve que reemplazar y asi evitándose una nueva llamada a new.

En este articulo no mostré como hacer un QuadTree solo mostré mi propia implementación de este y los detalles que tuve que considerar, ya que está lo suficienmente explicado en Wikipedia

Sin embargo a pesar que logré exitosamente agregar QuadTree a mi engine, de 8 a 20 FPS que apenas lograba con cierto nivel del juego ahora alcanzo los 40 a 50 FPS. Aún me quedan cosas por mejorar, investigar y que responder para poder llegar decentemente a los 60 FPS.

Desarrollo: Programando con Lua II

Hoy, aprovechando el rato libre que me quedaba decidí seguir programando con Lua. No es mucho lo que hice, es más estoy reprogramando una implementación que hice hace tiempo, le estoy aumentando el acoplamiento para ver si puedo evitar una clase Proxy (aunque con pocas esperanzas).

Hace tiempo atrás me topé con una maravillosa biblioteca se llama luabind que permite por arte de magia integrar Lua a C++, pero no pude integrarla ya que mi tiempo y mis ganas de aprender como funcionaba eran pocas. Por lo que lei necesitaba compilarse de una manera especial con bjam y Boost Build V2, asi que preferí hacer mi propia implementación pero no desde 0, si no modifiqué un ejemplo encontrado en la wiki de Lua Cpp Binding With Lunar. Con excelentes resultados en esa ocasión.

Ahora le agregué lo que hice en el articulo pasado y obtuve esto.

[javascript]
print(entero);
print(string);
test = Test();
test.a = 1;
test.b = 2;
test.c = 2.0;
test.hola = "Hola"
test.a = test:loles(test.b)
funcion(test);
[/javascript]

Codigo en lua a ejecutar

[cpp]
int funcion(lua_State *L){
int n = lua_gettop(L); /* number of arguments */
printf("Numeros de argumentos %dn",n);
//printf("%sn",luaL_typename(L,1));
LuaType v1(L,1);
Test t = (Test)v1;
printf("Test.a = %dn",t.a);
printf("Test.b = %dn",t.b);
printf("Test.c = %fn",t.c);
printf("Test.hola = %sn",t.hola);
lua_settop(L,0); //borramos todo
return 0;
};
[/cpp]

Codigo en C++ de la funcion pasada a Lua

Y el nada glorioso resultado

El resto del codigo, no lo publicaré para no hacer más latoso este tema LOL (aunque si alguien desea, puedo publicar las modificaciones que le hice a Lunar)

Saludos!

Desarrollo: Programando con Lua

Hoy dia, evitando mis quehaceres como siempre.
Me dedique a programar un ratito con Lua, no hice la gran cosa pero vamos bien encaminado.

[cpp]
template
class LuaType {
protected:
private:
T valor; //!< Contiene el valor que estamos Wrappeando
public:
/**
* brief Crea una nueva variable lista, para ser pasada a Lua
*/
LuaType(const T t):valor(t) {};
/**
* brief Extrae un valor en la pila, pero sin borrarlo
*/
LuaType(lua_State *L,int i = -1);

/**
* brief Pone este valor en la sima de la pila de Lua
*
* param L estado actual de Lua
*/
void pushValue(lua_State *L);

/**
* brief Esta funcion permite recuperar el tipo original de la variable
*
* Ejemplo:

* <code>
* LuaType entero(5);
* int variable_normal = (int)entero;
* </code>
* <code>
* LuaType cadena("Hola Lua");
* char *string = (char *)cadena;
* </code>
* return el valor de la variable del tipo de este template
*/
operator T() const {
return valor;
}

};
[/cpp]

Primero lo que fue es crear una plantilla de una clase Wrapper, la cual me permitira extraer y colocar variables entre Lua y C++.

Usando especialización de templates (plantillas) podemos especificar como agregaremos cada tipo de variable en lua.

[cpp]
template<> LuaType::LuaType(lua_State *L,int i) {
if(!lua_isnumber(L,i)) {
luaL_error(L,"Argumento incorrecto");
}
valor = lua_tointeger(L,i);
};

template<> LuaType::LuaType(lua_State *L,int i) {
if(!lua_isnumber(L,i)) {
luaL_error(L,"Argumento incorrecto");
}
valor = static_cast(lua_tonumber(L,i)); // -1 top stack
};

template<> LuaType::LuaType(lua_State *L,int i) {
if(!lua_isnumber(L,i)) {
luaL_error(L,"Argumento incorrecto");
}
valor = lua_tonumber(L,i); // -1 top stack
};

template<> LuaType::LuaType(lua_State *L,int i) {
if(!lua_isstring(L,i)) {
luaL_error(L,"Argumento incorrecto");
}
valor = const_cast(lua_tostring(L,i)); // -1 top stack
};

template<> LuaType::LuaType(lua_State *L,int i) {
if(!lua_isuserdata(L,i)) {
luaL_error(L,"Argumento incorrecto");
}
valor = lua_touserdata(L,i);
};
[/cpp]

Conviertiendo valores de la Pila de Lua a variables en C++

[cpp]
template<> void LuaType::pushValue(lua_State *L) {
lua_pushinteger(L,valor);
}
template<> void LuaType::pushValue(lua_State *L) {
lua_pushnumber(L,valor);
}
template<> void LuaType::pushValue(lua_State *L) {
lua_pushnumber(L,valor);
}

template<> void LuaType::pushValue(lua_State *L) {
lua_pushstring(L,valor);
}

template<> void LuaType::pushValue(lua_State *L) {
lua_pushlightuserdata(L,valor);
}
[/cpp]

Pasando las variables a Lua.

Parece que todo este código es muy engorroso, pero sin embargo nos facilitará más adelante para programar una clase proxy (la que nos facilitará el uso de estructuras o clases definidas en C++ en Lua)

Ejemplo:
[cpp]
#include <cstdio>
#include <cstdlib>
#include <EGa2D/Lua/Type.h>
#include <EGa2D/Lua/Member.h>

using namespace EGa2D;
using namespace Lua;

char *script = "print(string,entero)nfuncion(entero,string)";

int funcion(lua_State *L){
int n = lua_gettop(L); /* number of arguments */
LuaType<int> v1(L,1);
LuaType<char *> v2(L,2);
lua_settop(L,0); //borramos todo
printf("%d %s",(int)v1,(char *)v2);
return 0;
};

int main(int argc,char **argv){
lua_State *L;
L = lua_open();//abrimos lua
luaL_openlibs(L); //con todas sus bibliotecas

LuaType<int> entero = 5;
entero.pushValue(L);
lua_setglobal(L, "entero");

LuaType<char*> string = "Holaaa";
string.pushValue(L);
lua_setglobal(L, "string");

lua_pushcfunction(L,funcion);
lua_setglobal(L, "funcion");

if(luaL_dostring(L,script)){
printf("Error %sn",lua_tostring(L, -1));
}

if(L) {
lua_gc(L, LUA_GCCOLLECT, 0); // collected garbage
lua_close(L);
}

return 0;
}
[/cpp]

La idea de usar un Wrapper de los tipos de variables en C++ no es idea mía pero, lo vi programado en codigo que hacia lo mismo pero para una versión vieja de Lua. Así que quise probarlo y hasta el momento me ha traído algunos beneficios al programar (el código se vuelve más sencillo), y bueno espero poder terminar rápido, para poder implementarle scripting al juego y así volverlo más flexible a la hora de programar

Saludos

Desarrollo: Cargando niveles de Tiled

Ya había logrado cargar niveles con Tiled, aunque tenia un defecto en la física del nivel. Entonces tuve que primero agregar unas cosas que me recomendaron, una capa extra para definir la fisica en el Tiled. Y ya habia ordenado todo el codigo, asi que ahora me disponia a  cargar los niveles hecho en Tiled.


Vista en el editor Tiled. Lo rojo transparente indica que es colisionable

Gracias a esta capa extra y sin muchos problemas (habian unos problemas tontos, pero como siempre no más) pude añadirle la capa fisica que necesitaba el juego.

  Vista en el juego.

Aunque no todo era de color rosa, había algo que me incomodaba en ese momento. Tiled entregaba la capa fisica (los tiles de color rojo transpararente) como una matriz o una secuencia de 0 y 1.

Por ejemplo.

1,0,0,0,1,
1,0,1,0,1,
1,1,1,1,1

Pero box2D trabaja con rectangulos, circulos, lineas y polygonos y además tenia muchos problemas con la logica del juego como por ejemplo un fantasma que camina a lo largo de una plataforma no lograba caminar correctamente porque creia que su plataforma era más pequeña de lo que se veia. Entonces ¿Como podia pasar de las colisiones que estan en una matriz a muchos rectangulos?

Bueno como esa ocasión estaba apurado hice un algoritmo bastante ingenuo (sencillo o basico)

[cpp]
//codigo
uint16 *data; //es la matriz con los datos guardada en un arreglo
int layer_w,layer_h; // dimensiones de la matriz
//necesitamos procesar todos los rectangulos
Rect **r = new Rect*[layer_w];
for(int i=0; i<layer_w; i++) {
r[i] = new Rect[layer_h];
}
//agregamos los datos en los rectangulos
for(int y=0; y<layer_h; y++) {
for(int x=0; x<layer_w; x++) {
if(data[y*layer_w+x]) { //todo colisionable
r[x][y] = Rect(x,y,1,1);
}
}
}
//ahora aplicar el algoritmo ingenuo
//!todo optimizar el algoritmo ingenuo
for(int x=0; x < layer_w; x++) {
for(int y=0; y < layer_h; y++) {
Rect a = r[x][y];
if(a.width !=0 || a.height != 0) {
//buscar
for(int i=x; i<layer_w; i++) {
for(int j=y; j<layer_h; j++) {
Rect v = r[i][j];
if(v.width != 0 || v.height != 0) {
Rect suma = a + v;
//se pueden fusionar y son los mismos datos
if(suma.area() == a.area()+v.area() && data[layer_w*y+x] == data[layer_w*j+i]) {
r[x][y] = suma;
a = suma;
r[i][j].width = 0;
r[i][j].height = 0;
}
}
}
}
}
}
}
[/cpp]

Algoritmo sencillo en C++, se basa en crear una matriz de rectangulos de dimension 1×1 que reprensentan los 1s en las matrices y que pueden sumarse si hay algun rectangulo contiguo.

Luego en Box2D, consideraba los rectangulos que tuvieran Area distinto de 0 quedando esto.

Vista actual del juego después de la optimización

Lo que me permitia, que mis fantasmas u otro enemigo, pueda ver correctamente la plataforma y caminar a lo largo de ella.

Saludos

Desarrollo: Organizando y expandiendo

Uno de los tantos problemas que tenia mi motor (aparte del hecho que reinvencion de rueda) era la carga de Niveles que estaba muy mal programada. Aunque funcionaba pero, cada vez que tenia que agregar una funcionalidad nueva me costaba mucho y por lo tanto muchos dolores de cabeza también. Pero se me ocurrio una idea que tal si, cada tipo de nivel (formato, o como quieran llamarle) ¿Lo lea en distintas clases? Bueno talvez sea muy engorroso lo que planeo, pero actualmente tenia dos tipos de archivos de niveles, uno exclusivo para los actores(Entidades, Objetos de juego o como prefiera decirle) y otro exclusivo para el nivel (escenario, fisica, logica, etc…) entonces por eso me decidi en dos clases distintas y como soy un poco ambicioso hice una clase abstracta que el “Lector de Niveles” en caso de agregar muchas más cosas. Bueno la implementación de este lector fue bastante sencillo e inclusive más de lo que me esperaba, consta de una simple lista con los lectores distintos lectores ya añadidos y cuando quiero leer un nivel reviso su extension de archivo el cual uso para distingir que clase usar.

Cuando se llama LeerNivel en Contexto, lo que ocurre realmente este busca que Reader usar y finalmente lee el nivel con el Reader seleccionado.

Otro de los problemas que me tuve que solucionar era de como podia manejar los tantos niveles que podria tener, eso si la solución fue bastante estupida porque ya lo habia solucionado pero personalmente no aceptaba que deberia funcionar asi. Queria que un manejador de escena maneje muchas escenas, pero en vez de eso decidí que solo manejara una y que un algo superior manejara muchos manejadores de escenas, lo cual es mucho más limpio y ordenado según mi punto de vista. Lo más importante es que siempre mantengan simple y funcional su codigo.

Y el ultimo problema, aunque este solo fue copy and paste (jaja) es que cada actor podia modificar el entorno que lo rodea, entonces tenia que pasarle un puntero a Contexto.

En conclusión, mi motor no sera del todo poderoso y eficaz, pero se acerca cada vez a una version final y madura del mismo.

Saludos