Wednesday, December 30, 2009

Optimizations are great, but sometimes it helps not to be an idiot...

So, if you've been following my progress on magecrawl, you'll remember my article on optimization trying to cut down on memory usage and map generation time. If not, here and here.

Well, I did a bit of programming this morning before work, and on the way driving to work I had one of those "Wait a second..." moments. Here's the guilty section of code:

private void GenerateMapFromGraph(MapNode current, Map map, Point seam, ParenthoodChain parentChain)
            if (current.Generated)

            current.Generated = true;
            bool placed = false;

            System.Console.WriteLine(string.Format("Generating {0} - {1}", current.Type.ToString(), current.UniqueID.ToString()));

It's that last line that got me. It was some debugging code that I forgot to remove. This function gets called recursively during map generation, a huge number of times and writing to stdout is very slow.

Some baseline numbers (release mode attached to debugger) in generating 100 maps gives me:
  • Before - 47473ms
  • After - 1041ms
Yeah, only a 45x speedup. While all the other optimizations were great, and needed due to memory usage, this appears to be the root cause of my performance issues.

The lesson for today, next time performance is terrible, check stdout to make sure you aren't dumping 10000 lines of text to it during map generation.

Update: Now I just need to find some crazy optimization for my cave map generator and I can get rid of my "loading" screen, since I can generate 100 of the stitch levels in about a second.

Tuesday, December 29, 2009

Economy in Roguelikes - Part 2: Goals

Before I try to lay out what I hope for in Magecrawl's economy, laying out the main goals of what I'm trying to accomplish seems like a good idea. All game design decisions involve tradeoffs, and knowing what problems I really want to solve should highlight why I'm making certain decisions.
  • Fun - This is a game afterall, not an economic simulation. If in the end, it doesn't make the game more fun and replayable, it is not work having.
    • This is why some "optimal" behaviors, such as vacuuming floors clean of items, should be discouraged via game mechanics.
  • Good risk vs reward curve - The game should reward players for risk, and not reward for "safe" grinding or farming.
    • Prevent pudding farmings and other such nonsense.
    • The rewards should be useful for any character type. It is not fun to traverse the dangers of a dungeon to find that the only useful equipment is not useful to you (Finding a +5 awesome sword when you are a unarmed monk for instance).
  • Balanceable - There should never be one always optimal choice. Games are about tradeoffs, and clearly always better choices point toward brokenness. 
    • Some systems make balancing easier or more difficult. Some games will be easier or harder due to the whims of the RNG, but on average things should make sense.
  • Flavor - The system should fit in the existing world, style, and flavor. 
  • Ease to implement - After all, I'm currently a one man team. 
    • The most awesome system in the world would be great in theory, something I can implement "now" and improve later is better.

Wednesday, December 23, 2009

Economy in Roguelikes - Part I: Thoughts

In games that even roughly follow the RPG template, as the game progresses the player or party increases in power on two axes (axis plural apparently, I love English). One axis is character strength or experience, the other being character equipment and items. As someone who's creating a game, specifically a roguelike, making these areas of the game interesting is critical to my success. I'm going to cover some of my recent thoughts on the second area, equipment and items, in a short series of articles.

Anyone who's played a recent RPGish game has seen the drill. You start off equipped no better that a set of dirty rags and a dull knife and end the game in shiny enchanted plate armor and a +5 sword of awesomeness. This provides both a "carrot" to the player (look at how awesome your equipment is), and a "stick" (get behind on the equipment curve and suffer). In almost every game, the way one goes about this is pretty standard.
  • Enemies drop trash items and/or cash that one collects
  • Enemies (sometimes bosses) randomly drop items worth keeping
  • Unused items can be sold to shops for cash.
  • Cash can be used to either buy new equipment, gamble for new equipment, or improve existing equipment
There are some consequence to this system, one major one that has come to my attention is what I've seen called the "vacuum cleaner" behavior: Since in roguelike you have one life, people play optimally. Since every item dropped can be converted to cash, which can be converted into power, one should collect every item and return it to town to sell. This is generally boring, so games have come up with "band-aids" to patch over the issue.
  • "Town Portal" scrolls, to make return to the market less painful.
  • Pack mules or Bag of Holding - Increase amount one can carry, making return trips to sell items less frequent.
  • The items enemies drop are low weight and stackable (Final Fantasy XII), also reducing frequency of return trips.
  • Pets who can return to town and sell items (Seen in Torchlight)
  • Transmute spells, which will convert items to cash.
  • Shops and merchants who are co-located near/in the dungeon at hand.
  • Have a time system, either food or a deadline, which punishes players for returning to town more than the item is worth.
  • Remove the selling system in its entirety (Crawl)
The other half of the issue is returning home to buy better equipment. This almost always follows the Sorting Algorithm of Weapon Effectiveness (read this link). The ways I've seen new equipment introduced into game include:
  • As you travel farther from the starting area, or visit new towns, better equipment appears for purchase. 
  • As you progress in the plot, items shops everywhere restock with better items
  • Many items exist for purchase from the start of the game, but you can't use the good ones due to lack of skill, strength, or level
  • Many items exist for purchase from the start of the game, but are priced out of range of all but the most dedicated grinding players
Analysis of these thoughts and my plans for Magecrawl's economy will have to wait for another post. Let me know if I missed something, or your thoughts in the comments.

Thursday, December 17, 2009

A Christmas Break

Tomorrow I fly home for a ten day visit with family and a wedding to attend. Unless I get stuck in an airport due to weather, I'm not planning on updating this blog until I return.

However, that doesn't mean I won't be programming. I'll be taking my 7 year old Inspiron 5100 (I really need a new laptop) onto the plane to get as much coding done as I can before the batteries die. I'll update with what I've accomplished when I return.

Update: I found out that my "laptop" no longer will hold a charge for more than 10 minutes without dying. So, I guess no programming on the plane for me.

Merry Christmas everyone...

Monday, December 14, 2009

Let there be color (and a request for help)...

I just finished implementing something that didn't take that long, and was long overdue. Color. I'll let the screenshot speak for itself.

The amount of code it took to add this was almost non-existent.

The issue is that I don't have an eye for color. There's a good reason my wife picked out our room colors. Here's what I have so far:

case TerrainType.Floor:
    if (visible)
        return Color.FromRGB(42, 42, 42);
        return Color.FromRGB(15, 15, 15);
case TerrainType.Wall:
    if (visible)
        return Color.FromRGB(83, 41, 0);
        return Color.FromRGB(40, 20, 0); 

If anyone wants to play around with the color scheme in paint (or download the sourcecode and build) and comes up with something that looks better, let me know. I'd love to use something better than what I came up with.

Sunday, December 13, 2009

Evaluation Loop - Why build and setup times matter

Lately I've been thinking about "turn around time" and programming. I'd define this is the time it takes one a change is made to determine if it is correct. There are two parts to correctness:
  • The syntax is correct and the compiler will accept it.
  • The code "does what you want"
The most important resource you have as a developer is your attention. The shorter this cycle is, the more likely you are to not get distracted and get more work done. This is why in magecrawl, I've done what i can to make the turn around time as close to zero as possible.
  • Visual Studio will underline bad code as you type, so you don't even have to hit compile to know you forgot a ';'.
  • C# has a ridiculously short compile and build time. I can build my entire game in less than 3 seconds. 
  • The build step compiles and copies all the associated DLLs into a "dist" directory which has all the associated data files checked in. (No manual setup on new branches/machines).
  • Debug builds turn off the introduction screens, "are you sure" timers, save on closing window, and anything else that slows down testing.
There is one things I'm currently not doing which might reduce "turn around time" even more.
  • Unit and integration test the game engine and utilities module. This way, I could check common use cases with the hit of a button.
My excuse for this is lack of developer bandwidth. Ironically enough, something that could reduce my testing burden is too much of burden right now. As a developer, if other people aren't using my code, I tend to loose interest after awhile. That's why I released a tech demo of magecrawl, and want to get another tech demo finished soon, to get people to use it and keep my interest.

If you are programming at all, it might be worth investing time into making your build more automatic and faster. It's not the time savings as much as the attention savings that are paid back as dividends.

Sunday, December 6, 2009

Iterations - Iteration 6 Complete

So, I'm trying to build my game around "iterations", kinda agile-like. As I mentioned in another article, I've been on iteration 6 for the entirety of this blog's lifetime. Iterations are parallel to the "steps" in 15 steps to write a roguelike, but not exactly. I plan that each iteration takes less than 2 months of work. Here's my iteration list so far:
  • Iteration 1 - "Hello World" - Setup enviroment, walk around a map displayed on screen with doors
  • Iteration 2 - "Save/Load" - Save and load to xml files and xml compressed to .zip
  • Iteration 3 - "It's Alive, and it fights" - Time system, monsters, basic combat, LOS
  • Iteration 4 - "Tech Demo I" - Items, Magic, Dialogs, Data Files
  • Iteration 5 - "Content And Graphics" - Equipment Screen, Ranged Attack Graphics, more spells and items
  • Iteration 6 - "Level Generation" - Multiple map generators
  • Iteration 7 - "Combat" - Differing monsters, more spells/items, Color in game
  • Iteration 8 - "Tech Demo II" - Balancing, stuff needed for a releasable fun mini-game.
Today I just finished iteration 6. The map generator is a tad slower than I'd like, but it's good enough to move on.  While I primarily worked on the level generator, here is other stuff that got thrown in:
  • Help Screen
  • Multiple Levels with stairs (persistent state)
  • Save game if you close window

Optimization II - When the difference between struct and class saves you

So, I'm still on an optimization kick. Map generation is still taking way too long, maps take too much memory. I figured I'd share this story, since it wasn't what I expected.

So, I want the ability to have large levels, even if I don't use them. Say, 250x250, and maybe 50 levels total. My original data structure looked like:

class Map
     private MapTile[,] m_map;

class MapTile
   enum terrianType;
   bool visited;
   int scratch; //Use in map generation algorithsms.

There are two major issues with this, naive set of data structures. The first is that we have an array of classes. In c#, this means we really have an array of references. It looks something like this poor graphic.

This is a bit wasteful in my case, as it added 4 bytes (on 32-bit machines) for every map tile. 250 (tiles) x 250 (tiles) x 50 (levels) x 4 bytes = Around 12.5 megs. So switching to structs (which are stored inline) makes sense.

The second issue was the data types for the MapTiles. Ignoring padding, each maptile is (4 bytes (Enum) + bool (1 byte) + int (4 bytes)) 9 bytes large.

In c#, you can set the underlying type for enums. Since there will never be more that 255 terrain types, I switched that to a byte. The scratch value also never needed more than 255 types, so to byte that went as well. My final size is 3 bytes.

For each of these changes I measured speed and memory usages before and after and compared. This way, I could make sure things like structure padding and such wouldn't ruin my day and make things take the same amount of space anyway. I won't share the numbers, out of embarrassment of how much memory was being uses, but let's just say I use a much more reasonable amount now.

Thursday, December 3, 2009

Optimization - Or when your application eats up 150+ megs of memory generating maps...

So, yesterday I finished stairways and generation of multiple level maps. It's somewhat boring, but it works. I turned the map generator up to generator 5 levels and built a release build, to get an idea of performance. There was a second pause before the game started, a bit more than I'd like to see. I turned it up to 50 maps, and ran into a 30 second pause that the task manager claimed ate up 150 megs of ram.

Now before you get out pitchforks and tell me that all the managed code stuff I talked about in the previous article is the cause of it, I want to make two quick points.
  • Much of that memory would be reclaimed the minute another program asked for it, since it was a lot of garbage the garbage collected was waiting for next collection on.
  • The mistakes I made would have been just as slow in C++, RAII would have reclaimed the memory right away (good), but all the allocations I made would have been just as slow (bad).
I won't bore you with the normal two or three quotes about premature optimization and difficulty in predicting where to optimize, you have already heard them before. What I will say is that every time I run into performance, every single time the cause is not where I'd guess.

A month ago when I was just starting the map generator, I was seeing poor performance moving around. I figured it had to be in my game engine somewhere, maybe in the other actors movement. It turned out to be a part of the GUI that was walking every single tile in my map to draw, even if off screen. Since it was in my GUI loop, just the act of walking all the tiles didn't scale to 200x200 sized maps.

To get back at the story at hand, I figured the way I was generating maps was too slow, that I'd need to rip it out and start over. I made the decision to measure my performance and see what was slow. I'd like to tangent to point out the CLR Profiler and EQATEC Profiler, which are free and awesome. So, it turned out that the subroutine that placed chests and monsters was taking 55% of the entire generation time, and using a crazy amount of memory.

The way the chest and monster placement works for my cave generator is simple: from the generated map, get a clear point that isn't too close to the stairs and use it. Repeat for number of chests and monsters. The problem was in the get a clear point. My naive algorithms walked the entire map and created a list of free points. Then it randomized it, and started grabbing from the front of the list until it found one wasn't too close. I figured it'd be more effective than randomly generating points and checking them in maps with a small percentage of empty tiles. You might see the problem here already, I'm walked all the tiles to painstakingly generate a list, randomize it, and then throw it away when done. When you do this 20+ times per level, then 50 levels in a row, it adds up.

Once I cached the list, the generation time dropped in half, and so did memory. I found another similar issue in the core map generator, see here for details. I'm tracking one more down in the stitch map generator right now.

The "lesson" from this story, if there is one, is that I would have never guessed that GetClearPoint was the culprit. A lot of people claim they want fast code, and might try to optimize where they think it's going to be slow, and do nothing but add bugs and obscure coding constructs. Write the simplest code first (with reason, no bubble sorts), then measure and see what's slowing you down. Once you know that, you can whip out the black magic optimizations there.

Tuesday, December 1, 2009

Why your next roguelike should be in a managed language

So I strongly believe that for new projects, the language of choice is important. It determines what platforms you can target. It can determine your license. It determines the type of code you write. It determines who would be interested in working with you. It determines how quickly your code can run, and how quickly you can write code and find bugs. It is one of the more important decisions you can make, since changing it requires a huge amount of work.

Now I'm going to divide languages into two groups, with a grouping I feel is pretty safe to make:

  • On one hand you have unmanaged languages. Those are ones that are generally considered "lower level". 
    • They almost always have pointers. 
    • They compile down to assembly (or are written in it). 
    • They are generally extremely fast when run, with little overhead when carefully programmed in. 
    • They are also very unsafe. You can scribble over memory almost anywhere. You can corrupt your stack and crash on returning from a function. You can many times walk off the end of arrays and lists and crash. I generally program in these at work, and some bugs can take days to sort out. 
    • Good examples include: C, C++, and assembly
  • On the other hand you have managed languages. The are the ones that are generally considered "high level"
    • They never have pointers, unless dealing with unmanaged code
    • They generally compile to a virtual machine or are interpreted
    • They are slower they the equivalent unmanaged code. How much depends on the language and what your doing
    • They are generally "safe". You get exceptions for doing incorrect things like walking off arrays and such. If you don't catch that exception, your program will still die, but you'll get a nice stack trace.
    • There are many example, the most common include Java, Python, Ruby, C#
When making your decision, you have to make tradeoffs in determining what language to use:
  • What languages you know - People generally lean towards languages they know for their "fun" projects. Others enjoy the chance to learn something new
  • Speed vs. Portability vs. Speed of Development 
    • All things being equal, C is the fastest and most portable. However, it's also the easiest to shoot yourself in the foot with. It also doesn't have a standard Graphics and Input Output library. 
    • Other languages come with portable graphics libraries, but may be too slow. Also note, that most roguelikes are turn based, so speed is in general less of a concern
  • Syntax and language - Sometimes the language itself is not suited for what you want to do with it or is hard to read and write.
  • Library - Sometime there is a library you really want to use for your roguelike, but it can only be used in a given language
    • Note, with many languages, it is possible and sometimes easy to call other languages. C# gives P/Invokes (see libtcod-net), and Java the JNI for example.
  • Ideological - Some people choose languages to write in based upon a philosophy or outlook.
    • Some people reject Java due to it being "too slow", with too slow based upon Java from the 90's on machines twice as slow as today
    • Some people reject C# due to distrust in Microsoft and fear of lawsuits, even though there is a open source implementation of it and the lawsuits could only matter if your using the interop libraries.
I wouldn't be honest in saying I don't have a preference. C# is in my opinion the nicest language to work with. It runs everywhere with mono, it is type safe and fast enough for what I'm working on, and the syntax is close enough to c++ that I picked it up easily. The bindings to libtcod make things nice as well.

However, Java is a good language as well, with many successful roguelikes written in it. Python is another language I enjoy to write in, and has multiple good toolkits to write roguelike in (libtcod, pygame, wcurses).

What I'm not saying here is that unmanaged languages are bad. C is the mothertongue of roguelikes. C++ is very popular as well. I use both at work daily. I'm just saying is that for turn based, and low graphic real time games, the benefits may not out weight the costs.