gyakoo blog

Posting on ...

2010-09-30T18:15:00.004+02:00

Lastly I've been posting links, status and thoughts on twitter, buzz and linkedin. It's an experiment, to try keep posting more often.

If you wish, you can follow me in twitter
http://twitter.com/gyakoo

google buzz
google profile

or linkedin
http://es.linkedin.com/in/gyakoo/

Implementing a script language I

2010-09-12T18:22:00.009+02:00

There are a lot of literature and articles about using script languages in games (lua, python, unrealscript, lisp, javascript, c# ...) or applications like 3dStudio Max, Maya, even FXComposer. In some projects I've bound the C++ code with Python or Lua (the most popular languages AFAIK), by using the language SDK or wrapping it around with boost::python or Luabind for advanced object oriented features.

To bind your application with those script languages, optimally and without memory leaks, is something which requires mid progamming skills about stack based virtual machine, reference counting objects, and sometimes a lot of C++ template stuff. Obviously, there're design issues about when, where and what is the script language used for. There's a great (and old) presentation by Tim Sweeney about their (Epic) thinking about how should be the next mainstream programming language. Slides talk about the importance to choice a well designed script language in next gen games.

Python and others languages are designed for generic purposes. Actually they're good enough for most of applications, but sometimes you need more specific features built-in in languages, like parallel and concurrency support or processes synchronization. Recently, languages like haskell, lisp or erlang are being considered because of their usefulness in concurrent environments, whether it is by functional programming or actor model paradigm.

We're working with a propietary MMO technology which uses its own script language. That language has specific keywords to synchronize client and server processes, to make remote procedure calls, to work with the server-centric data definition and objects' global states, to specify replication issues in fields and classes, and to merge classes in the way of component (behaviors) pattern, among other features (GUI, plugins, external functions, nodes ...). A language, in cases like that, which provides specific field application issues, increases productivity while technical risks are maintained low. It's a big advantage to count on it.

Several weeks ago, while I was working on my own project, at home, I decided to implement my own script language. That's a complex, titanic and unnecessary work, because is very difficult to program a better script language that existent ones, and I should to use them, but I kept thinking about it. Compiler subject has been always fascinating to me, and I started a project with some simple features in mind. Rapidly I figured out a lot of problems, specially those related with performance, but I've to say that I'm learning really useful things about compiler internals details, and to respect the work lua or python's developers have done.

At this point, I've implemented successfully a script language with an hybrid lua/python syntax and the following features:

- Stack based virtual machine

- Main language constructions (conditionals, loops, expressions, subroutines...)

- Object oriented

- Dynamic typing

- Native types: int, double, string, unicode, dictionary and list

- Binding with C++ functions

- Reference counting for objects

And currently I'm working on:

- Binding with C++ objects

- Concurrent paradigm

- Optimization

- Debugging issues

But the roadmap is very large. I'm applying extreme programming, with a little bit tech design, and doing refactoring every few steps. I'm very proud about simplicity of C++ code, actually I'm doing big efforts to achieve it, maintaining things as small and simple as possible. Also, there is not memory leaks, and binding with C++ is really simple, in fact is simpler than the others languages'. But that simplicity has a cost, performance. I'm not doing benchmarking, at least for the time being, but I suspect that optimization will be mandatory. Anyway I'm considering it while program, but without enter in paranoia mode.

I will post more technical details about how I did it in stages like lexer, parser, generating abstract syntax tree (AST), optimizing the tree, generating final stack VM code, code optimization and execution in virtual machine. Contexts/scopes are interesting to implement, and classes and objects too.

Below you've a code snippet:


Vector3 =
{
    x = 0.0,
    y = 0.0,
    z = 0.0,

    _init( _x, _y, _z )
    {
        this.x=_x;
        this.y=_y;
        this.z=_z;
    }
 
    add( o )
    {
        this.x = this.x + o.x;
        this.y = this.y + o.y;
        this.z = this.z + o.z;
    }
};

suma(a,b)
{
    return Vector3( a.x+b.x,a.y+b.y,a.z+b.z );
}

// -- Main code
v0 = Vector3(1,2,3);
v1 = Vector3(3,3,3);
c = suma(v0,v1);
v0.add( v1 );
if ( c.x == v0.x && c.y == v0.y && c.z == v0.z )
{
    print( "Equals" );
}else
{
    print( "Differents" );
}

As you can see, my approach is to use tables (dicts) like objects. This is used in Lua too, and other languages, but the difference here is I'm trying to do it in an easier way. The syntax is almost minimal, and you can invoke a table with the () operator, and when exists a constructor (I called it '_init') it is called to create a new object. 'print' is an external c++ function and you have others like 'std.execfile' or 'std.execstring', grouped.

I've created a powerful variant type which supports (via tagged union) reference objects, script code, native types, even C++ code, so, the C function 'print' is a variable in global context which is a CFunc, but you can pass it to a function, or you can overwrite it.


meta( func, param )
{
    func( param );
}
doit( m )
{
    m(print, 3);
}

doit( meta );

About the final stack based machine code, below you have the extensive code corresponding to the first snippet. Explaination in next posts:


[CODE]
[Func] $00001
load _x
push this
push x
dotlv
store
load _y
push this
push y
dotlv
store
load _z
push this
push z
dotlv
store


[Func] $00002
push this
push x
dot
push o
push x
dot
add
push this
push x
dotlv
store
push this
push y
dot
push o
push y
dot
add
push this
push y
dotlv
store
push this
push z
dot
push o
push z
dot
add
push this
push z
dotlv
store


[Func] suma
push a
push x
dot
push b
push x
dot
add
push a
push y
dot
push b
push y
dot
add
push a
push z
dot
push b
push z
dot
add
lst 3
call Vector3
ret


pushtable
load $00001
store _init
del $00001
load $00002
store add
del $00002
push 0.000000
store x
push 0.000000
store y
push 0.000000
store z
poptable
store Vector3
push 1
push 2
push 3
lst 3
call Vector3
store v0
push 3
push 3
push 3
lst 3
call Vector3
store v1
load v0
load v1
lst 2
call suma
store c
push v0
push add
dot
load v1
lst 1
call
push c
push x
dot
push v0
push x
dot
eq
push c
push y
dot
push v0
push y
dot
eq
and
push c
push z
dot
push v0
push z
dot
eq
and
jz 66
push Equals
lst 1
call print
jmp 69
push Differents
lst 1
call print

A long time ago...

2010-09-02T07:54:00.004+02:00

Hi, I'm back, after about 1 year since I wrote the last post. A lot of things has happened in my life, personal and professional.

I left the company and moved to another city where I'm currently working on a massively multiplayer online game, mainly focused to learn the Spanish language, but it's almost a traditional MMORPG eventually. It's a big project with a considerable budget, to develop in several years. I'm really excited with it.

...and I got married last July, after ten years sharing my life with a great person, who understands all my freak passions :)

From now I will try post in this blog more regularly.

Something about security

2009-10-19T12:27:00.004+02:00

Exploiting of systems is a subject of which I'd like to know more about. I think it's good to understand how avoid future hacking, but really you neither find much information on web nor books related. I've found a book which maybe could help us to improve these skills. Topics in book include:

Program computers using C, assembly language, and shell scripts
Corrupt system memory to run arbitrary code using buffer overflows and format strings
Inspect processor registers and system memory with a debugger to gain a real understanding of what is happening
Outsmart common security measures like nonexecutable stacks and intrusion detection systems
Gain access to a remote server using port-binding or connect-back shellcode, and alter a server's logging behavior to hide your presence
Redirect network traffic, conceal open ports, and hijack TCP connections
Crack encrypted wireless traffic using the FMS attack, and speed up brute-force attacks using a password probability matrix

And related to that, in the video below, speakers Michael Stail and Felix Domke talk about The XBox 360 Security System and its Weaknesses. They first talk about all weaknesses in old Xbox I, and one by one they're going giving technical information about how they fixed them.

Please, no more discussion about C vs C++

2009-10-17T08:15:00.006+02:00

I'm really thinking that C vs C++ discussion will never end. I just read a Peter Seibel post about interviews he has written in his book Coders at Work, asking to fifteen top programmers and computer scientist around the world about what are their opinions in using C++ language.

Well, maybe you're going to be surprised since most of them think that C++ is a bad, too complex, useless language, and they prefer C when they need performance. That's what a couple of well considered programmers said.

Reading the post, I can see that they had that opinion mainly focusing in how the complex the C++ is. They said that sometimes programmers use only a subset of the language. They think that what you mostly need to do with an OO language, you best do it with some other like Java or Python, because they're better structured languages and things can be done in the same way by different programmers. They insist in the complexity of language and the different compiler implementations, which is a pain in compatibility issues.

Anyway, although I'm not by far as good programmer as they are (years of experience are talking here), I think they're old-school programmers, I mean, C++ has been changing along these years and already there exist another standard revision, as well as compilers do. In reference to the language complexity, all is about using it. If you're a Java experienced programmer and you want to program in C++ after a lot of years, it is obvious that C++ is very complex for you in the beginning. You'll get confused with OO artifacts (which is half-implemented in C++, it is true), or by the using of pointers and references.

C++ is a great language, as well as C and Java and others, depending on what you need to do. The google jam code contest is a good example about it. I've a good colleague that tried to resolve its exercises by using C++, but he said me that more rounds he passed more difficult the questions were, but difficult in the sense of he hadn't enough time to program the result algorithm, not by the algorithm's complexity itself. He was spending a lot of time with language (C++) to do simple tasks like word parsing, splitting a string ... I wonder if he had used python, I'm pretty sure he had obtained a better results.

A place where you can find a lot of C++ code is in the videogames industry, but anyway there is a common evolution there, the using of more high level scripting language, loosing a bit of performance but gaining flexibility and avoiding bugs. That evolution is focused also in tries to make an better script parallel language. And talking about parallelism, it is true that C++ might be a bit painful. That's because the lack of a memory model like Java has. But next language standard has done efforts in that field.

To summarize, my honest opinion about using C++ is that if you've got a couple of good programmers that understand well the language, and they're pragmatic, you could program a very good product (in the performance sense) by using C++, but even so there are parts of a system that is better program in another not-so-risky language. To make good use of the C++ you need good and experienced C++ programmers.

C++ is a dangerous language, like a knife is. But that has not made it so bad. All depend on who is using it and how he/she uses it. You don't let a child that plays with a knife, don't you?

C++ or C (in this era?)

2009-10-15T15:11:00.005+02:00

A post from The Endeavour blog about a Linus Torval's response in a forum, makes me remember the ethernal dilemma about OO and Procedural methodologies flamewar, C++ vs C, STL vs C, Java vs C, well whatever vs C...

Linus:

C++ is a horrible language. It's made more horrible by the fact that a lot
of substandard programmers use it, to the point where it's much much
easier to generate total and utter crap with it. Quite frankly, even if
the choice of C were to do *nothing* but keep the C++ programmers out,
that in itself would be a huge reason to use C.
...

John:

...
Well, I’m nowhere near as talented a programmer as Linus Torvalds, but I totally disagree with him. If it’s easy to generate crap in a relatively high-level and type-safe language like C++, then it must be child’s play to generate crap in C. It’s not fair to compare world-class C programmers like Torvalds and his peers to average C++ programmers. Either compare the best with the best or compare the average with the average.
...

John's impressions are clever and looks like more polite, against Linus's outspoken attitude but completely honest, but anyway after read a lot of controversial comments and what Stroustup said about his C++, finally I think that why do we have to chose one of them? Are always things black or white? I neither agree nor disagree with extreme positions ... people like discussions!

A real life agile development? Posmortem.

2009-10-10T12:32:00.022+02:00

What do you think about agile software development? Is it suitable for all kind of software? Maybe it isn't, but, are you sure that you can't apply principles of agile programming to some parts of your non-agile development process? Well, like almost everything in the life, it isn't a black or white response, but a gray one.

Whether you have the chance to apply it or not, learn more about this topic is very useful to improve your programmer or analyst toolboox, and always you can extract only the interesting part to integrate it in your daily process, I think. At least that was what we did for the last year, creating a big infrastructure from the scratch, with a quite few resources and always with short schedules for intermediate deliverables. Follow is almost like a project postmortem, mostly at management level, I hope you find it useful, that is this post's target.

The target

Currently, the result of our work is helping to the SQA department to do their work faster and more reliable, and the tools we've created are being used in the production's department to trace and debug the applications they create. The statistics we generate and store by executing automated testcases, are very important for the management process. We are consolidating the basis of how the different modules of production's department are shipping and integrating theirs products (at least we're trying to). Also, we've created an intranet where all the company can communicate their issues to SQA department, with a normalized procedure to do that.

It's an unfinished work, but for the things we got successfully, I'll try to expose here how we did it and what problems we found. How did we resolve them? What did we learn?

Team and work

Let's see, as you'll see in next paragraphs we needed to use an agile process, but the first and most important thing we didn't want was to spend a lot of time in the programmer training in terms like iteration, continuous process, pig/chicken roles, scrum master, features documents ... I assimilated all those concepts and then integrated them into our work pipeline, without give bored talks about agile to the team. We wanted to work and ship deliverables in a rapid pace, because we had short milestones and in the meantime we were developing tools, libraries, cluster, web, database and their integration, we wanted to improve certain numbers for the management. Well, really only a number. That number was the hardest part in the entire project. It was showing how many automated test cases we had, since it was used in the calculation of rate of return to justify our team work. Yes, everything must be viewed as a money problem in the end. But we can't increase that number without create a minimal technical infrastructure! It's a cyclical dependency!

So a work division was neccesary, due the limited number of developer we had. The division was accomplished in two ways: making sub-teams, one for tools, the other one for that magic number. And also, in certain moments, developers split their labor in two parts, programming some hours, and helping with the number the rest of the day. As you already know, developers are the most valuable asset in the company, so obviously we had to permute them to avoid their demotivation, and as result the entire team have a good cross-knowledge about the project. It is important. Nobody, individually speaking, is most important than other, only the global team and the inter-relationships are essentials.

Taking the control over the project

As you can read, targets were high enough being our resources so limited. We needed a process to handle that. More specifically an agile development process. I think here is where the project manager (in other cases the lead programmer doing management functions), have to do their work. By having in mind targets and times, as well as resources (how many programmers?) and their development (mixing junior and senior developers), you have to get the things running and giving us results.

Another of the things I wanted was to have the technical control about everything. It is an impossible issue, but you know that things can diverge. People have tendency to do the things the best they can, and although it isn't a bad action, when you're a lead developer you need to achieve a mix between fast and quality. Also as I said before, intermediate results were needed. So, we were updating a prioritized list of features every we wanted a new sub-product, feature, tools or procedure. Returning to the technical control, I meant that I always was getting feedback from developers. Helping them to solve any problem that can block them, and giving them advices about more technical parts that I have the experience about. Maybe it sounds a bit hard for people, but it isn't at all. You have to balance again between training, personal improvement and slight control, leaving to developers do their work, with their own ideas and code style, but continously retargeting them to the global team direction.

Anyway, I insist it can be viewed as a dictatorial technical leadership, but it is not at all. This it is because we had a lot of brainstorming meetings, and every decision and action was previously agreed with the sqa director and with the team as far as possible. In fact, I think you cannot make a really good decision entirely with your own. You need some feedback from your team and colleagues. Maybe your original decision will go as it, but by talking with people you can make some changes or to prepare some things for the future, and actually, they will be who develop that feature, so at least you need bear them in mind. What do you think? :)

Continuous meetings

To correctly apply agile principles, and to receive feedback continuously, we had daily meeting with developers working on a task. But I was clear here. Meetings was driven by something, with a clear target and no more than fifteen minutes long. These were tracking meetings, where the team talked about their progress and problems found, and I repeated targets, priorities and tasks for incoming labor day.

Exceptions were the brainstorming meetings, where we met for a period of an hour or more, talking about how to implement a feature for a new sub project, different approaches to a solution, how a specific technique could affect to other parts of architecture, ... Those meetings were very productive, and everyone can contribute with their own thoughts. Finally I gathered all that information and a solution came to us at the same time the team felt useful and made up relationships between them.

The place where we met was basically in the same place where we work. Trying not to disturb any co worker, we met around a white board where we made a note of everything we talked about. Again everyone can write down on the white board, and those notes were translated into tasks, a class diagram update, a feature, or a change in a function prototype in the emailing library.

But things aren't so easy as you think. People must to pay attention to meeting's driver, you need to avoid parallel discussions, and try to let only the topics around the main goal of the meeting, because fifteen minutes perhaps aren't enough, but it's what we have. Important things first.

Communication and continuous refinements

To perform a continuous refinement process obviously you need what I said before, a continuous feedback, and in one hand you have a continuous meetings with team and in other hand you've the control over what the developer is doing every moment. That's a lot of continuous stuff! So we reach a conclusion here: communication.

The success of any project, or at least a key factor, from my point of view, is the communication among team. Let me explain it. You always should to boost the communication between developers, and the simplest thing you could do is when a developer ask you for a doubt about a technical aspect or whathever, you already know the entire project and what is doing everyone in every moment, so you could forward him to talk with his team mate, depending on doubt he asked you. That is useful and in a short time you can see how people are talking amongst them when is needed. You're building a team. Doesn't matter if you have a team with a couple of gurus or über programmers if there not exists communication because they're almost autistics, or even worse, all of them are trying to impose their solutions. The synergy is the most important part in your team, and it is difficult to achieve: the know-how. I had luck to work with great and honest people there.

Once you have a communicative team, there are a lot of daily work to lead their efforts to build a product. As I said, in progress tracking meetings you can view how your list of tasks (or gantt chart) is being completed, letting you update priorities. But the real problem comes with unexpected events. What does happen when your director changes priorities? or even what if your director gets a developer out of the project? Well, there is no a perfect solution for these misfortunes. Here I have to say that sometimes some sub-projects gone frozen for a time while the entire team was changing the global targets, and in other moments you end up with only two developers when you had five. At least we had a agile team, which responses to changes very quickly, and all the developers understood this. Also at any moment, due the cross knowledge, a junior script writer can sit down to fix in c# a issue related with the debugger tool we were creating, for example, as well as a c++ senior developer can help with cluster maintenance at adminitration level, setting interfaces because he already knows how to do it. This also is a good thing to enrich the people.

But even so, there is a big work to break down complex requeriments into simpler tasks, to achieve rapid results in a week. That is what I did with the building of Studio Application, a complex .net desktop application which is used to generate automated testcases, integrating a lot of processes, techniques and languages. The first step I did was to analyze the requeriments, making a high level list of features needed. After that, a blocks diagram was created, following a class diagram. Once an overall classes and sequences diagrams were created, it was easier to distribute tasks to people, bearing in mind a milestone for a week. In a week we gone through the results and we had a minimal functional application. The remaining work was refinements, week after week, until we reach a quality product. But a good design is needed because you have to create code structure in order that it is extensible, for the next refinement weeks. It is always a painful work when code is not prepared for extensibility, anyway. And a grateful one when things run ok.

There is another minor problem with continuous refinement: features or tasks starvation. Maybe you're updating priorities in your project plan, and there are features that they're not as important than others, or maybe they're less motivating than others. You should to set priorities with that in mind, because among features, you'll find bugs and other issues that need to be fixed in order to unblock certain other developments, and they can be pushed down in the list.

Conclusions

To adopt an agile software development process should be a natural process. It is good all the documentation and theory about agile methodologies out there, but if you force the team to adopt that cool methodology you read a month ago in a magazine, without taking in mind that it's almost a way of react before a changing environment, maybe it will cost more than you expected.

Because the team cannot change suddenly, in fact, the agile process is focused to train the team to do that! It is important go floating with the work flow of your team and slightly retarget their motivations, doing something similar that we did.

Anyway, all what I've written here is mostly the beautiful parts of our work. Once you have seen all process from another point of view, when (important) things have finished and when you get results, it's very easy to see what you failed and what was a success, but anyway it depends on the company, project and people you have. In our case we learned a lot of interesting ways to do the things, but also ways to don't do them. Again, this isn't a magic recipe or the correct way to do the things, and what worked ok to us, not necessarily is suitable to another company. But it was only a postmortem!

Sorry for the long post.

Hacker's Delight

2009-10-09T14:53:00.005+02:00

Since I read an article from EntBlog about this book, I pushed it in my pending books queue. And ... finally a good colleague at Optenet give it to me like a present. I'm really excited. Thank you dude.

Sure I'll learn a lot of interesting things.

Games are not only graphics (again) and other anecdotes

2009-10-08T23:33:00.007+02:00

Today a person asked me for books to learn to "program videogames". Well, despite that this question is more difficult to answer than you initially can think, I knew what he actually meant and I asked him (intentionally):

Me: What do you mean with "program videogames"? - He: Well, you know, to draw 3D meshes with textures and so, these things...

Nooo, graphics again! There is no problem, but, how many times I've heard this wrong association?

I said him: Why don't you begin with other things different from graphics? And his response was: Bah, that another stuff (non-graphics) is easy, at least I can understand it without problems, but I've never done graphics programming.

Wow!, Overall engine architecture, entities system, networking or even AI? Gameplay and entities behavior is really exciting. Sound system or script binding. And a parallel engine architecture, with tasks scheduling is also cool. Another good stuff is the filters pipeline, more related with graphics if you want. These are complicated ones, but are videogames too. And there are a lot of more things I can't talk you about. Also, XNA or Ogre3D are good start points. Even you can download my simple c++ space invaders game and modify it.

He: Yes, yes, but, what about graphics? Draw models. Textures!

Ok then, definitely he wants draw primitives :)

This conversation makes me remember other anecdote, whith a good co-worker who wanted program a fluid simulation, if I can help him. I asked him: what kind of simulation, a water shader effect, a particle based simulation or simply something like the old plasma demo effect?- He: No no, I want make a good fluid simulation, and I think I can, in fact I've already done something.

Me: Really? You're a crack!, Have you ever been working with CFD or Navier-Stokes equations?. I don't know much about it, so I can't help you, tell me more, I said.

He: Well, I don't know that CFD or equations. I don't need them, I think I'm going to deduce them.

I finally said: Ah ok, why don't, good luck, and don't forget to show me any result you get :)

Good people, best regards to them.

It's all about complexity

2009-10-06T10:23:00.012+02:00

Complexity Order I mean. Algorithmic is an useful tool which every programmer needs to know. As you already know, you could find/do a very very fast routine to compare two strings, by using new SIMD instructions built in the SS4, as the PCMPEQQ for example, and reordering instructions to minimize cache fails and take advantage of out of order micro execution. But if you're applying a direct algorithm to traverse words or a direct structure to store them, there is nothing you can do when you get an asynthotic input. It is the beauty about algorithmic, an university's subject that all the software engineers should know, and apply it in their daily technology decisions (whenever they can), because the system's behavior with large input matters and can makes the difference.

I remember, when I was studying at UCA, we did practices about algorithmic and complexity order theory by measuring different algorithms times to the same problem. We sampled the time that an algorithm takes for different input sizes, so you're sampling the complexity order curve/function and then by comparing all the algorithms-times, you can see how they behave asynthotically, in a graphic manner.

I've been using this technique since then, when I need to test different approaches to same problem, or when I need to empirically demonstrate a data structure, for example. In another post in this blog I talked about a special radix tree to store IP numbers, demonstrating you'll get a constant complexity order O(k) when search for an IP, independently you store all internet IPs (another thing is the complexity order in space). This means that you'll perform same number of instructions to search any number.

So you have, O(1) < O(logn) < O(n) < O(n·logn) < O(n^2) < O(n^a) < O(a^n) < O(n!), being O(1) the best you can get in time and space. Related with this you have the NP complete problems.

Sometimes when trying to get a best time complexity, probably you'll get worse the spatial one, and vice versa. Another important note about measuring times is the time precision. Although you use a high performance counter, you cannot measure how much time takes two std vector's inserts, because current microprocessors are very fast. You should use a big N input, repeated M times, because memory never is enough (you can't insert 1·10^12 words in a vector, at least you shouldn't), and then divide the time to compute the average time. Selection of N and M is important. Also, you need to know that another daemons or processes are continuously interrupting the algorithm, maybe the compiler can generate an optimize version of your algorithm (only improving the multiplicative constant). All these variables can corrupt the times you get, so the conclusion is do not use the times as it, but the graphical comparisons between algorithms' times, or in other words, you need to extract all the multiplicative constants and think only in terms of sampled curves' behavior.

In the code below you see a snippet to measure a std list insert varying N.


unsigned long step = (MAX-MIN)/N_POINTS;
// Varying our input N
for ( unsigned long N = MIN; N < MAX; N+=step )
{   
double time = 0.0;
// Repeating M times
for ( unsigned long m = 0; m < M; ++m )
{
  Clock cl;
  cl.Start();
  // Algorithm test comes here.
  // Trying to insert N numbers in a stl list
  std::list<int> lis;
    for ( unsigned long i = 0; i < N; ++i )
    {
        lis.push_back( i );
    }
  time += cl.Stop();
}

printf ( "%lu\t%0.10lf\n", N, time/(N*M) );
}

This code will print an output like follow:


99999 0.0000001016 
6759999 0.0000001023 
13419999 0.0000001042 
20079999 0.0000001021 
26739999 0.0000001028 
33399999 0.0000001037 
40059999 0.0000001016 
46719999 0.0000001051 
53379999 0.0000001017 
60039999 0.0000001020 
66699999 0.0000001012 
73359999 0.0000001021 
80019999 0.0000001005 
86679999 0.0000001011 
93339999 0.000000101

This data can be obtained for several algorithms. All those data then can be graphically represented using a plot program, like gnuplot for example.

Follow are curves for insert algorithms in <vector>, <list> and <map> Before you look through the image below, it would be interesting you know what are the complexity order for insertions in these containers. In this page you can see all O for stl containers. O(1) for vector and list. And * for map. Well, the time complexity requirements imposed by the standard for each map operation suggest a balanced binary search tree mostly. Let's see the results:

Wow!, it is interesting that the vector (red line) and the list (blue line) are constant ( O(1) ). In other words, doesn't matter how N increase, always you'll get a constant time. And the map (green line) follows a logarithmic curve ( O(logn) ). Obviously a linear interpolation between measuring points are used.

As you can view, vector has O(1) in push_back operations. Wait a minute! When a vector increases beyond its capacity, a memory resize is needed, and a copy for all elements is performed. So, why is it O(1)? It's a O(n) just because asynthotically you'll need to make N copies... Well, there exists a thing called amortized analysis to deal with it. In fact, in the wikipage about amortized analysis, the example used to describe it, is the array push back operation.

Also you can get from graphic that vector is faster than list when inserting elements, due to multiplicative constant, being smaller in vector structure. But remember, with this implementation and in the CPU I used. This is can be because in list you need to make pointers operations when a new node is added, in vector you only need access to last available memory slot to put the element. Also in list you need to create every new node (memory alloc operation).

Another comparison graphic below, measuring find operations in the three same containers.

But, what happened to green line (map's find operation)? This is a common issue you'll get when comparing very different measuring scales. Map's searches are so fast, comparing with the vector or list ones. So, you cannot see the green line because is very near to X axis, in other words, with low times. You need to change scale, but anyway you can see here that vector and list find operations are linear ( O(n) ), with different constants (again vector has lower constant). To view if map searching operation behaves like a logarithmic one, we represent independently the third curve.

And finally, it behaves like a logarithmic curve!.

The Duct Tape Programmer

2009-10-06T10:00:00.004+02:00

Do you think you're a Duct Tape Programmer? It's more difficult than people think. Another Spolsky's great article.

And the duct-tape programmer is not afraid to say, “multiple inheritance sucks. Stop it. Just stop.”

...you’re not here to write code; you’re here to ship products.

One principle duct tape programmers understand well is that any kind of coding technique that’s even slightly complicated is going to doom your project. Duct tape programmers tend to avoid C++, templates, multiple inheritance, multithreading, COM, CORBA, and a host of other technologies that are all totally reasonable, when you think long and hard about them, but are, honestly, just a little bit too hard for the human brain.

Journal Hook

2009-10-01T18:58:00.004+02:00

Following last Windows focused post, I come to talk you about hooks. Well, I'm not an expert about hooks, but basically, a Windows' hook is a procedure that you can register in the operating system to intercept events before they reach an application. More information in msdn.

Well, in our try to automatize systems, we need to create a mechanism to intercept all mouse and keyboard messages generated by user in desktop. So, we can record something similar to macros in Windows, and later playback them. For example, we need to automate the Skype user interaction, or the Outlook application, and then play the macro.

It's a very interesting thing because, WM_MOUSEMOVE is a message too ;), and we could save it for example to perform some QA automated tests in a game, moving the avatar around scenario, capturing mouse moving and keyboard strokes. There are a lot of applications about hooks, and there are more hooks than only Journaling which is only a kind of hook.

Here you have a very simple application that creates this hook and records all messages. Just a note: Be careful when you're executing from Visual Studio IDE, because if you set a breakpoint in code, the hook cannot be established correctly. Maybe it could be generated by VS thread (attached to process) which avoid messages to hook, I don't know, but it is a very rare bug, difficult to find, and can drives a team's member crazy. In fact, done it.

The idea behind, you intercept all messages and serializes them (lparam, wparam, time, message number, even the hwnd but have no sense) and when you want play them you've to feed to journal playback hook with those messages. In the code below, (all) the messages are stored in a plain txt file, but its performance can be pretty bad due to the big number of messages intercepted. You can buffer and then flush them. Also you can change this, for example, sending them by network or something. Let your imagination flies.

Finally, it is not a new thing, you can google for "winmacro" and you'll find an open software (with source code) which does this journaling stuff, but with an own interface and more control. Anyway, in my code below you only have a record feature. Playback in another post...

CPP file here.


#include <windows.h>
#include <stdio.h>

// -- wow, two global objects!
static HHOOK gHookHandle = 0;
static FILE* gFile = NULL;

LRESULT CALLBACK JournalRecordProc(int code ,WPARAM wparam,LPARAM lparam)
{
if ( code == HC_ACTION )
{ 
 EVENTMSG* mesg = (EVENTMSG *)lparam; 
 // -- Serializes entire message
 fprintf_s( gFile, "%d %d %d %d %d\n", mesg->message, mesg->paramL, mesg->paramH, mesg->time, (UINT)mesg->hwnd );
 // -- Exiting when PAUSE key is pressed
 if ( mesg->message == WM_KEYDOWN && GetAsyncKeyState(VK_PAUSE) )
 {
  const LRESULT result = CallNextHookEx( gHookHandle, code, wparam, lparam);
  UnhookWindowsHookEx( gHookHandle );
  gHookHandle = 0;
  PostQuitMessage(0);
  return result;
 }
}
return CallNextHookEx( gHookHandle, code, wparam, lparam );
}


// WinMain
// --------
int WINAPI WinMain( HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow )
{
// -- Record hook and file to store messages
if ( (gHookHandle = SetWindowsHookEx(WH_JOURNALRECORD, JournalRecordProc, hInstance, 0) ) == NULL )
 return 1;
if ( (gFile = fopen( "msgs.txt", "wt" ) ) == NULL  )
 return 1;
fprintf_s( gFile, "# Message ParamL ParamH Time HWND\n" );

// -- Main message dispatching
MSG msg = {0};
GetMessage(&msg, 0, NULL, NULL );
while ( msg.message != WM_QUIT )
{
 TranslateMessage( &msg );
 DispatchMessage( &msg ); 
 GetMessage(&msg, 0, NULL, NULL );
}

// -- Closing
fclose( gFile );
return 0;
}

Advanced Windows Debugging

2009-10-01T18:31:00.004+02:00

My company just bought it. A must-to-have book.

Me, pretty happy

Colin McRae: Dirt

2009-09-26T16:49:00.008+02:00

This so addictive game really impressed me by its playability. The graphics aren't bad, and you have a lot of gaming modes, vehicles and tracks. When you're playing for a while, you get an inmersive experience, and is cool how you're running at 160km/h, listening to your co-driver giving you track information, while the car is skidding near to the trees.

And the menus are incredible. As you can see in the video below, menus are in real 3D space, with special effects and movement. An off voice is telling you tips and tricks, depending on your selected race configuration, and you can review all kind of statistics about your profile progress while the race is loading.

And finally, the best of all, I bought an original copy only for 9.95€.

Bjarne Stroustup on C++0x {cvu}

2009-09-23T11:48:00.002+02:00

Yesterday, a coworker passed me a pdf extracted form the {cuv} magazine, Sep09, where Bjarne Stroustup talks briefly about the incoming c++ standard revision, c++0x. Last revision was c++98.

At the beginning of article, he says:

‘What will C++ be once we have the facilities offered by the upcoming
standard?’ This is not an innocent ‘just philosophical’ question. Consider
how many programmers have been harmed by believing that ‘C++ is an
object-oriented language’ and ‘religiously’ built all code into huge class
hierarchies, missing out on simpler, more modular approaches and on
generic programming. Of course C++ also supports OOP, but a simple
label – especially if supported by doctrinaire teaching – can do harm by
overly narrowing a programmer’s view of what can be considered
reasonable code.

Is interesting what the main creator of c++ thinks about using it in complex Object Oriented systems.

You can download the pdf here.

Elevated

2009-09-23T08:41:00.005+02:00

Did you remember the last breakpoint's 4k intro winner?: Yes, you did, Elevated!

How did he done it? How did he compress all assets in only 4 kilobytes? Well, he actually didn't compress any asset: he generates textures, geometry, sounds, ... procedurally, using parametric functions, and programming hacky code to save until last byte, also he used raymarching algorithms (some similar to raytracing on GPU) to generate all the geometry in only two triangles, by programming a very complex pixel shader. Also, like most of 4k intros, a special linker can be used to reduce final object code. Crinkler or similar. That linker, instead of MS or GNU ones, is capable of compress with high rates, ignoring most of unused standard libraries. Iñigo Quilez (RGBA) has presented a "behind the scenes" presentation here. Amazing!

Fantastic AI in Neurogence

2009-09-22T20:15:00.002+02:00

In Neurogence, my another blog related with Artificial Intelligence, I've post an article about how I implemented the Artificial Intelligence for players in a non-interactive football game: Fantastic League, when I was working at Gextech.

Post here.

SQA Automation

2009-09-09T11:34:00.004+02:00

Last months I've been working on the automation system for our products, here at Optenet. As senior software architect I've been in charge of analysis, design, implementation and team management for several internal tools and procedures to automate sqa test cases, having developed with success:

A set of libraries to automate all company's common tasks to test features and functionality related with our filtering solutions. Libraries to generate protocols traffic, web requesting, mail sending,...
A set of procedures to automate manual test cases, making use of the library above. We use selenium and qantium (an own .net component similar to selenium).
A clusters system, where to run automated test cases in parallel. Our clusters can run up to 50 test cases simultaneously. The typical test case's duration can be about 10/11 minutes. Also, the cluster is capable of resolving dependencies, and supports both technologies, selenium and qantium.
A .net application where non-technical people can automate test cases, without programming knowledge. It works like Visual Studio, acting like the designer. This application generates (transparent) source code for testcases, depending on actions registered about web clicking and other specific actions, which is sending to cluster to run. Also this tool communicates with database the results and stores in it the testcase in xml format.
A .net debugger for test case visual debugging like visual studio, so the user can be in realtime how the testcase is being executed in its solution.
A solution to integrate our modular and advanced product configuration, making use of virtualization (vmware mainly) with an internal network.
Other minor stuff related with scripting and technologies integration.

Technically speaking we've integrated a lot of technologies, machines, languages and procedures. Creating an internal and powerful protocol based on byte-code communication between processes along multiple machines. We've used c++, c#, asp.net, python, perl, shell scripting, com, soap and our protocol (like mpi) among others.

You can see a very basic and summarized presentation below.

Sqa Automation

View more presentations from gyakoo.

Break in August

2009-09-03T15:08:00.008+02:00

Relax: No sport, no computers, no freakism, swimming pool.
Reading classics: Ringworld (Larry Niven), Ender's game, Ender's shadows (Orson Scott Card),The Fencing Master (A. Perez Reverte), Gateway (Frederik Pohl), The complete stories I (I. Asimov)
Holidays in Paris and Disneyland.
Planning my incoming wedding (Yes, I'll get married next year).
Fixing the car.
... and ... working hard.

That was my August.

C++0x wiki page

2009-07-23T12:36:00.004+02:00

As you already know, the new c++ standard is code named c++0x.

Here you have a good wiki page where to learn more about changes and improvements:

http://en.wikipedia.org/wiki/C%2B%2B0x

Mandelbrot on GPU

2009-07-15T20:23:00.007+02:00

Mandel fractal, what a classic!,
here you have a very simple code in HLSL using Shader Model 3 to draw the fractal using the GPU.

Using floats is not recommended due to low precision, but in SM3 we have not double types yet (only in SM4+), as well as only up to 256 iteration loops. But to represent the overall fractal, in the range CMin = { -2.0f, -1.0f } CMax = { +1.0f, 1.0f } it is enough.

Apart from the shader code, in C++ you should have a quad covering the entire screen area and then apply this shader before to draw it. So, you don't use any texture, instead the color for each pixel is computed by computing the fractal value for that pixel.


float2 CMin = { -2.0f, -1.0f };
float2 CMax = { +1.0f, 1.0f };
float2 pixelSize = {1.0f,1.0f};
int Mode = 0;
//////// COMPLEX N. COMPUTATIONS ////////////
float2 mulcomplex(float2 A, float2 B)
{
    return float2(A.x*B.x-A.y*B.y, A.y*B.x+A.x*B.y);
}
float2 sqcomplex(float2 c)
{
    return mulcomplex(c,c);
}
float2 expcomplex(float2 c)
{
    float ex = pow(2.7182818f,c.x);
    return float2( ex*cos(c.y), ex*sin(c.y) );
}
float lencomplex(float2 c)
{
    return sqrt( c.x*c.x + c.y*c.y );
}
///////// STRUCTURES //////////////////////////
struct VSINOUT
{
    float4 pos : POSITION;
    float2 uv  : TEXCOORD0;
};
///////// VERTEX SHADING //////////////////////
VSINOUT vs_basic(VSINOUT vsin)
{
    VSINOUT vsout;
    vsout.pos = vsin.pos;
    vsout.uv = vsin.uv;
    return vsout;
}

///////// PIXEL SHADING //////////////////////
float4 ps_mandel(float2 uv:TEXCOORD0) : COLOR
{ 
    float2 C = float2(CMin.x + uv.x*(CMax.x-CMin.x)*pixelSize.x,
                      CMin.y + uv.y*(CMax.y-CMin.y)*pixelSize.y);
    float2 Z = float2(0.0f,0.0f);
    float2 lastZ = Z;
    int maxiters = 254;
    int iter = 0;
    while ( iter < maxiters )
    {
        lastZ = Z;
        Z = sqcomplex(Z) + C;
        if ( Z.x*Z.x + Z.y*Z.y >= 200.0f ) break;
        iter = iter + 1;
    }
    float4 color = float4(0,0,0,1);
    if ( iter < maxiters )
    {
        float dt = 1.718281f/253.0f;
        float cf = saturate( log(1.0f+dt*iter*8.0f));
        color = float4(0.0f,0.0f,cf,1.0f);
    }
    return color;
}
///// TECHNIQUES /////////////////////////////
technique Main
{
    pass p0
    { 
        VertexShader = compile vs_3_0 vs_basic();
        PixelShader = compile ps_3_0 ps_mandel();
    }
}

Space Invaders C++/DX

2009-07-14T19:54:00.007+02:00

A two months ago I was thinking in a very simple idea, but difficult in essence: Could I program an entire game only in a few hours?. Well, it's a trap question. Of course I can, if the game is a pong or .... a space invaders, not a MMO.

It's not impossible if you keep in mind a very basic concept, and you're pragmatic when programming. An opportunity came, to show to myself if I was able to do it, and started to work. I had to control my creative personality, both in design and implementation, because you have no idea how your programmer brain can diverge when you're encapsulating code in a class, or creating an entity system, but I done it (I think so). As you see, the main handicap with this project was the time constraint.

You can download the project here: DX Space invaders (source + binaries)

The project was structured in modules: a namespace in a cpp object that contains all necessary to encapsulate its tasks. They're a kind of singleton classes. You have modules like Sounds, Graphics, System and Game. The last one is the most interesting, it contains all entity code and game logic for invaders and stages. Sorry for the poor encapsulation there, but I didn't refactorize it.

A curiosity: there aren't news/deletes in code. During game, system doesn't use dynamic memory. All remain in stack.

Absence and DNS server

2009-07-13T14:52:00.009+02:00

Hi all,

after about three months of absence, I come back here to post my geek thinks and things. In that time, my life hasn't really changed, or at least visibly changed, but my person does. I'm starting another post to share with you a philosophical dissertation about my current life, but now, let's freaking:

Lastly I've been implementing (among other things) a single standard DNS server to support inverse queries (see RFC1035), in C++.
Well, it was an interesting exercise, specially in the optimization side of the program, because of the stability and performance issues due to large amount of incoming connections and stored IPs/domain associations. The server was developed in six days and neither STL nor another third party library was used. As you know, I actually love to do this kind of things for learning purposes.

You can download the project from: http://www.dimensoft.com/data/code/dnsserv.tgz
The sources are both for linux and win32 platforms, but only makefile for linux is provide (you should to create a VS solution or similar for windows).

Some interesting things and features:

I had to learn how a DNS server works, at least for inverse queries: Given an IP, the DNS server resolves which hostname is associated to it.
I had to learn how a DNS packets are formatted, researching in RFC1035. It was a hard part because of some responds packets didn't work and the dns client didn't recognize them. I had to sniff packets using tcpdump (wireshark) and decode them with real traffic using real dns servers.
UDP protocol.
Socket, thread, lock and condition classes multiplatform for linux and win32. The rest of code is ansi c++.
To support simultaneous queries from clients I implemented a special kind of threads' pool. It uses N threads, each containing a tasks' queue. When a query packet is received by UDP, the best worker thread (balancing load or simply by round robin algorithm) is selected and the task for this query is created and enqueued it. The threads are waiting for a thread condition, which is signaled when a new task is enqueued. So with this we avoid spinlocks by reading and checking the queue's size. By default, 4 threads and 128 max. connections (queue size) per thread are used.
Currently each thread performs the IP searching in structure, being a bottleneck here, so we could have another threads' pool for IP searching.
IPv4, this is, 4 bytes = 2³² ips = 32 bits to represents an IP.
Find an optimal (both in space and time) structure to store IP/host domains associations was not an easy issue. In fact I think this is the hardest part of this program. Finally I used a prefix tree to store IPs. A spatial optimization for this could be a radix-tree (aka patricia trie), which collapses single paths in a leaf. The one used here is the prefix tree, which has 4 levels of depth. Each node contains an array of up to 256 possible children nodes, ordered for binary searching algorithm. So, we have a constant complexity order in searchs, O(k), with a multiplicative constant of 32 comparisons ( log2(256) * 4 ). This is because the sorting of arrays and binary search, otherwise we would have also O(k) but with a multiplicative constant of 1024 (256*4). In our case, O(k) means that doesn't matter how big the tree is or the number of stored IP, always we will perform same number of comparisons in worst case to find our domain name.

You can read more notes about solution in README.

How to design a good API

2009-03-31T00:26:00.005+02:00

Is a matter of fact that a good API design matters. Everybody knows this issue, but really are the principles of good design applied in companies? Well, it depends but in general it is difficult, sometimes due to deadlines and the thinking on a rapid results more than to spend time on design robust systems.
I think that software engineering is essential, a minimal UML diagram used to discuss some aspects of architecture sometimes help us to design a good API, because this is only a contract between creators and users (another developers), and at least we need to meet them all together. There are a lot of developers who think that UML is lost time. Some managers think it too. And then the problems arrive in a few weeks or months, usually as bugs, maintenance or growth difficulties.
With a simple whiteboard, a meeting place, a team leader and a little bit time, we can design very good systems. A leader or a project manager needs more than one brain, and it is often forgotten. It's good for manager, developers and the entire company, but always there are people who don't see it. API aren't easy to design, but once you've got it, give us a powerful tool and a very valuable asset for company.
Please think as an engineer.
--
References:
How to design a good API and Why it matters (pdf)
APIDesign.org
API-writing blog
Fog creek on API design
Artima forums: Design
Compactness and Orthogonality

Onlive and Zeebo

2009-03-28T00:49:00.003+01:00

The future of gaming is here.

Onlive is a microconsole (a platform) who receives the game you're playing via video streaming, something like youtube but applied to games. It uses an own video compression algorithm which gives high compression ratios, but it depends on your connection bandwidth to play in HD or not. There are already a couple of companies supporting and working on it.
Zeebo is similar, but it is a console yet with only a (free!) internet connection to download games we want to play. It doesn't use disks.

As you can see, the future is the online distribution, to make life easier (no more PC requeriments), cheaper (these platforms will be cheap, but with a monthly/annual payment), and sure (avoiding piracy, or trying to).
Well, I don't know if these new platforms will be really the future, in any case, I would like to check if the games (server) will respond rapidly when you are playing with a very quickly game like a FPS. Also, the image quality maybe won't be as good as in current consoles. (why do we want HD images if a lot of people are always playing videotubes/gametubes?)
Only time will tell.
--
References:
More gamestreaming: Gaikai
Why Onlive can't possibly work

EGO Technology

2009-03-27T23:08:00.007+01:00

We always are talking about the most known game engines, like the Unreal's, CryEngine, Gamebryo, IdTech or Source. Those engines are very good (and expensive too), and obviously there are a lot of marketing with them, but did you know another next-gen technologies used in games today?

A couple of days ago, I'd news about the new Codemasters' technology: EGO. It's an evolution from their Neon engine and is being entirely developed by them, since three years ago. It's a company's investment to improve all their new titles, as well as an intelligent movement to make easier the transition for next generations. EGO supports next-gen multicore in both consoles and PC, car physics (bringing deformations to new levels of realism), next-gen graphics, tools and a lot of features that make it truly powerful, and a very good choice to be used in next-gen AAA titles.

The last point is that EGO is actually a fact, in other words, is being successfully used for titles like Operation Flashpoint 2: Dragon Rising and Racedriver: GRID, with incredible results.

In my opinion there are not too much companies who have the opportunity (vision and risk too) to invest in proprietary technology, like Codemasters is doing, but I think that needs a better marketing work, for example, a good website like UnrealEngine has, showing its features. Anyway I'm sure they're working on it.

--
References:
Gamespot: Codemasters' EGO has landed
Codemasters
List of game engines

Monsters Vs Aliens

2009-03-26T01:01:00.008+01:00

Possibly another hit from the creators of Shrek and Kung-fu Panda. It looks great.
Since 2001 I was waiting for another comic monsters related movie in 3D. In that year Pixar released Monsters Inc, the best 3D film ever (to me), difficult to beat, seriously, but seeing what the Dreamworks' guys have done in Kung-Fu Panda, MvA could be the next Oscar for the best animated feature film (Pixar won the last edition with Wall-E).

Anyway we need to wait for incoming Pixar's Up, which is again directed by Peter Docter, director of Monsters Inc, so it's very good new to me again. Coincidences?. And what about our Planet 51? This year looks promising for computer animation industry.
I hope you enjoy it, I will do it.

Incredible short

2009-03-21T20:25:00.001+01:00

Half-life 3?, a Samsung's promotional video?, an amateur's video?

Puzzles and interviews

2009-03-21T11:12:00.003+01:00

Do you like the puzzles? Ok, and... What if those puzzles are asked you in an interview?
In my opinion, I think that the companies who do some kind of coding test or interesting interview questions are good companies.
Years ago, a good friend talk to me about it. In fact, in my current company I did an online C/C++ questionnaire and then an exercise in office. The exercise wasn't too difficult, but enough to check distinct levels of programming style.
Something similar I did four years ago, for Gextech, and I remember a question in special, something like:
What would you like to be, if you'd reborn?
Damn it!, I didn't study this question on school. What do I have to answer? Well,..... I would be a Cactus!
A cactus?, why?
Because I like the sunshine and the peace that a cactus have. (I thought this was the last question to me..., but not).
Reading in Coding Horror, an article about puzzles and curious interview questions I've found this web: techInterview.com, where you have the most freak interview questions I ever heard about. I recommend you read them if you want to move to a company you think will do these kind of interviews.
In any case, do you think these kind of questions or puzzles are always valid? I don't think so. There are a lot of people that get nervous and block themselves, but they could be valid candidates, maybe with a more systematic or a mid-term thinking, sometimes doing the work with more careful, and you can't guess it if you only judge them with a puzzle.
You can't build a good team with only top brilliant freaks. You'll need more meticulous people, perhaps slower than others, but with a better sense of safe work. It depends of course. Not all puzzle-solver people are freaks, and vice versa, but you understand what I say. Don't you? ;)

Programming Paradigms

2009-03-20T11:48:00.004+01:00

How many programming paradigms do you actually know? Let's enumerate the most used:

Declarative, like Prolog
Imperative
- Structured, like C
- Object Oriented, like Java
Event driven, like C# or OO Pascal (Delphi)

More...? Well, in this page you'll see quite a few: Programming Paradigms

I recommend those rare like Nondeterministic or Feature Oriented ones. They're interesting.

Neurogence. My new AI blog.

2009-03-17T13:49:00.010+01:00

For a long time I was thinking about to post more articles on AI in this blog. As the matter of fact even I wanted to post a series of techniques, algorithms, ideas about AI for gaming, but never I did it.
This thinking comes again to me recently, because of I'm reading two books about AI, and have cleaned all my knowledge base about the artificial intelligence discipline, to re-start with a new (and hope more robust) approach. These books are:

- Roger Penrose's The emperor's new mind: A deep reflexion and demonstration about why the AI as science will not be able to build really thinking machines like in Sci-Fi books and films.

- An academic 1.3k pages book, written by several university teachers in Spain, with a lot of solutions, applications, methodologies, tools, algorithms, techniques and theory in general.

I was working for three years in a non-interactive football game in AI for players. Finite state machines for low level (animation selection and blending) and a fixed/imperative rule based system for high level (strategy and position in field) techniques were used. Vector forces and some trigonometric/linear algebra was necessary of course. But no neuronal networks, no genetic algorithms, no learning machines, and even so the results were very good for our purposes (a mix between AI and statistical sequences).
I've found some people with the thinking of "NN are the solution to all our problems" or "with a genetic algorithm we solve it" or even "A* for every situation". Sometimes, we don't need to make our lives harder just because, and a good understanding about the difference between AI as science or AI as Knowledge Engineering is elemental to put limits to AI, and go right to the point.

And so Neurogence is created. This is my new blog about AI in general (not only for games).
Initially this blog site will contain a few articles, news and links. I'll need more time to make a good site. I've a lot of ideas about this blog, but the time is insufficient, you know, I hope you like it. By the way, if somebody wants to contribute to Neurogence, let me know by send a mail to gyakoo@gmail.com

Links Soup

2009-03-14T10:25:00.003+01:00

Today I just woke up thinking to post a few links:

It curious how OS interfaces have changed along time: OS interface design between 1980-2009
Did you know Autodesk's Kynapse?. It's a middleware for AI in games, mainly focused on dynamic pathfinding. I recommend to watch the demo videos: Autodesk's Kynapse
Unreal Engine 3, for XBox360, PS3 and PC (DirectX10): Unreal Engine 3 technology
GDC2009 is inminent.
Current book I'm reading, about Physics/Maths and AI: Roger Penrose's The Emperor's New Mind. (thanks Antonio).
Planet 51's new images. (spanish)
APB is the new MMOG game by Real Time Worlds.
How to be a program manager. Joel Spolsky.
Why doesn't the Spanish state provide more support to videogame industry? However to the cinema... (spanish)

Have a good weekend

God of War III trailer

2009-03-08T00:14:00.002+01:00

It is impressive, graphics, gameplay, ambient and music.
Try to watch it in HD, if you can:

Framework for distributed computing

2009-03-07T00:38:00.007+01:00

Lastly I've been designing a simple framework to distribute tasks in a cluster environment (a multi computer system where nodes are connected via network). One of the most used framework to do this is the BOINC project, which was created originally for the project SETI@home. Obviously my framework doesn't try to simulate the BOINC's, but it tries to explore the main idea behind.

There is a web page for the project where you can view how it is implemented, examples and you can download it. It's called gydis (gyakoo distributed computing library) :)

Gydis project website.

Basically it is a set of classes which offer you an easy API to create a job and to distribute it in the cluster. By using the power of python's introspection a protocol communication between nodes using a own remote object is created.

The main idea is you must to inherit from a Job object (same syntax like a Thread class), to implement its run method and call to start to schedule the job in cluster. For job grouping you must to do the same but with JobGroup class, implement its reduce method and call to start to schedule all its jobs and wait for them, until results are computed and your reduce method is called back to combine them.

Here you have two (stupid) examples of use, but you can do a lot of things with this.

Single Job

The example below shows how to calculate a single factorial of 15 on a node. Yes it's a dumb example, but basic enough to show you how to create a Job and schedule it in cluster.

import job

class SimpleFacJob(job.Job):
    def __init__(self,n):
        job.Job.__init__(self,"controller-hostname")
        self.n = n

    def fac(self,n):
        if n <= 2   : return 2
        else        : return n * self.fac(n-1)        

    # Executed remotely on a node.
    def run(self):
        self.result = self.fac(self.n)

    # Called locally (here) when job finishes.
    def response(self):    
        print "Job result=",self.result

if __name__ == "__name__":
    j = SimpleFacJob( 15 )      # Create the job.
    j.start()                   # Launch the job to cluster
    # Wait until finalization
    while not j.result:
        pass

Single Job Group

Now another dumb example, we are going to calculate a factorial of 11 by computing eleven factorials of 10 and then sum them. We create ten jobs, each one computing factorial of 10. The reduce method will be a sum.

import job

class SimpleFacJob(job.Job):
    # See the example above
    ...

class FacSum(job.JobGroup):

    # Adds all results
    def reduce(self):    
        r = 0
        for j in self.jobs:
            r += j.result
        print "Reduced to:", r
        return r

if __name__ == "__name__":
    jobs = []
    # We create eleven jobs, each one with factorial(10) computation
    for i in range(0,11): 
        jobs.append( SimpleFacJob(10) )

    jg = FacSum( jobs )    # Creating the group of jobs
    jg.start()             # Launch the group to cluster

    # Wait until finalization
    while not jg.result:
        pass

Currently it's the version 0.1 so you'll find bugs, and the documentation is not completed yet, but I hope that this prototype will be continued.
Any recommendation to gyakoo@gmail.com

Music Composition

2009-03-02T11:58:00.003+01:00

Well, last weekend I've been surfing between some projects done during last years, and surprise!, I've found some music files composed using fruity loops. BTW I remember that won a mod tracking contest prize in PCMania (a well known spanish magazine) about ten years ago, but I lost them of all. Anyway here you have some rescued trance/goa/progressive modules, enjoy them.

Chasse

Neikan

Pianel

Refask

Wisdom

Yassto

An abstract file access system

2009-02-26T13:24:00.002+01:00

Sometimes our products need to release all data assets as images, sounds, models, configuration files, ... packed in a single file, often called packets.
This allow us to hide some files, best management of update/modding packets, compress data or avoid asset ripping.
In many situations, a zip packing structure could be used, in others, a tar, or a own structure with checksums or additional information.
But we need to split here two concepts: Compression and packing. It's trivial but necessary to know that a zip file is a packet/file format, meanwhile the deflate/inflate algorithms (used by zlib) are compression techniques. Zip uses zlib for every stored file.
Also, whether we want implement a library for this purpose, we need to provide, a single api mechanism to access transparently to a file using native os file-system (throughput C API) or to a file stored in our packets.
Lastly I've developed a library to do this. With an own packet format and using the free LZO compression algorithm (one of the fastest I know), you can access to your data from a packet(s) or from normal files with follow code:


#include "gfs.h"
int main(int , const char** )
{
    // gyakoo filesystem initialization
    gfs::init();
   
    // Adds a packet search path.
    gfs g;
    g.add( gfs::PACKET, "data.pak" );
    {
        char chunk[4096];
        // pickup a file from abstract file system.
        gfile* f = g.grab( "images/texture.jpg" );
        if ( f != 0 && f->length() > 0 )
        {
            // read in 4k chunks the file.
            while ( ! f->eof() )
            {
                unsigned long r = gf->read( chunk, 4096 );
                // do something with chunk ( r is number of bytes read )
            }
            f->close();
            delete f;
        }
    }
    return 0;
}

You could change the packet adding g.add( gfs::PACKET, "data.pak" ); by a folder using g.add( gfs::FOLDER, "data/" ); and the code doesn't need to be changed to access to the file.

With this library, I release a command line tool, like the tar one, to create, visualize and make another operations with packets and files.

The internal format of packet uses md5 for name, to avoid variable-length reading, and tries to minimize the seeks and read operations.
Here you have the format of packet: specs.txt

And here you have the source of library (linux and makefile): gfs-0.1.tgz

Bon Appétit

Planet 51

2009-01-17T13:24:00.003+01:00

Finally Sony Pictures has released the trailer of upcoming Ilion's title "Planet 51". The film will be in theaters in the last quarter of this year 2009.

After watch the trailer, have to comment that the Ilion's guys have worked hard and the results looks great, with an original and very comic story. With this I think that national products always can be as good as international ones (pixar, dreamworks skg, bluesky, ...) because in Spain we've a lot of talented people, maybe new and old studios would need more capital investment, although I suppose things aren't as easy.

I recommend you see the trailer.

Congratulations and good luck.

Fable II

2008-12-11T00:00:00.003+01:00

One month ago I bought Fable II, and since then I can't stop to play it. Is incredible what Molyneux and his team have created. An unique fantasy world, with special care about expressions, actions and all the socials stuff around main character. It is curious how your actions change the aspect of your avatar along time. (In my case, the avatar goes to same direction as me, eating a lot of cake pies to recover health but gaining weight as secondary effect of that).

Also, a feature that keep me always alert in game, is that you can do everything you want. You could to kill all citizens in a region. You could help them or simply you could ignore them.
You could make one family, or more, with or without children, or simply lead a solitary existence, practicing sex with *you want*. There are much more other actions you can do. Therefore, all these actions make you more sexy, scary, respectable, ... to people. Again in my game, people want to give me presents when they see me and acclaim to me for help them with bandits. So, if I would, I could play for a long time only performing alternative missions, working in a tavern or forge to carry money to my family, gain honor and reputation, stealing ...

Like every other action rpg game, you have different skills, and you can specialize. Again, depending on which skills you increase, your human aspect could change to be taller, stronger or with glow symbols on skin in the case of magic skills. There are a lot of swords, axes, guns, crossbows. And the fight system is very elaborate and polished. It is very easy fight against eight or more enemies at same time, doing combos and changing target very fast with only stick and one button. Avatar's animations are beautiful and very fast. You can throw magic spells, with different levels, but it is difficult because to charge a high level you need maintain freeze and the enemies could damage you. Anyway this is again very balance, same as experience sphere collecting.

It is the game that I was waiting for. Beautiful, with a very special world, a great history and a very fast gameplay system, among another must-to-play features.

I could talk much more about Fable II, but first I have to finish it, although I'm starting to think that this game never ends.

Very good game. You should play it.

Trying to optimize a dictionary

2008-11-26T18:33:00.006+01:00

It is truth that sometimes when programming, specially when you are designing data structures for your application, a dictionary-like structure is needed.
Also it is called hash tables/trees, maps, associative containers ... A stl map often is implemented using a hash tree.

You could need a fast way to map a type into another. A dictionary is a mapping between a word (string) and another user defined type, like an integer, a vector or even another string.

It is important that the accesses (mapping) will be as fast as possible.
The c++ standard library stl provides the follow complexity orders depending on container/operation pair:
http://www.cplusplus.com/reference/stl/

In fact, most of stl implementations are very fast, and it is difficult improve them maintaining the flexibility and portability. It is difficult, not impossible.

Last days I have been implementing an associative container using a hash table, to optimize words storing, without use a std::map. In other words, a dictionary.
First benchmarks throws a improvement in performance, better than using std::map< std::string, type >, but with some disadvantages such as a certain loss of flexibility, although we could fix this.

show/hide ...

The very first (and easiest too) way to make a dictionary is using stl:


typedef std::map< std::string, float > TDictionary;
TDictionary   mydict;

mydict[ "enemies" ] = 5.0f;
mydict[ "life" ] = 100.0f;
mydict[ "shadowfactor" ] = 0.8f;

But, what about systems without stl? or systems with poor/slow implementation of it? or system where you use plain C?
And, what if you need a more efficient way to do a dictionary, when doesn't matter loss of flexibility?
We could google for public libraries, or write it ourselves.

Well, the other day, I found a problem with this kind of handicaps and implemented the follow very specialized hash table. I'm sure that you could find a better implementation or even some mistakes in code. In both cases please let me know.
The explanation and pros/cons will be shown later:


// -------------------------------------------------
// DefaultHasher
// -------------------------------------------------
struct DefaultHasher
{
    inline unsigned long operator()( const char* data, int len )
    {
        register unsigned long h = 0;
        register int i = len-1;
       
        for ( ; i >= 0; --i )    h = 37*h + data[i];
           
        return h;
    }
};
// -------------------------------------------------
// Dictionary
// -------------------------------------------------
template<   typename K,
            typename V,
            int CAPACITY         = 8167,
            int INITVSIZE        = 32,
            typename STRHASH     = DefaultHasher >
class Dictionary
{  
protected:
    struct sNode
    {
        K    key;
        V    val;
    };
    struct sHead
    {
        int     mSize;
        sNode*  mData;
    };
public:
    Dictionary     (){ memset( mData, 0, sizeof(sHead*)*CAPACITY ); }
    ~Dictionary    (){ destroy(); }
    void destroy   ()
    {
        for ( int i = CAPACITY-1; i >= 0; --i )
        {
            register sHead*& sh = mData[i];
            if ( sh != 0 )
            {
                delete [](sh->mData);
                delete sh;
                sh = 0;
            }
        }
    }   
    void add( const K& word, const V& value )
    {   
        const int ndx = hashkey(word);       
        if ( mData[ndx] == 0 )
        {
            // this entry doesn't exist, creates it.
            sHead* se = ( mData[ndx] = new sHead );
            se->mData = new sNode[ INITVSIZE ];
            se->mSize = INITVSIZE;
            memset( se->mData, 0, sizeof(sNode)*INITVSIZE );           
            se->mData->key = word;
            se->mData->val = value;
        }else
        {
            // entry exists, push back to vector.
            register int i = 0;
            register const int siz = mData[ndx]->mSize;
            sNode* vec = mData[ndx]->mData;
            while ( vec[i].key != 0 && vec[i].key != word && i < siz ){ ++i;}
            if ( i < siz )
            {
                vec[i].key = word;
                vec[i].val = value;
            }else
            {
                // cannot insert. ¿resize current array 'vec'?
                assert( false && "Hash table error inserting\n" );
            }
        }       
    }   
    inline void add( const char* word, const V& value, int len = -1 )
    {
        add( mFuncHash(word, len == -1 ? strlen(word) : len), value );
    }
   
    V* exists( const K& word )
    {
        assert( word != 0 ); // don't search for zero hash words
        V* ret = 0;
        const int ndx = hashkey(word);
        sHead* dat = mData[ndx];
        if ( dat != 0 )
        {
            ret = seqSearch(dat, word);
        }
        return ret;
    }
   
    inline V* exists( const char* word, int len = -1 )
    {
        return exists( mFuncHash( word, len==-1 ? strlen(word) : len ) );
    }

protected:   
    inline int hashkey( const K& w ){ return w % CAPACITY; }
    inline V* seqSearch( sHead* ent, const K& k )
    {
        register int i = 0;
        register sNode* arr = ent->mData;
        while ( arr[i].key != k && arr[i].key != 0 && i < ent->mSize ) { ++i; }
        return (i < ent->mSize && arr[i].key == k) ? &arr[i].val : 0;
    }
   
protected:
    sHead*        mData[CAPACITY];
    STRHASH       mFuncHash;
};

Before to explain it, I have to say that think it isn't completed yet, and not fully tested against more scenarios, but in a rapid benchmark using 81500 words extracted from a txt dictionary, I had the follow results in an Intel Core 2 Duo, with GNU CPP Compiler 4.2 and -O3 optimization flag:

Inserting all 81500 words and then searching for each one:


std::map< std::string, std::vector<int> >       average ~ 0.213 seconds
std::map< unsigned long, SimpleArray<int> >     average ~ 0.062 seconds
Dictionary< unsigned long, std::vector<int> >   average ~ 0.040 seconds
Dictionary< unsigned long, SimpleArray<int> >   average ~ 0.029 seconds

It is about 2x times faster than using same types and 7x faster than original dictionary, although I have to say that it makes use of several tricks.

- Briefly, it is a fixed-size array of pointers, initially nulls. When you inserting a word, first it is converted to a number using a hash function, and then indexed in main array using a modulus operator. If target position is null, a sHead structure is created and the node is inserted, otherwise we have a collision, and then we travel an array with collisioned elements. If found an equal word (number), node's value is overwritten, otherwise the node is pushed back.
- Analogous operation is done when search for a word.

Most important features are:

* First at all, the key factor here is that we transform each word (string) in its numerical representation, using a simple and fast hash function, called DefaultHasher. Thus, we store only an unsigned long for each word, instead string itself, and the comparisons between words are done very quickly (to compare two 32bits integer is faster than comparing n-length strings). But there are some problems here with this approximation:
- We lost the word itself because we store numbers. This could be fixed adding a string field to sNode structure.
- Collisions in hash function (two distincts words generate same number) will give false positives . We could use a perfect hash function to resolve it.

* Also, as you can see, the size of hash table is fixed, as well as each entry's vector. This problem could be resolved testing bounds and reallocating dynamic memory, but in this case we would have to make it carefully, because heap fragmentation and elements' copying when resizing.

* The correct selection of CAPACITY constant is essential, because it is used in modulus operation when indexing string hash number ( ::hashkey() ). It is important to select a prime number not too close to a power of two for a good indexing distribution (search in google for uniform distributed hash functions). Sometimes a MAD (Multiple Add Divide) operation is used to index, using (A*hashvalue+B) % CAPACITY. In other case, when you use a poor indexing function, is probably that the number of collisions per entry increase and the entries' vectors too much populated, with consequently dynamic memory work.

* Also, the INITVSIZE is very important, because indicates number of elements for each table entry. A large number will decrease performance (both temporal and spatial) when allocating new entries, and a small number could be even worse in this version, making a fail when there are too many collisions in the same entry. I have seen that with smaller initvsize numbers better results.

* In this version, the memory comsumption complexity order is about O( CAPACITY * INITVSIZE ). This consumption depends on K and V sizes, so be careful with these numbers.

Yes, I know. After all, to get a boost in performance using this implementation implies a good tunning work in settings. To know the limits of input data is important to do this, but I think that if we perform some changes in code in order to flexibility ... Anyway, for my purposes this version was good enough.

---------------
Finally, as shown, a SimpleArray class is used as mapped type for dictionary. Again, it is a poorly tested class to manage an array of types, with its limitations, but with good results to me and when use it carefully.


// ------------------------------------------
// SimpleArray
// ------------------------------------------
template< typename T, bool USEMEMCPY = true >
class SimpleArray
{
public:
    SimpleArray(int initsize = 0 ): mCur(0), mSize(0), mData(0)
    {
        if ( initsize > 0 )
            resize( initsize );
    }   
    ~SimpleArray()
    {
        destroy();
    }
    inline void clear(){ mCur = 0; }
    inline void add( const T& val )
    {
        if ( mCur >= mSize )
        {
            resize( mSize * 2 );
        }
        mData[mCur] = val;
        mCur++;
    }
    inline T&   get( int ndx )    { return mData[ndx]; }
    inline int  size()            { return mCur; }
    inline void destroy()       
    {
        if ( mData != 0 )
        {
            delete []mData;
            mData = 0;
            mSize = mCur = 0;
        }
    }
   
    SimpleArray( const SimpleArray<T>& o ): mCur(0), mSize(0), mData(0)
    {
        *this = o;
    }
    inline const SimpleArray<T>& operator =( const SimpleArray<T>& o )
    {
        if ( o.mData != mData )
        {
            destroy();
            resize( o.mSize );
            mCur = o.mCur;
            if ( mCur > 0 ) copy(mData, o.mData, mCur);
        }
        return *this;
    }
    inline T& operator[]( int ndx ){ return mData[ndx]; }
protected:
    void resize( int newsize )
    {
        if ( newsize > 0 )
        {       
            T* tmp = mData;
            mData = new T[ newsize ];
            if ( tmp != 0 )
            {
                copy(mData, tmp, mSize );
                delete []tmp;
            }   
            mSize = newsize;
        }
    }
    inline void copy( T* dst, const T* src, int c )
    {
        if ( USEMEMCPY )
            memcpy( dst, src, sizeof(T)*c );
        else
            for ( int i = c-1; i >= 0; --i )
            {
                dst[i] = src[i];
            }
    }
protected:
    int  mCur;
    int  mSize;
    T*   mData;
};

The USEMEMCPY template parameter acts like a #define (the compiler generates conditional code, depending on true/false). When it is true, the libc memcpy function is used when reallocating and copying. You should use True to gain performance if using native types or basic structures as template argument for T. If the value of USEMEMCPY parameter is False, then objects are copied using the assign operator (=) which could invoke an operator overload. Use False if T is a complex type with specialized copy constructor and assignment.

Again, you could improve and enrich this class.

PS: In the for loops, like the Dictionary's Hasher, SimpleArray's copier, ... you can make use of unrolling (with steps of two) to help the optimizer to use cpu's pipelining, but caution with indices when odd sizes.

Binary constant in C/C++

2008-11-18T20:30:00.007+01:00

Many times, when programming in C/C++, and depending on level, you use decimal, hexadecimal and even octal literal constants, specially when you're involved on bits stuff, like flags.
A common C/C++ programmer's complaint is that language doesn't have native support for binary literals.
Today I needed this kind of code sugar and implemented the next code snippet.
It's only a form, and I suppose there will be another ones. This implementation is resolved at compiling time. Let's see:


#define _B8BE(s) ( ((int)s[7]=='0'?0:1<<0) |    \
                   (s[6]=='0'?0:1<<1) |        \
                   (s[5]=='0'?0:1<<2) |        \
                   (s[4]=='0'?0:1<<3) |        \
                   (s[3]=='0'?0:1<<4) |        \
                   (s[2]=='0'?0:1<<5) |        \
                   (s[1]=='0'?0:1<<6) |        \
                   (s[0]=='0'?0:1<<7) )
// Using it:
const val = _B8BE("01100011");
const exists = (flags & _B8BE("01001100")) != 0;

A words about this:
- It's for 8 bits, and macro should be invoked using just 8 characters.
- BE are stands for Big-Endian, because the most significant bit is the bit numbered 0 (the first character), and it is the first character at memory.

The most important thing is that the compiler changes the expression by its constant, and this macro does not decrease the performance. We're going to see how the compiler works:


// binary.c

#define _B8BE(s) ( ((int)s[7]=='0'?0:1<<0) |  \
                  (s[6]=='0'?0:1<<1) |        \
                  (s[5]=='0'?0:1<<2) |        \
                  (s[4]=='0'?0:1<<3) |        \
                  (s[3]=='0'?0:1<<4) |        \
                  (s[2]=='0'?0:1<<5) |        \
                  (s[1]=='0'?0:1<<6) |        \
                  (s[0]=='0'?0:1<<7) )


int main()
{
 return _B8BE("10100000");
}

When compiling with optimization flag, generating assembly output:


$ gcc -S -O3 binary.c

We can see a code like :this:


 .file "binary.c"
 .text
 .p2align 4,,15
.globl main
 .type main, @function
main:
 leal 4(%esp), %ecx
 andl $-16, %esp
 pushl -4(%ecx)
 movl $160, %eax            ; here you have the "10100000" generated by compiler.
 pushl %ebp
 movl %esp, %ebp
 pushl %ecx
 popl %ecx
 popl %ebp
 leal -4(%ecx), %esp
 ret
 .size main, .-main
 .ident "GCC: (Ubuntu 4.3.2-1ubuntu11) 4.3.2"
 .section .note.GNU-stack,"",@progbits

Finally, you could create more macros with a distinct numbers of bits, endianess or syntax.
Last words, I suppose that googling you'll find more code and info about this issue.

Code optimization (I)

2008-11-16T20:58:00.007+01:00

In next series of posts I would like to expose techniques and methods that currently I'm studying to improve the performance of C/C++ chunks of code. These optimizations are not based on algorithmic order, but on multiplicative constants that commonly are ignored on algorithmic complexity. When you have an algorithm to do any task, and it is difficult to improve it talking in complexity terms, the constant and code optimization are very important.

Verification of compiler result code (with and without optimization flags) is essential. Also we will make use of intel's specific SIMD instruction (SSE instruction set) to parallelize vectorial operations (commonly used on computer graphics). Other thing we will do is to check how works the Intel's compiler, giving a well optimized code in x86 platforms. And more...

Of course I'll give you references where to learn more and better these concepts and techniques, but a simple google's search will be enough in most of cases.

In this first post, I'll review the simplest form of parallelization. CPU pipelining, with a trivial example.

Let's go.

One of the things you can learn from the University's subject "Parallel System Architecture" is that most of modern microprocessors have a very low level form of parallelization, called segmentation, also known as pipelining.

This technique is used to increase the number of instructions executed in each clock time, by splitting it into smaller tasks that can be executed simultaneously. In order to use this method, actually you can't do nothing to use it directly, but you can perform small changes on code to decrease data dependencies between instructions.

For example, the below shows how a simple loop unrolling can improve slightly a function that computes the scalar product of two vectors:

// Dot product between two 8-dims vectors.
// Classical method.
float dotprod0(const float* v0, const float* v1)
{
  float dp = 0.0f;
  for ( int i = 0; i < 8; ++i )
  {
      dp += v0[i] * v1[i];
  }
  return dp;
}

// Dot product between two 8-dims vectors, making use of
// loop unrolling to take advantage of pipelining.
float dotprod1(const float* v0, const float* v1)
{
  float dp = 0.0f;
  for ( int i = 0; i < 8; i+=2 )
  {
      dp += v0[i] * v1[i];
      dp += v0[i+1] * v1[i+1];
  }
  return dp;
}

To prove the improvement of second method, we could to use the processor time stamp counter, if available. So we can get clock cycles used by two functions.
Under Windows platform you can use QueryPerformanceCounter function, and in a Linux system, the standard clock() function gives the number of clock ticks since program start.

In our example, we are going to use directly the RDTSC instruction. There are a lot of information on web about performance measurement and monitoring using this instruction.
So we have next function:


// Return no. of clock cycles since program was launched.
// We store registers eax and edx and pack it in 64 bits.
static inline long long rdtsc()
{
  unsigned a, d;
  asm volatile ( "cpuid    \n"
                 "rdtsc    \n"  : "=a" (a), "=d" (d) );
  return ((long long)a) | (((long long)d) << 32);
}

In the previous function we are using the "cpuid" instruction to force all instruction to complete. (We will discuss this "cpuid" instruction and its uses later). So, this instruction is used to synchronize processor execution, avoiding misleading cycle count caused by out-of-order execution of modern processors (i.e. pipelining). Finally, we need to execute several times the same code chunk, to detect the cpu context switches and cache warm-up effects on clock cycles. Last measurements should give constant results.
So we have:


// test for classical dotprod method.
{  
 long long r0 = rdtsc();
 float dp = dotprod0(v0,v1);
 long long r0 = rdtsc();
    printf ( "dotprod=%.2f (%lld) clock cycles\n", p, r1-r0 );
}
... repeat > 5 times ...

// test for second dotprod method.
{
 long long r0 = rdtsc();
 float dp = dotprod1(v0,v1);
 long long r0 = rdtsc();
 printf ( "dotprod=%.2f (%lld) clock cycles\n", p, r1-r0 );
}
... repeat > 5 times ...

And the results are (using gnu c++ compiler with no optimization):
Method 1
==========
dotprod=159.00 (1190) clock cycles
dotprod=159.00 (1105) clock cycles
dotprod=159.00 (1122) clock cycles
dotprod=159.00 (1105) clock cycles
dotprod=159.00 (1071) clock cycles
dotprod=159.00 (1071) clock cycles
dotprod=159.00 (1088) clock cycles
dotprod=159.00 (1088) clock cycles
dotprod=159.00 (1088) clock cycles
dotprod=159.00 (1139) clock cycles

Method 2
==========
dotprod=159.00 (1241) clock cycles <== cache warm up
dotprod=159.00 (1003) clock cycles
dotprod=159.00 (1003) clock cycles
dotprod=159.00 (1003) clock cycles
dotprod=159.00 (1020) clock cycles
dotprod=159.00 (1003) clock cycles
dotprod=159.00 (1020) clock cycles
dotprod=159.00 (1003) clock cycles
dotprod=159.00 (1003) clock cycles
dotprod=159.00 (1003) clock cycles

As you can see, the second method throws less number of clock cycles, only doing a small code change, taking advantage of cpu pipelining, minimizing data dependencies.

Next: CPUID instruction and compiler's assembly output.

Accessing to character in explicit string.

2008-11-14T14:21:00.006+01:00

I did not know the follow C syntax to access to specific character in a string. It is interesting to inline functions that use some kind of LUT.


int dummy_function( int param )
{
     return (int)( "j4Cg+\x64\x5F_"[ param % 8 ] );
}

You should remember that an ASCII character takes values between 0 and 255, and to use specific control ones you need to use a 8-bit numeric escape sequence '\xnn', where nn is an hexadecimal code for ASCII character. Also, if you have Unicode support, you can use the 16-bit sequence '\unnnn' and the 32-bit version '\Unnnnnnnn'.

Ray-Triangle intersection

2008-11-12T21:45:00.006+01:00

Lastly I've implemented a function to compute the intersection between a ray and a triangle, in my personal raytracing project I'm working on. It is old problem in computer graphics, but always interesting.

I don't know if there is another better (in performance terms and with no precomputed data), but I decided to program one based on "Fast, minimum storage ray/triangle intersection" paper, from Möller and Trumbore.

It is called "minimum storage" because doesn't need to store the triangle's normal. This method either tests against plane extracted from triangle.

Well, the method and a C example code is on paper for anybody, but I'll try to explain here briefly.

First we can write a point in a triangle using a barycentric form, as:

T(u,v) = (1-u-v)·V0 + u·V1 + v·V2

A point inside triangle must have

u >= 0, v >= 0 and u + v <= 1

Then, if we use the ray equation:

O + t·D = (1-u-v)·V0 + u·V1, v·V2

expanding and rearranging the equation, translating coordinates to the origin, it gives:

-D·t + E1·u + E2·v = T
where:
E1 = V1-O
E2 = V2-O
T  = V0-O

If we use a matricial form, like this:


[-D E1 E2] · [t    = T
      u
               v]

then we can apply i.e. Cramer's rule to resolve it. The key point here is the follow linear algebra relation:


det([A B C]) = -(A x C)·B = -(B x C)·A

thus we have:


t = Q·E2 / P·E1
u = P·T / P·E1
v = Q·D / P·E1
where,
P = D x E2
Q = T x E1

If we only need to test intersection in the positive face of triangle, it must to be fulfilled P·E1 > 0, but if we don't care, only need P·E1 != 0.
We could use parametric coordinates (u,v) for texture mapping. t is the distance in ray.

Next I suggest an implementation in pseudocode, only performing some computation tasks when needed.


# R is the ray and Vi are the three triangle vertices, all of them in world coordinates.
# I is true if intersection detected, false otherwise.
# t, u, v, are parametric coordinates, only valid when I is true.

ray_vs_triangle: R, V0, V1, V2 -> I, t, u, v
   I <- False    
   E2 <- V2 - V0    
   E1 <- V1 - V0    
   P <- cross_product( R.direction, E2 )    
   det <- dot_product( P, E1 )    
   if det > Epsilon
      T <- R.origin - V0       
      Q <- cross_product( T, E1 )       
      u <- dot_product( P, T ) / det       
      if u > Epsilon
         v <- dot_product( Q, R.direction ) / det          
         if v > Epsilon ^ u+v < 1+Epsilon
            t <- dot_product( Q, E2 )
            I <- True

Ubuntu 8.10 (The intrepid ibex)

2008-11-10T15:30:00.003+01:00

The new Ubuntu 8.10 - The intrepid ibex has been released (on October 2008).

Well, I have to say that it is great.

Until now I have been using Ubuntu 8.04 (Hardy Heron), released on April 2008, and my experience is that it is incredible for programmers with no fear to return to command line tools (too much Visual Studio can make you to forgot common and useful practices).

After unpack my brand-new laptop (I never had one), with a GeForce 9600GT (yes, it support CUDA), I found that lastest nVidia drivers (177) were automatically downloaded and installed without problems. (In 8.04 the installation was manual).

I have to install wine for 3d benchmark supporting, because I want to install 3DMark (and emulate it) in order to compare performance under Linux and Windows Vista.

Here you can find an application-level performance comparison between Ubuntu and Windows XP.

And, finally I'm warning you all if you're thinking that I am a converted linuxer. No I'm not. I still love Visual Studio. The new 2008 version is amazing.

In next posts I will talk about performance issues that I have been working, using SIMD instructions of Intel (SSE instruction set), using Intel C Compiler (which uses cpu cache dependant optimized code) and GNU C's one, viewing assembler code produced by an optimizer and comparing several methods to do vectorial/matricial operations. Yes I'll return to assembly (fpu stack and so), only to review result code). Thus, I'll comment compiler intrinsics, helping to compiler to optimize code.

Huelga de informáticos y writing in english.

2008-11-05T21:45:00.003+01:00

Como algunos sabreis:

"El pasado 23 de octubre el Ministerio de Educación presentó las fichas de los nuevos títulos de grado y master de todas las ingenierías menos la de informática cumpliendose así los peores presagios. La excusa ha sido que nuestra ingeniería no tiene atribuciones y que la informática es una materia transversal y por lo tanto no debe de concentrarse en una titulación concreta."

Aunque todo es relativo, supongo que los informáticos con experiencia no serán infravalorados por las empresas, pero de alguna u otra manera afectará.

Hay una huelga el día 19 de Noviembre, podeis ver más información en los siguientes enlaces.
http://huelgainformatica.es/
http://www.cpiia.org/index.php?option=com_content&task=view&id=169&Itemid=1

Por otro lado, voy a intentar escribir a partir de ahora las entradas en inglés.

Yes, I know. My english is so bad, but I need to improve it in the sense of write, understand and speaking it, and I think that it is a very good initiative to me, that's I hope. So, sorry with mistakes.

"If you don't use it, you loose it."

Ambient Occlusion (II)

2008-10-24T23:16:00.017+02:00

Finalmente cambié la función de generación de rayos en el hemisferio de la superficie.
Ahora sigo una función de densidad, extraida de una lectura en el Siggraph 2003, titulada "Monte Carlo Raytracing", organizada por Henrik Wann Jensen, el creador de Photon Mapping.

Intepretando lo que he podido el apartado 2. Function Inversion, se extrae, para una función de densidad determinada, el siguiente par de coordenadas polares, aleatorias, en el hemisferio:
El primero es el ángulo desde la normal,, entre 0 y PI/2, mientras que el segundo es el azimut entre 0 y 2PI.
El exponente n sirva para indicar la apertura del cono en el hemisferio, similar al exponente de la función specular Phong. Si n vale 0 tenemos el hemisferio completo.

Una vez tenemos este par de ángulos, en coordenadas polares, lo transformamos a coordenadas cartesianas así:

Ahora ya tenemos el vector unitario aleatorio en el hemisferio, solo que no está orientado a la normal. Debemos de realizar un cambio de base, y para ello extraemos la base de la normal, u, v y w, siendo w la propia normal. Una vez lo tenemos generamos la siguiente matriz de rotación, y la multiplicamos por el vector obtenido arriba.
A continuación el código para generar NSAMPLES samples usando esta función de densidad:


// generamos la base (N es la normal).
v3f w( N );
v3f t( w );
t[ minMagnitude(t) ] = 1.0f;  // aseguramos que t no es colinear con w.
v3f u( t.cross( w ).normalize() );
v3f v( w.cross( u ).normalize() ); 

// genemos todos los bases
v3f samples[ NSAMPLES ];
for ( int i = NSAMPLES-1; i >= 0; --i )
{
    // muestreamos dos variables aleatorias en [0,1]
    float r1 = rndRange(0.0f,1.0f);
    float r2 = rndRange(0.0f,1.0f);

    // función densidad para obtener los angulos
    float n = 0.0f;
    float a1 = acosf( pow( 1.0f - r1, 1.0f / ( n + 1.0f ) ) );
    float a2 = piby2 * r2;   

    // transformamos a coord. cartesianas
    v3f _a( cosf(a2)*sinf(a1), sinf(a1)*sinf(a2), cosf(a1) );   
    
    // cambio de coordenadas a la normal.
    float a = _a.x;
    float b = _a.y;
    float c = _a.z;   
    samples[i] = v3f( a*u.x + b*v.x + c*w.x,
                      a*u.y + b*v.y + c*w.y,
                      a*u.z + b*v.z + c*w.z );
}

Una vez que ya tenemos éstos samples, lanzamos dichos rayos desde el origen del punto y calculamos la media ponderada. A continuación el pseudo-código de la computación de la intensidad de ambient occlusion, en el punto O, con la normal N. D es la distancia máxima permitida para la occlusion.


hits <- 0.0
para cada sample S en samples[]:
    ray <- (O, S)
    r <- trazar_rayo( ray )
    si r.intersecta ^ r.t > Epsilon ^ r.t < D :
        hits <- hits + ( 1.0 - r.t / D )

intensidad <- 1.0 - hits / NSAMPLES

A mayor número de samples (NSAMPLES) lanzados (distribuídos), más cubrimos el hemisferio con lo que el mapa de oclusión será más suave y preciso. En el ejemplo que muestro más abajo lanzo en un rango de 32 a 64 samples.

Otra nota de esto, es que es una técnica que no tiene en cuenta ninguna luz en escena, solo la geometría, es por eso por lo que se llama "ambient" por lo de la luz ambiental.

La intensidad ambiente obtenida la podemos combinar con la componente difusa. La manera en la que se combina aún no sé muy bien como puede ser, pero una forma en la que yo lo he hecho para el ejemplo de abajo es:


intens = compute_amb_occ( O, N, D, 64 )
intens.r = ambient.r + kDiffuse.r * intens.r * dotnl;
intens.g = ambient.g + kDiffuse.g * intens.g * dotnl;
intens.b = ambient.b + kDiffuse.b * intens.b * dotnl;

kDiffuse es el color difuso del material. dotnl es la función Lambertiana. ambient es la iluminación ambiente general.

Los resultados los siguientes, para un color difuso beige para todos los materiales. (click para agrandar).

Si haceis zoom podeis ver zonas con geometría alrededor, sutilmente más oscurecidas, dando una sensación más real. De todas formas, en esta escena el mapa de oclusión es bastante sutil.
Además, el tiempo de renderizado se ha disparado bastante, de unos 14 minutos la escena com AO, y de 20 segundos la escena sin ella. ¿donde quedó el realtime?

Lo próximo... mejorar el rendimiento y materiales.

Raytracing: Ambient Occlusion

2008-10-23T11:30:00.009+02:00

Aquí estoy de nuevo, a las tantas, con el mismo tema.
Después del comentario de Javi Santana he decidido meterle manos al Ambient Occlusion, una técnica de aproximación a la iluminación global, en la que se calcula la intensidad de la componente ambiente de cada pixel, teniendo en cuenta la geometría del entorno cercano.
Para ello se lanzan N rayos en el hemisferio que forma la normal al punto, y estos rayos se pueden seleccionar (sampling) de varias formas: De una forma sistemática como con coordenadas polares (alrededor de la normal), o distribuciones [pseudo]aleatorias (ver Monte Carlo).
La idea es aproximar la siguiente integral:Donde la función de visibilidad V nos da 0 ó 1, dependiendo de el rayo está oculto o no.

Os muestro los mapas de oclusión en mi primera aproximación:
- 64 Rayos aleatorios en el hemisferio.

* Un rango de distancia para considerar oculto un sample. Cada sample que está oculto, se multiplica por un ratio entre distancia al punto y distancia del rango anterior. Los samples que no colisionan no se suman. Luego se computa la media de estos valores. Sería una media ponderada.

* Similar al anterior, con un rango, pero sin multiplicar por el ratio, solamente 0 si no está oculto o 1 si está oculto. Luego se hace la media aritmética.

* Una prueba, en la que no se desechan las colisiones fuera del rango, solamente se utiliza el rango para ponderar (siempre de 0 a 1) cada muestra. No me gusta mucho el resultado.

Se puede ver como hay defectos en el plano derecho. No sé exactamente aún a qué es debido, pero me temo que el sampleo aleatorio en el hemisferio no está del todo fino.

Raytracing. Phong shading.

2008-10-22T02:06:00.006+02:00

Sí, lo sé, estas no son horas. Son aproximadamente las 2:30 am, pero es cuando he podido descansar de los compromisos laborales. :S

En estos ratos de relax, sigo con el raytracer, y lo último ha sido meterle iluminación Phong.

Como sabéis este modelo es una función empírica, no basada en las propiedades físicas de la luz y los materiales, pero es resultona, y sencilla de calcular. Muy básicamente, la intensidad final es calculada mediante la contribución de las componentes ambiente, difusa y especular, y todas dependen del número de luces (sus vectores de incidencia) y de los materiales.

Existe un modelo mejorado de esta BRDF, llamado Anisotropic Phong el cual está bastante interesante.

Os pongo una imagen de muestra, antes sus caracteristicas y la del raytracer:
- antialiasing stochastic supersampling, 16 muestras.
- mismo material para *todo*. exponente specular = 10.0
- un único punto de luz omnidireccional, sin función de atenuación (ya la tengo lista aunque no se está usando).
- iluminación local, profundidad de rayos= 1, no reflexión no refracción.

Features nuevas:
- Phong shading.
- Mejora del binding con python, para poder seleccionar si mostrar (creando una ventana opengl), o guardar el frame a disco (tga/bmp/dds).
- Un thread independiente para renderizar la imagen, y el thread principal para mostrar la ventana opengl, o una barra de progreso en shell. El thread de render va escribiendo sobre la imagen, y el thread principal opengl la va leyendo y mostrando, o espera a que acabe.
- A little bit mejora sobre el cálculo de color de sombra, ahora tiene en cuenta el valor difuso que hay en la sombra, el ambiente y un valor de la intensidad de sombra.

No es mucho, pero en estos ratos libres que tengo no me da más tiempo.

¿Siguiente? Quiero ir poquito a poco...
pero para que os hagais una idea de todo lo que un raytracer moderno puede llegar a tener: (mejor seguir mirando en un entorno de epsilon features)...

- Interseción con otras primitivas y mallas.
- Multiples luces / tipos de luces y factores de atenuación.
- Precálculo de rayos, para poder cambiar la intensidad de las luces y sus componentes en tiempo real, una vez que se ha renderizado la escena.
- Sampling de texturas.
- Materiales.
- Reflexión y transmisión de los rayos.
- Shaders programables (en python).
- Técnicas de sombras suaves, depth of field ... con oversampling.
- Photon Mapping/MLI. Quiero probar con una incursión al mundo de la iluminación global (¿saldré vivo?)
- Cantidad de cosas... pero poco a poco. Os pondré varios links muy chulos que he encontrado.

un saludo a todos, me voy a la cama.

Fantastic League

2008-10-19T12:16:00.004+02:00

Gracias a un ex-compañero de trabajo, he podido saber que el proyecto en el que estuve trabajando durante casi 3 años, por fín ha sido publicado en una conocida web de apuestas.

Lo podeis encontrar en www.digibet.com (pestaña Fantastic League), necesitaréis real player.

La web oficial en www.fantasticleague.com

Grandes recuerdos, grandes jornadas y grandes dolores de cabeza y estómago, pero verlo en funcionamiento me hace sentirme orgulloso de mi parte del trabajo y del equipo.

Raytracing. Escena en python.

2008-10-17T00:49:00.004+02:00

A petición de Javi Santana, muestro el ejemplo de escena en python, la cual es interpretada por el motor.


from raytracing import *
import raytracing


PARAMS= RaytraceParams()
PARAMS.width = 1024
PARAMS.height= 768
PARAMS.AASamples = 24
PARAMS.ambient = rgbf( 0.0, 0.0, 0.03 );
PARAMS.observer.position = v3f(-1.0,2.0,4.0)
PARAMS.observer.lookat( v3f(0,0,0) )
PARAMS.observer.nearDistance = 0.5
PARAMS.observer.farDistance = 15.0
PARAMS.observer.fovY = 0.785398163
PARAMS.imageflags = IMGFLAGS.FLIP_Y
PARAMS.ambient = rgbf(0,0,0.05)

SCENE = Scene()
SCENE.sceneName = "Mi escena desde python"
   
# Creamos las esferas
for i in range(-2,3):
    for j in range(-2,3):
        SCENE.addPrimitive( PrimSphere.create( v3f(i,0.3,j), 0.3 ) )

# Creamos los planos
SCENE.addPrimitive( PrimPlane.create( v3f(0,1,0), 0 ) )
SCENE.addPrimitive( PrimPlane.create( v3f(1,0,0), 2.5 ) )
SCENE.addPrimitive( PrimPlane.create( v3f(-1,0,0), 2.5 ) )
SCENE.addPrimitive( PrimPlane.create( v3f(0,0,1), 5.0 ) )

SCENE.render( PARAMS )

Raytracing (II)

2008-10-16T21:23:00.004+02:00

Un par de técnicas simples añadidas al raytracer:

* Antialiasing: Se trata de lanzar x rayos más por cada pixel del plano de barrido, luego computar la intensidad final del pixel, utilizando las distintas intensidades, normalmente la media aritmética. Específicamente he usado el Stochastic Sampling, esto es, en lugar de dividir el pixel en un grid, se pilla aleatoriamente y se calcula la intensidad de ese rayo en concreto en función de la distancia al centro del pixel. En este caso he usado 16 muestras por pixel, lo que realmente equivale a renderizar la imagen 16 veces su resolución (4x4). El resultado es interesante.

* Una función de variación leve, mediante una semilla, para la "perfección" difusa que muestra la ley del coseno de Lambert,. Esto es simplemente una prueba. La intensidad de la componente difusa se obtiene mediante el producto escalar del vector normal a la superficie del punto de intersección del rayo, y el vector hacia la fuente de luz usada (lo que viene siendo la técnica dot(NL) ). Pues probé a meterle un pequeño ruido y el resultado le da un poco de granularidad a la imagen.

* Binding con python, de forma que la escena está en python. Tanto la definición de las primitivas y luces (escena virtual), como los parámetros de render. Es interesante, ya que ahora tengo una especie de POV.

Imagen sin antialiasing: (click para agrandar)

Imagen con antialiasing: (click para agrandar):

PD: El framerate cae muy mucho, así que de realtime... :(, pero bueno, aún hay que meterle un algoritmo de voxelización para acelerar los cálculos.

Raytracing en tiempo real

2008-10-16T12:19:00.005+02:00

Tengo las primeras imágenes de un Raytracer en tiempo real que estoy programando.
Por ahora tengo lo básico, el lanzado de rayos, detección de colisiones con primitivas básicas, iluminación difusa, fuente de luz y sombras. Le quiero meter más features.

Por ahora lo tengo a unos 12fps para 640x480, pero le estoy ya metiendo directivas OpenMP para que me cree automáticamente hilos de ejecución a la hora del barrido de la pantalla, así que cada uno se dedique a una parte de la misma.

También podría usar GPU, pero prefiero primero dominar el raytracing en CPU, y ver hasta que punto puedo paralelizarlo.

Para los que no lo sepais, el raytracing es una alternativa para renderizar una escena en la que se trazan rayos desde el punto de vista del observador (uno por pixel) y se detecta el color que tiene ese pixel con un modelo de iluminación determinado. Hay otros métodos para renderizar una escena, como el rasterizarla (tal y como las tarjetas 3d hacen actualmente para los gráficos en tiempo real) o el radiosity, el cual es el más lento, con trazados de rayos desde los puntos de luz y calculando la contribución de la luz en determinados patches. Los resultados de este último son muy buenos.
El método que estoy haciendo, de raytracing, es el utilizado por infinidad de paquetes como POV, OpenRT, yafray o Maxwell rendering, solo que cada uno utiliza sus modelos de iluminación y técnicas particulares.

La construcción de un raytracer sencillo como el que muestro, es una tarea didáctica muy interesante, y solo involucra algunos bucles y calculos vectoriales, nada complejo, y lo recomiendo para aprender bastante de muchos temas de gráficos. Eso sí, se puede complicar todo lo que se quiera.

Para más información, teneis la wikipedia.

Introducción a la programación paralela

2008-09-25T23:44:00.004+02:00

Hace poco me he comprado el libro "Introducción a la programación paralela" porque lo descubrí por casualidad trasteando por la casa del libro.

Me puse a ojearlo y la verdad es que me gustó bastante.

Ya sabeis que el futuro está en la paralelización (a todos los niveles), y hay que estar prevenido. El libro está escrito por cuatro profesores de universidad (española), y tiene fecha de 2008. Trata:
- Nociones, conceptos y teoría de computación paralela. Tipos, historia...
- Análisis matemático de los algoritmos paralelos. Algoritmia para saber la ganancia en determinados problemas, al aplicar modelos de computación orientados al paralelismo.
- Explica detalles técnicos e introduce dos lenguajes/entornos de programación paralela: OpenMP y MPI, para sistemas de memoria compartida y de pasos de mensajes respectivamente.
- Expone problemas habituales (computables), a los que se les aplican las técnicas de paralelismo, como diferenciación, sistemas matriciales, ...
- Tiene ejercicios y problemas propuestos.
- ... Muchas cosas más ...

La verdad es una auténtica adquisición, por solo 35€, de la que estoy muy contento, y estoy aprendiendo bastante. Y tiene poco de "introducción" la verdad.

http://www.popularlibros.com/libros/INTRODUCCION-A-LA-PROGRAMACION-PARALELA/L0430001268/978-84-9732-674-2

Un saludo compis.

Offtopic: Media

2008-09-10T23:15:00.005+02:00

Aunque me he comprado auténticos clásicos en este tiempo (juegos, pelis y lps), tengo que decir que estoy especialmente contento con las dos últimas adquisiciones:

Terminator 2

Sí, vale. La tenía en VHS en casa de mis padres, pero quería tenerla en DVD.
¿Antigua? Sí, pero marcó época para mí.

7€

SFDK - Los Veteranos

Estos sevillanos tienen un arte tremendo.
Tienen su propia discográfica. Letras increíbles. Llevo tiempo escuchándoles.
Les deseo toda la suerte del mundo.

8€

Saludos compis.

Resign Patterns

2008-07-31T07:39:00.003+02:00

No podeis dejar de echar un ojo al siguiente artículo, donde se comentan patrones de diseños "chungos", en su mayoría extraídos de código antiguo. Son prácticas que no deberían de volver a cometerse.

http://www.lsd.ic.unicamp.br/~oliva/fun/prog/resign-patterns

Bjarne Stroustrup's Homepage

2008-06-10T10:50:00.004+02:00

Un link que todo amante de C++ debería tener entre sus favoritos:
El website personal del creador.

http://www.research.att.com/~bs/

Dentro de la misma podeis acceder a una FAQ bastante interesante sobre estilo y técnica programando en C++:

http://www.research.att.com/~bs/bs_faq2.html

Simple Var & VarManager

2008-06-09T11:03:00.016+02:00

Últimamente he estado investigando un poco acerca de la reflexión/introspección del código C++. Fruto de ello, en mi librería (o plataforma o motor), del que algún día tengo que hablar algo más, he creado una serie de clases para soportar la reflexión C++. Esto lleva a crear una serie de artefactos sobre el lenguaje, haciendo uso de clases globales que registran tipos de datos, prototipos de métodos, etc... y para facilitar la escritura usando macros que se sustituyen por código según los parámetros pasados.
También están los patrones de diseño Factory y Builder.
Aquí podéis leer la diferencia entre ellos.
En el inmediato siguiente post, os enseño el código de Factoría que tengo y muestro su utilización.

Pero ahora, voy a mostrar unas clases que representan un tipo Variant, del que hablé en otro de mis posts. Y una clase que recoge en un diccionario estas variables.
Aunque en mi antiguo puesto creamos un sistema de variables variants, contenidas en diccionarios, y un sistema de reflexión basado en estos y el patrón de factoría, que se enlazaba (binding) con el sistema de script lua, he considerado rehacer este sistema y hacerlo más simple en mi librería. También he intentado minimizar el uso de memoría dinámica (heap), así como las funciones virtuales y tipos polimórficos. Pero claro, esto tiene la desventaja de que mi sistema es menos "flexible" o "extensible" por así decirlo, aunque va bastante rápido y es bastante estable, al no hacer uso extensivo de punteros, memoría dinámica, objetos con contador de referencias...

Primero voy mostrar ejemplos de uso, luego paso a describiros otras maneras de implementación y por qué finalmente utilizé esta, y finalmente os mostraré las utilidades de usar algo así.

Uso aislado de la variable Var


// -- Var es un flotante
gy::Var v = 3.0f;
funcFloat( v.asF() );

// -- Ahora es una cadena
v = "hola mundo!";
funcPrint( v.asS() );

// -- Copia en w, la cual es una cadena.
gy::Var w = v;
funcPrint( w.asS() );

// -- Recibirá aquellos tipos que Var tenga sobrecargado su construcción
void funcSomething( const Var& _v )
{
   std::cout << "El tipo de var es: " << _v.getType();
}
funcSomething( 3.0f );
funcSomething( "hola" );
funcSomething( 200 );

Uso simple de VarMan


//-- Recibe parametros de entidad y muestra su tipo
void funcEntity( const gy::VarMan& vm )
{
   gy::Var* e = vm.get("entityType");
   if ( v != 0 )
   {
      std::cout << "Type: " << v->asS() << std::endl;
   }
}

En el siguiente ejemplo se muestra la manera de utilizar el VarMan para contener variables jerárquicamente. Realmente no hace uso de ninguna estructura jerárquica de datos, sino más bien está colapsada en el propio diccionario principal de VarMan. Esto mejora el rendimiento de acceso, al no tener que recorrer ningún arbol, aunque por ejemplo, tendría sus problemas en multithreading, ya que si estuviera en árbol, quizás podría darle una rama del árbol a un hilo, sin tener que interferir con otro hilo que esté trabajando en otra rama, pero de todas formas estas clases no son Thread-Safe (por ahora).
Creación de VarMan con VMBuilder


VarMan vm;
VMBuilder(vm)
   .def( "entityType", "Box" )
   .def( "name", "PandoraBox" )
   .begin_space( "position" )
      .def( "x", 1.0f )
      .def( "y", 2.0f )
      .def( "z", 3.0f )
   .end_space()
   .begin_space( "color" )
      .begin_space( "diffuse" )
         .def( "r", 100 )
         .def( "g", 240 )
         .def( "b", 50 )
      .end_space()
      .begin_space( "specular" )
         .def( "r", 200 )
         .def( "g", 200 )
         .def( "b", 200 )
      .end_space()
   .end_space()
;
funcEntityHier( vm );

Ahora, para acceder a estas variables de manera igualmente jerárquica podemos hacerlo de las siguientes formas:
Lectura de VarMan simple y con VMTraveler


// -- Lectura simple
// -- El '.' nos sirve para acceder al sub-espacio
void funcEntityHier( const gy::VarMan& vm )
{
   std::cout << "Posicion: "
                   << vm.get("posicion.x")->asF() << ", "                         
                   << vm.get("posicion.y")->asF() << ", "                         
                   << vm.get("posicion.z")->asF() << std::endl;

}
// -- Lectura por sub-spacios
void funcEntityHier( const gy::VarMan& vm )
{
   // -- Acceso directo al espacio "color"
   gy::VMTraveler col( vm, "color" );
   float diff[3] = { col.get("diffuse.r")->asF(),
                     col.get("diffuse.g")->asF(),
                     col.get("diffuse.b")->asF() };

   // -- Acceso al espacio color.specular, usando el anterior
   gy::VMTraveler spec( col, "specular" );
   float sp[3] =   { spec.get("r")->asF(),
                     spec.get("g")->asF(),
                     spec.get("b")->asF() };

}

Por último, podemos recorrer el VarMan mediante iteradores:
Recorrido con iteradores VarMan


// -- Recorremos todo, mostrando la variable y su tipo.
void funcPrintAll( gy::VarMan& vm )
{
   gy::VarMan::iterator it = vm.getIterator();
   while ( it->isEnded() )
   {
      std::cout << it.getName() << " = " << it.getVar()->getType() << std::endl;
   }
}
// -- Tambien sobrecarga const
void funcPrintAll( const gy::VarMan& vm )
{
   gy::VarMan::const_iterator it = vm.getIterator();
   while ( it->isEnded() )
   {
      std::cout << it.getName() << " = " << it.getVar()->getType() << std::endl;
   }
}

¿Otras maneras de implementación de Var Managers?

Existen otras maneras de implementar un Variant así como un Var Manager de estos.

Una opción alternativa puede ser la de crear un interfaz de Variant, el cual tenga unos métodos virtuales tales que implementen las distintas variables. De esta manera podemos tener variant con diferentes tipos de variables.


struct IVar
{
   virtual float asF() = 0;
   virtual const char* asS() = 0;
   ...
};
struct VarFloat
{
   float asF() { return mFloat; }
   const char* asS() { /* convertir float a cadena y devolver*/ }
   ...
protected:
   float mFloat;
};

struct VarString ...

Luego tendríamos un VarManager que no es más que un diccionario del mismo tipo que VarMan, cuyo tipo sería el puntero al IVar, el cual es polimórfico.
Incluso, una variable que especialice IVar podría ser un propio VarManager, de esta forma podríamos tener un árbol real dentro de un VarManager, sin artefactos de nombres compuestos por ".".
Personalmente evité, como os comenté antes, usar este tipo de implementación, ya que hace un uso extensivo del heap y de las funciones virtuales. Además, hay que tener cuidado con las copias y las referencias a los punteros de las variables. Para ello se usa objetos contadores de referencias así como un tipo smart pointers.
Nota: De esta forma lo usábamos en el trabajo.

Algunos usos más obvios de estos VarManagers

Métodos / funciones con número, tipo y nombres de argumentos variables.
Prototipo único de constructor, para el patrón de factoría es genial, ya que tenemos una clase base que se construye con un VarMan. Todas las clases que hereden han de tener un constructor con VarMan, así podemos tener un único tipo de creación de objeto. Un ejemplo muy simple sería:


class Base
{
   Base( const VarMan& initParams ){ ... }
}

class Derived : public Base
{
   Derived( const VarMan& initParams ) : Base(initParams) { ... }
}

// -- Factoría muy simple.
template<class T>
T* create( const VarMan& initParams )
{
   // Aqui se asume que T tiene un constructor que recibe un VarMan
   return new T( initParams );
}

// -- Construimos el vm y creamos
VarMan vmbas, vmder;
...
boost::scoped_ptr<Base> bas ( create<Base>( vmbas ) );
boost::scoped_ptr<Base> dev ( create<Derived>( vmder ) );

Otro uso que podemos darle a nuestro VarMan puede ser el de diccionario de variables de configuración, tal que podamos leer de un fichero de texto/script externo y usar el VarMan como almacen de estos parámetros leídos. Además se podrían modificar y volver a guardar en el fichero. Se puede implementar externamente o mediante métodos de serialización. El pseudocódigo sería:


// -- Usando serializacion
class VarMan
{
   ...
   // -- Escribe en "sd" los datos del diccionario interno
   void serialize( SerializeData& sd ) { ... }

   // -- Lee de "sd" los datos de diccionario y lo vuelca en nuestro interno.
   void deserialize( const SerializeData& sd ){ ... }
}

// -- IO de ficheros de texto.
class VarMan
{
   ...
   void readFromFile( const char* file ) { ... }

   void writeToFile ( const char* file ) { ... }
}

El formato del fichero puede ser cualquiera. Puede ser un fichero ini, o en algún formato propio. También puede ser un formato similar al de algún lenguaje de script que tengamos en el motor implementado/binded. Por ejemplo puede ser un diccionario de Python o una tabla de Lua. Esto nos ayuda a la hora de parsearlo ya el intérprete de estos lenguajes lo hacen por nosotros, además de que así facilitamos la compartición de datos entre el script y nuestro sistema.
Un ejemplo de formato propio podría ser:


entityType = "Box",
name = "PandoraBox",
position = {
   x = 1.0,
   y = 2.0,
   z = 3.0
},
color = {
   diffuse = {
      r = 100,
      g = 240,
      b = 50
   },
   specular = {
      r = 200,
      g = 200,
      b = 200
   }
}

Aunque también en formato ini, colapsando la jerarquía:


entityType = "Box",
name = "PandoraBox",
position.x = 1.0
position.y = 2.0
position.z = 3.0
color.diffuse.r = 100
color.diffuse.g = 240
color.diffuse.b = 50
color.specular.r = 200
color.specular.g = 200
color.specular.b = 200

Habría que parsearlos.

Espero que os sea de utilidad. Saludos.

Wikibook: Eficiencia en C++

2008-06-08T21:12:00.003+02:00

Leo a través del grupo comp.lang.c++, que han creado una wiki para mostrar distintos consejos a la hora de escribir un código C++ más eficiente. Tiene algunas cosas interesantes, y está abierto a colaboraciones. Esperemos que vaya creciendo.
Optimizing C++

Y como muestra, un botón:

Template code independent of parameters

If in a class template a non-trivial member function do not depend on any template parameter, define a non-member function having the same body, and replace the original function body with a call to the new function.

Let's assume you wrote the following code:
template 
class C {
public:
   C(): x_(0) { }
   int f(int i) { body(); return i; }
private:
   T x_;
};
Try to replace the above code with the following:
template 
class C {
public:
   C(): x_(0) { }
   void f(int i) { return f_(i); }
private:
   T x_;
};

void f_(int i) { body(); return i; } 
For every instantiation of a class template that uses a function of that class template, the whole code of the function is instantiated. If a function in that class template do not depend on any template parameters, at every instantiation the function machine code is duplicated. Such code replication bloats the program.

In a class template or in a function template, a big function could have a large part that do not depend on any template parameters. In such a case, first, factor out such a code portion as a distinct function, and then apply this guideline.

GOA - Free to play

2008-05-11T16:55:00.004+02:00

GOA es un portal de comunidad que ofrece videojuegos multijugador (por ahora tres), de un buen nivel de calidad y acabado cartoon.

Me ha sorprendido porque solo tienes que darte de alta y descargarte el juego que quieras. Gratis. Jugarás contra otros usuarios online. Yo lo he hecho con Kart n' Crazy y es bastante chulo.

También tiene una opción de pago, en la cual, los usuarios tendrán una serie de valores añadidos a los juegos, aunque no por pagar tienen más ventajas a la hora del juego en sí.

Tengo que buscar otras iniciativas parecidas. Recomiendo que se le eche un vistazo.

GoW2 Trailer

2008-05-10T11:50:00.004+02:00

Hoy exclusiva mundial, Trailer de Gears of Wars 2.

Bigger and better, como dice el director de diseño. Desde luego es bastante impresionante la lucha que aparece en el video, contra los monstruos esos bípedos gigantes con cañon en la espalda (no me acuerdo de su nombre).

http://www.gametrailers.com

Las habilidades del personaje parecen haber mejorado ligeramente, además de que están usando la nueva versión Unreal Engine 3.5, cuya presentación en el GDC08 la teneis aquí:

Aquí teneis una versión con mejor calidad del UE3.5: http://www.gametrailers.com/player/30825.html

Descargas

2008-05-07T09:30:00.005+02:00

Al fin he podido hospedar algunos de los desarrollos que he realizado.
Poco a poco iré subiendo otros que tengo más pequeños y que aún no he podido recopilar, tales como demos y cosas de esas.
En la barra de la derecha, en .Descargas lo teneis.
Para ejecutarlos necesitareis tener una tarjeta gráfica aceleradora 3D normal, así como instalar las dependencias del Visual C++ 2005.

Xungo Game: Es el prototipo de juego para probar temas de gravedad en juego 2D. No tiene prácticamente nada, más que un personaje que se mueve por las paredes y salta, porque lo hice en un fin de semana. Entrada aquí.

Soldados: Demo de un juego simulador de combate urbano. Los modelos, mapa y animaciones los hice yo (así se ve de mal, así que sed buenos please ;), con un poco de ayuda en el modelado del soldado. Se hizo en dos meses partiendo de cero, usando Ogre3D un pelín tuneado. Aquí podeis ver el postmortem (I y II).

Whakman: Hice una prueba de programación durante el proceso de selección en Grin Entertainment. La prueba consistía en varias preguntas teóricas y prácticas, con análisis algorítmico, así como una prueba de programar un juego desde cero, dados unos sprites, usando Python y pygame. Al final no entré, los motivos me los guardo, aunque se que algunos de vosotros lo sabéis. Podéis ver la entrada aquí.

BRIF: No os he hablado de esto. Es una demo, escrita en Java3D y ejecutada a través del protocolo JNLP (Web Start). Simulador para la formación de brigadas de extinción de incendios forestales. Escrita usando JME. Se ejecuta desde el propio enlace, como si fuera un ejecutable, solo que lanza el Web Start, se descarga automáticamente los paquetes necesarios y se comienza a jugar.

Como os comento, iré subiendo más cosas que tengo por ahí sueltas. Así como el source de algunos de ellos.

Un saludo.

Euphoria

2008-05-06T14:07:00.002+02:00

Euphoria es un entorno de desarrollo para animaciones procedimentales en personajes bípedos, por la empresa Natural Motion.
Llevan varios años desarrollando ésto, y en su gama de productos también tienen herramientas para animación en cine. Además, se han aliado con algunas compañías, como LucasArts, para sacar un producto que luce como sigue:

Gracias The Prompt.

The Next Mainstream Programming Language

2008-05-06T13:43:00.006+02:00

Enlace por The Prompt:

Interesante presentación, por Tim Sweeney, sobre lenguajes de programación y la tecnología de desarrollo de videojuegos

The Next Mainstream Programming Language: A Game Developer's Perspective by Tim Sweeney

Google Talk Chatback Badge

2008-04-30T13:36:00.003+02:00

Google no se puede estar quieta.

Quizás algunos lo conocereis, ha sacado ahora un servicio mediante el cual incrustas un iframe en la página que tú quieras, y te aparece un pequeño balloon para que cualquier usuario, tenga o no cuenta en gmail, y a través de la web, pueda enviarte mensajes instantáneos a tu cuenta.

Enlace aquí: http://www.google.com/talk/service/badge/New

Eso sí, yo tengo que estar conectado:

Alternativa3D y Efecto Mar Muerto

2008-04-27T10:51:00.003+02:00

Hola a todos de nuevo, hacía bastantes meses que no volvía a postear nada, pero es que he estado tan ocupado en mi nuevo trabajo, y ha sido tan intensa mi vida en este tiempo, que ni siquiera he podido acercarme a 10kb de las páginas que suelo mirar, por no decir de mantener mi blog.

Pero bueno, las penas os las contaré en otro momento, por ahora un par de noticias que me han gustado en especial:

Alternativa3D (visto en ExeBlog): Es un motor 3D por software para flash, y no está nada mal. http://www.exelweiss.com/blog/414/alternativa3d-nuevo-motor-3d-para-flash/
Efecto Mar Muerto (visto desde CodePixel): Es un artículo que explica ese extraño fenómeno que se dan en algunas empresas punteras en tecnología cuando comienzan a irse una serie d. Interesante de leer. http://www.codepixel.com/content/view/5152/1/

Pues por ahora estos dos temas, que no me da para mucho más tiempo.

Un saludo a todos.

Nueva etapa

2008-01-21T10:08:00.001+01:00

Casi tres años después vuelvo a dar un gran salto.
En éste tiempo he conocido a grandes profesionales y a grandes personas. He aprendido tantísimas cosas tanto en el plano profesional como en el personal, que me resultaría imposible listarlas aquí. Y lo más importante para mí, me he dado cuenta que aún me queda un mundo por descubrir, aprender y explorar.
Es por esto por lo que voy a dar un gran salto. Me traslado a Madrid, donde se me abren nuevos y distintos horizontes en todos los aspectos. Es una sensación muy rara la que siento, de estar ilusionado por el reto que me queda por delante, y de miedo a la vez. Y he de admitir que sin el apoyo de una persona, que considero imprescindible en mi vida, me costaría muchísimo el cambio.

Pero pasteleo aparte, deseo lo mejor a mi ya antigua empresa, Gextech, con sus proyectos. Que cumplan sus objetivos y sueños tanto empresa como empleados. Los echaré de menos.

Deseadme suerte. Planet Media, allá voy.

Fin de semana gravitacional

2007-12-02T21:06:00.000+01:00

Sí, vaya título más raro, pero no sabía cómo describir éste fin de semana que me he tirado programando a saco.

Después de una semana marcada por Super Mario Galaxy, juegazo que trajo un compañero para probarlo en la oficina, me dije: "tiene que estar interesante programar algo así".
No voy a realizar ningún análisis del juego aquí, más que nada porque seguro que los hay mucho más profesionales por la web. Simplemente baste con decir que ha sido catalogado por muchos como el mejor juego de la historia. Mi opinión, me la guardo. ;)

Pues sí, llegó el viernes por la tarde y resultaba que me pillaba solo en casa, así que, a la carga con el Visual Studio.

1) Lo primero: Saber qué quiero hacer.

Un jueguecillo de plataformas de scroll lateral, pero con todo en 3D, y que el personaje pueda moverse en todas direcciones, ésto es, que pueda trepar por las paredes, o boca-abajo.

2) Segundo: Cómo voy a hacer los niveles.

Quiero tener plataformas que sean auténticas mallas de cualquier forma. Y luego hacer niveles sin tener que andar repitiendo patrones. Habrán plataformas, comportamientos, items y texturas comunes y que se vean entre niveles, pero también flexibilidad para realizar niveles de muy diversa índole. Así pues, aquí tengo un nivel de prueba, con el 3D Studio Max.

3) Tercero: Entorno de trabajo

Me lo pensé bastante. Estoy desarrollando, muy lentamente, un minimotor en C# sobre MDX (Managed DirectX), el cual es bastante interesante y potente a la hora de realizar herramientas como un editor para posicionar entidades en los niveles.
También pensé en usar XNA, ya que estoy ahora tocándolo un poco y me resulta cuanto menos, útil para hacer juegos rapidos y prototipos.
Pero al final me decanté por C++, sobre Ogre3D. Cogí el proyecto de soldados, y reutilizé toda la parte común. Reusé el core, sistema de sonido, de script, de parser de tablas, factoría, patrón de game - actores - acciones, y otras rutinas en común.
Una vez con ésto, me puse a escribir código dependiente de lo que quiero hacer.
Más: Visual Studio 2005 + SP1, Ogre3D, Fmod, lua.

4) Cuarto: Assets.

Comencé modelando simples cajas, y cilindros para las plataformas y player.
Al final, hice el mapa que veis arriba y utilicé un modelo y animaciones gratuíto de la web. No me acuerdo del autor, pero lo pondré en cuanto lo encuentre. Es un modelo muy simple, pero tiene las animaciones que me interesan: Idle, Walk, Run, Jump y Fall. (hacer click para agrandar).

El personaje, tuve que abrirlo con Max8, y exportarlo usando el genial plugin Lexi Export. Pero me daba un fallo, ya que habían vértices que estaban pesados por más de 4 bones. No se usar el Max todo lo que me gustaría, y no funcionaba, pero al final lo que hice (para propósito de pruebas) fue exportar las animaciones como lo denominan PoseAnimation, básicamente, haciendo morphing, con el consiguiente gasto de memoria y tal... no es la mejor opción, pero para tener un modelo que probar.... de lujo!.

5) Quinto: Complicaciones.

Después de haber programado antes, el movimiento de entidades en 3D, de personajes, tener que hacerlo para personajes que se mueven únicamente en 2D al principio me desconcertó.

Luego está el tema de las colisiones con las plataformas. No está del todo afinado, pero estoy usando trazado de rayos con las entidades, que son nuestras plataformas. Si detecta colisión a alto nivel (bounding volumes), calculo la colisión con con la maya (bajo nivel). En ésta colisión detecto el polígono, el punto de intersección y la normal al mismo, ya que me servirá para la orientación del player.

El salto se compone de dos animaciones, jump y fall. Cuando el personaje salta, aplico la animación de jump, y muevo manualmente al personaje (lo elevo en su eje relativo Y ó up vector). Este salto tiene un máximo de altura y tiempo. Terminado, este tiempo, aplico el estado de fall, otra animación. Aún tengo que detectar las colisiones con la cabeza, al saltar, así como hacer que la elevación y caída del personaje no sea lineal, tal y como es ahora. La caída debe de seguir la fórmula de la gravedad y el salto he pensado en algo exponencial.

Por último, la orientación del player cuando está activada la gravedad relativa a las plataformas. Esto lo que hace es, con la normal del polígono donde estoy, calculo el quaternion, y lo encolo para interpolar al nodo de la entidad (para hacer los cambios de orientación más suaves). Además no hay que presuponer ninguna orientación (up, right, zaxis) para los saltos y movimiento.

Resultado: (hacer click para agrandar).

6) Sexto: Lo siguiente?

Pues queda mucho, mucho. Pero la base que yo quería ya está lista. El resultado final es bastante interesante y jugable, ya que puedo saltar en cualquier posición y el personaje va cayendo hacia la derecha, izquierda o hacia arriba !!. Esto da mucho juego ya que puedo poner plataformas que solamente sean accesibles si me pongo de lado y me dejo caer hacia la derecha por ejemplo.

Tengo que hacer el sistema para programar el comportamiento de las plataformas por lua. Ya está casi listo.

Queda programar los items, enemigos, más habilidades, interfaz, etc... O sea, un montonazo, pero ya va siendo interesante, ya que es código de juego puro y duro, y me encanta.

La siguiente imagen muestra la pantalla del juego, con la cámara alejada para ver el nivel cargado. Si la agrandais vereis al personaje en el centro.

Un fin de semana de frikazo total !! Saludos.

Arquitectura multihilos para motores 3D

2007-11-27T14:17:00.000+01:00

No podeis dejar de leer el siguiente artículo.

Arquitectura multihilos para motores 3D.

Vía Min.

10 tipos de programadores

2007-11-27T12:31:00.000+01:00

Me ha resultado, cuanto menos interesante, una lista de diez tipos de programadores distintos.

¿Qué tipo te consideras que eres? Conozco a algunos que encajan a la perfección en algunos tipos.

http://blogs.techrepublic.com.com/10things/?p=262 (inglés)

Vía wisefox.

Cuentas en Outlook 2007

2007-11-09T17:40:00.000+01:00

Me ha resultado curiosa una característica que trae el nuevo Outlook 2007.

Posiblemente muchos de vosotros tendreis varias cuentas de correo web, como hotmail, gmail, yahoo, etc...

Pues bien, si añadimos una nueva cuenta a Outlook, y simplemente le indicamos el nombre de correo electónico, nombre y contraseña, Outlook resuelve con el servidor y se configura automáticamente.

Antes ésto tardaba unos diez minutos, aparte de tener que saber la configuración manual.

Los dos últimos

2007-11-03T14:14:00.000+01:00

Mis dos últimas lecturas han sido:

El fin de la Eternindad - Isaac Asimov

Solo pienso qué se fumó Asimov para tener la idea de éste libro. Es de nuevo original al máximo. La eternidad es una organización que viaja entre años y cambia las realidades para dirigir el transcurso de la humanidad y del tiempo.

En la novela realmente tratan el tiempo como si fuera espacio. Y hasta aquí puedo leer... ;)

El pintor de las batallas - Arturo Pérez-Reverte

Éste autor escribe como nadie. Realmente notas la calidad de sus palabras, cuando lees otros libros en inglés traducidos y lees ésto en español puro.

Alavo cómo puede coger una historia tan pequeña, tan escueta, y realmente simple, y extraerle todo un mundo de sentimientos y realidad alrededor. Saca petróleo de cada una de sus expresiones. No hay ninguna palabra que sobre ni que falte. Me parece un genio. Cada párrafo es para leerlo muy tranquilo y disfrutarlo.

Lo único: No me ha gustado el desenlace. Esperaba otra cosa, pero es artístico hasta el final.

Java : Mi gran desconocido I

2007-11-03T13:02:00.000+01:00

Este post es otro de la serie de post estoy haciendo sobre aventuras y desventuras de un programador cansino con C++, como yo era, descubriendo nuevos entornos, lenguajes y herramientas; y of course, todo relacionado con desarrollo 3D en general.

Un día os contaré cosas relacionadas con C#, que me resultó mejor de lo que pensaba en un principio para escribir juegos, pero por ahora toco mi gran rival y enemigo. El lenguaje al que muchos programadores C tratan con la "punta del pie", pero creo que mayormente es por desconocimiento de sus capacidades (tanto del lenguaje como del programador en sí). Estoy hablando de Java.
Voy a intentar explicar lo que me he encontrado a la hora de enfocar la utilización de Java con respecto al desarrollo de software de entretenimiento, gráfico, y sobre todo 3D. (como siempre, vaya).

Evidentemente, muchos pensarán que: "¿Cómo vas a hacer un juego 3D en un lenguaje ejecutado en una máquina virtual?". Se nos viene a la cabeza que una aplicación 3D necesita de unos algoritmos mayormente costosos recursos como tiempo y espacio. Por lo tanto, necesitaríamos usar un lenguaje a bajo nivel como es C, ya que tenemos acceso a todos los recursos de la máquina (por ejemplo para un mejor control de la memoria), y como es compilado a lenguaje máquina directamente su ejecución no tiene que pasar por la máquina virtual y de esta forma es más rápido.

Bien, perfecto. Teneis razón, además de que no estoy diciendo nada nuevo. Pero también puedo argumentar lo siguiente:

A día de hoy, las operaciones 3D se realizan mayormente (por no decir "todo lo gordo") en la tarjeta gráfica, la cual acelera por hardware éstas operaciones, ya sea usando la api gráfica con fixed pipeline, o usando un lenguaje de shader determinado.
Otro punto a tener en cuenta es que, para nuestro propósitos, no queremos, ni podemos, ni debemos hacer el Crysis 2. Normalmente hablo desde un punto de vista amateur de creación de juegos.
Además, si no eres muy experimentado en C/C++, puedes empezar a hacerte un lio con punteros, referencias, arquitectura de la aplicación ... lo que se traduce principalmente en fallos en runtime y en memory leaks a punta pala.
La independencia de la plataforma es algo que con el auge de entornos domésticos en Linux y Mac, es algo muy a tener en cuenta, y Java nos proporciona ésto mucho mejor que tener que desarrollar nuestras propias clases de abstracción.
Mediante JNI en java, tenemos acceso a librerías escritas en cualquier lenguaje. A Dlls como la de DirectX o la de OGL. Aunque no tiene sentido acceder a DirectX si lo queremos mantener multiplataforma.
Y a través del nuevo compilador JIT (a partir de la 1.2), java permite traducir en tiempo de ejecución el bytecode a código nativo optimizado para la plataforma.
JMonkeyEngine.
Protocolo JNLP.
WebStart.

De los tres últimos puntos hablaré más detalladamente.

Creo que por éstas cosas, y por algunas otras que se me escapan, podemos decir que java es un candidato interesante a la hora de programar algún jueguecillo. Parece que se está haciendo un gran esfuerzo por usar Java allá donde siempre ha mantenido C++ la hegemonía.

Pero, de nuevo es obvio, Java nunca podrá llegar a tener mejor rendimiento bruto que C++. Pero nos ofrece otra serie de ventajas, aparte de las ya enumeradas, que son muy buenas a la hora de decidir el lenguaje.

Es por ésto, que decidir qué lenguaje usar para hacer nuestro pequeño proyecto es muy importante. Creo, desde mi minúscula opinión, que decir algo como:

"Vamos a hacer un juego. Ah, por supuesto C++". Es un gran error, pero que mucha gente lo comete. Y luego muchos proyectos terminan siendo inmanejables. Me explico:

Sé, a ciencia cierta, que cuando estamos diseñando o ya desarrollando un proyecto de un juego o una aplicación 3D, en C++, muchos recursos (económicos, temporales y humanos) son dedicados para diseñar un conjunto de librerías internas, clases u otras estructuras de ayuda, para facilitarnos la vida con el lenguaje, y facilitar la tarea a la hora de hacer extensible, leíble y manejable nuestro sistema C++.

Generalmente, estas ayudas que nos creamos, después de un gran esfuerzo, la agruparemos en módulos de un motor, que pensaremos reutilizar y tal... Esa es la idea. Pero con todo esto no estamos más que gastando nuestro tiempo en facilitarnos el uso del lenguaje, alejándonos del quiz de la cuestión, que es escribir código del juego. Esto es como el dilema de escribir nuestro propio motor o usar uno existente (Ogre3D por ejemplo).

Debemos pensar que lo que nos interesa es acabar y escribir código de juego. Aunque por supuestísimo depende de los intereses de cada uno (alguien puede querer hacerse fuerte en C++, o en gráficos).

Como digo, gastamos tiempo programándonos nuestras estruturas auxiliares para hacer callbacks a través de punteros a función o a miembros, o a exportar variables a script, o a llevar la cuenta de las referencias a un objeto, o a muchas otras cosas, cuando lenguajes como C# o Java incorporan todo esto built-in en el lenguaje de por sí.

La reflexión que nos brinda C# o Java es genial. Los delegates de C#, las definiciones inline de Java, etc... Además, de que nos abstraen del manejo de memoria y ofrecen sus propios recolectores de basura. Y casi seguro que aunque tú mismo implementes estos "azucarillos" en el lenguaje C++, no conseguirás el mismo resultado, y habrás perdido un tiempo que puedes emplear en código de juego.

Luego está el tema de que todas estas ayudas no son gratis. Suelen consumir tiempo/memoria, pero realmente, si las usamos bien, la pérdida de rendimiento del lenguaje en sí, puede ser inapreciable para nuestros propósitos.

En resumen: Aunque C++ sea de las mejores opciones (por no decir la única) a la hora de programar un videojuego de última generación, como Crysis, Bioshock, etc... Cada vez más son los desarrollos independientes, y lenguajes que nos brindan más potencia, aunque sean managed como C# o basados en máquina virtual como Java. Y yo personalmente no veo tan claro la utilización de C++ para todo. C++ tiene mucho riesgo en desarrollo para un equipo amateur que lo que le interesa es sacar ese juego original, sin necesidad de ser puntero en tecnología. Un riesgo que es arreglado por esos otros lenguajes de manera nativa.

En el siguiente post escribiré sobre cómo acceder a la tarjeta gráfica a través de OpenGL, usando Java. Qué motor open source buenecito hay disponible. Y la ventaja de usar el protocolo JNLP para distribuir nuestro juego.

De vuelta!

2007-11-01T13:03:00.000+01:00

¡Al fin vuelvo al mundo real! ... o virtual mejor dicho.

Tras casi tres meses de baja por enfermedad, vuelvo a la carga recuperado y con muchas ganas y fuerzas de darle fuerte a la programación y a todo lo que se precie.

No hay peor cosa, al menos para mí, que te veas obligado a tomar reposo durante tanto tiempo, y sí, eso incluye no sentarme delante del ordenador con mis frikadas oportunas. Muy chungo. Y en el curro me han recibido con los brazos abiertos, y eso siempre te da ánimos y ganas de tirar para arriba, cuando vuelves a la carga.

Pues nada, os deleito con una imagen fantástica del igualmente fantástico Zelda Phantom Hourglass. Juegazo donde los haya. Los de nintendo lo han vuelto a conseguir. Engancha desde el principio, y la jugabilidad / control es perfecta.

Después de jugar con él, pienso que parece que ya queda poco que inventar en cuanto a jugabilidad en NDS. Me da la impresión de que han cubierto todo lo que se puede hacer con una Nintendo DS en un juego, y aunque si investigas un poco, ves que lo que ofrece, ya lo hacen otros juegos, también ves que ninguno agrupa tantas cosas, tan bien mezcladas y en una historia tan interesante. Sus joyitas de jugabilidad van desde soplar para apagar antorchas o mover molinos, gritarle a gente que no te oye para que se gire y te vea, trazar rutas para distintas armas e incluso el barco, escribir símbolos para viajar por los mares, tomar anotaciones en mapas y con ellas conclusiones de puntos donde debes de seguir, cerrar la tapa de la consola, sin apagar el juego, para unir dos mapas y poder continuar, tirar de una caña de pescar dibujando una línea, para luego dibujar rápidamente círculos y recoger el sedal, y un largo etcétera.
Y todo esto sin contar con la historia principal y subhistorias secundarias, todas muy cuidadas y ralmente "bonitas".

Para despedirme: Retomaré el blog, seguiré posteando esas cosillas que me gustan, completaré los borradores que tengo pendientes de subir, y nada, ¡a frikear se ha dicho!

¿Quien se ha llevado mi queso?

2007-09-06T17:46:00.000+02:00

Al fin me leí éste libro de ayuda. Fue un regalo de la empresa hace más de un año, lo que pasa es que nunca ví el momento oportuno de leérmelo. Ahora que lo he hecho, realmente estoy pasando por el momento que nos plantea el relato. Y me siento completamente como Hem, uno de sus personajes. Aunque creo que no estoy haciendo bien, no puedo evitar actuar como él.

Es altamente recomendable para intentar encontrar la felicidad en la vida. Lo único que pasa es que se vuelve pesado repitiendo lo mismo una y otra vez, como si estuviera dirigido lectores un poco "cortitos".

Tiene pocas páginas (yo me lo leí en una hora y media o algo así), así que no hay excusas, como la que yo he estado poniendo durante éstos meses. :)

El honor del samurai

2007-09-06T17:36:00.000+02:00

Sigo de baja con anemia. Con fuerzas para muy pocas cosas, asi que aún no he decidido volver a ponerme al ordenador, para recuperar las fuerzas y volver al trabajo con más ganas.

Sigo leyendo y lo último ha sido "El honor del samurai". Me ha gustado mucho la forma de describir las emociones de los personajes y la historia. También me ha gustado que describe la violencia y crudeza de algunos actos de manera sencilla y directa. Y otra cosa buena es que aún siendo el autor japonés no ridiculiza de ninguna manera a los personajes norteamericanos, ni tampoco eleva la condición de los samurais, más bien lo contrario.

No me ha gustado tanto el final, y será porque te lo tienes que imaginar según transcurre la novela, y deja cosas un poco en el aire. ¿o será que quería que la historia siguiera?.

Don't Panic

2007-08-24T13:07:00.000+02:00

Solo comentar que aún estoy recuperándome de un episodio de hemorragia chunga, así que de ordenador nada (he escrito ésto después de casi 3 semanas sin teclear).

Eso sí, he podido leerme dos novelillas, y uno de ellas me gustaría definirla como:

"Fundamentalmente recomendada".

Otro libro que considero que he tardado demasiados años en descubrir.

(IA) Introducción: Agentes

2007-08-03T07:00:00.000+02:00

Necesidades

Antes de todo necesitamos sentarnos, y ver cuales son las necesidades de nuestra IA. Qué necesitamos que hagan nuestros agentes, y qué no. Confeccionar una gran lista con todo lo que se nos ocurra, en sesiones de brainstorming, donde estaría bien contar con las ideas de hardcore gamers objetivos de nuestro juego. Incluso caben detallar ideas descabelladas. La idea es tener una lista que se irá refinando y ajustando a lo largo del proyecto. (Bob Scott).

Para nuestro minijuego de trabajo, tendremos una serie de soldados que estarán patrullando, y que pasarán a buscarte o atacarte si te detectan de alguna manera, como visualmente o escuchando. Estarán por un terreno con obstáculos, y podrán dispararte o huir en caso desfavorable.

Una vez especificado nuestro minijuego, el cual "parece" sencillo, podemos pasar a romperlo en piezas más manejables, y a diseñar la arquitectura más adecuada. Para éste caso, diseñaremos un sistema de agentes y unidades de "inteligencia". Usaremos ésta arquitectura conjunto máquinas de estados para animaciones y comportamiento, y una serie de reglas para representar las transiciones entre estados.

Agentes
Un agente, en términos generales y centrándonos en lo que nos concierne, no es más que una entidad o actor del mundo del juego, que se diferencia de otros, objetos estáticos como cajas o algunos items, en que éste muestra un cierto comportamiento, que no es fijo, que depende de un entorno. O sea, que reacciona de una manera que pueda parecernos "inteligente".

Entonces podemos ver que un agente, no es más que una entidad más del sistema, con una cierta especialización que le hace poseer "inteligencia". Y podemos definir ésta "inteligencia" como unos algoritmos y/o datos.

Vamos a modelar esta relación. Esto es solo una de las maneras posibles. Hay decenas de arquitecturas para agentes y comportamientos. Así como algunas soluciones middleware para lo mismo. Aquí mostraremos una manera natural, flexible y estructurada de hacerlo, pero no es la única ni la mejor:

Hacemos que nuestro agente sea una entidad (o derivada), la cual puede representar información gráfica (para visualización), o física (para colisiones), o incluso de red. También podríamos ser agregado de la entidad.

Un objeto AIUnit es una unidad de pensamiento que se puede "enchufar/desenchufar" a/de un agente. La idea es que podemos tener varias de éstas unidades bajo un agente, idealmente auto-contenidas e independientes entre sí, sin tener que conocerse los interfaces unas de otras, y comunicándose mediante paso de mensajes.

Los métodos polimórficos "on..." son callbacks que son invocados, automáticamente para representar determinados eventos.

onSync() - Síncrono al frame, llamado una vez cada fotograma. Utilizado para interpolar y cálculos con delta de tiempo.
onAsync() - Asíncrono, es llamado de manera fija, cada cierto tiempo, o cada cierto número de frames. Podría ser ejecutado en threads diferentes. Y ejecuta cálculos que no son necesitados en tiempo real al frame (por eso son asíncronos), como pathfinding, detección en rango visual, etc...
onActivate() - Llamado cuando ésta unidad es activada, y comienza a ejecutarse. Por tanto podemos pensar que éstas unidades pueden ser desactivadas (o pausadas).
onDeactivate() - Llamado cuando la únidad es desactivada o pausada.
onMessage() - Aquí se responden a aquellos mensajes que son recibidos, y nos interesan. Cada mensaje tiene una información adicional, que varía según el tipo de mensaje que fuera.

Al menos ya tenemos definido así a grandes rasgos lo que un agente es. Un NPC o un enemigo, sería un agente en el sistema, de forma que tendremos varios de ellos navegando (o no) por el mundo del juego.

Vemos como aquí no se está detallando nada sobre gráficos (modelos, animaciones, etc...), ni sobre colisiones, ni siquiera por ahora estamos diciendo nada de la representación del espacio de mundo. También vemos cómo la lógica de los agentes se mantiene separada. Aislamos el comportamiento de lo que es el agente en sí. Trataremos de diseñar comportamientos genéricos (siempre cuando se pueda) para poder ser asignados a diferentes agentes.

En el siguiente post veremos como diseñar máquinas de estado basándonos en ésta arquitectura, para seleccionar distintas animaciones según el estado de nuestro personaje o agente.

Antz Wars

2007-08-01T14:09:00.001+02:00

Inauguramos un nuevo proyecto: Antz Wars.

Un minijuego 2D casual, propuesto a ser desarrollado en un mes o mes y medio. Mezcla entre estrategia y simulador de hormigas.

Aquí podéis ver su diario de desarrollo, que iré rellenando durante el transcurso de su realización, desde mi punto de vista técnico.
http://antzwars.blogspot.com

Y ésta es su página en Sourceforge:
http://sourceforge.net/projects/antzwars/

No es un juego ambicioso, ni grande, pero los tres desarrolladores esperamos que sea entretenido, rápido de jugar, y sobre todo que nos aporte algún tipo de experiencia en alguno de sus campos de desarrollo. ... Ah se me olvidaba ... por lo menos vamos a divertirnos haciéndolo.

Los propios Dioses

2007-07-30T09:12:00.000+02:00

En éstos pocos días de playa, he tenido la ocasión de leerme el libro de Isaac Asimov, "Los propios Dioses". Aunque no es difícil de leer, sí que tiene partes que pueden llegar a aburrir o a desesperar, ya que pueden parecer bastantes complicadas. Pero todo va tendiendo a explicarse avanzado el libro.

Sobre todo, me ha encantado la segunda parte, en la que comienza hablando de cuatro tipos de seres. Comienza a hablar de sus vidas, sus costumbres, sus formas de reproducirse, etc... cosas tan raras como "...y su borde se puso duro para mostrar desaprobación...", ó "... nunca ninguna emocional admitía que le gustaba fusionarse con las rocas, pero lo hacían ...".

Claro, te quedas extrañado, y no sabes qué estás leyendo, hasta que caes en la cuenta de que está hablando del universo paralelo, con leyes físicas distintas al nuestro, del que hablan en la primera parte de la novela. Primera parte, donde si entiendes algo de física, pues mejor.

A mí me ha gustado bastante, porque es muy Asimov ... fuera de lo común.

Python, pygame y whakman

2007-07-27T17:25:00.000+02:00

Primero comentar que he estado más de medio mes primero ocupado y segundo de playeo (no de la playstation), por eso, no he podido postear los artículos sobre IA que tengo en borrador, pero aunque se extienda más allá de Julio (como era de suponer), seguiré con ellos.

Luego, exponer e invitar a todos aquellos que no han tenido la ocasión de trabajar con Python, como yo hasta hace poco, que lo prueben y lo evalúen muy concienzudamente. Es object-oriented. Bastante rápido. Fácil de embeber en aplicaciones. Existen muchas librerías. Una gran comunidad detrás. ... Y google trabaja mayormente bajo python (incluso han contratado a su creador). Más pros y contras aquí.

Existe una libería para Python, llamada pygame, que utiliza la SDL, la cual nos proporciona una serie de clases y funciones, (una especie de motor), para desarrollar jueguecitos 2D mayormente. Es fácil y rápida.

Bien, resulta de que hace poco he tenido que realizar una prueba para una empresa de desarrollo de videojuegos.

Parte de la prueba era programar un juego, usando únicamente python + pygame, y para el cual me suministraron una serie de sprites. Tenía que hacer un juego estilo pacman, o algo similar con dichos gráficos. Lo realizé en tres días, y algunos screenshots del juego son los siguientes:

Es una serie de niveles laberínticos con scroll 2D, donde tenemos que guiar a nuestro whakman a conseguir todas las monedas sin ser asesinado por fantasmas y calaveras. Podemos usar guantes de boxeo para golpearlos, un patín para acelerar el ritmo y un muelle para saltar enemigos y obstáculos. Los niveles se editan con un editor de texto.

Lo subiré para que os lo podais descargar, junto con otras cosas que tengo que subir, un día de éstos.

(IA) Introducción: Unos párrafos sobre IA

2007-07-03T13:59:00.000+02:00

Definiciones
Definiciones de IA (Inteligencia Artificial) hay muchas. En las asignaturas de universidad, en libros, o en sites. También aquí, en la wikipedia.
No creo que pueda definir IA mejor que las decenas de definiciones existentes, pero sí podría decir lo que parece que se entiende por IA, enfocada al desarrollo profesional de videojuegos.

De manera muy básica, entendemos por IA enfocada a los videojuegos, una serie de algoritmos y estructuras de datos que "simulan" el comportamiento de una determinada entidad del mundo, real o imaginario; que deben de llegar a un compromiso entre precisión y optimalidad; y que desde hace unos años conforma uno de los pilares básicos en el éxito o fracaso de un videojuego. Se está intentando llegar al aprendizaje automático de dichos agentes simulados, a su auto-adaptabilidad al entorno, y a la cooperación entre ellos.

La IA implementada para juegos, no es, por regla general, tan avanzada como la utilizada en el campo académico, en cuanto a redes neuronales y algoritmos genéticos se refiere. Tampoco se pretende que sea así, ya que con máquinas de estados finitas o difusas, así como con sistemas basados en reglas, se cubren las necesidades de la mayoría de los videojuegos (Steven Woodcock en la GDC'01), aunque esto está tendiendo a cambiar.

Últimas tendencias
Desarrollos en la paralelización de operaciones gráficas (mediante GPU), ahora nos permiten disponer de más tiempo de CPU para las tareas de IA. Hace años, no podíamos ver el perfil de programador única y exclusivamente dedicado a IA; pero actualmente ésto está cambiando, y son predominantes las demandas de programadores de IA, por encima de las de programadores gráficos. De hecho, en la mayoría de los desarrollos de hoy, los recursos dedicados a IA son mayores que los de tecnología gráfica.

Otros campos que se están explorando y comienzan a implementarse, es la paralelización de la IA. Con los nuevos procesadores multinúcleo, multiprocesadores y las videoconsolas de nueva generación, es factible la realización de cálculos como raycasting, pathfinding y otros, en paralelo, cuidando siempre las dependencias y otros problemas comunes en programación concurrente.

Técnicas

Existen una diversidad de técnicas que podemos emplear, y dependen del tipo de objetivo que queramos conseguir, algunas vendrán mejor que otras, e incluso otras ni vienen al cuento. Cito algunas: Sistemas expertos, razonamiento automático, máquinas de estado finitas, árboles de decisión, métodos de búsqueda, planificadores, sistemas multiagente, vida artificial y flocking, algoritmos genéticos, redes neuronales, comportamiento emergente, dead reckoning, mapeado de influencia, evasión de obstáculos, análisis de terreno, lógica difusa, visión artificial, y algunas más, e incluso híbridos entre éstas técnicas (AIWisdom).

Es muy importante, como todo, tener bien claro qué queremos conseguir. Qué agentes queremos representar y hasta qué grado de precisión. Cómo influye al gameplay, y al flujo de juego (ai story-telling). Como hacerla configurable y qué sistema de reflexión o scripting es el más adecuado. Hasta qué punto un diseñador (de nivel o de personaje), puede modificar la IA, mediante parámetros o incluso código script ejecutable.

Cosas que también son importantes es mantener simple el código de IA y bien estructurado en capas, de manera que sea más sencillo su depuración. Por ejemplo, uno de los consejos de un AI Wisdom es que distribuyas la inteligencia en los distintos agentes del mundo, no solo en el player. Así es como lo explota "Los Sims". De esta forma, además de simplificar la depuración, ayuda a extender el mundo, pudiendo incrementar la inteligencia de algunos agentes, como humanos, ya que añadiendo una lavadora, descargada desde web, por ejemplo, tiene información de animaciones y reacciones, que pasa mediante mensajes o similar al humano que interactúa con ella.

Distintos géneros de juegos, usarán distintas aproximaciones para simular "inteligencia" en sus personajes. E incluso, hay juegos que basan su gameplay únicamente en la IA, como la serie Sim o Black&White.

Desarrollo
Con esta serie de artículos solamente se pretende dar un paso en éste mundo del análisis y programación de IA para aplicaciones de entretenimiento.

Vamos a ver una serie de técnicas e implementaciones muy básicas, para representar y simular IA en personajes. Al final de todo tendremos un escenario, donde nos podremos mover, y disparar; y habrán enemigos, patrullando y respondiendo a diferentes eventos, que te perseguirán, huirán y trabajarán un poco en equipo. Algo así como un Commandos o un MGS más básico. Podremos modificar el comportamiento de los enemigos sin necesidad de cambiar código interno; y mostraremos objetos visuales de depuración, para ver qué está haciendo la IA en cada momento. Así que ¡al lío!

Julio: IA

2007-07-02T21:29:00.000+02:00

Voy a escribir una serie de artículos~~, por mes,~~ relacionados a un tema en particular. Inauguro con ~~éste mes,~~ algunos post relacionados con investigación en el campo de la IA para juegos en particular.

Esto me va a servir para ir investigando más en éste fascinante campo. Me iré documentando, y afianzando conocimientos, así como citando las fuentes. Intentaré implementar a mi manera todos aquellos algoritmos y estructuras interesantes, sobre un framework (minijuego) que me estoy preparando.

Estos son los temas que tengo planeado ir desarrollando. July Roadmap.

Introducción: Qué se entiende por IA para juegos. Arquitectura para agentes y acciones. Conceptos básicos. Implementación del framework de trabajo. Scripting.
Máquinas de estado: Simples, jerárquicas y basadas en pila. Uso por niveles de las FSM.
Máquinas de estado a bajo nivel: Animaciones.
Máquinas de estado a alto nivel: Comportamiento.
Sistema básico basado en reglas: Transiciones para las FSM. Cambio entre estados. Scripting de las reglas. Raycasting.
Representación del espacio de búsqueda: Tipos de representación para los algoritmos de pathfinding. Generación automática. Estructuras. Representación para juegos de carrera.
Algoritmos de posicionamiento: Pesos y parámetros de los nodos. Como lo hace Killzone.
Pathfinding: Distintos algoritmos. A* y mejoras, teniendo en cuenta pesos.
Tácticas: Algoritmos de IA en equipo.
Learning: Conceptos.

La bibliografía que voy a utilizar va a ser principalmente, la serie AI Wisdom, algo de los Game Programming Gems, artículos en la red de los que iré detallando sus enlaces, algunos conocimientos adquiridos y otros que iré desarrollando.

~~Julio~~ movidito, eh!.

More on Endian

2007-07-02T15:55:00.000+02:00

Un test para ver si estamos en una máquina little-endian:


inline bool isLittleEndian()
{
static unsigned short s = 0x0001;
return *( (char*)&s ) == 0x01;
}

Conceptos básicos, funciones de swap y endianness en networking:
http://www.codeproject.com/cpp/endianness.asp

Más sobre endian, y como escribir código endian-neutral:
http://www.gamedev.net/reference/articles/article2091.asp

Intel White paper sobre endianness y guías para escribir código endian-neutral:
http://download.intel.com/design/intarch/papers/endian.pdf

Endian

2007-07-02T14:12:00.000+02:00

Wisefox me hizo recordar, una cosa que debí poner antes, y es que los ejemplos de código que expongo en los posts de éste blog, están probados y compilados bajo Visual Studio 2005, con su compilador, bajo la arquitectura PC Intel x86.
Esto afecta, entre otras cosas al "Endianness". Así por ejemplo, habría que tener cuidado con las clases xcc/fourcc, al tratar directamente con bytes y tal, ya que la mayoría de videoconsolas utilizan un endian cambiado (big endian), en lugar del de Intel (little endian). Aunque como bien me comenta, algunas arquitecturas tienen un endian configurable.

La siguiente función me invierte de una manera rápida el endian de una palabra de 32 bits. He cogido y he calculado los desplazamientos que al final requieren cada byte, realmente, ya que algunas implementaciones que he visto por ahí, primero aislan los bytes para luego ponerlos en su sitio. Ésta lo hace de manera más óptima:


inline unsigned long inv_endian( const unsigned long _n )
{
return unsigned long( ( _n & 0x000000ff ) << 24 ) |
       ( _n & 0x0000ff00 ) << 8  |
       ( _n & 0x00ff0000 ) >> 8  |
       ( _n & 0xff000000 ) >> 24 ;
}

Precode Macro

2007-06-29T08:46:00.000+02:00

Como hemos visto en el post anterior, hemos definido una macro para realizar un Registro semi-automático en un vector. Esta macro no es más que la definición de un namespace determinado, una estructura y un objeto global estático, cuya construcción nos permite ejecutar el código que queramos.

Las siguiente macros, generalizan un poco más éste concepto, y nos permite definir zonas de código que se ejecutan de la misma manera que antes.


#define BEGIN_PRECODE(UNIT) namespace { struct temp##UNIT{ temp##UNIT(){
#define END_PRECODE(UNIT) } }; static temp##UNIT temp##UNIT##Ins; };

Y ahora podemos definir código dentro de estas dos macros, que deben de ir siempre en pareja y en un modulo cpp.


---- SomeTest.cpp ----
#include "SomeTest.h"
...
BEGIN_PRECODE(SomeTest);
 OutputDebugStringA( "This code is executed on initial constructor calls\n" );
 ClassManager::registerClass( "Zerg", new ZergAllocator() );
END_PRECODE(SomeTest);
...
int main( int, const char* [] )
{
 // Application begins.
}

El nombre pasado a las macros debe de ser un identificador válido, sin comillas, y único en el sistema, ya que lo utilizamos para construir una estructura y una instancia en tiempo de preprocesado, bajo el namespace anónimo.

Namespaces e inicialización automática.

2007-06-28T18:28:00.000+02:00

Algunas veces, es necesario registrar una serie de objetos al comienzo de una aplicación; como podría ser tener un array de nombres de tipos.
Por ejemplo, tenemos la siguiente clase global estática, que contendrá un vector con cadenas de texto. Cada entrada del vector es un nombre de un tipo.


using namespace std;
struct ClassManager
{
 static vector<string>   gClasses;
}
vector<string> ClassManager::gClasses;

Bien, ahora imaginemos que empezamos a diseñar e implementar clases, en distintos puntos del proyecto, como por ejemplo:


class BaseEnemy
{
 ...
};
class BaseItem
{
 ...
};

Y ahora queremos tener en nuestro array global ClassManager::gClasses, registrados los nombres de éstas clases (para éste ejemplo resulta de poco uso almacenar ésto, pero al final del post pondré un ejemplo más interesante).
Habría varias formas de hacer ésto.

Por ejemplo podemos tener en un código principal, que sepamos que se ejecuta una única vez y al comienzo del programa, algo tal que así:


int main ( int , const char*[] )
{
 // Init del ClassManager
 {
    ClassManager::gClasses.push_back( "BaseEnemey" );
    ClassManager::gClasses.push_back( "BaseItem" );
    ...
 }

 // Empieza app.
}

Cada vez que definimos un nuevo tipo, tendremos que venir a éste código y añadir una entrada.
Otra cosa que podemos hacer es registrarlo en el constructor del objeto, lo que pasa que entonces tendremos que mirar si está previamente registrado. Y también pasa que puede que queramos acceder a la lista de clases, antes de haberse registrado alguna.

Una cosa mejor que ésto, es haciendo uso de namespaces y construcción de objetos globales. Si definimos, en un namespace anónimo, una clase como la que sigue:


struct Register_BaseEnemy
{          
 Register_BaseEnemy( const char* _n )
 {
    ClassManager::gClasses.push_back( _n );
 }
};

Entonces podemos declarar, por ejemplo en el cpp de BaseEnemy, una instancia global de ésta clase, y su constructor se invocará justo antes de tan siquiera entrar en el código main. Con lo que tenemos un registro semi-automático.


static Register_BaseEnemy ___BaseEnemy( "BaseEnemy" );

Pero aún sigue siendo ésto, cuanto menos, pesado y engorroso. Tener que definir una estructura auxiliar para cada clase que queramos registrar en nuestro ClassManager. Y luego instanciarla globalmente en algún módulo cpp.
Podemos simplificar algo, haciendo uso de macros, de la siguiente manera:


#define REGISTER_IN_MANAGER( C ) \
namespace ns_Register_##C     \
{                             \
 struct Register_##C         \
 {                           \
    Register_##C( const char* _name ) \
    {                        \
       ClassManager::gClasses.push_back( _name ); \
    }                        \
 };                          \
                             \
 static Register_##C ___##C( #C );\
};

Los tokens # y ## son operadores para el preprocesador, para convertir a constante de cadena y concatenar nombres respectivamente.
Ahora, de esta forma, cuando definimos una clase, en su cpp correspondiente, o en algún cpp que sea linkado, podemos dejar el código como sigue:


---- BaseEnemy.cpp ----
#include "BaseEnemy.h"
REGISTER_IN_MANAGER( BaseEnemy );
...
---- BaseItem.cpp ----
#include "BaseItem.h"
REGISTER_IN_MANAGER( BaseItem );
...

Esto es interesante. Quizás el ejemplo no sea acertado, pero imaginemos que en lugar de tener un vector para registrar string's, tenemos un mapa que aplica string a un functor, por ejemplo, el cual crea una instancia en memoria dinámica de ese tipo que define la cadena. Esto que cuento es una de las implementaciones del patron factory, de la forma que podemos crear instancias según el identificador de cadena de texto con el que la hallamos definido.

Static methods y this == NULL

2007-06-28T08:48:00.000+02:00

Supongamos que tenemos una clase que sigue un patrón determinado como la siguiente:


struct ClassA
{
  ClassA ( float field ): mField( field ){}

  float avg( int a, int b )
  {
     return (a + b) / 2.0f;
  }

  float mul ( int a )
  {
     return mField * a;
  }
private:
  float mField;
};

Si hacemos uso de ésta de la siguiente manera:


ClassA* pA = NULL;
float a = pA->avg( 3, 5 );  // no falla
float b = pA->mul( 4 );     // sí falla

La primera línea no falla. Y ¿por qué?, si tenemos un puntero nulo a ClassA. Pues en principio, el primer método no hace uso de ningún campo de la clase. El segundo sí que lo hace, por lo que, cuando intente leer de la memoria reservada para la clase, en el offset de mField, daría un error, al no tener acceso, en este caso, a la posición de memoria 0x0.

Podemos plantearnos, en métodos como éstos, si realmente dependen de la instancia de la clase, o tienen más sentido ser estáticos a la misma:


...
static float avg( int a , int b )
{
  return ( a + b ) / 2.0f;
}
...
float a = ClassA::avg( 3, 5 );

También vemos que tiene un método como mul, el cual accede a mField. Suficiente para dejarlo como método de la instancia, ya que depende del estado de la misma, para mField. Pero si analizamos el código de la clase, vemos que mField únicamente se inicializa en construcción del objeto. Y no se vuelve a cambiar. Ni siquiera tiene métodos que lo cambien. Podríamos poner estático igualmente éste método.


...
static float mul( int a, float field )
{
  return field * a;
}
...
float b = ClassA::mul( a, 4.5f );

A veces me ha pasado que, en algunos códigos necesitando de una cierta funcionalidad, tenía que crear un objeto, para asignarle un cierto estado, luego llamar al método necesitado y eliminar el objeto. Si podemos sacar patrones como éste, y funcionalidad independiente del estado de la instancia, pues podríamos plantearnos métodos estáticos de clase.

Por último, podemos ver que los parámetros de entrada en ambos métodos, a, b, field, no son modificados, solo leídos. Ayudemos al compilador a optimizar, metiéndolos en registros oportunos, hagamos const:


struct ClassA
{
  inline float avg( const int a, const int b )
  {
     return (a + b) / 2.0f;
  }

  inline float mul ( const int a, const float field )
  {
     return field * a;
  }
};

Postmortem Soldiers II

2007-06-28T00:01:00.000+02:00

En esta segunda y última entrega del postmortem del juego de soldados que he programado, voy a explicar algunos detalles interesantes de la implementación.

Quiero recordar que este juego fue una prueba que me propuse terminar empezar y acabar en dos meses. Tuve que forzarme a ser pragmático y realista con el tiempo y recursos; por lo que algunas técnicas, aunque fueron pensadas y planteadas, no llegaron a ser llevadas a cabo.

Detalles técnicos.

El plugin BSP de Ogre, carecía de un sistema para devolverme información de material del plano de colisión de un rayo. Lo modifiqué para cuando le lanzara una query de test de rayo, me devolviera el nombre del material utilizado por dicho plano. Aunque los bsp (q3) definen materiales con metadata (datos extra aparte del material propiamente dicho), el sistema de materiales de Ogre no. Y al cargar el nivel se creaban los materiales tipo Ogre, a partir de los del tipo Q3, perdiéndose la posible metadata. Es pues por lo que tenía aparte una tabla mapeando el nombre del material a información extra, en éste caso, el nombre del recurso de sonido. En definitiva, lo usaba para saber qué sonido reproducir cuando caminaba por distintos materiales.
El sistema de colisiones, sliding y subidas de desniveles. Todas las colisiones están realizadas a través de lanzar queries de rayos al manager. Tuve que lanzar rayos extras a los lados de la esfera del player para que no atravesara las esquinas, dando la sensación de colisión esfera-plano. Tuve que detectar la colisión en bucle para cuando llegaba a esquinas con otras paredes. Las subidas a desniveles se hizo calculando la altura del siguiente punto a donde caminar, e interpolando hacia el mismo, para la suavidad. La altura del siguiente punto es ajustable, para evitar subir grandes obstáculos. Aún así existe un bug por el cual, los soldados se quedan atrapados en ciertos puntos, colisionando con paredes.
El sistema de partículas, para la explosión de la granada, me dio algún que otro quebradero de cabeza. Éste sistema de partículas utiliza texturas animadas para cada una de las partículas. El control del frame actual de la animación de textura no estaba fino en ogre, de hecho es un bug aún sin resolver, y la forma de hacerlo era la de clonar la textura para cada explosión simultánea en pantalla, eliminándola cuando acababa, de esta forma cada vez que explotaba, empezaba en frame 0.
El sistema de física de la granada, fue implementado utilizando ODE, con un proxy de cápsula. A veces, en algunos planos, la cápsula lo atravesaba. Puse un delta, en el código del ogre del interface con ode, cuando calculaba la distancia al plano, y las colisiones fueron bien.
Para especificar los puntos de la malla navegación para la IA, hice una pequeña clase que me permitía añadir, modificar y borrar puntos del mapa, a modo de editor. Luego podía serializar dichos puntos a un fichero de puntos de navegación. Supongo que podría hacer un algoritmo para rellenar automáticamente el mapa, pero prefería editarlos a mano para seguir con otras cosas.
El sistema de partículas para los disparos de las balas, para los soldados manejados por cpu son distintos que el del avatar. No podían ser iguales porque la impresión que daba visto desde el hombro del avatar, era que no iban en la misma dirección del punto de mira en pantalla.
Cuando el avatar dispara, el arma se mueve arriba y abajo, dando la sensación de que el retroceso de la misma hace al soldado moverse. Este movimiento es aleatorio arriba y abajo. Pero para los soldados manejados por cpu evité ponerlo así, ya que al rato de disparar podía acabar apuntando muy arriba o muy abajo. Aunque podía haberle puesto un código que le hiciera apuntar al frente cuando dejara de disparar.
La cámara debía tener sistema de colisión, ya que cuando acercaba un soldado a una pared y giraba, la cámara acababa apuntando a otra habitación (clipping), y ésto hacía cambiar el conjunto de visibilidad (pvs), con lo cual desparecían algunas cosas. En lugar de tener la cámara como una esfera, se trazaba un rayo desde el punto a donde mirar hasta el punto donde debía estar. Se quedaba en el primer punto donde había colisión. Aunque no le puse interpolación, con lo que a veces podía dar saltos.
Las entidades del sistema tienen un sistema de acciones, que son trozos de código autodependientes, que cuelgan de la entidad. Podemos asignarle / quitarle éstas acciones a las entidades, en runtime, sin problemas. Por ejemplo, tenemos una acción que representa el comportamiento de IA, que puede ser asignado a cualquier soldado. Estas acciones no conocen de otras acciones hermanas, y se comunican mediante el paso de mensajes a través de su padre entidad.
Aunque Lua proporciona una definición y uso de datos en forma de tablas, muy potente, preferí utilizar mi propio formato, a su vez muy similar, para definir ficheros de configuración. Solo utilizo Lua para bind de funciones de código a script. Tengo un parser y un manager de variables que me permiten definir configuraciones como la siguiente. Son tablas, que pueden ser jerárquicas, tantos niveles como se deseen.


soldier
{
  type   "Soldier"
  name   "Avatar"
  mesh   "Soldier.mesh"
  weap   "M4.mesh"
  life
  {
     type   "Life"
     tick   5.0
     def    100
  }
}

El comportamiento de los soldados enemigos es muy básico. Es una máquina de estados con tres estados: { IDLE, ATTACKING, ALERTED }. En el primer estado, el soldado va patrullando, mirando a sitios aleatorios. Cuando escucha una granada, o recibe un impacto o ve a un soldado enemigo, pasa al segundo estado. Atacando, el soldado se mueve entre los puntos de un entorno, mientras dispara al soldado. Cuando deja de ver a ningún soldado pasa a Alerted, estado en el cual se queda mirando un tiempo hacia el último punto donde vió al enemigo. Si pasado un tiempo no lo ve, vuelve a Idle.
Existe un módulo para el soldado, aparte del comportamiento, que es el de movimiento (animaciones). Máquina de estado a bajo nivel. Éste tiene una función que le hace ir desde el punto actual a un punto especificado. Durante éste movimiento, según al punto donde esté mirando, y la dirección a donde se dirige, se selecciona una animación u otra. Haciendo strafe, diagonal, backward, ...
Los soldados enemigos tienen un factor de precisión, que influye en una cierta aleatoriedad en el vector de di sparo.
En último momento, quise implementar un sistema de reseteo, para re-arrancar el juego, sin tener que reiniciar la aplicación. Aqui me di cuenta lo importante que fue tener una de init() / reset(), para volver al estado inicial de los objetos. Pero aún así me costó algunos quebraderos.
El arma tiene configuración de distinto daño según la distancia de impacto. Lo mismo pasa con la granada.

Refinamiento, bugs.

La mayoría de los bugs fueron ocasionados por no saber exáctamente el orden de liberación de ciertos recursos de Ogre . Objetos "atachados" a nodos por ejemplo.

También a la hora de crear entidades y nodos, los cuales deben de tener nombres únicos.

En cuanto a la jugabilidad y al testeo, pues el juego lo han probado varias personas, y la mayoría de feedback han podido ser solucionado mediante el ajuste de parámetros.

Futura versión.
Se está trabajando sobre las texturas y animaciones de los modelos.
El algoritmo de IA debe de ser mejorado, y permitir tácticas en grupo, y funciones de posicionamiento según pesos.
Añadir pathfinding, ya que ésta versión carece de él. Por ahora se está viajando entre puntos visibles de la malla de navegación.
Hardware skinning y normalmapping para modelos.
... etc ...
Un wish-list que a ver hasta que punto tengo tiempo de ir completando.

CryEngine2 Level Editor

2007-06-27T09:03:00.000+02:00

Estos videos tienen un tiempo, pero no deja de ser impresionante el editor que tienen.
Parte I

Parte II

Especialización parcial

2007-06-27T09:01:00.000+02:00

Cuando tenemos una función templatizada de la forma:


template< typename T, typename U >
T* create( const U& _v )
{
 return new T( _v );
}

Podemos usarla para hacer llamadas como las siguientes:


 Protoss* p0 = create<Protoss>( AmmoPack(5000) );
 Protoss* p1 = create<Protoss>( LifePack(200) );
 Zerg* z0    = create<Zerg>( LifePack(100) );
 Terran* t0  = create<Terran>( LifePack(150) );

Nota: Mientras que no introduzcan los nuevos tipos decltype y/o auto en el estandard de C++, tendremos que seguir llamando con create<Type>, ya que el compilador no puede deducir el tipo del argumento T devuelto.

Ahora bien, si deseamos sobreescribir el comportamiento de create() para cuando es de tipo, por ejemplo, Terran podemos hacer varias cosas.
La primera, que se nos viene es una sobrecarga. Puede quedar de la forma siguiente:


template< typename U >
Terran* create( const U& _v )
{
 return new Terran( _v );
}

Y otra cosa que podemos hacer es una especialización del template. Pero solamente queremos especializar para el tipo T, que es el de Terran. El tipo U queremos dejarlo genérico.
Aquí viene el problema. El compilador no nos permite especialización parcial del template.


// Error en compilación.
template< typename U >
Terran* create<Terran, U>( const U& _v )
{
 return new Terran( _v );
}

Aunque sí que nos permite especializaciones parciales para las clases, no lo hace para las funciones a nivel de namespace ni para los métodos. Tendríamos que hacer algo así, para cada uno de los U que pueda permitir con T=Terran:


template< >
Terran* create<Terran, AmmoPack>( const AmmoPack& _v )
{
 // Hacer algo con T = Terran, U = AmmoPack
 return new Terran( _v );
}
template< >
Terran* create<Terran, LifePack >( const LifePack& _v )
{
 // Hacer algo con T = Terran, U = LifePack
 return new Terran( _v );
}

Pero ésto no es lo que queremos. Queremos dejar U genérico, o sea, una especialización parcial.

Pues bien, el Modern C++ nos da una idea, con su patrón Type2Type, definido como sigue:


template< typename T >
struct Type2Type
{
 typedef T Tipo;
};

Con ésto, podemos hacer especializaciones parciales de métodos y funciones, de la siguiente manera:


template< typename T, typename U >
T* create ( const U& _val, Type2Type<T> )
{
 printf ( "Creating element\n" );
 return new T( _val );
}

template< typename U >
Terran* create( const U& _val, Type2Type<Terran> )
{  
  printf ( "Creating specifically Terran\n" );  
  return new Terran( _val );
}

Hemos consegido tener una especialización para T=Terran, y U genérico. Nuestro código de llamada queda de la siguiente manera:


 Zerg* z     = create( AmmoPack(1000),  Type2Type<Zerg>() );
 Protoss* p0 = create( LifePack(200),   Type2Type<Protoss>() );
 Protoss* p1 = create( AmmoPack(3000),  Type2Type<Protoss>() );
 Terran* t0  = create( AmmoPack(5000),  Type2Type<Terran>() );
 Terran* t1  = create( LifePack(100),   Type2Type<Terran>() );
 Terran* t2  = create( SimpleHuman("Pepe"),Type2Type<Terran>() );

 // La siguiente línea no compila, ya que el tipo Protoss no tiene
 // constructor a partir de un objeto SimpleHuman.
 // Protoss* p2 = create( SimpleHuman("John"),Type2Type<Protoss>() );

El resultado es:


---- Output ----
Creating element.
Creating element.
Creating element.
Creating specifically Terran.
Creating specifically Terran.
Creating specifically Terran.

Ya os comenté que el Modern C++ tiene tela ;)

Modern C++ Design

2007-06-27T08:29:00.001+02:00

Libro que recomiendo encarecidamente a todo aquél interesado en la programación genérica usando templates.

Aunque lo había visto varias veces, nunca me dio por abrirlo, pensando que era otro libro más de aprender a programar en C++ donde únicamente son interesantes los dos o tres últimos capítulos. Wisefox me lo pasó y me di cuenta de que no es así.

Este no. Este desde el comienzo se enfoca a los templates, a un nivel avanzado, haciendo un uso magristral de ellos. Te explica el porqué utilizarlos y muchas técnicas útiles haciendo uso de ellos. Además te explica como implementar algunos patrones de diseño, usando templates.

Curioso el capítulo dedicado a los que llaman TypeList. Y ahora me doy cuenta de que la clase List que implementé en otro post, no es más que ésto. Me hubiera ahorrado algún que otro quebradero de cabeza, aunque por otro lado, pensar nunca puede ser malo, no?

Argument list

2007-06-26T18:15:00.000+02:00

Sabemos que la forma nativa y directa de poner una lista de argumentos variable, en lenguaje C es mediante el operador la ellipsis (...), y haciendo uso de unas macros, llamadas va_star(), va_end(), y va_arg().
Esto tiene numerosos inconvenientes, además de que no se yo hasta que punto está recomendado su uso bajo C++. Aquí podeis ver más del tema.


void func( int _a, ... )
{
  va_list   marker;
  va_start( marker, _a );
  // bucle
     int a = (int)va_arg( marker, int );
  // fin bucle
  va_end( marker );
}

Existen múltiples alternativas a ésto.
Por ejemplo, una es utilizando la clase Variant, previamente definida en otro post. Podemos hacer una pequeña clase contenedora. Soportando únicamente los tipos que soporte dicho Variant, como parámetros.
Ahora, nuestra función con lista de argumentos variable:


template< typename T >
void func ( const T& _params )
{
  for ( int i = 0; i < _params.size(); ++i )
  {
     Var v = _params[i];
     // Hacer algo con v.
  }
}

El código de llamada a ésta función quedaría así:


func ( VArray<4>().push(5).push(3.5f).push("hola").push('a') );

Y finalmente nuestra clase VArray queda así:


template< int N >
struct VArray
{
  VArray ():ndx(0){}

  inline VArray& push( const Var& _v )
  {
     array[ndx] = _v;
     ndx++;
     return *this;
  }
  inline Var  pop  ( )  { return array[--ndx]; }
  inline bool empty( ) const { return ndx == 0; }
  inline int  size ( ) const { return SIZE; }
  inline Var  get  ( const int _ndx ) const { return array[_ndx]; }
  inline Var  operator[]( const int _ndx ) const { return get(_ndx); }

private:
  enum { SIZE = N };
  int  ndx;
  Var  array[N];
}

Debo decir que éste código de arriba no hace test de índices ni de rangos. Puede provocar un fallo en runtime si accedemos fuera de array, es solo demostrativo, y debe de mejorarse.
Este VArray tiene tamaño estático en compilación, pero podemos quitar los templates y usar un std::vector para tener un VArray con tamaño dinámico.

Por otra parte, usando la clase List podemos hacer algo similar, y nos permitiría más tipos aparte de los nativos. Unicamente que sería todo resuelto en compilación, con lo que, además de otros contras, no podríamos recorrer nuestro VArray con un bucle, como lo hacemos arriba.

Templates recursivos

2007-06-26T00:22:00.000+02:00

El otro día se me apeteció jugar un poco con los templates de C++, para coger más soltura con ellos. Estuve probando con los templates recursivos, similar al típico ejemplo de factorial. Me puse a implementar una clase template que representara una lista de distintos tipos, estática (tamaño solo resuelto en compilación).
Un ejemplo de código que utiliza ésta clase lista podría ser el siguiente:


// -- Definimos nuestra lista (o tupla), e inicializamos --
List< Player , 
List< Computer , 
List< Door , 
List< Monitor > > > > MyTuple ( Player ( "Juan", 32 ),
    Computer( "Dell", 512, 2 ),
    Door ( 3.0f ),
    Monitor ( "Sony" ) );

// -- Obtenemos referencia al segundo elemento, y lo modificamos --
Computer& c = MyTuple.get<1,Computer>();
c.mem = 1024;

// -- Cambiamos directamente el elemento 2 --
MyTuple.set<2>( Door(5.0f) );

// -- Obtenemos el nº elementos --
printf ( "Size = %d\n", MyTuple.SIZE );

// -- Recorremos lista imprimiendo sus datos --
MyTuple.print( );

Y el resultado sería el siguiente:


---- Output ----
Size = 4
Player "Juan" (32)
Computer "Dell" (1024,2)
Door 5.0
Monitor "Sony"

Al final, acabé con algo similar a la boost::tuple.
El código de mi pseudo-tuple es el siguiente.


// -- Tipo base ( caso base ) para finalizar lista --
struct ListEnd
{ 
   // -- Nº elementos de esta lista vacía --
   enum { SIZE = 0 };

   // -- Casos base en recursión --
   template< int NDX, typename VT > VT& get(){ static VT v; return v; }
   template< int NDX, typename VT > void set( const VT& _v ){ }
   void print(){}
};

ListEnd sirve para especificar el tipo del caso base en recursión del template. Contiene aquellos métodos base, que no realizan nada, y son para hacer que el compilador no proteste.


template< typename T, typename L = ListEnd >
struct List 
{
   // -- Numero de elementos para la lista -- 
   enum{ SIZE = L::SIZE + 1 }; 
 
   // -- Constructors --
   List ( ){}
 
   template< class T0 > 
   List( const T0& _v0 ) { set<0>( _v0 ); }
 
   template< class T0, class T1 >
   List( const T0& _v0, const T1& _v1 ) 
   { set<0>( _v0 ); set<1>( _v1 ); }
 
   template< class T0, class T1, class T2 >
   List( const T0& _v0, const T1& _v1, const T2& _v2 ) 
   { set<0>( _v0 ); set<1>( _v1 ); set<2>( _v2 ); } 

   // ... Sucesivas sobrecargas del constructor aquí ... 

   // -- Accessors --
   template< int NDX, typename VT > 
   VT& get( ){ return mList.get< NDX - 1, VT >(); }
   template<> T& get<0,T>( ){ return mElm; }

   // -- Mutators --
   template< int NDX, typename VT >
   void set( const VT& _v ){ mList.set< NDX - 1, VT >( _v ); } 
   template<> void set<0,T>( const T& _v ){ mElm = _v; }
 
   // -- Recursive print --
   void print ( )
   {
      mElm.print( );
      mList.print( ); 
   }

   // -- Data --
   T   mElm;  // Elemento
   L   mList; // Resto de la lista
 
};

Notas:

Los tipos de datos de la tupla deben de tener el método print() definido.
Para acceder al tamaño (SIZE) de la tupla, se accede mediante la instancia y con el operador punto (.), aunque sea un elemento de una enumeración.
Intenté no utilizar sobrecargas del constructor para permitir lista de inicialización variable. Usando la ellipsis (...) y con va_list, pero no me convenció la transformación de tipos, así como que no me funcionaba va_arg() en algunos casos.
Notad las especializaciones de los métodos templatizados get() y set(). Para cuando NDX vale 0. De esta forma, cubrimos sus casos base en la recursividad en compilación; pero aún así necesitaba definirlos para el tipo ListEnd, porque el compilador me protestaba. A ver si averiguo porqué.
Notad también el tipo por defecto, para el argumento L de la estructura List, definiendo como por defecto ListEnd, el cual marca el final de la lista.
No he podido probar a mantener subtipos List dentro de los tipos de List...(si alguien se anima).

Postmortem Soldiers I

2007-06-25T08:40:00.001+02:00

Hace poco he terminado un proyecto de un "juego" de soldados.

Manejas a un soldado que tiene que tomar un edificio, donde se esconden otros, como si fueran terroristas.

Para ello dispones de un fusil automático, de unas cuantas granadas y del control de tus compañeros que te siguen y actúan a unas órdenes básicas. Tanto enemigos como compañeros están manejados por la CPU con una IA muy básica.

Tecnologías utilizadas.

Me propuse acabar este juego en dos meses. Para ello, tenía que partir de algún desarrollo previo, o alguna librería. Y aunque estoy diseñando un motor, aún está muy verde para ser usado así que me decanté por las siguientes third-parties:

Ogre3D como motor gráfico. Plugin BSP para Ogre, modificado, como manager de escena. Fmodex como sistema de sonido. Lua como sistema de script.

Luego, como aplicaciones utilizadas, caben destacar, Visual Studio 2005 + SP1 para código, SVN como source control, gtk Radiant para diseñar el mapa, 3DStudio Max 8.0 + LexiExporter para los modelos 3D, doxygen para documentación, y alguna que otra herramienta más.

Assets.

Las texturas para el mapa son extraídas de aquí y allá. Del quake3, del rtcw, y del q3ut. Luego, algunas otras me las pasó un compañero, obtenidas fotografiando un edificio.

El modelo del carro de combate está sacado de una librería de modelos. Y los sonidos igualmente de la librería sound ideas 6000, gracias norky.

El skinning del soldado y su geometría están limpiados por dvicente. El modelo de granada y su textura por asaborido. Luego, tanto las animaciones, como el modelo del soldado base, como el diseño del mapa e iluminación, está realizado por mí. (he ahí la precariedad de los mismos). Pero para tirar me valían.

El mapa está realizado bajo gtkRadiant. El modelado bajo 3dsmax 8 y exportado con LexiExporter, a formato mesh de ogre. Solamente está diseñada la planta baja del edificio, y aunque podemos subir a otras plantas, ni la IA lo soporta, ni tampoco vas a ver nada, por que solo se ilumina la planta baja.

En sucesivos posts iré describiendo un poco lo que fue bien y lo que fue mal. Algunas características internas del código, así como muchos pequeños detalles y bugs que fueron consumiendo el tiempo.

DirectX9 SDK, June 2007

2007-06-25T08:00:00.000+02:00

Nueva versión del SDK aquí.
Pulsar Release Notes para ver los cambios y problemas conocidos.

Inlining printf format

2007-06-24T22:32:00.000+02:00

Supongamos que tenemos la siguiente función:


void log( const char* _msg )
{
   ...
}

Muchas veces es necesario llamar a funciones como ésta, con una cadena de carácteres descriptiva, formada por varios campos. A veces se utiliza el siguiente código para componer la cadena y llamar:


{
   char  str[64];
   sprintf ( str, "Player position = %.2f, %.2f, %.2f\n", player->x, player->y, player->z );
   log ( str );
}

Este patron de declarar una cadena, rellenarla y usarla podemos encapsularlo en una función tal que así:


template< unsigned long T >
const char *str( const char *_format, ... )
{
   __declspec( thread ) static char g_str[ T ];

   va_list   marker;
   va_start ( marker, _format );
   vsprintf ( g_str, _format, marker );
   return g_str;
}

Y el código quedaría así:


log ( str<64>("Player position = %.2f, %.2f, %.2f\n", player->x, player->y, player->z) );

Esto crea una cadena estática por cada tamaño que especifiquemos, y por cada thread (__declspec(thread)). La cadena que devuelve debe de ser copiada al momento, y no quedarse con el puntero a char, ya que otras llamadas a str pueden modificarla, al ser static.

Win32 Debug CRT Heap Internals

2007-06-24T17:28:00.000+02:00

Interesante y útil artículo en el cual podemos ver los valores que se asignan a la memoria, por el Visual Studio. Cuando ejecutamos una aplicación en debug, desde el IDE, éste inicializa y maneja la memoria dinámica, asignándole patrones de valores que pueden ser luego reconocibles cuando depuramos al encontrar un bug, por ejemplo.
Aquí teneis el enlace.
Win32 Debug CRT Heap Internals.

Id's Tech 5

2007-06-24T16:21:00.000+02:00

John Carmack ha presentado en la Apple Worldwide Developers Conference de 2007, su nueva tecnología, disponible también ahora para los Macs, llamada Tech 5.

Memory leak detection code snippet

2007-06-24T15:41:00.000+02:00

El siguiente código muestra cómo activar las funciones de depuración del heap, para que muestren un informe de posibles memory leaks. Más información aquí.
He añadido el re-define del operador new, ya que, a mi parecer, faltaba en el enlace anterior, y no me salía la información del fichero donde se produce el leak.
Nota: Solo bajo el depurador de Visual Studio. Compilar en DEBUG (directiva de preprocesador _DEBUG).


// Las 4 siguiente lineas activan la detección de leaks.
#define _CRTDBG_MAP_ALLOC
#define new new(_NORMAL_BLOCK, __FILE__, __LINE__)
#include <stdlib.h>
#include <crtdbg.h>
int main(int argc, char* argv[])
{
  _CrtSetDbgFlag ( _CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF );
  int*  pInt = new int(0);
  char* pStr = new char[256];
  return 0;
}

Y el resultado en la ventana de output es:


---- Output ----
Detected memory leaks!
Dumping objects ->
main.cpp(70) : {127} normal block at 0x003A6740, 256 bytes long.
Data: <                > CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD
main.cpp(69) : {126} normal block at 0x003A6700, 4 bytes long.
Data: <    > 03 00 00 00
Object dump complete.

Nos muestra dos bloques sin liberar, de 256 y 4 bytes respectivamente. Si hacemos doble click en la línea del fichero main.cpp, ya sea de uno u otro bloque, nos lleva exactamente al código que reservó dicha memoria dinámica, y del cual deberemos partir para averiguar el porqué no se está liberando.

El código de arriba saca el report de leaks cuando se acaba la aplicación, en cualquier punto. Si queremos específicamente sacar el report en un punto especificado podemos usar la función _CrtDumpMemoryLeaks(), y también podemos cambiar la salida del report, por si la queremos en un fichero o en una ventana de diálogo, con la función _CrtSetReportMode().

Variant type

2007-06-23T12:00:00.000+02:00

Un tipo de datos Variant brevemente, es aquel que puede representar varios tipos de datos (enteros, flotantes, doubles, fechas). E incluso en runtime se puede cambiar su valor y representación.

C++ estándar no define variant como uno de sus tipos nativos. Aunque Microsoft tiene una implementación del mismo para soporte de objetos COM. C# tiene su tipo object que es como un variant. VB sí lo soporta. Algunos sistemas de script como lua también lo soportan.

En el trabajo usamos actualmente un Variant polimórfico. Es útil para poder extenderlo y hacer que soporte nuevos tipos nativos. Además no obliga a tener memoria reservada para representar un double, si solo estamos representando un byte, por ejemplo. Pero hay que tratar demasiadas veces con memoria dinámica, así como con polimorfismo, con la consecuente penalización de resolver la dirección en las tablas virtuales.

Para casa, utilizaba una idea similar, pero el otro día, tras analizar varios miniproyectos donde los utilizaba llegué a la conclusión que solamente lo estaba utilizando para tipos nativos, y que no me hacía falta la posibilidad de extensión que me ofrecía. Pensé pues en definir un variant más específico, pero intentando ser un poco más óptimo en espacio y tiempo. He visto el boost::variant y boost::any, además, aquí, Christopher Diggins explica algunas desventajas de éstas y expone su propia implementación. Y luego, nada más que hay que buscar un poco para ver otras implementaciones.
Pero me decidí a reinventar la rueda e implementé la siguiente clase. Es sencilla, y no es más que la abstracción de uso de una unión:


struct Var
{
   enum{ V_NONE = 0, V_INT, V_BYTE, V_FLOAT, V_BOOL, V_HANDLE, V_STRING, V_TABLE };

   // -- Constructors
   Var ( )  : type(V_NONE){ asInt = 0; }
   Var ( int _i ) : type(V_NONE){ setI (_i); }
   Var ( char _c ) : type(V_NONE){ setBy( _c ); }
   Var ( float _f) : type(V_NONE){ setF ( _f ); }
   Var ( bool _b ) : type(V_NONE){ setB ( _b ); }
   Var ( void* _h )     : type(V_NONE){ setH ( _h); }
   Var ( const char* _s ): type(V_NONE){ setS ( _s ); }  
   Var ( const Var& _r ): type(V_NONE){ *this = _r; }

   // -- Destructor
   ~Var( )
   {
 destroy(); 
   }

   /// -- Accessors
   inline char  getType( ) const { return type; }
   inline int  asI( )  const { return asInt;}
   inline char  asBy( ) const { return asByte;}
   inline float asF( )  const { return asFloat;}
   inline bool  asB( )  const { return asBool; }
   inline void* asH( )  const { return asHandle; }
   inline const char* asS( ) const { return asString; }
   
   // -- Type conversion operators
   operator int()  const { return asI(); }
   operator char() const { return asBy(); }
   operator float()const { return asF(); }
   operator bool() const { return asB(); }
   operator void*()const { return asH(); }
   operator const char*() const{ return asS(); }

   // -- Mutators
   inline void setI ( int _i ) { destroy(); type = V_INT; asInt = _i; }
   inline void setBy( char _c ){ destroy(); type = V_BYTE; asByte = _c; }
   inline void setF ( float _f){ destroy(); type = V_FLOAT; asFloat = _f; }
   inline void setB ( bool _b) { destroy(); type = V_BOOL; asBool = _b; }
   inline void setH ( void* _h){ destroy(); type = V_HANDLE; asHandle = _h; }
   inline void setS ( const char* _s) 
   { 
       destroy(); 
       type = V_STRING; 
       const int strLen = (int)strlen(_s); 
       asString = new char[ strLen+1 ];  
       memcpy( (void*)asString, _s, strLen );
       asString[strLen] = 0;
   }
   
   // -- Assignment operators
   inline const Var& operator =( const int _i ){ setI(_i); return *this; }
   inline const Var& operator =( const char _c){ setBy(_c); return *this;}
   inline const Var& operator =( const float _f){ setF (_f ); return *this;}
   inline const Var& operator =( const bool _b ){ setB( _b); return *this;}
   inline const Var& operator =( void* _h){ setH(_h); return *this;}
   inline const Var& operator =( const char* _s){ setS(_s); return *this;}
   inline const Var& operator =( const Var& _r )
   {
      destroy();
      type = _r.type;
      if ( _r.type == V_STRING )
      {
         asInt = 0;
         setS( _r.asS() );
      }else
      {
         asInt = _r.asInt; 
      }
      return *this;
   }

private:
   // Invalidate current.
   inline void destroy( )
   {
      if ( type == V_STRING && asString != 0 )
      {
         delete [] asString;
      }
      type = V_NONE;
   }

private:
   // Distinct representations of var.
   union
   {
      int     asInt;
      char    asByte;
      float   asFloat;
      bool    asBool;
      void*   asHandle; 
      char*   asString; 
   };

   // Type of var, only support 256 types!
   char type; 
};

Esta implementación tiene algunos inconvenientes.

No es segura. Si representamos un int y aún así queremos obtener un asS() para tratarlo como una cadena, podemos tener errores en runtime. La compilación no protesta.

Conjunto reducidos de tipos que puede representar. Un double no puede ser representado. Se puede añadir como tipo soportado, aun así.

Byte alignment. La unión ocupa el valor máximo, 4 bytes. Pero tenemos que mantener un campo más, type para indicar el tipo. Este campo, podría ocupar 1, 2 o incluso 4 bytes, da igual, la estructura se alineará a 8 bytes. Pero bueno, entonces con un type de 1 byte como está, podemos usar 3 bytes extras para otra información adicional.

Almacenamos 8 bytes independientemente de si representamos un dato de menor longitud

Aunque también tiene algunas ventajas.

No trata con memoria dinámica. Todo se queda en stack, exceptuando si estamos representando cadenas.

No necesario polimorfismo, para estos tipos básicos. No necesaria tabla virtual.

Poco espacio, 8 bytes.

Facilidad de uso, al sobrecargar operadores y constructores

Pongamos un ejemplo de código de uso:


Var v0 = "hola mundo!";
Var v1 = 5+3;

printf ( "v0 = %s\n", v0 );
printf ( "v1 = %d\n", v1 );

v1 = "my string";
printf ( "v1 = %s\n", v1 );

-------- Resultado ----------
v0 = hola mundo!
v1 = 8
v1 = my string

Bueno, como os comenté, para mis propósitos me viene bien. Aun así habrá que seguir investigando, como siempre.