Entradas en "c++"

Maestros de la indirección

Publicado por LaNsHoR el 29/10/2013 en Problemas | 0 comentarios

Este problema lo diseñé hace unos años, cuando le daba clases a mi amiga Marta para preparar su examen final de programación en la universidad. En cuestiones de punteros en C++ soy de los que piensan que no hay medias tintas; o eres capaz de resolver este ejercicio en unos minutos (cuatro o cinco de media, aunque el tiempo no es importante), o no te has enterado de nada.

Esta vez no hay premio porque para obtener la solución sólo hay que compilarlo y ejecutarlo. Papel, lápiz y 300 segundos: ¿Cuál es la salida del programa?

PS: Marta por supuesto sacó un 10!
PS2: No hay punteros a funciones porque esta vez no entraban en el temario.

#include <iostream>

int main()
{
   void *x[2];
   char *y=(char*)new void*[3];
   void *z=y;
   *x=&z;
   *(void**)y=(((char*)x)+sizeof(void*));
   y+=2*sizeof(void*);
   x[1]=(void*)y;
   *((void**)x[1])=(void**)z+1;
   *((char**)z+1)=new char[1<<4];
   ((void**)z)[0x2]=((void**)z)+1;
   y=((char**)z)[1];
   y[0]=y[1]=*(y+2)=*&y[3]=0140;
   y[3]+=&x[1]-x;
   y[2]+=(((void**)x[1])-(void**)z)*0x6;
   *(&(*(&(*(&(*y))))))+=8;
   *(&(*(&(*(&(*(y+1)))))))+=017;
   y[4]=(1<<5)%(1<<6);
   y[5]='6'*2+1;
   *(y+0x6)=*((**(char***)*(x+1))+3);
   y[(1<<3)-1]=*y==228?*y/(char)2:(char)57*2;
   y[(1<<3)-0]=y[(1<<3)-1]+2;
   y[(1<<3)+1]=*(y+6);
   y[012]=0x21;
   y[013]=y[012]-23;
   y[014]=y[013]-10;
   std::cout<<******(char*******)x;
}

Leer más

Ligando LUA con C++

Publicado por LaNsHoR el 24/10/2013 en Scripting | 1 comentario

A nivel de ingeniería computacional, un juego abarca casi todos los ámbitos y los explota llevándolos al extremo, marcando la evolución y la capacidad del progreso y la tecnología. Resulta extraño que un segmento que pertenece a la industria del ocio (y que factura más que las industrias del cine y la música juntas) sea con mucho el motor principal de investigaciones en materiales y arquitecturas hardware y software de las dependen el resto de avances realmente “relevantes” para la sociedad… pero es una cuestión de dinero, y la vida es así.

Computación gráfica, inteligencia artificial, comunicaciones de baja latencia todos a todos, sintetizadores y recreadores de sonidos, sistemas de archivos virtuales locales y en la nube, generación procedural… es difícil encontrar un ámbito cuyo máximo exponente no esté representado en esta industria.

A mediados de los 90 la complejidad de los juegos había crecido hasta un límite en que los poderosos motores quedaban desaprovechados por las limitaciones de las configuraciones que admitían. A pesar de ser bastante dinámicos y abiertos (para esa época) sólo se permitían configuraciones sencillas que fueran rápidas de procesar. Cualquier cambio mayor requería compilar el juego entero (o gran parte de él), algo que entonces suponía varios días y dificultaba extraordinariamente la creación de parches, por lo que las nuevas modificaciones eran difíciles de distribuir.

Así surgió la necesidad de incorporar motores de script a los videojuegos, haciendo que parte del código del juego fuese soportado en scripts de texto plano que se podían cambiar en cualquier momento sin necesidad de compilar. Muchos juegos tuvieron su propio lenguaje de script, a menudo muy limitado, pero que permitía con mayor o menor suerte lograr un entorno dinámico y configurable.

La variabilidad entre leguajes de script era enorme; casi a una por estudio y generación. Hasta que por fortuna, en 1993 nació LUA, un lenguaje “semi”-interpretado que destacaba por su velocidad y su capacidad de extensión. No era puramente interpretado puesto que los scrips se podían compilar (al vuelo o no) a bytecode, usando una máquina virtual para su ejecución. Su flexibilidad, su licencia, y su genial integración con C hicieron que desde entonces miles de juegos lo adoptasen en masa.

LUA fue usado en toda la saga de Baldur’s Gate, por ejemplo, y también es la base del motor de interfaz de World Of Warcraft. Heroes V, Crysis, Mods del Half-Life 2… etc.

Y hasta aquí, la lección de historia.

(***)

En mi opinión, la pega más importante de LUA es su integración con C++ (que no con C). Hacer los “bindings” entre clases LUA/C++ es una tarea tediosa y a menudo insoportable para la gente que, como yo, no quiere perder el tiempo escribiendo lo mismo 2 veces (por no hablar de los problemas de mantenimiento que eso supone). Sin embargo, hace algunos años, cuando trabaja en el motor para un generador de juegos de rol en 3D, desarrollé una ingeniosa solución a este engorroso tema que evita duplicar código C++ en LUA y nos da acceso a objectos y clases de C++ en LUA sin complicaciones; y de eso voy a hablar hoy.

La solución implica renunciar al orientado a objetos en LUA, pero podremos usar las clases de C++ mediante funciones al estilo C en LUA. Por ejemplo, si tenemos una clase “Player” en C++, que tiene un método “Poison()”, en LUA podremos hacer algo cómo:

Poison(player);

Es decir, renunciamos a la sintaxis de OO, a la herencia y a la encapsulación (algo no imprescindible en un script de última capa), pero podremos trabajar con todos los métodos originales de clases escritas en C++ (los métodos siguen existiendo). Dado que los scrips en los juegos suelen ser muchos pequeños paquetes, es bastante cómodo trabajar así y crear nuestros propios comandos KISS.

(***)

La idea:

La idea es que todos los objetos C++ tengan un identificador númerico único. En C++ crearemos los comandos que recibirán un número que será el ID del objeto con el que trabajaremos (además de otros argumentos necesarios para el comando en cuestión).

Por ejemplo, veamos el siguiente código en LUA:

lanshor=newPJ("LaNsHoR",100);

El método newPJ(“LaNsHoR”,100) crea un objeto Player (en C++ desde LUA) llamado “LaNsHoR” y que tiene 100 puntos de vida. La línea anterior puede dar a entender que un objeto Player análogo en LUA se ha guardado en la variable “lanshor”, pero realmente sólo se ha guardado un entero: el identificador único del objeto real que sólo existe en C++.

Esa es la idea de este proceso, ahora escribiremos en C++ otro comando, por ejemplo “Poison()”, que ha de recibir el personaje al cual queremos envenenar. Como desde LUA sólo tenemos los IDs de los objetos, realmente la función Envenenar recibirá un ID, y el motor, ya desde C++, buscará el objeto con ese ID y lo envenenará.

Por supuesto, en C++ no vamos a ir preguntando uno por uno a todos los objetos que tengamos cual es su id y comparándolo para ver si ese es el objeto que buscamos. Necesitamos acceso directo al objeto conociendo su id, con un salto de memoria como máximo; así que para evitar esto diseñamos una nueva estructura para la ocasión que en su día llame “MegaVector”.

(***)

Para que todos los objetos tengan un ID único crearemos una clase “Identidad” de la que todas las demás heredarán. Esta clase simplemente asigna un atributo id a cada objeto y va incrementando un contador estático para el siguiente:

#ifndef __identity__
#define __identity__

class Identity
{
   private:
      static unsigned int _next;
      unsigned int _id;
   public:
      Identity();
      ~Identity();
      unsigned int getID();
};

unsigned int Identity::_next=0;

Identity::Identity() { _id=_next++; }

Identity::~Identity() {}

unsigned int Identity::getID() { return _id; }

#endif // __identity__

Con esto hemos conseguido 2 cosas: la primera, todos los objetos tendrán una ID automática sin que tengamos que hacer nada, y la segunda, todos los objetos tendrán una interfaz común como hijos de Identity, de esta forma podremos aprovechar el polimorfismo para crear la siguiente clase clave: MegaVector.

Un MegaVector es un array de punteros a Identity que contendrá todos los objetos, cada objeto estará en la posición de memoria del array que indique su ID, de esta forma podemos acceder a él directamente sin tener que buscarlo; sólo con un salto a memoria.

El nombre de MegaVector hace referencia al hecho de que tendremos que reservar suficiente memoria como para contener todos los posibles objetos que puedan haber simultáneamente en la partida, si usamos por ejemplo medio millón de posiciones necesitaríamos unos 2 megas de RAM sólo en punteros (el doble en sistemas de 64bits). Puede parecer demasiado, pero no es mucho si tenemos en cuenta la velocidad de acceso que ganamos, y la simplicidad de “hablar” con C++ desde LUA; sin contar con el hecho de que este espacio está usándose realmente de forma dispersa en distintas variables si los datos existen simultáneamente (si no, podemos hacer un reset al MegaVector entre fases).

Por supuesto podemos hacer dinamismos para ampliar el vector si nos quedamos sin memoria o fragmentarlo en partes más pequeñas; pero en este ejemplo simple no voy a tratar de hacer eso. Además, otro aspecto importante es la fragmentación: si estamos creando y destruyendo objetos de forma continua iremos avanzando en el contador del MegaVector dejando atrás casillas vacías. Para solucionar esto simplemente tendremos que tener otro vector de enteros del mismo tamaño en el que iremos guardando las posiciones libres, y con un par de marcadores controlaremos la asignación de IDs (un poco más lento pero podemos reducir varios órdenes de magnitud el espacio necesario).

Un megavector básico y simple, a modo de ejemplo, que no controla la fragmentación ni es ampliable sería el siguiente:

#ifndef __megavector__
#define __megavector__

#include "identity.h"
#include <iostream>

class MegaVector
{
   private:
      int _next;
      int _max;
      Identity** _vector;
      MegaVector(int max=500);
      static MegaVector* _instance;
   public:
      ~MegaVector();
      Identity* get(unsigned int);
      void add(Identity*);
      static MegaVector* getInstance();
};

MegaVector* MegaVector::_instance=0x0;

MegaVector::MegaVector(int max)
{
   _max=max;
   _next=0;
   _vector=new Identity*[_max];
   for(int x=0;x<_max;x++)
      _vector[x]=0x0;
}

MegaVector::~MegaVector()
{
   for(int x=0;x<_next;x++)
   {
       if(_vector[x]!=0x0)
          delete _vector[x];
       _vector[x]=0x0;
   }
   delete[] _vector;
   _vector=0x0;
   _instance=0x0;
}

Identity* MegaVector::get(usigned int x)
{
   if(x>=_next || x<0)
   {
      std::cerr<<"Warning: Access out of range ~ "<<x<<endl;
      return 0x0;
   }
   return _vector[x];
}

void MegaVector::add(Identity* object)
{
   if(_next>=_max)
   {
      std::cerr<<"Error: MegaVector Overflow"<<endl;
      return;
   }
   _vector[_next++]=object;
}

MegaVector* MegaVector::getInstance()
{
   if(!_instance)
      _instance=new MegaVector();
   return _instance;
}

#endif // __megavector__

Perfecto, ahora hagamos un juego de ejemplo. En muchos juegos cosas como los hechizos, o el propio combate esta 100% programados y controlados desde script. A modo de ejemplo creamos una clase “Player” y una clase “Weapon” en C++ y luego escribiré una función en LUA para el combate; haré que los personajes luchen entre ellos con distintas armas, cada arma tendrá hará una cantidad determinada daño y todos los personajes y todas las armas las crearemos dinámicamente desde LUA. Por supuesto como en todo juego de rol que se precie, el azar debe jugar ocupar su lugar, así que el daño de las armas estará definido por una tirada de un dado de X caras.

Creamos la clase Dado:

#ifndef __dice__
#define __dice__

#include <time.h>
#include <stdlib.h>
#include "identity.h"
#include "megavector.h"

class Dice: public Identity
{
   private:
      int _sides;
   public:
      Dice(int sides=6);
      ~Dice();
      int roll();
};

Dice::Dice(int sides)
{
   _sides=sides;
   MegaVector::getInstance()->add(this);
}

Dice::~Dice() {}

int Dice::roll()
{
   return (rand()%_sides)+1;
}

#endif // __dice__

Fijaos en que la clase Dice, hereda de Identity. En el constructor de Dice hago que todos los dados creados “se registren” a si mismos en MegaVector, no obstante hubiera sido más correcto hacer esta operación en el constructor de Identidad (así no tendríamos que hacerlo en todos los hijos de Identidad), pero no quería poneros nada del “MegaVector” hasta explicarlo, así que por esta vez… lo haremos así.

Ahora crearemos la clase Arma:

#ifndef __weapon__
#define __weapon__

#include "identity.h"
#include "megavector.h"
#include "dice.h"
#include <string>

class Weapon: public Identity
{
   private:
      string _name;
      Dice* _dice;
   public:
      Weapon(string, Dice* dice=0x0);
      ~Weapon();
      string name();
      int use();
};

Weapon::Weapon(string name, Dice* dice)
{
   _name=name;
   if(!dice)
      dice=new Dice(6);
   _dice=dice;
   MegaVector::getInstance()->add(this);
}

Weapon::~Weapon() {}

string Weapon::name() {return _name;}

int Weapon::Use() { return _dice->roll(); }

#endif // __weapon__

Como podemos ver en el constructor, para crear un arma necesitamos 2 cosas: un nombre, por ejemplo “Espada Corta”, y un dado para hacer las tiradas. Un arma a la que le asignemos un dado de 10 caras podrá hacer de 1 a 10 puntos de daño, etc. El método “Usar” lanza el dado del arma y nos devuelve el resultado.

Y por último, creamos la clase Personaje/Jugador:

#ifndef __player__
#define __player__

#include <iostream>
#include "identity.h"
#include "megavector.h"
#include "weapon.h"

using namespace std;

class Player:public Identity
{
   private:
      string _name;
      Weapon* _weapon;
      int _health;
   public:
      Player(string, int health=100);
      ~Player();
      void equip(int);
      int addHealth(int);
      string name();
      Weapon* weapon();
};

Player::Player(string name, int health)
{
   _name=name;
   _weapon=0x0;
   _health=health;
   MegaVector::getInstance()->add(this);
}

Player::~Player() {}

void Player::equip(int x)
{
   _weapon=(Weapon*) MegaVector::getInstance()->get(x);
}

int Player::addHealth(int x)
{
   _health+=x;
   return _health;
}

string Personaje::name() { return _name; }

Weapon* Player::weapon() { return _weapon; }

#endif // __player__

La explicación de la clase Player es simple. Para crear un personaje debemos indicar un nombre y una cantidad de vida inicial. Después tendremos varios métodos, como “Equipar”: al que le pasamos un ID de un arma para que, metafóricamente, el personaje la tome y la use para atacar a sus enemigos.

Otro método interesante es “addHealth”, que recibe una cantidad de vida para añadir (o quitar si la cantidad es negativa) y se la resta al personaje, además devuelve la vida final tras hacer la operación. De esta forma, si queremos consultar la vida del personaje podemos hacer “addHealth(0)”.

Y por fin tenemos todas las clases de nuestro juego! Ahora llega la mejor parte; el binding y definición de los comandos que queremos que estén disponibles desde LUA:

#include "identity.h"
#include "megavector.h"
#include "player.h"
#include "weapon.h"

extern "C"
{
#include "lua/lua.h"
#include "lua/lualib.h"
#include "lua/lauxlib.h"
}

using namespace std;

//Implementación en C++ de los comandos LUA



int newDice(lua_State *L)
{
   /*
   Desde L (lua_state) obtenemos todos los argumentos que se 
   le han pasado al comando (aquí 1, el número de caras) y pusheamos
   los valores de retorno.
   */
   Dice* dice=new Dice(lua_tointeger(L,1));
   /*
   LUA funciona como una pila de estados,
   devolvemos el ID del dado y se lo pasamos a LUA como
   valor resultante del comando 'newDice'. En esencia, podemos
   devolver cualquier número de valores.
   */
   lua_pushnumber(L,dice->getID());
   return 1; //Devuelve el número de valores devueltos
}

MegaVector megavector=MegaVector::getInstance();

int newWeapon(lua_State *L)
{
   Dice* dice=(Dice*) megavector->get(lua_tointeger(L,2));
   Weapon* weapon=new Weapon(lua_tostring(L,1),dice);
   lua_pushnumber(L,weapon->getID());
   return 1; //Devolvemos 1 valor; el ID del arma creada
}

int newPlayer(lua_State *L)
{
   Player* player=new Player(lua_tostring(L,1),lua_tointeger(L,2));
   lua_pushnumber(L,player->getID());
   return 1;
}

int Equip(lua_State *L)
{
   Player* player=(Player*)megavector->get(lua_tointeger(L,1));
   player->equip(lua_tointeger(L,2));
   return 0;
}

int Health(lua_State *L)
{
   Player* player=(Player*)megavector->get(lua_tointeger(L,1));
   int health=lua_tointeger(L,2);
   lua_pushnumber(L,player->addHealth(health));
   return 1;
}

int Roll(lua_State *L)
{
   Dice* dice=(Dice*)megavector->get(lua_tointeger(L,1));
   lua_pushnumber(L,dice->roll());
   return 1;
}

int use(lua_State *L)
{
   Weapon* weapon=(Weapon*)megavector->get(lua_tointeger(L,1));
   lua_pushnumber(L,weapon->use());
   return 1;
}

int getWeapon(lua_State *L)
{
   Player* player=(Player*)megavector->get(lua_tointeger(L,1));
   lua_pushnumber(L,player->weapon->getID());
   return 1;
}

int getName(lua_State *L)
{
   Player* Player=(Player*)megavector->get(lua_tointeger(L,1));
   string name=player->name();
   lua_pushstring(L,nombre.c_str());
   return 1;
}

//Main: Bindings de los comandos a LUA

int main(int argc, char **argv)
{
   srand(time(0x0));
   //Fichero a leer:
   const char file[]="script.txt";
   lua_State *L=lua_open();
   luaL_openlibs(L);
   lua_register(L,"newDice",newDice);
   lua_register(L,"newWeapon",newWeapon);
   lua_register(L,"newPlayer",newPlayer);
   lua_register(L,"Equip",Eqip);
   lua_register(L,"Health",Health);
   lua_register(L,"Roll",Roll);
   lua_register(L,"useWeapon",useWeapon);
   lua_register(L,"weapon",getWeapon);
   lua_register(L,"Name",getName);
   int s=luaL_loadfile(L,file);
   if(s==0)
   {
      //Ejecución del archivo
      s=lua_pcall(L, 0, LUA_MULTRET, 0);
   }
   lua_close(L);
   cin.get();
   return 0;
}

Este programa, ejecutará el archivo “script.txt” con código LUA, desde el que tendremos disponibles los comandos que hemos ligado a la VM de LUA.

Una vez compilado tendremos nuestro ejectable que buscará un archivo de texto “script.txt” y lo ejecutará. En ese archivo, que podremos modificar siempre que queramos sin tener que volver a generar el binario ejecutable, crearemos una función de combate con algunos personajes y sus armas, ¡todo usando las clases de C++ desde LUA! 😀

Este es el archivo script.txt que he escrito con el combate (he puesto los nombres en español para distinguir qué está en LUA (español) y qué en C++ (inglés)):

-- Archivo script.txt: Lenguaje: LUA
io.write("--Inicializando Programa\n\n");
--=====================================
--Creo el método de ataque 1
--=====================================
AtacarEspecial=function(personaje1,personaje2)
   vida1=Health(personaje1);
   vida2=Health(personaje2);
   dado20=newDice(20);
   contador=1;
   personaje_actual=personaje2;
   personaje_contrario=personaje1;
   while vida1>0 and vida2>0 do
      personaje_contrario=personaje_actual;
      if contador%2==0 then
         personaje_actual=personaje2;
      else
         personaje_actual=personaje1;
      end;
      critico=Roll(dado20);
      damage=useWeapon(Weapon(personaje_actual));
      io.write("Ronda "..contador..": ["..Name(personaje1).."("..Health(personaje1,0)..") "..Name(personaje2).."("..Health(personaje2,0)..")]\n");
      if critico==20 then
         damage=damage*2;
         io.write("   "..Name(personaje_actual).." hace un golpe critico!!: "..Name(personaje_contrario).." recibe "..damage.." puntos de golpe.\n");
      elseif critico==1 then
         damage=0;
         io.write("   "..Name(personaje_actual).." fallo critico: "..Name(personaje_contrario).." esquiva el ataque.\n");
      else
         io.write("   "..Name(personaje_actual).." golpea a "..Name(personaje_contrario).." y le causa "..damage.." puntos de golpe.\n");
      end;
      Health(personaje_contrario,-damage);
      vida1=Health(personaje1,0);
      vida2=Health(personaje2,0);
      contador=contador+1;
   end;
   io.write(Name(personaje_contrario).." muere y sufre la peor de todas las humillaciones.\n");
end;

--=====================================
--Creo los personajes
--=====================================
lanshor=newPlayer("LaNsHoR",15);
gex=newPlayer("Gex",15);
neton=newPlayer("NeToN",25);
--=====================================
--Creo los dados
--=====================================
dado100=newDice(100);
dado8=newDice(8);
dado6=newDice(6);
dado4=newDice(4);
--=====================================
--Creo las armas
--=====================================
espada_larga=newWeapon("Espada Larga",dado6);
mandoble=newWeapon("Mandoble",dado8);
hacha=newWeapon("Hacha",dado4);
--=====================================
--Equipo a los personajes
--=====================================
Equip(lanshor,mandoble);
Equip(gex,mandoble);
--=====================================
--Empieza el programa...
--=====================================
AtacarEspecial(lanshor,gex);
--=====================================
io.write("\n--Finalizando Programa\n");

El combate funciona de la siguiente manera: por turnos, los personajes usan sus armas para atacarse alternativamente, el primero que llega a 0 puntos de vida (o menos) muere y pierde. Además antes de atacar, cada personaje tira un dado de 20, si saca 20 hace un golpe crítico y el personaje hace el doble de daño, si saca 1 hace un fallo crítico y ese turno no hace nada de daño, y si saca cualquier otra cosa hace el daño normal del arma. Así, el sistema de ataque está definido en LUA y no en C++ siendo completamente flexible y pudiendo ser alterado sin volver a compilar.

En el archivo creo varios personajes y varias armas para que podáis cambiar el código con cuidado y hacer pruebas. Si lo ejecuta tal y como está… este es el resultado:

Por supuesto el resultado varía en cada ejecución. Podéis editar con cuidado los personajes, las armas, la cantidad de vida, etc del .txt y probar vosotros mismos.

NOTA: Este programa básico no comprueba errores en la sintaxis o en la ejecución de LUA ni nada parecido. Si editáis algo mal en el archivo de texto el programa no funcionará (no uséis acentos, eñes, etc, sólo caracteres de la “a” a la “z” y de “0” a “9”; espacios, guiones bajos, puntos, etc también están permitidos).

Leer más

Rompiendo la pared

Publicado por LaNsHoR el 24/09/2013 en Problemas | 5 comentarios

Tercer problema, esta vez un poco de C++, y además muy fácil. Este es un problema clásico de mi carpeta de problemas a plantear en entrevistas de trabajo (yo personalmente nunca contrataría a alguien que no supiera resolverlo).

Este problema vino inspirado cuando, una vez, escuché a una persona A decirle a una persona B que no había forma de acceder a un miembro privado de una clase sin un getter, sin ser friend, etc…

Vamos a demostrarle todos a A que sí se puede:

class Locked
{
   public:
      int number;
   private:
      int secret;
   public:
      Locked() {number=-7;secret=85;}
};

int main()
{
   Locked black_box;
   int x = /* solución aquí */ ;
}

Tenemos un clase “Locked” con un entero público (number) y otro privado (secret). Tenemos que guardar en la variable “x” el valor del entero “secret” de la instancia “black_box” de la clase “Locked”. La solución cabe en una línea y por supuesto no puede escribirse nada fuera del main.

¿Voy abriendo ya la cerveza? 😀

Leer más