Game Lisps

When I see a game that uses Lisp for it’s game code, I usually ask a few questions.

1) Does the Lisp support continuations? Games often have latent actions, such as, play an animation, and then do something else when the animation is done. Continuations (often found in Scheme) are an easy way to model this.
2) Does the Lisp support macros? Macros are one of the largest advantages Lisp has over other languages, in terms of expressiveness and programmer productivity.
3) Does the Lisp have a listener prompt and/or allow the game code to be changed while the game is running? Fast iteration is a requirement of any game scripting language, and is a large advantage over the compiled language used for the core engine code.
4) Does the Lisp support cons? This implies some support for memory management and garbage collection, which is a huge minus for a game system.

Sometimes, I hear about a game that uses Lisp, but doesn’t support the first three, and occasionally, it may support the fourth. At that point, I wonder what is the advantage?

Posted in Technical | Leave a comment

Signed integer overflow

I was reading through the Google Native Client docs and I came across the coding style guide. One of the points in the coding guide was to beware of integer overflows, such as the following:

int32_t foo;
int32_t bar;
...
foo = bar + 1;  // may overflow

They then discuss how to prevent this:

if (bar > INT32_MAX - 1) {
    /* error handling */
}
foo = bar + 1;

It is interesting and subtle that they leave the discussion at this. In many cases, particularly for unsigned operations (on a two’s complement machine, which is basically everything), programmers are taught to do something like:

if (bar > bar + 1) ...

The subtle point is that Google doesn’t warn against this form, even though it is a common mistake, and it’s an obvious derivation from the original form. The second form may look like it would work for signed integers, and in particular, it is mathematically valid for two’s complement. But for C/C++ signed integers, wrapping is undefined.

This is a subtlety that optimizing compilers, particularly GCC and LLVM/clang, take advantage of, and they can optimize this undefined code away, which can have a negative security impact. I found it interesting that Google chose this example without explaining the subtleties given the close relationship the Native Client has with LLVM/clang.

The moral of the story is, if you are doing validation, delegate it to a library or inline functions. Even if this library is custom built, at least corrections can be done in one place.

P.S. I posted a bunch of code to my GitHub recently, including my lock-free algorithms, my gene finding code, and some old DirectX tutorials. The code is fairly technical, so it should be good fun for the those interested.

Posted in Technical | Leave a comment

Yes, WoW is too hard

On June 28th, World of Warcraft introduced their 12th tier of raiding, referred to as The Firelands. The tier includes seven bosses, and two modes – normal and hard. Sites such as wowprogress.com track the progress of guilds as they complete the content.

As of six and a half weeks later, 15 guilds worldwide have completed the tier on hard mode. Paragon, the Finnish eSports team considered to be the best in the world for the last two years, took 500+ attempts on the final boss, Ragnaros, and this appears to be on-par with the attempts it took other top teams.

When completed, Ragnaros is a 15 minute fight that requires perfect execution by all raid members during the entire fight. Failed attempts will be around 10 minutes, counting raid time, and the time after a “wipe” to reset and start again. So, for the top raid team in the world, it took over 83 hours of in-game time. The time outside of the game that the team used to develop strategies and “theorycraft” was likely much more than this.

From my experience, an average raid team will raid maybe 10 hours a week. My question is, does it make sense to have content that takes the best team in the world 83 hours to do, if the average team raids for 1/8th that time per week and is considerably less skilled?

In general, raiding guilds seem to operate similar to the Peter Principle, in that they will attempt content that is just beyond the teams’ ability. In effect, this means that nearly all raid teams will fail at completing the content. At some point, it is common practice for Blizzard to “nerf” the content, so that more teams have an opportunity to do it. This means that for some period of time the players are paying for content that isn’t pragmatically possible, at least until the nerf.

I imagine that most people get material enjoyment for achieving a certain mastery over an obstacle. For raiders, this means being able to down raid bosses with a certain consistency. But for all except the top 20 raid teams in the world, this means months and months of an inability to complete the content, let alone achieve this mastery over it.

Both Tier 12 and Tier 11, which was introduced last December, have been considered some of the most difficult content Blizzard has produced. In this period of time, WoW has lost 900,000 subscribers. I know correlation doesn’t equal causation. But having been in one of the top 500 guilds in the world, I can say that content that difficult doesn’t have the payoff for the time investment required, at least for this ex-raider.

Posted in Culture, Personal | Leave a comment

disktools now on GitHub

I just posted some older tools on GitHub that I used when I was first writing TurboHex over a decade ago.

https://github.com/AceRoqs/disktools

When I’m posting my older code to GitHub, I take some time to do some refactoring.  Generally this means updating the coding style to something closer to what my current conventions are, which is pretty trivial.  In some cases, this means addressing some of the TODOs in the code, which were probably okay when I was the only consumer of my code, but probably not appropriate when actually publishing.

It took a bit longer than I expected to publish the disktools, in part because the tools themselves were written as needed, and never grouped as part of a package before.  There was not only a lot of duplicated code, but also a lot of code that was not really factored to be reusable at all.  In particular, partinfow, which was a GUI app, was pretty gnarly, as I had at least three different branches of that code, with presentation code intermixed with other logic, and other shortcomings which were acceptable when I expected to throw it all away.  Most of my refactoring time was on partinfow, and I was able to extract some nice libraries for future use, and share a bunch of code between all of these previously redundant tools.

One of the weird things I ran into when doing this was that VC++ 2010 was building an export library for the ripiso project.  It didn’t do it for other projects, but I was able to narrow it down to usage of new(std::nothrow) in ripiso, where previously it used HeapAlloc().  Changing the code to use throwing new worked fine and didn’t create the bizarre ripiso.lib/exp files before linking the final EXE.

I discovered a thread on the Internets where someone was running into this same issue.  I was going to respond with a fix, but I needed to create a MSDN profile.  When logging in, it asked to create a Display Name.  After telling me my name (Toby Jones) was taken, I attempt “Toby Jones (ace.roqs.net)” before it tells me that periods and parentheses are invalid characters.  I stopped at this point, because having a unique ID is perhaps a bit excessive for a message board that I would post to only once.  And while I think my name is pretty unique already, I still have to compete with this guy.

Posted in Technical, TurboHex | Leave a comment

Is Test Driven Development a toy?

I’m continuously trying to find ways to make my code better.  I experiment with a lot of tools for code correctness.  I play with constructs to make my factoring better, increase code mobility, and decrease complexity.  I like these because I can find things that work and distill them into rules.  Maybe I have rules on what references I allow in headers, or maybe I bias towards functional code over OOP to minimize coding by side effects.  Whatever.

It is a bit more difficult to evaluate things like processes or methodologies.  Take Test Driven Development (TDD) as an example.  It’s difficult to make a solid case against writing test code (though occasionally I see a persuasive argument).  The arguments tend to be self reinforcing – you want your code to stay correct over time with changes, you want consistency in QA, you want reduced sustained engineering costs, etc.  TDD makes the suggestion that test code should be written before production code.  The argument is that writing test code first puts a soft upper bound on the complexity of production code, since you cannot write the test code without understanding the production code behavior.

I have this code that I wrote a very long time ago.  It changes the position and size of a dialog’s child controls when the dialog changes size.  It’s not particularly complex, but it has some math that most would just gloss over.

int xPos = m_original_listview_rect.left;
int yPos = m_original_listview_rect.top;
int cx   = new_client_width - m_original_client_rect.right +
                              m_original_listview_rect.right;
int cy   = new_client_height - m_original_client_rect.bottom +
                               m_original_listview_rect.bottom;

HWND hWndDlgItem = GetDlgItem(hWnd, IDC_LIST1);
MoveWindow(hWndDlgItem, xPos, yPos, cx, cy, FALSE);

xPos = new_client_width - (m_original_client_rect.right -
                           m_original_button_rect.left);
yPos = new_client_height - (m_original_client_rect.bottom -
                            m_original_button_rect.top);
cx = m_original_button_rect.right;
cy = m_original_button_rect.bottom;

hWndDlgItem = GetDlgItem(hWnd, IDC_BUTTON1);
MoveWindow(hWndDlgItem, xPos, yPos, cx, cy, FALSE);

I didn’t write this with TDD, as TDD wasn’t in vogue in ~2000 when I wrote it.  The code isn’t particularly complex, and isn’t particularly great.  It looks testable, and probably could have used TDD.  But what isn’t obvious to me is how TDD might have made the factoring better.

When refactoring some code for GitHub recently, I came across this and decided it was a candidate to make better-er.  I pushed and pulled at the code.  I messed with the math.  I played with the units (should a rectangle be defined as two points, or a point and a size?).  I attempted tracking the minimal state needed to recalculate everything.  I ran it through a debugger and watched the numbers actually behave.  I played with redundant sub-expressions.  In the end, I came up with something like this (the controls are a bit different, but the idea stands):

void reposition_window_by_offset(
    _In_ HWND window,
    _In_ int control_id,
    const RECT& original_control_rect,
    const POINT& position_offset,
    const SIZE& size_offset)
{
    HWND control_window = ::GetDlgItem(window, control_id);
    ::MoveWindow(control_window,
                 original_control_rect.left + position_offset.x,
                 original_control_rect.top + position_offset.y,
                 original_control_rect.right -
                     original_control_rect.left +
                     size_offset.cx,
                 original_control_rect.bottom -
                     original_control_rect.top +
                     size_offset.cy,
                 FALSE);
}
    int offset_width = new_client_width -
                       m_original_client_rect.right;
    int offset_height = new_client_height -
                        m_original_client_rect.bottom;

    POINT position_offset = {};
    SIZE size_offset = { offset_width, offset_height };

    reposition_window_by_offset(window, IDC_LISTVIEW1,
                                m_original_clientspace_listview_rect,
                                position_offset,
                                size_offset);

    position_offset.x = 0;
    position_offset.y = offset_height;
    size_offset.cx = 0;
    size_offset.cy = 0;

    reposition_window_by_offset(window, IDC_MYLABEL,
                                m_original_clientspace_label_rect,
                                position_offset,
                                size_offset);

I like this code.  Its a bit longer (in terms of LOC), but its immediately obvious what is changing on each of the controls.  The calculation code that nobody reads is separate from the code that states what needs to change.  If I started with test code, I have no idea how I would have ended with the second implementation.  Even for simple things, often times you need to mold the code.  This is where languages like Python and Lisp, which have a REPL loop, really excel, as they provide a playground for this type of experimentation.

Arguably what I’ve done here is the refactoring step of TDD, so I could have just made a test against expected outputs. However, I wasn’t even sure of the format of my inputs, including what shared state there was. I wasn’t even sure of the number of functions I’d end up with. What I’m making a case for is exploratory programming as a tool for requirements gathering. And if writing code is used for gathering requirements, perhaps the idea of writing test code first should be reexamined.

This is hardly damning for TDD, but it’s hard to know where TDD might be applicable if I didn’t see how it would work for a toy example.  I worry that TDD might be focusing on the wrong metric.  In my world, the problems I deal with aren’t on the function level, or often even on the module level.  They’re race conditions.  They’re scalability issues.  They’re issues with information leakage or security.  I don’t know how TDD might catch those issues.  I am concerned for the developer that uses TDD as a crutch to avoid thinking through code especially if they are the same devs that need to worry about threads, scalability, or security.

I’ll keep an eye on this space.  I still have a nagging feeling this is useful somewhere, but I can’t quite put my finger on it.

Posted in Technical | Leave a comment

WoW needs real Voice Chat

World of Warcraft is a social game. It is arguably THE social game. Unlike, say Farmville, people log on just to hang out with people they know. WoW includes voice chat functionality, but nobody uses it. Instead, they opt for Ventrilo, or increasingly, Mumble for voice chat, for a variety of reasons.

Some time ago, Blizzard added a Dungeon Finder that would match you with people in your Realm (and later, your “Battlegroup” or even your continent) in order to do group/team content. As this happened, players were rightfully concerned that they lost a social aspect of their game, as they were grouped with people outside their own server, and the social bonds between players on a single server were weakened.

Nobody uses voice chat during a dungeon, because it takes time to set up the voice chat for use. Instead, a primitive text box is used, where people can slowly type in their chat text to their group or individual. Not surprisingly, communication in these environments is weaker than when voice chat is used. The difficulty of the game content, combined with the extreme latency of text chat, gives these “pick-up groups” a bad name, as players consistently have poor experiences.  Additionally, text chat as a communication medium increases anonymity, and from my experience, anonymity encourages antisocial behavior (such as trolling).

Blizzard has done a number of things to “manage” these poor experiences, including a voting option to kick people from the group, penalties for leaving a group early, rewards to players who provide unique roles (such as a healer or “tank”), etc. All of these are ironically anti-social, when the clear solution would be for Blizzard to make it’s voice chat functionality competitive.  In this sense, if Blizzard provided voice chat that was low-latency, but high quality, and had zero-setup when connecting to groups, and an easy interface for moving between channels, problems with pick-up groups would solve themselves, and would increase the player satisfaction immensely.

I suspect that, in the future, social team games that have a high quality voice chat as a baseline feature will have a significant competitive advantage over those that don’t.  This will have some interesting impact on the mobile space as well.

Posted in Culture, Personal | Leave a comment

Encrypted home directories

I’ve been spending a bit of time on my Linux Tor relay lately (which is also doubling as a staging server for a few projects I have brewing). For kicks, I’m now using an encrypted home directory, which I’ve not done before. Not having a home directory accessible without mounting it causes an amazing number of problems that I’m working around:

1) SSH private keys are stored in ~/.ssh, which prevents key based authentication unless the directory is mounted.
2) Bash startup/shutdown scripts may or may not be run, depending on whether the directory is mounted. The immediately obvious side effect is that colored ls or certain aliases don’t work.
3) The document root for user web sites are often stored in ~/public_html, which means that the website is not accessible unless the directory is mounted. If the public_html is located outside the home directory, there is typically a symbolic link to it in the home directory so that it is accessible via FTP/SCP. …which, of course, is only available when the directory is mounted.

These are all straightforward to work around, but it’s now the case that most of my home directory has ended up unencrypted. In the end, given the current state of the art, it might have been better to just have a mount point inside the home directory for encrypted data.

Really, the cause of most of these problems is the SSH key authentication interaction with encrypted home directories. If a password is used instead of key authentication, then the file system can be mounted before the bash scripts are run, or during FTP connections, etc. It appears that this might be a ripe area for a good solution to be written, if someone was so inclined.

Posted in Technical | Leave a comment

Static Analysis

I’m building most of my code with VC++ 2010 Professional, which is pretty much all you need for Windows app development, but it is missing the static analysis tool.  I think at this point static analysis should be a baseline expectation for a compiler (particularly for C++), much like how optimization is something you expect out of a production compiler.

You can pay for VC Pro and get no static analysis, or you can download the Windows SDK and get a compiler with /analyze for free.  The only trick is that they do make it a bit challenging to integrate into your projects.  First, here is the compiler output from cl.exe using the VC compiler:

C:\Program Files\Microsoft Visual Studio 10.0\VC\bin>cl /analyze

Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 16.00.40219.01 for 80×86

Copyright (C) Microsoft Corporation.  All rights reserved.
cl : Command line warning D9040 : ignoring option ‘/analyze’; Code Analysis warnings are not available in this edition of the compiler

cl : Command line error D8003 : missing source filename

Installing the Windows SDK, and doing the same thing:

C:\Program Files\Microsoft Visual Studio 10.0\VC\bin>cl /analyze

Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 16.00.40219.01 for 80×86

Copyright (C) Microsoft Corporation.  All rights reserved.
cl : Command line error D8003 : missing source filename

Okay, so there is no version number change, and apart from actually trying the compiler with /analyze, there is no way to tell that you actually have a version with static analysis enabled.  Whatever, let’s give it a go.  Put /analyze into the command line arguments of my project, and what happens?

1>cl : Command line warning D9025: overriding ‘/analyze-’ with ‘/analyze’

VC automatically adds /analyze- to the command line for you, with no way to remove it.  I don’t think there is a way to silence D9025, nor would I want to, since its generally useful.  Anyway, this leaves me with either ignoring the warning (which isn’t exactly a great door to open), or running the tool from the command line, which is sort of okay, but would require me to do some actual work to make it scale.

All of that aside, I got it working, and migrated my SAL annotations from declspec SAL to attribute SAL.  My code has been annotated with declspec SAL for years, and I’ve sort of gotten use to the aesthetic, so the new format is a bit jarring at first.  I have some other code on GitHub that I’ll need to move to attribute SAL at some point, and most of my projects could probably use a run through AppVerifier to see how they’ve withstood the years.

Here’s a pro tip for Microsoft: just integrate VC++ Express into the Windows SDK and make it work together.  It’s a better solution for everyone than charging $800 for a toolchain that is inferior than the one you give away for free.

Posted in Technical | Leave a comment

Boot sector disassemblies

I had forgotten to mention a couple weeks back that I had posted a few disassemblies I had done of boot loader code on GitHub. Most of them are reasonably old at this point, so they aren’t so much for for active use as they are for reference.

https://github.com/AceRoqs/bootsector_disassemblies

Posted in Technical | Leave a comment

Array Oddities

There are some oddities in C++0x as well, that are sort of annoying. Initializer lists are a great new addition to the spec. std::array is great as well. That said, getting them to work together is a bit odd. For example, the following is legal:

int a[] = { 1, 2, 3 };

And the following is legal:

std::array<int, 3> a = { 1, 2, 3 };

But you cannot do the following:

std::array<int> a = { 1, 2, 3 };

Having to specify the array count is redundant with the initializer list, and manually keeping this up to date is almost a worse solution for larger arrays. So it appears in my code that std::array and initializer lists will be mutually exclusive.

Posted in Technical | Leave a comment