Steep To Compile

Programming, tea, and music

Properly Access the User’s Home Directory on Windows

I don’t have my home directory on my C: drive. This is apparently blasphemy in the eyes of most windows users, but I’m not insane. I like to use my home directory as, well, my home directory, and my C: drive is too small. I have a solid state drive, so it has enough room just for the OS and all my programs. I also don’t like a bunch of read/writes to appdata on an SSD, since that can damage it. So I’ve moved my home directory from C:\Users\Howard to D:\Users\Howard. Just one tiny character change! However, a lot of programmers didn’t think that “hey, what if a windows user ISN’T insane, and keeps their documents on a different drive than their OS?” Therefor, I have to keep my C:\Users\Howard folder around just for a few programs. I will be calling them out now:

  • Android Studio and Gradle
  • Microsoft Media Player (This was surprising to me)
  • Avast Antivirus

If you work for any of the companies making any of these projects, email someone on the team that is working on it, and get them to fix this. Now.

So how do you fix it? Like this:

Batch Scripts

Getting the user’s home directory from these is really easy, since it’s just a macro that expands to the proper directory:

%userprofile%

Python

Python makes it pretty easy to do, mimicking a Unix way of doing things. To do this from python:

from os.path import expanduser
home = expanduser("~")

Java

With Java, just use the System.getProperty function. You don’t even have to import anything new.

String home = System.getProperty("user.home");

C/C++

C can of course be a bit more tricky, but its still just one function call.

#include <Shlobj.h>

// ...

WCHAR home[MAX_PATH];
SHGetFolderPathW(NULL, CSIDL_PROFILE, NULL, 0, home);

C#

And finally, C#:

string home = Environment.GetFolderPath(Environment.SpecialFolder.UserProfile);

I have tested all of these and they work, so you have no excuse not to do this properly now. I have done your job for you, now you owe me money. If your language is not listed here, I would much rather have an email in my inbox from you asking for help than bug in a program I use.

</rant>

Thoughts on Swift

Swift seems interesting. I’d love to play around with a programming language where I can confuse other people with emoticons for variable names. Dogcow… Oh Apple, its so cute that you spent the time to actually make that a feature of the language.

My London Fog Recipe

A London Fog (Also known as an Earl Grey Latte) is essentially Earl Grey tea and steamed milk, together in frothy goodness.

Its a beverage I enjoy every morning, and have developed a perfect recipe for.

What you’ll need:

  • 12 Ounces of boiling water
  • 1 tablespoon Earl Grey tea
  • 1 teaspoon Paris blended tea
  • About 4 ounces of milk (I prefer whole milk for the creaminess, but whatever you’d want in a latte will work perfectly)
  • 4 tablespoons vanilla syrup
  • 1/4 teaspoon Vanilla Paste

What devices you will need:

  • Something to steam milk with
  • A basket infuser, or the filter out of your coffee maker
  • A cup you can put boiling water in (Not the mug you’ll serve the drink in!)
  1.  Put the tea in the bottom of your cup (Both kinds). Do not put it in any infuser – mix it directly with the water (This makes it stronger!) Pour the boiling water over it. Give that 5 minutes to steep.
  2. While that is steeping, steam your milk with the vanilla syrup mixed in.
  3. Pour the tea through the basket infuser to filter out the leaves.
  4. Stir the vanilla paste into your brewed tea, and then pour the steamed milk in.

It’s not exactly healthy or easy to make, but this is my special recipe for a London Fog. I’m lazy, so I have one of those automatic milk frothing machine and I just use that to make the milk. If you use one of these, set it 140 Fahrenheit for ideal results.  A few extra notes:

  • You can use lavender Earl Grey tea for even more flavour
  • If you want to make the vanilla syrup yourself, just make simple syrup (1:1 water-to-sugar ratio) with 1 tablespoon of vanilla extract for every half cup of water
  • The Paris tea isn’t something you need for the recipe, but I think it adds a nice flavour to the drink.

Bloom Filters and Message Apathy in Game Engines

This is something I’ve been working on in my most recent project, but didn’t make it in to the final production. I finally got it working yesterday, and I’m quite proud.

Messaging systems are important for a lot of game engines, and can be extremely useful for divorcing logic from one system from the logic of another. For the context of this post, I will assume you are using some kind of component based architecture in C++, though the concept should extend to any architectural model and language.

Bloom Filters

Bloom filters are not a widely known data structure, so let me give a bit of background on them. If you are already familiar with them, you can go ahead and skip ahead to the next part. Bloom filters were first thought up by Burton Howard Bloom in 1970 as a space efficient test to check if an element is a member of a data set. They can return a false positive (Saying data is in a set when it is not) but can never return a false negative (Saying data is not in the set when it is).  They are also incredibly fast at determining this information, much more so than a hash table or binary search tree.  So, what are they useful for? They can only tell if something is not in a data set, they can’t actually hold any data! The name is a giveaway: Filters. Any time you want to filter something, bloom filters are a great way to do it. For example, say you run a giant search engine and want to filter out malicious sites from coming up on your search results. However, you don’t want this to hinder the speed at which your search results will be returned to your users, since you would have to check every single result returned by the search against this filter. So, you need something fast. Google does exactly this. If the bloom filter says a site might be malicious, then they can go run it through a more complicated check to see if it actually is. Here is the Wikipedia article.
This video provides a pretty good explanation of how bloom filters work:

So what do we do with them?

Well, there are two ways to do messaging that I’ve seen used. The simple way, and the proper way. The simple way looks something like this:

virtual void Player::SendMessage(unsigned message_id, void *message_data)
{
  switch (message_id)
  {
    case MESSAGE_KEY_DOWN:
    {
      unsigned key_id = *reinterpret_cast<unsigned *>(message_data);
      this->key_down_logic(key_id);
    }
    break;

    case MESSAGE_KEY_UP:
    {
      unsigned key_id = *reinterpret_cast<unsigned *>(message_data);
      this->key_down_logic(key_id);
    }
    break;
    // Maybe more
  }
}

This switch statement approach works pretty well, and this is how Windows (The OS) handles sending messages to its UI. I wouldn’t exactly knock it, but there are a few problems:

  • There’s a lot more logic there than there needs to be
  • The SendMessage function is always called, even if the message being sent isn’t cared about
  • This function can get pretty huge and annoying to deal with, sometimes even with multiple developers working in the same functions, which component based architecture strives to avoid.

So, this won’t work. This leads to the proper way to use messages, and it looks something like this:

virtual void Player::Initialize(/* Whatever parameters */)
{
  RegisterMessageProc("KeyDown", (MESSAGE_PROC) &Player::key_down_logic);
  RegisterMessageProc("KeyUp", (MESSAGE_PROC) &Player::key_up_logic);

  // initialize other stuff
}

Where your RegisterMessageProc looks like this:

typedef (Component::*MESSAGE_PROC)(void *data);

void Component::RegisterMessageProc(const char *name, MESSAGE_PROC proc)
{
  m_message_table.insert(name, proc);
}

To call a message procedure based on the name, you just look up that name in the table, and call the function for it.

This is much less verbose, and it forces all logic for an event to be placed into its own function. Because, trust me, if you don’t force people to use good coding standards, they will not.

You may also notice that now message ID’s are strings, instead of unsigned integers. This is very useful for not having to reserve an identifier and making sure that you can avoid strange post-merge bugs from two developers using the same name. Granted, two developers may use the same string, but this is much less likely than two of them using the same integer because they just chose one at random. So, you can take those strings and throw them into a hash table. Great. This works pretty well, but we can do even better.

By using the bloom filter, we can immediately determine that an object doesn’t care about a message. Thus the name, message apathy. We can then take advantage of one property of bloom filters in component based architectures: You can run a bitwise or operation on them to combine them. So, you do something like this in your game object composition:

void GameObject::Initialize()
{
  for (unsigned i = 0; i < m_component_count; ++i)
  {
    m_component[i]->Initialize();
    // Assuming you have the += operator overloaded for your bloom filter
    m_apathy_filter += m_component[i]->GetApathyFilter();
  }

  // initialize other stuff
}

Where your GetApathyFilter function looks something like:

BloomFilter<string> Component::GetApathyFilter()
{
  BloomFilter<string> apathy_filter;

  // Whatever iterator type is appropriate for your hash table
  for (iterator it = m_message_table.begin(); it != m_message_table.end(); ++it)
    apathy_filter.insert(it->first);

  return apathy_filter;
}

Now, in your game object, you have an apathy filter. The game object can immediately ignore the message if it is determined from a check in that filter that it is not a message the object will ever respond to.

Going further

Perfect hashing. Its a beautiful thing. There are tools to generate functions, like gperf, and they will give you some pretty awesome results. So, how do we use these? First off, because the message ID’s we will be using will be some data set that will never change for the life of our program, we can generate our perfect hash function from this list of id’s. For example, we could have the ID’s “KeyDown,” “KeyUp,” “LogicUpdate,” and “Collision.” We can use these to generate a perfect hash function that will give us one hash value for each key in the set. How does this affect the bloom filter? Well, it will prevent false positives from happening, ever. Our bloom filter will use only one hash function, so checking if something is in the filter becomes a very cheap operation.

Because of this, we can prevent our objects from ever distributing a message it doesn’t care about. We can take this a step higher – Lets say we post a message to the entire world. The Zero Engine that is used at DigiPen has a composition called Game, one called Space, and one called COG. Games have spaces for children, spaces have COGS for children, and COGS have other COGS for children. So, moving up this hierarchy, we can have each one keep a filter of what it cares about for its own components, as well as what its children care about. So lets say there is a space for game objects that don’t care about key input messages. Maybe it’s a space for the stars in the background of the screen, and they don’t respond to user input in the slightest. Using the approach of a perfect hash function, and combining all of the apathy filters for each of those objects into an apathy filter for the children, we can avoid ever sending the message for key input to any object in the entire space. This can cut down on a lot of completely unnecessary operations.

Of course, to generate this perfect hash function, you need a list of all of your message ID names. This list can be pretty difficult to actually create, depending on how everything works. Generating the perfect hash function may not be trivial, either. Some tools can take hours to generate one, depending on the data set you are using. To solve these issues, I recommend using a hash like “return 0″ or maybe a regular hashing function like FNV while developing the game, and then generating the perfect hash function when you are ready to deploy. Keep in mind that even if you get a false positive, the game will still work. This is only an optimization. You could even use your editor to make a list of all the message ID’s, and then as part of your packaging process have a step that creates this hash function, then your engine can load it from a DLL your editor spits out.

 

If you have any questions about how to implement this, or any specifics on how I have done it, please feel free to ask me in the comments section below or by emailing me!

Hello world!

Welcome to my website! Here is where I will post all my passing fancies of technology and my career, and document most of my own independant work.

© 2014 Steep To Compile

Theme by Anders NorenUp ↑