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

Posts I've Made

In Topic: Share the most challenging problem you solved recently! What made you fee...

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;
    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;
    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);
           microsecond_sleep(rand() % 1000);

    void unlock()
        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. 

In Topic: What do consider with P2P game?

28 May 2014 - 10:28 AM

Some information about how to establish the connection between two hosts behind a firewall : http://en.wikipedia.org/wiki/Hole_punching, especially http://en.wikipedia.org/wiki/TCP_hole_punching ; this might not be an easy trick if you don't have much network knowledge (in which case I suggest you to read http://www.bford.info/pub/net/p2pnat/index.html). An informational RFC has been published on the subject (http://tools.ietf.org/html/rfc5128). http://www.comp.nus.edu.sg/~bleong/publications/netgames09-p2p.pdf provides a state of the market (always interesting). 


Some libraries out there might help (summoning google)


https://github.com/ckennelly/hole-punch is about UDP hole punching. 

http://cs.nyu.edu/zilin/cplusplus/ provides some source code to do UDB hole punching as well


Source code that shows TCP hole punching in C or C++ is harder to find (I found C# examples, Java examples, but I failed to find any C or C++ example). 


But then, the first issue is not connection : it's identification. What is the IP/port address of an unknown distant machine? If you're playing on the local network you can setup some broadcast-based discovery protocol (a la upnp). But you can't use that on the internet and thus you need to setup something to help your users to find another player (using what is called a rendezvous protocol : http://en.wikipedia.org/wiki/Rendezvous_protocol).



In Topic: Why does game GUI have to be rectangles?

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. 

In Topic: std::vector vs std::unique_ptr

28 June 2012 - 09:36 AM

I concur.

Thou shall never manage arrays through anything but std::vector<>.

For one, the std::default_deleter (that you don't want to change, otherwise you manager a std::unique_ptr<T,Deleter> instead of a std::unique_ptr<T>) performs a delete on the underlying object, while you'll want a delete[].

Second, std::vector<> is a smart pointer for arrays. There is no need for anything else.

In Topic: Clean Design vs Efficiency

15 February 2011 - 04:58 AM

I get a feeling that the people who voted for "efficiency" have not worked in a corporate setting for long, or at all. If a design is clean, as it's been said, it will be easy to change large scale factors that would make it efficient later. Developing poor code adds a lot of time when something large scale wants to get changed, and in the end may doom a project. Develop a clean design and you will have, by nature, developed an efficient one as well.

You can't really apply principles suitable for a corporate setting to games (which is what the OP asked about); it's comparing apples to oranges. Well, you can, but you should be aware of what you're doing and why you're doing it, and reasonably certain that you're going to get definite ROI from it.

This is kind of weird to me. Corporate settings are defined to

1/ make sure ROI is here
2/ ensure software quality

Which are desirable properties, even in the game development world.

I agree that in many situations, large corporations tends to implement policies that go too far beyond these goals, mostly because they have to deal with existing softwares or software with a very long life cycle (defense contract in France requires companies to provision development time for 10 to 30 years), because in some situations development teams can be quite large (how many people are working on the next iteration of Windows? Think to a digit in the 2-5 range, multiply by 1000, and you'll get a number which is not very far from the reality) and because (sorry for non game development companies(*)) they also have to deal with a non-null pool of inneficient developers. This is a Bad Thing, true.

But then:

1/ game code base tend to have a life cycle which is longer and longer (see third party and in-house middlewares)
2/ teams are increasingly large (see the credits for TES:Arena, then TES:Daggerfall, then TES:Morrowind, then TES:Oblivion)
3/ in these teams, it is inevitable that the developers efficiency level are disparate.

The game industry is facing the same evolution than the classical software industry, and one of its challenge is to handle this evolution cleanly. More and more software engineers are recruited (10 years back, providing a convincing demo of your skills was enough to get a job in the GI), and game development companies now implement helpers that have been common in the software industry for the past 5 to 10 years (continuous integration, source version tracking, bug tracking, but also architecture documents, multi-team setup and so on).

So in essence, comparing the classical software industry and the game industry is not the same as comparing apples to oranges : it's comparing an old, solid, calm apple tree to a young, shiny and vigorous apple tree. The young tree learnt from the experience of the old tree and try to not reproduce the same errors, with various results (read the various post mortem in GDmag, and see how many of them cite development problems due to a code base that grew out of control).

Having said that, clean design wins every time. Unless you seriously overengineer the thing, with multiple layers of abstraction, the performance trade-off (assuming that there even is one) should be minimal. Then profile, identify your bottlenecks, and tackle them explicitly.

That + code for your platform, know your build settings (including your compiler) and so on. All the things an architect should master before he can call himself a software architect. Vitruvius already saw this point 2000 years ago: you cannot be an architect if you don't know at least a large part of everything which is important in your industry. You have to have a clear understanding of both the theory (architecture principles ...), the history of your engineering field and the practice (implementation). Missing one of these will either lead you to inneficient architecture, reproduction of common errors, unscalable conception, and so on.

(*) disclaimer: I do not work in the game industry (I work in the telecom industry ; I spent most of my work life on embedded, critical systems). I worked in the game industry, and I have continuously studied it for the past 15 years.