Bad, very bad coding practices.

[xahodo]

This project in its current state is a pile of spaghetti code, in which classes are used as an excuse for OO code.

Since when are things like rendering, AI and pathfinding the worry of the class which is responsible for managing the map?

Whichever moron decided that using the vector class from STL is a good idea? You are aware that STL uses lots and lots of exceptions and that exceptions are a definite no-no for real time games, aren't you?

Why not keep things simple and use a static map array (but not for the creatures) which uses 64 bits to store all information needed per tile (owner, type, precise content, etc.). If you remove creatures from the map and keep track of them individually and figure out via some hash-table which one is where (for the viewport).

Also; the rendering engine has no business in the map array whatsoever other then figuring out what to render where (translation: . To make sure surface irregularities are rendered correctly, there should be another map of which it is the sole job to track surface irregularities.

You also seem to forget about cache missed and hits. This will hurt performance in the long run.

[andrewbuck]

This project in its current state is a pile of spaghetti code, in which classes are used as an excuse for OO code.

I happen to be quite proud of my design as a matter of fact. The design manages to abstract most of the underlying working code into accessors methods without too complex of a call chain to get to the "tight loop" code which is speed critical. There are certainly places where it needs some reorganizing but it is not "spaghetti code" by a long shot.

Since when are things like rendering, AI and pathfinding the worry of the class which is responsible for managing the map?

They aren't. The GameMap class is responsible for managing the game map, hence its name. AI is done in the Creature class and rendering is done in ExampleFrameListener class (it uses a semaphore protected message queue to allow other threads to perform rendering ops without creating race conditions or deadlocks). The pathfinding is actually the "worry" of the GameMap class because it involves the GameMap. By putting it in there it avoids having to do accessor calls to other classes in one of the most time critical pieces of code there is.

Whichever moron decided that using the vector class from STL is a good idea? You are aware that STL uses lots and lots of exceptions and that exceptions are a definite no-no for real time games, aren't you?

The same moron that is dumb enough to respond to rants like yours, the moron who wrote the vast majority of the code (which you would know if you had bothered to check the git logs), and the moron who moderates this forum and is wondering if it is worth taking the time to figure out how to ban users who make uninformed claims without bothering to back them up with reasoned argument. As to your assertion that the STL uses lots of exceptions, that may very well be the case and is really the only legitimate point you may have made. I say may because although I wasn't previously aware of this specific issue I had considered the performance implications using templated STL classes instead of handrolling my own. I then weighed this consideration against the potential impact on code readability, maintainability, reliability, and cross platform issues and decided that it made far more sense to use the STL implementations. Weighing heavily on my decision was the fact that something like 85% of security vulnerabilities in C and C++ code come from buffer overflows, which are greatly reduced by sticking to tried and tested STL code which throws exceptions when exceptional circumstances occur instead of just crashing the engine, or worse, allowing for arbitrary code execution injected by the untrusted people you are gaming with. Furthermore, you might be confusing Real-time strategy games which are a common gaming genre and Real-time computing which is a field of computer science dedicated to writing code to run on time critical devices where human lives are often at risk if critical routines take even slightly longer than they are supposed to. Confusing these two terms is a very common mistake as they have a lot in common.

Why not keep things simple and use a static map array (but not for the creatures) which uses 64 bits to store all information needed per tile (owner, type, precise content, etc.). If you remove creatures from the map and keep track of them individually and figure out via some hash-table which one is where (for the viewport).

Well lets see, x and y positions that's 2*16 or 32 bits for position, lets say 4 bits for color (if we set a maximum of 16 seats which I don't like), 4 bits for type, 8 bits for fullness that gives us 48 bits so far. Yeah it looks like I could get all or at least most of the information into a 64 bit unsigned int. Then I could spend a few weeks trying to debug the issues that pop up when it is ported across platforms or onto other hardware. I would also have to give up the ability to do O(log(n)) lookups on tile positions and instead go with O(n) array searches; either that or I could nix the ability to have dynamically expanding non-rectangular maps. But why worry about throwing out one of the key innovations that sets my game apart from the half-dozen other DK clones when I can save 5 whole megabytes of RAM usage.

Also; the rendering engine has no business in the map array whatsoever other then figuring out what to render where (translation: . To make sure surface irregularities are rendered correctly, there should be another map of which it is the sole job to track surface irregularities.

I really have no idea what your talking about here. The rendering engine has no more connection to the map tiles than it does to any other class representing a visible object. I don't know what you mean by surface irregularities and frankly don't care.

You also seem to forget about cache missed and hits. This will hurt performance in the long run.

Cache misses, cache misses, CACHE MISSES?!? You, the person who keeps nagging about including scripting into the core of the game engine and wants the server to do a perodic hash of the ENTIRE game state, are concerned about cache misses. Tell me, how many cache misses does it take to equal the amount of time spent by a call to a script interpreter. Keep in mind that calling the interpreter will likely involve a processor context switch which means flushing the translation lookaside buffer, pushing the registers onto the stack, exectuing a far jump to a new segment, running the code for the interpreter which will likely muck up the cache anyway, then a far jump back, popping all the registers, converting the results of the script back into something my game engine can handle, and a slow agonizing period while the translation lookaside buffer repopulates.

I have no problem with criticism of my design choices involving the game engine. However, if you plan to tell me I should redesign a 15,000+ line codebase of (in my opinion anyway) a pretty well designed system then I would appreciate a bit more informed criticism. You may want to start by reading the ~25 pages of documentation I wrote on how the design is structured. You may also want to have a look at the threading diagram showing how the message passing works to prevent race conditions in the code. For your conveniece you will find a PNG of that diagram attached to this message. The diagram is a bit out of date and doesn't give you a complete picture of the message semantics however it serves as a basic starting point.

-Buck

[svenskmand]

This project in its current state is a pile of spaghetti code ... Whichever moron decided that using the vector class from STL is a good idea? ...

Please stop trolling. If you have constructive criticism then please communicate it in a civil tone, and show evidence to support you claims.

... my game ... my game engine ...

I thought that OpenDungeons was a community effort?

[andrewbuck]

I thought that OpenDungeons was a community effort?

It is, I only used my because I am am the one who designed the aspects of the engine he was complaining about. It is also just much easier to say "my code" than "the community designed code" when you are using it repeatedly.

-Buck

[svenskmand]

It is, I only used my because I am am the one who designed the aspects of the engine he was complaining about. It is also just much easier to say "my code" than "the community designed code" when you are using it repeatedly.

Our (3 characters), my (2 characters). So a difference of 1 character.

[charlie]

Don't be so touchy svenskmand.

Buck has done the vast majority of the hard work for OD. Naturally, given the level of his contribution, he'll think about it in terms of being his game because without him, the project does not exist. Of course, there's a big difference between feeling a sense of ownership (as any majority contributor will) and considering the efforts of others to be your own (for which I see no evidence of Buck doing).

[svenskmand]

I am not trying to be picky/too sensitive, but just wanted to point out that it is a community effort, one should always remember that

And I am very glad for what Andrew has done (and is doing, and will do) to the code This cannot be stressed enough

[Skorpio]

Good reply Andrew, although I find you could have been a bit less polite. I mean how impertinent is it to come here and call a team member a moron? This only deserves a (verbal) kick in the nuts, if you ask me.

The same moron that is dumb enough to respond to rants like yours, the moron who wrote the vast majority of the code (which you would know if you had bothered to check the git logs), and the moron who moderates this forum and is wondering if it is worth taking the time to figure out how to ban users who make uninformed claims without bothering to back them up with reasoned argument.

I <3 that part.

[xahodo]

Ok, I was rude. Point taken (had a lot of stress to cope with recently ).

I'll keep things logically. Here comes some explanation of what I intended:

• Hash of the game state:
  It is not needed to involve all game data in updating the hash. You could simply take the changes as the server receives them and use them to update the hash. No need to recreate the hash again and again. Once in a while you query each client for the hash; if it's different there's something wrong (might indicate a bug or a cheater).
  
• Grinding on and on about scripting:
  Two posts (in a different thread) is grinding?
  
• Map array:
  The map array appears to be nicely structured indeed. However, some things are in there which shouldn't be in there. It also appears to be organized in such a way that it hampers performance.
  
  While the pair class may have its uses, it's not really useful in conjunction with the map; you could just as simply write your own custom hash routine combining X and Y, which would also be a lot faster then simply using the map STL class. But I presume this is one of the things which are on your todo list.
  
• Tile class:
  Why is it the job of a tile to know which creatures are on it? It's more logical for a creature to know where it is and to initiate communication with the tile then it is in reverse (a tile is a passive object, while a creature is an active object). A tile could keep a count of how many creatures are on it (might be of interest to something), but not much else.
  
  In addion: it should be easy and fast to check its neighbors i.e. no need to store pointers to its neighbors. Why not store all tiles in a linear array (no vector class) and write your own safety checks, more attuned to what you need?

Just a note: while I do know what I'm talking about, it has been a while (decades) since I've last coded (would like to pick it up again, though ).

[svenskmand]

It is good that the discussion has been tune to a more civil tone I also think that it would be nice with more programmers on the team, to relieve Andrew once in a while -- we would not like if you get all stressed out.

So xahodo if you have the time, then it would be nice with some help on the project

Another thing, although speed is important, I think that code-readability is more important, but I am not saying that the two cannot go hand in hand

[andrewbuck]

Yes, things have quieted down a bit. I am about to head to work so I this reply will be brief but basically:

Regarding the hash idea -- I really don't need to do this anyway due to the design. All the critical computation happens on the server and periodic updates go out to the clients. If the client becomes inconsistent future updates will propagate out and fix the inconsistency.

On the scripting -- You haven't said an awful lot about it, I was just pointing out that cache misses are the very last thing you worry about. First and foremost is the "big-oh" notation performance of core algorithms, then their implementation, and finally the memory layout to improve cache hits.

Map array -- The tiles are stored in a map rather than a vector or simple array because the map shape is completely arbitrary. It can have rough edges, holes, islands, and it can be grown dynamically during the game. Maps have an O(log(n)) lookup time (log base 2 of course) which means that on a map containing 1,000,000 tiles you can find a tile in a maximum of about 20 hops. Additionally, since all the tiles store pointers to their neighbors, flood filling for things like pathfinding and vision bypass the map lookup entirely and basically just copy the pointers.

Tile class -- The creatures inform the tiles for various reasons. Currently it is primarily to compute vision, you start by flood filling the region the creature can see (using neighbor lookups described above), then you make a list of all the creatures in that region by concatenating the list from each of the tiles. In the future it will be used to implement traps, etc, because when the creature informs the tile about entering/leaving it you can trigger trap code on that event.

Regarding your note at the end, if it has been a while since you coded that would explain our difference of opinion on performance. I looked up a page on your note about STL and exceptions. The penalty you pay is a fixed load/unload code block being called on function entry/exit. In modern algorithm analysis we usually totally ignore things like this as it runs in constant time and on modern multi-core systems it zips by so fast as to not hardly matter. Analysis by gprof shows routines like the vector classes "size()" function being called tens of millions of times, however the total runtime for this function constitues less than a few percent of the total program execution. That's why I mentioned that the "big-oh" notation like O(n log(n)) etc is really what I care about at this point, and the code runs fast enough that a lot of it may well be left as it is, but some things will likely be tuned later on. My plan was to do basically "rapid prototyping" using the mechanisms I have now and then refine them once the engine is mostly complete. I don't want to spend time optimizing a routine that may not even be in the final version of the game anyway.

-Buck

[Andrew]

I use STL in hardwar as well and side strongly with buck on this. Everything you mentioned in your first post is nonsense. You simply don't need to do hard core optimisation in the way that you're suggesting.

Games only need to draw 100 frames a second max. An STL container isn't going to be even noticable forget slowing the game down. I believe STL is used throughout the ogre code base as well.

[Zlodo]

Not that I want to pour any oil on the fire, but let me tell you a story about the performances of STL. Ten years ago, I worked at a video game development studio and we were about to embark on writing a game on the PS2 for the first time.
We had to throw away our old PS1 engine and build something new on top of renderware.

The "shall we use STL containers" question naturally popped, and some guy set out to get a definitive answer. He implemented a set of hand-written containers, optimizing them as well as knew how (he was an experienced coder and was active on the PC demo scene so he had a lot of knowledge of micro-optimization).

He benchmarked those on the PS2 along with the STL implementation that came with gcc. The verdict (he had graphs etc. but I don't have all those docs around anymore): STL containers were as fast or slightly faster, and their memory footprint was as small or smaller than his hand written containers. On top of this STL containers are very well designed and modular.

Regarding exceptions, STL don't use them much at all (go have a look at the current c++0x working draft: http://www.open-std.org/jtc1/sc22/wg21/ ... /n3225.pdf, there aren't many exception throwing specified in most places of the standard library, especially in containers).

Also there is a myth floating about that using exceptions at all has a big performance impact. It actually depends on how well the compiler implements them.

Proper implementations are called "zero overhead exceptions"'. In those implementations, there is no overhead whatsoever in the non exceptional code path. As long as you don't throw, no additional code is executed (there's of course the tests for the error condition that may lead to a throw, but those tests are going to be there however you handle errors).

In a zero overhead exception implementation, what exception and object cleanup handlers have to be executed is solved by walking up the call stack and the instruction pointer on each call along with some precomputed tables that describe what handlers are active at that point of the code. It means that throw is slow because it does a lot of work, but then again it should be obvious that exception handling is supposed to be an exceptional code path. When you're recovering from an error high performance is typically not your priority. Just don't use exceptions for expected, normal occurrences such as reaching the end of a file you're reading.

The problem is of course that one of the most popular C++ compiler, visual studio, is a poorly implemented compiler which wastes its time pushing and popping exception handlers while executing the non-exceptional code path, which means that in VC++ exceptions have an overhead even when you never throw any.

Since this is a forum about free game development, the solution is easy: don't use a shitty compiler. Don't use visual C++. Both gcc and clang have a zero overhead exception implementation.

[StefanP.MUC]

I can only support this. Using another compiler would make it easier for people getting into the project. I failed on getting it to work in Eclipse. I'm not a "hardcore super coding freak", so I surely missed some important points there, but if someone with more "environment knowledge" could provide an Eclipse project or a tutorial on how to get it working in Eclipse (with MingW), I'll definitly would contribute code to ztis project.

[oln]

Yeah, I will have a look at it when I have time. Shouldn't be any large changes needed.

[oln]

Should now work in eclipse on windows. If you follow the guide on the wiki and tell cmake to make eclipse mingw makefiles, it will generate an eclipse project which you can import.

[StefanP.MUC]

Thanks, this is definitly a step in the right direction. I already tried, but cmake didn't find CEGUI. But I'm to new to cmake to get it to work, when I tried.

[MyEmail]

@xahodo: I haven't had a deep encounter with OpenDungeons code so I can't vouch for it, but I definitely disagree with several key points you outlined in your post which I will cover bellow.

Whichever moron decided that using the vector class from STL is a good idea? You are aware that STL uses lots and lots of exceptions and that exceptions are a definite no-no for real time games, aren't you?

You are aware that you can disable exceptions at compile-time, right? (-fno-exceptions). On top of that, so long as you use the STL correctly you will never trigger an exception. So, my question too you is: What kind of crappy code do you write that is triggering STL exceptions?

Why not keep things simple and use a static map array

Well, an extremely obvious reason to keep using stl::vector is the speed boost RAI's provides (that's "random access iterators"). Additionally, using any form of hash-tables (static or dynamic) can be very detrimental to performance under the right circumstances. The purpose of hash-tables is quick access via a key, which will always be much slower than sequence containers' positional access (that's that whole "RAI" thing I was talking about).

I don't know about the other claims this user has made about OpenDungeon's code, but based off of these two claims I would wager the others are equally as bogus.

[oln]

I tried profiling with gprof and I got this result:

I don't know for sure if this is completely accurate, but it seems looking up tiles in the map takes a rather large amount of the processing time.
The map of tiles are currently stored as a std::map<std::pair<int,int>, Tile*>
Even though looking up a tile should be reasonably fast (O(log2(N)), there is a huge amount of lookups to determine visibility.
Wouldn't it be better to use a 2d-array of pointers or references, with an x and y offset if we want to have negative coordinates. Then the lookup would be in constant time.
To allow non-square maps non-existing tiles can simply be null.
If we want the map to be able to grow at some stage it can be resized and repopulated when needed. (e.g if something reaches the edge, the size is doubled.)
Memory usage shouldn't be an issue compared to a map either. The map has to store the x and y values in addition to the tile pointer, so an array could have at least 3 times as many elements and still not use more space, and even then, the space used here is really insignificant.

EDIT:
Might also be an idea to cache tile visibility information for each tile though that is a bit more work.

[StefanP.MUC]

I agree. I don't think we ever need growing maps in-game, so a fixed size array Tile*[x,y] for an in-game map is enough.

And for the editor we don't need realtime visibilty calculations. So we can there still use the dynamic map<pair<int,int>, Tile*>.

With the GameState class we will be able to easily distinguish between editor and ingame state.