Jump to content

  • Log In with Google      Sign In   
  • Create Account


Emmanuel Deloget

Member Since 27 Aug 2003
Offline Last Active Jun 26 2014 01:47 AM

#5161473 Share the most challenging problem you solved recently! What made you fee...

Posted by Emmanuel Deloget on 19 June 2014 - 07:07 AM

One I'm proud of (although it's not game-related): I found a way to store our XML configuration files in a way that allows us to share said configuration in multiple programs directly, without the need to load the XML file again. I did this by pinpointing a shared memory block at the same address in each process.

 

But the most challenging part was to make sure that we were able to read/modify the configuration concurrently without the help of mutexes to limit context switches. So we went the road of spinlocks. But spinlocks introduced some weird priority inversion issue - so in the end we have what is called a Test-and-Test-and-Set spinlock with a variable backoff parameter (it took me a while to figure it out).

 

The classical test-and-set spinlock is mostly written like this:

class spinlock
{
    int sl;
public:
    void lock()
    {
        while (!atomic_test_and_set(&sl, 0, 1)) { }
    }
    void unlock()
    {
        atomic_set(&sl, 0);
    }
};

A TTAS+Backoff is a bit more complex (I added the priority boost, as it also had a major impact on the contention). 

class ttas_backoff_spinlock
{
    int sl;
    int old_priority;
public:
    void lock()
    {
        while (1) {
           if (atomic_test(&sl, 0) {
              if (atomic_test_and_set(&sl, 0, 1))
                  old_priority = save_and_boost_process_priority(HIGH_PRIORITY);
                  return;
           }
           microsecond_sleep(rand() % 1000);
        }
    }

    void unlock()
    {
        set_process_priority(old_priority);
        atomic_set(&sl, 0);
    }
};

With carefull research, you'll find numerous explaination of both the TTAS algorithm. The backoff principle is a bit more obscure: first, its a wait for a random very short time (in the example above: at most 1 millisecond). Second, the wait is done through a system call - that gives the OS the opportunity to schedule.

 

It should be noted that while I'm proud of the solutions I used in this program (it even have a carefully written garbage collector that use some weird heuristic to discover if a block os sizeof(void*) bytes is a pointer to another part of the same memory area or not), it must be noted that I found a better solution to implement the lock. My original reason to use a spinlock had to do with the poor state of the pthread mutex implementation (read: weird, difficult to explain behavior on mutex release when more than one other process waits on the mutex) when the mutex is shared by multiple processes (I'm working on a not-that-recent version of Linux). I finaly found relatively painless solutions to implement named mutexes on Linux that overcomes the pthread mutex limitations - yet I haven't had the time to implement it and fully test it. 




#5156266 Why does game GUI have to be rectangles?

Posted by Emmanuel Deloget on 27 May 2014 - 07:31 AM

 

yes i understand that its easier to implement as a rectangle for easy functionality with the mouse coordinates,but its is possible to make a star button and been able to click it without it being a rectangle point checking.


Of course. Why wouldn't it be possible? It's software - you can make the screen show anything you want and process input any way you want. You can take a mouse position, check if it's contained by any arbitrary shape, and then do whatever the heck you want with that information.

 

 

On the technical side, the shape can be arbitrary. 

 

On the human size, one have to consider how we are procesing shapes. If it's a bit complex we'll lost the purpose of the button and we'll focus on the button itself. That makes it less readable. If it's really complex (for example a really weird concave shape with numerous holes and so on) we'll have problem discerning the button itself, and we won't know where we are supposed to click. 

 

So while we're not limited to rectangle, it's still a good idea to limit ourselves to simple, convex shapes - unless they represent a pattern which is easily understood (such as a country on a world map). Noone wants to make something that is too complex to be parsed by an average humain brain. 




#4765327 Making ratios whole numbers

Posted by Emmanuel Deloget on 26 January 2011 - 05:29 PM


Just since no one seems to have mentioned it yet.. this is a Greatest common divisor problem. Google gave me the following code for it, if shorter is better.

unsigned b_gcd(unsigned a, unsigned b) {
	while (B) b ^= a ^= b ^= a %= b;
	return a;
}

So if you have Width x Height, just divide them both by GCD(Width, Height).

(Guess we found another bug in the source view.. cause those B's were entered as lower case b's :)


That code blows my mind. I thought I understand C pretty well, but I don't understand that.

Anyway, nice thread, thanks guys!


I guess that every body understands a %= b, so the critical part is the b^=a^=b^=a.

So let's rewrite this as the compiler will rewrite it
  while (b)
  {
    a %= b;
    b ^= a; // XOR
    a ^= b; // XOR
    b ^= a; // XOR
  }

Those who know the shortcut might understand that the 3 last lines is a swap(a,B). For those who don't, remember that XOR is

* associative : a XOR b XOR c = (a XOR b) XOR c = a XOR (b XOR c)
* commutative : a XOR b = b XOR a

Let's restart from the begining:
 b1 = b0 XOR a0
 a1 = a0 XOR b1 => a1 = a0 XOR (b0 XOR a0) => a1 = (a0 XOR a0) XOR b0 ==> a1 = b0
 b2 = b1 XOR a1 => b2 = b1 XOR (a0 XOR b1) => b2 = (b1 XOR b1) XOR a0 ==> b2 = a0

So what we effectively do is:

  while (b)
  {
    a %= b;
    std::swap(a,b)
  }

Which is, in essence, Euclid's recursive algorithm written as an iterative loop. In a single, cryptic line of code :)

PS: the b which becomes B is not a bug in the source view ; it's a feature (emoticon's replacement). Which is even more annoying.

Can't this be removed? Emoticons are better when they are used on purpose.


#4761399 [C++] Classes and namespace across DLL boundaries? Will it break?

Posted by Emmanuel Deloget on 19 January 2011 - 01:28 PM

ahh... does that mean if I have namespaces, but if all data types are POD, everything would be good?

Everything that can be linked by C source code shall be good. BTW you don't export POD types - although you can export instances of POD types.

Funny enough, there was a discussion on this very subject on French forum I visit regularly.

You must understand that there are different problems with linking DLL that contains C++ code, especially when the context of compilation of the client program is different of the context of compilation of the DLL.

1) different compilers are using different abtract binary interface (ABI). This means that both their memory model and the name mangling (which is required to transform a C++ symbol name into something that can be understood by a linker which is limited to C) are different. For example, compiler A might not implement a virtual fonction call like compiler B - thus if any exported class defines a virtual function, calling it will likely crash the application. There is an ongoing effort by some compiler vendors to impose a common ABI (most notably on Linux, where the g++ team is leading the effort ; the Intel C++ compiler is supposed to be fully compatible with g++.

2) different compilers are using different implementations of the standard library. Since many types in the C++SL are implementation defined (for example std::vector<>::iterator), the source of possible incompatibilities is quite large.

3) different compilation options might have an impact on the generated code. The most known case is the new/delete couple as implemented by Microsoft in their standard library (disclaimer: this is a simplification. Microsoft did not implement the standard library which is shipped with their products). A Debug build will allocate slighly more memory and put guards around the memory you're supposed to use. It allows it to implement checks on delete - which in turn give you some diagnostic information if you break something. The pointer which is returned by new does not point to the start of the allocated memory block. Of course, in Release mode, this is no longer the case.

In pseudo code
// debug mode ; in this pseudo-code, last is computed from size
new (size)
{
  char* p = allocate (size + 3 * sizeof(int))
  int* pi = (int*)p
  pi[1] = guard value
  pi[0] = size
  pi[last] = guard value
  return &pi[2]
}

delete (p)
{
  int* pi = (int*)p
  pi -= 2
  if (p[1] != guard)
    error : begin guard has been overwritten && die
  size = pi[0]
  if (pi[last] != guard)
    error : end guard has been overwritten && die
  dealloc (size + 3*sizeof(int)) from pi
}

With a code like this one, you can understand quite easily what will happen if I try to delete (in Release) memory that I allocated in debug mode.

So there is plenty of reasons to avoid C++ in DLLs, especially when the DLL and the client program are not compiled in the same context. Some of these problems can be worked around ((3) can be limited by performing memory dealocation in the module that allocated it) and for a limited number of cases, you might be able to make something that work. But that will be a particular case.

I tipically avoid that situation. When I want to export a class from a DLL, I implement C wrapper around that object, including a new_object and delete_object function. All the functions work on a handle, which is (from the client point of view) an incomplete type. I then encapsulate the C interface in a C++ class in my client code. The amount of work to do both the C wrapper and the C++ wrapper of the C wrapper is quite limited (we speak of 1, maybe 2 hours) and I avoid any kinf od issue (I haven't met the case where this solution is limited).


#3497045 OOP/Modular based Game design?

Posted by Emmanuel Deloget on 27 February 2006 - 05:33 AM

Quote:
Original post by Mr_Fhqwhgads
When I say OOP/Modular I mean make it so its easy to add new features without having to modify a whole lot of pre-existing code.

What would be the best way to design a OOP/Modular game? So main() creates a GameCore object which does/handels everything instead of main() doing it. Then have a different class for different parts of the game: NPC, Player, Item, Map, GUI, Networking, Graphics etc.

This this a good way to program a game, or is it better to do everything in main() and call the classes from that? OR is there a compleatly different/better way to desing a OOP/Modular game?


Like steeg, I'm not a professional game programmer, but I am a professional software architect (well... it sounds like a shameless plug; please, don't forget that my opinion is just that: an opinion) so I may be able to help.

Before saying "what should be where" - which is the first cause of OOD failure because doing so already add constraint on your design - you have to find what are your needs and what will be your needs. Too much "wanno do this" and you'll over-engineer your engine (and it will never be perfect). Not enough thinking of your engine future and you'll forget some basic needs that may break your design when you'll implement them.

Before continuing, you must understand that over-engineering is acurately defined by "beyond your comprehension", not by "too complicated". Once you feel lost in your design because of its complexity, it is over-engineered. It also means that you must stick to what you understand in term of OO design - don't try to do "what the others do" (mostly because "the others" are really scary).

The second main thing to do before anything else is to get some information about design patterns and OO design principles (Coad's rule, OCP, LSP, ISP, and so on. You'll find some interesting informations on Object Mentor). It is also good to get a UML modeler and to learn the basics of UML - it will really help you (note that UML can be replaced by OMT or by some other object oriented methodology; UML is prefered).

The reason for learning OO design principles and patterns is that they really enhance your way of thinking.

Now, you have everything ready and you mind full of idea. Launch your UML modeler and create your project.

First, it is obvious that you are going to handle a game. Thus, it seems taht a Game class is required. This game will probably have different states (loading screens, option screens, game lost/won, and so on) so you'll have a GameState class.

Try to define your game states correctly (this is where "game design" as seen by Sandman is important because it will defines the features needed by your game), this will give you your game classes.

Note, you have seen, we only had a look to the game itself (not the technology behind it). This is because the game is a model that is not dependant upon its representation and the user actions (thus, the core game is not dependant on the graphic/input engine). This simple sentence also say that we have 3 different entities to deal with: the game model, its representation and the user actions (I let you find why I say this in this particular order [smile]).

Once you defined your game model, it is easier to spot your needs in term of user input (and how to deal with them) and game representation. This will give your some hints about the objects that are needed in the interface of each main entities (game, representation, input).

Needless to say, you'll have a pretty decent amount of work to do before you put your first line of code in your project.

Oh. Did I mention that coding once you finished (and polished) everything is the only choise you have ? Because coding before the design is finished will give you some headaches if you make a design mistake :)

Of course, as I stated before, this is only my (humble?) opinion [smile]

HTH,


PARTNERS