Where Does the Time Go?
Forenoon watch, 8 bells (12:19 pm)

Now that my MUD (which I've recently settled on the name ForeverMUD) is getting more stable, I thought I'd run some profiling tools on it. Valgrind is a very cool utility made to do this very thing.

When I first started developing, I wrote in a loop timer that keeps track of the longest processing time as well as the average loop time. After the introduction of a large (16,200 room) world map, the loop times jumped from 10-30 µsec to over 190,000 µsec—no bueno.

So last night I ran Valgrind and used kcachegrind to view the results, which showed me this:

Valgrind and kcachegrind results

Put simply, most of my time is spent manipulating mutexes. I'm going to have to rethink my design, because that's way too much time…

Leave a Comment »
MUD Progress
Posted in MUD Development
First watch, 4 bells (10:21 pm)

I've been making a little progress on the MUD again. I don't work on it much, but it hasn't been building for a while, and I've got a drive to get it fixed so at least I can continue testing it.

I've made a few modifications lately, the biggest being changing the command objects to Singleton objects since that's the way I've been using them anyway. I've also been working on the get command, and as happens when a design gets better, it's shrinking in size. Hopefully I'll be able to wrap it up tomorrow, since Lorien will be working until almost 9:30pm tomorrow night anyway.

I've also been lax about source control. My current system is rolling up a tarball, bz2-compressing it, and dropping it into my gmail account. I really should get something a little more sophisticated. At some point I'm going to have to do something about it. But the goal right now is to get it building again, and to test out the get revision.

Leave a Comment »
Using the yaml-cpp Library
Forenoon watch, 7 bells (11:57 am)

I've been using the yaml-cpp library for a while now, and I have to say that overall I'm greatly pleased by how well it works.

As I was making some adjustments to my I/O last night I ran across a bit of documentation that I never noticed before. Of course, it could be newly added. Anyway, I've found the most convenient way to parse my documents (I have many thousands of them to read and write), is to access them by node-name. For example:

node["location"]["name"] >> mObjectLocation.location;

The information I read last night, however, may convince me to change this behavior.

Apparently, named-node access in yaml-cpp is order-n2 complex over the entire document. Put simply, every time you access a node like this the library loops through all nodes looking for a match. Personally, I think a hashed table lookup would have been much faster, and perhaps they'll add that later.

Overall, I wouldn't normally worry about it because my documents tend to only have a few dozen nodes. But I do have 20,000 documents to parse. And to top that off, as they are used they become more complex. And as more items are added, the node size will grow geometrically. I can easily envision a future where a single document contains hundreds of nodes, and it's starting to scare me.

The solution? Well, I can honestly say I don't have a good one yet. I think perhaps if I enforce the order things are written, which already only happens in one way, I can then read in linearly instead of by node-name. The problem with that is if a file is edited by hand and the order is accidentally changed. So by renaming my current solution to readCompatible() and writing a new linear read() function, I should cut down on a lot of extra unnecessary processing.

But I'm still not sure that's the best solution. Any smart people out there have a better idea?

Leave a Comment »
Boost::Spirit 2 Redux
Last dog watch, 8 bells (8:27 pm)

Well if you stopped by yesterday you may have read my post about Boost::Spirit 2 and the trouble I had converting to the new Spirit 2 library. Fortunately, Hartmut Kaiser, one of the Boost::Spirit authors must have a Google blog notification when Spirit is mentioned in a blog, because he left a comment with a suggestion for me earlier!

Unfortunately, I still can't seem to get qi::phrase_parse to work right. The problem is that I'm trying to match one of a set of increasingly complicated grammar structures (perhaps starting at the most complicated and working backwards would fix this issue…). So, here is my problem in gruesome detail:

I'm implementing a get command for a MUD, an online text-only game system. Since I'm writing it from scratch, I decided to use some of the most up-to-date tools I could find to do so, and Boost has some terrific libraries that make this possible. As far as I can discern, the get command can come in the following forms:

  1. get hammer
  2. get 20 nails
  3. get hammer 2 (the second hammer)
  4. get 20 nails 3 (20 of the 3rd type of nails visible)
  5. get hammer from toolbelt
  6. get 20 nails from bucket
  7. get hammer from toolbox 2 (the hammer from the second toolbox)
  8. get 20 nails from bucket 3 (you get the idea)
  9. get hammer 3 from toolbox 2
  10. get 20 nails 2 from bucket 3

The problem comes when using phrase_parse with an empty space skip-parser. Given the two rules:

bool res = qi::phrase_parse(first, str.end(),
				(
					+qi::alpha
				),
				' ',
				item
);

And

bool res = qi::phrase_parse(first, str.end(),
					(
						+qi::alpha
						>> "from"
						>> +qi::alpha
					),
					' ',
					item,
					container
);

If I check the phrase get hammer from bucket it matches rule one, because after you remove all the spaces from the string it's just one long word! This is an unexpected result, and even if I check rule two before rule one I only match rule one!

And now I'm really lost. I imagine there's a better way to do this, but I can't seem to figure it out. Also, since my allergies are going crazy, I've got to take the night off anyway. Anybody out there know of a solution?

3 Comments »
Boost::Spirit 2
Last dog watch, 1 bell (6:34 pm)

Last year I added Boost::Spirit to my MUD project. A few weeks ago I learned that all of the work I had done was deprecated in the new Spirit 2 library. I could still use "Spirit classic," but it is deprecated and may be removed at some point in the future. So I spent some time today figuring out how to convert my grammar rules.

For example, in Spirit classic, I had this rule to handle the most complex rule for my get command. In this case, it handles a command like get 20 items 2 from container 3:

rule6 = int_p[assign_a(mNumberToGet)] >> ' ' >>
			(+alpha_p)[assign_a(mItemToFind)] >> ' ' >>
			int_p[assign_a(mItemNumber)] >> ' ' >>
			str_p("from") >> ' ' >>
			(+alpha_p)[assign_a(mContainerToLookIn)] >> ' ' >>
			int_p[assign_a(mContainerNumber)];

which could be tested by the following code: if(parse(str.c_str(), rule6).full)

Here is the equivalent code in Spirit 2

	std::string::iterator first = str.begin();

	bool r = qi::parse(first, str.end(),
					(
						qi::int_ >> ' '
						>> +(~qi::char_(' ')) >> ' '
						>> qi::int_ 	>> ' '
						>> qi::lit("from") >> ' '
						>> +(~qi::char_(' ')) >> ' '
						>> qi::int_
					),
					mNumberToGet,
					mItemToFind,
					mItemNumber,
					mContainerToLookIn,
					mContainerNumber
	);

	if(r && first == command.end()) {
		return true;
	}

In many ways, the new Spirit 2 library is better, and purports to be much faster as well. The parse function has certainly been made somewhat more convenient. Overall, I'd rather not have had to spend time on this, but the only other option is to lock in with an old version of Boost that may hamper me in the future.

5 Comments »
Grammar Implementation
Posted in MUD Development
First watch, 6 bells (11:06 pm)

I just finished writing the get() functionality I mentioned a few days ago. Using Boost::Spirit it was really easy to parse the grammar. It was much more work to actually act on the results of the parsing.

There are nine different ways to use the get command, each with its own grammar rule. Each of the rules gets more programmatically complicated, so the command code itself got pretty long.

I do suspect that the get and put functions will be some of the most complicated to write. I'd say I'm halfway done, but I haven't done enough testing on the get code to really call it "done."

Leave a Comment »
Programmatical Grammar
Posted in MUD Development
First watch, 6 bells (11:15 pm)

I've been working on implementing boost::spirit in my MUD to parse complicated grammar. Once I figured out how the library worked, it wasn't difficult to add to my existing codebase. The complicated part comes from actually using the results of the grammar. Take the get command, for instance. Now that I have an easy-to-use grammar system, I can make it as complicated as I want. I currently support the following types of get commands:

I had to define a search order, too. If a player is carrying a container, and a similarly-named container also exists in the player's current room, the player can only manipulate the one in their inventory, and would have to first pick up container, then take items from it. I could work out a way to combine the inventories of the player and their location, but I'm not sure I want to go that far. Honestly, the way I've coded things it's not too difficult, but I'm more worried about perception of items and the confusion combining them all could potentially cause.

In any case, the get command is growing in complexity by orders of magnitude right now, and it's almost too much to keep in my head. I'm going to have to go through and refactor it before I've even finished writing it.

Here's a code example of one of my rules:

// 'get 20 items from container 2' grammar
rule5a = boost::spirit::int_p[boost::spirit::assign_a(mNumberToGet)] >> ' ' >>
	(+boost::spirit::alpha_p)[boost::spirit::assign_a(mItemToFind)] >> ' ' >>
	boost::spirit::str_p("from") >> ' ' >>
	(+boost::spirit::alpha_p)[boost::spirit::assign_a(mContainerToLookIn)] >> ' ' >>
	boost::spirit::int_p[boost::spirit::assign_a(mContainerNumber)];

Which reminds me, since this class (the get command) is a shared pointer, I have to lock up the volatile bits in a mutex so multiple threads play nice together.

Leave a Comment »
Tons of Progress
Posted in MUD Development
Morning watch, 8 bells (8:06 am)

I've had a lot of time here in Portland, especially in the mornings when nobody else is up, to work on my MUD project. I converted it to use YAML to load and save everything, and the issue that caused me to have to choose a structured language, the inability to show relationships between deeply nested containers is now fixed. I also rewrote the login process to use dynamic handlers depending on the login state you're in (thanks Jeff!).

I know I'm on the right track, because in nearly every case, the code changes were smaller than the original code. So far, that's always been a good sign for me.

The best part is now I have loadable and saveable objects all working, and I can continue to build the rest of the functionality to complete the MUD and make it playable. Thank goodness for lazy vacations!

Leave a Comment »
Another MUD Update
Posted in MUD Development
First watch, 2 bells (9:08 pm)

Yeah, you're probably getting bored of these. You're probably wondering: "Jacob, what exactly is a MUD, anyway? Well, at least some of you are. But I'm not going to get in to that. The Internet is a big place, you can find that on your own. Suffice (for me) to say, it's my current hobby, a "pet project" of mine spanning nearly a decade. Off and on. Okay, so mostly off, but some on.

On with the update! If you keep up with this blog (and I can only assume you do if you read this), you know I've run in to issues with unstructured text files and saving complicated data objects to a storage media and then restoring them. I began a search for the right solution—a white whale, a magic bullet, whatever you wish to call it. My first instinct was to leap to XML because it can surely solve this small problem with ease. Right?

Wrong! XML is complicated, both to read and write (by machines anyway). Yes, there are libraries to help with that. Oh there are such libraries that you have no idea what you may be getting yourself in to (most of you, anyway).

Throwing out XML, and going with a cow-orker's recommendation of implementing JSON, I began writing a proof-of-concept program to save and restore data, but quickly ran in to a serious issue: JSON doesn't support multi-line strings.

Yet more searching around yielded a link to YAML, which I posted about the other day. YAML is easy to read from a human standpoint, and even has a couple of C++ libraries to help read it. YAML supports everything I want to do. So I scrapped the JSON project and started a proof-of-concept for YAML. I quickly ran in to an issue reading YAML, but it turned out to be my own fault: I didn't understand how a part of the library worked. Shortly after that, though, I did uncover a bug in the yaml-cpp library with indicator characters used as scalars (this is where you non-technical people either stop reading, or stick your fingers in your ears—metaphorically—and ignore me from here on out). With that issue wrapped up, serious work began and the proof-of-concept grew wings and took off. Just like I hoped it would.

Now I'm in the midst of tearing out underlying serialization code (the part that handles the loading and saving of objects), and it looks like it may take many hours to get things back up and working again. But hopefully by that time I'll have a full-blown, ready-to-use system that will require very little future modification.

Since then I have also become aware of (thanks Keith) the Boost Serialization library. It does the same thing I'm looking at doing, but a little more generically, just like Boost always does. Now the dilemma is: do I go forward with the YAML code, or switch to boost::serialization? Perhaps another proof-of-concept program should be written to determine this, but I need to do a little more research. Right now I have no idea how the serialized data looks to human eyes, and I haven't found any examples yet. It's important to my project to have these files as easily modified by humans as by machines.

In summary, that's where the project sits today. I may have some time this week to work on it, but if it's anything like last week I'm not going to have the brainwidth (I just came up with that word!) to work on it. Fortunately, Lorien and I plan a vacation to see family in Oregon in another week, so I should have a few idle days to work on it then.

PS. And wouldn't you know it, I just ran across Google's Protocol Buffers, yet another solution for basically the same problem. I have my work cut out for me!

Leave a Comment »
Structured Files
Posted in MUD Development
First watch, 4 bells (10:19 pm)

I've reached the point with my MUD project that plain old text files make saving and restoring information prohibitively difficult. I need to add some structure to them. On the other hand, I'd like them to remain easy to read and modify by hand as well as by computer.

Enter YAML. First thing it has going for it is a recursive acronym for a name: YAML Ain't Markup Language, which gives it ++coolFactor.

Secondly, YAML supports multi-line strings, and JSON doesn't (excluding the hack of using Unicode newlines to separate your lines—DO NOT WANT!).

Anyway, I decided on writing a proof of concept for using YAML, and started it this evening. I haven't gotten terribly far, but far enough to run in to some issues reading files with yaml-cpp. Even reading the YAML 1.2 spec sample files. I'm not sure what's wrong. In any case, I hope to resolve this soon and that YAML works out. I'd really like to use it for the MUD!

I can parse the "complete example" code, though. Right down to each individual scalar. I used recursion to read the nodes until I hit a scalar value instead of their fancy operator>> overloading.

Leave a Comment »
Zones and Zone Maps!
Posted in MUD Development
First watch, 2 bells (9:16 pm)

This is a red letter day for the MUD I've been working on forever. Today, I have finished implementing and testing a map function. A map is generated based on a radius around the player's current location. Optionally, and by default, the map will also have a context-sensitive key explaining the surrounding terrain. But a picture is worth a thousand words…

MUD map #1

And here is a second example:

MUD map #2

So there are 2,000 words for you. I'm totally excited! The World Map I have is 180x90, which comes out to 16,200 "rooms" in the world. Each zone, like the world, lives in a directory, and can contain an optional map, map key, weather map, and weather map key. There is another subdirectory for all the room save files that make up the zone.

Leave a Comment »
MUD Update
Posted in MUD Development
First watch, 7 bells (11:44 pm)

I got some more bits together for the MUD today, but not very much. I was hoping to have all the zone exits working properly, but there have been a few issues and I'm too tired to solve them right now. I'm very close to having custom, printable maps displaying for each client. Screenshots will be taken when the feature is working.

Leave a Comment »
State of the MUD
Posted in MUD Development
First watch, 4 bells (10:10 pm)

I've done just a little work today on my ongoing MUD project. I fixed a small problem this evening that shows up if you enable MySQL but don't have proper permissions configured. In that case, the server just quits—no coredump, no error message, nothing. So I fixed that case.

Overall, I'm quite proud of how well it runs. The socket code is first rate rock solid stable. It should be, I've rewritten it enough times now. After this weekend's work, the binary size just topped 6mb, but that's with all the debugging symbols. If I strip them out, it's only about 650kb. I'm right around 15,000 lines of code. Wow, did I get that right? I can hardly believe it's at 15k. Almost a full third of that (over 4500 lines) is devoted to commands alone.

The only thing I'm not happy with right now is how Windows telnet connects to the server. Windows telnet does something funky with the way it sends data and I haven't quite got it working right. It still connects, but it does weird things. Every other telnet or MUD client (zMUD, cMUD, etc) that I've tested with it work great.

I generate some fantastic documentation via Doxygen (view it here). Currently the server only runs under Linux/UNIX machines (in theory it should run fine on a Mac assuming you have a development environment with the proper libraries, but I don't have one to test it on). As I make more use of cross-platform libraries like Boost this may change, but I'm not porting it to Windows on purpose.

My future development roadmap is in my head, and largely consists of the next feature: maps. I've designed a drop-in directory style zone system so it's easy to add/copy zones. A zone could be the entire world or a single hut. Each zone will support a map with a legend (although they're not required). An ASCII map of the local area, optionally coloured, will be available to each client based on their current location. A key will also be written out explaining the map if a key is available. Much of the foundation has already been laid for this map system. In ten to twenty more hours of development I should have it fully integrated and working.

After the map feature, things get a little fuzzy. I may implement more objects, and probably several more commands. Mobiles and AI are on the list, but still require some careful planning before I start work on them. One thing at a time, I guess.

PS If you want to see how Doxygen generates complex dependency graphs, I would recommend this file.

2 Comments »
Book Recommendation?
Posted in MUD Development
First dog watch, 1 bell (4:53 pm)

I'd like to find a good book (or website/reference material etc) on AI programming for game development. There are a lot out there though. I'd like to hear from someone that uses it. Specifically, this post is targeted at Ben :) Or Richard, if he comes around here.

Any suggestions?

Leave a Comment »
Telnet Issues
Posted in MUD Development
First watch, 1 bell (8:33 pm)

My MUD server (yes, the one I've been writing forever) seems to have some issues with certain telnet clients. I think it's because they're sending weird telnet option requests and I just ignore them. I really should fix that. Here's a nice site that talks about the telnet protocol and its large group of obscure options.

What I really need to do is read up some more about boost::asio and enter the modern age of network coding. Maybe.

Oh yeah, and boost::format, too! So many tools, so little room in the toolbox…

Leave a Comment »