My game is running faster. Really faster.
I used gprof to find where the game was spending the more time and improved the code there.
I took some time to replace my own "double-linked-sorted-list" class by a simple stl::vector in some of my code. I still have some places where I want to replace it but I already get really good results. I think it is possible to have a stl container that can manage the sort but I will have to check if it can make things faster than without the sort.
During the various tests, I was surprised by the large amount of triangles rendered. I disabled the objects types (statics, dynamics, statics associated to the tiles) one after the other to discover that I was rendering ALL of the weapons used by the creatures every frame. I changed this to render only the weapons of the visible creatures and got a new performance improvement. Once again a big mistake I didn't discovered early when I only had a few objects in the level.

Here is a new video (bad quality for now, I don't know if YouTube will allow the "watch in high quality" option):

">DDream video 10
Do not hesitate to give me feedback on what to improve/change (like the position/color of the text when you hit or are hit by a creature).

Edit: the "watch in high quality" is enabled now.