by andrewbuck » 27 Feb 2010, 15:10
Thanks for the suggestions, I'll try to work on that today. With regard to the level shape, yes, that is how the original dungeon keeper did it; a rectangular level with certain bits filled in with impenetrable rock. I don't like that for several reasons, first it gives the level designers the idea that the level should be square which leads to a lot less interesting and less natural feel for the levels. Second, it makes it inefficient to store the level if you want a mostly rectangular level with a few "arms" sticking out that make the map dimensions bigger, you then have to fill huge areas with the impenetrable rock tiles, even though they don't contribute anything. Finally, this design allows the game engine to add tiles during the game if desired. For example if you just start digging in one direction the game could just keep adding new map in front of where you are digging by randomly generating the map as you go. I'm not sure if we would want to do this or not but I think its a neat idea.
Ultimately the ability to have it be an arbitrary shape isn't much more difficult (and in some ways is easier) to implement than just a rectangular level. The downside is that looking up a tile in the game engine is a bit more expensive, however the tiles are stored in a C++ map which maps x-y coordinates onto tile pointers. Maps offer O(log(N)) lookups so it is fast enough that it is not too much of a drawback (looking up 10,000 tiles can be done in well less than a second, and if you need to loop over the entire map you can get an iterator to loop over it just as fast as you would an array). I also plan to optimize tile neighbor lookups sometime soon here to allow for very fast "floodfill" style calculations to be done. Also, the C++0X standard (actually it will be C++1X now when it finally gets done) has a standard template hash table which will make lookups O(1), this will almost entirely remove the (already small) speed penalty on tile lookups.
-Buck
