Showing posts with label just for fun. Show all posts
Showing posts with label just for fun. Show all posts

Monday, September 19, 2011

Operation HackMaster Crit Tables, episode 2

Now that I've explained what data structures are for, I can finally explain how I approached the problem of deciphering those ponderous HackMaster tables.

First of all, I discovered to my dismay that the tables were only available in the form of PDF files -- images, not text.  Just as I was about to tell my friend that I didn't want to waste time converting six pages of tiny print to very usable data, my lovely assistant Lynnea (the aforementioned fiancee who actually plays the game) stepped in and volunteered to do it.  This is one thing about her personality that I've never been able to understand, but she loves doing data entry, filling out forms, etc.  I think it's some kind of OCD thing.  But for whatever reason, she's extremely enthusiastic, diligent, and thorough about this kind of work.  And by the way, if you need this kind of work done, she's available to hire!  Ask me for a resume.  :)

With this powerful slave human resource at my disposal, I wrote up a few sample lines of text in a spreadsheet to show how I wanted them, wound her up and let her go at it.  She cranked the rest out in a surprisingly short time.  I then converted the results to standard comma-separated value format, some of which you can download from here: Hacking weapon table part 1; List of effects.  In case you're not familiar with them, .csv files are a generic text-only format which can be read in a spreadsheet program like Excel, or any standard text editor.

Working with just my sample rows, I set out to work out what the abstract properties of the data were.  The first thing to consider is the way a body part is selected.  In the hacking weapon table, you can see that if you roll a 1-100, you get hit in the "Foot, Top"; if you roll 101-104, you get hit in the heel, 105-136 is Toe, and so on.

This is like a hash table, almost, but it's not one.  If it was a hash table, you'd usually have one body part per number: 1 -> Foot Top, 2 -> Heel, and so on.  Here, we're working with a range of numbers corresponding to each lookup value.

I decided to start with a generic lookup table, where you start with objects which contain a "low" value, a "high" value, and a generic object which can get returned from the lookup. The declaration looks like this:
public class RangeLookup<T>
{
   private List ranges;

   private class Entry
   {
      protected T item;
      protected int low, high;

      public Entry( T i, int l, int h )
      {
         item = i;
         low = l;
         high = h;
      }
   }
   ...
}
In Java using the "<T>" notation means that "T" could be anything.  Even though I wasn't going to be using this lookup table more than once, I like to keep structures as all-purpose as possible.  That's partly because I might want to reuse them in the future, and partly because I want to be able to test how the component works without making it dependent on the equally complex item which will be retrieved by the lookup.

Every structure needs an interface -- a means of communicating with it that only does what you want and hides the guts of it from the rest of the program.  I created an "addEntry" function to the RangeLookup class, so that you could insert a new entry with a high, a low, and a retrieved object of type T.  Then I added a "lookup" function where you send in a number, it gives you an object.  In my implementation, the lookup function simply walks through all of the possible results and checks whether the requested number is between the high and the low.  This would be inefficient if there were going to be a lot of entries, so I might have come up with some kind of hashing structure or tree search; but since there are only about 20 or so body parts, it wasn't worth the extra effort and runs fine as is.

After verifying that this was working right, I created the following additional structures:

  • Looking at the Effects table, it is a basic mapping (in my case, placed in a HashMap) from one string to another.  You put in the code "f", and the resulting effect is "fall prone and drop items".  So, I created a simple object called an "effect," containing "key" and "description."
  • It's a bit more complicated than that, though.  Often the table will contain numbers, but the effects will contain only the symbol "X".  For instance, if the table says "d4" then the relevant effect is "dX", which means "reduce Dexterity by X".  Therefore I made another class called an "Outcome," which contains an Effect AND a number (which may be zero if it's not necessary).
  • I made an EffectTable, which implements the HashMap of Effects.
  • Almost ready to create an actual table object, I first made a class called "CritTableEntry."  This represents a cell in the table.  It contains: a low roll, a high roll, the name of a body part, and a List of effects (because each cell may result in several outcomes, not just one).
  • A CritTable class to put them all together.  This class has an addEntry method and another method for retrieving the entries.

As a final step, I created a "Reader" class which did the heavy lifting of reading and interpreting the CSV files and adding one row at a time into a generated table.  I don't like to reinvent the wheel, so I googled class libraries which would read CSV files and interpret them as lists.  I settled on using OpenCSV.  I could have written my own parser, but when the task is as common as reading a CSV, I tend to assume that somebody has already done all the work before me and has already been through the process of making all the mistakes and catching the bugs which come up.

Notice that none of these objects deals with input and output directly.  It's preferable to test each component of your program separately as much as possible BEFORE trying to decide what kind of user interface to make.  Your interface should be tailored to the problem space.  As it turns out, I wound up creating several different interfaces before I settled on created a web application.  I'll discuss these concerns in a later post.

When testing your data structures it's a good idea to create unit tests.  A unit test is a small, self contained application which is designed to test one thing at a time.  You need to think about every possible way that your program might break, create a unit test for each one, and make sure that it works right at the boundary conditions.

Off the top of my head, here are some boundaries of the crit tables that needed to be tested:

  • Spot check several "body part" rolls with random(ish) numbers and see that the returned information matches the table.
  • Spot check several "outcome" rolls in one row and see that the returned effects match the table.
  • Test the boundaries of some rolls.  For instance, on the table I linked, "4301-4492" corresponds to "Arm, upper inner", and "4493-4588" corresponds to "Elbow".  Therefore I have to make sure that a roll of 4492 returns a different part from 4493.
  • Test when happens when the body part roll is 0 (invalid), 1, 10000, and 10001 (invalid).
  • Test what happens when the effect roll is 0, 1, 24, and 25.

Keep all your unit tests around forever.  If something breaks, that's a quick way of figuring out which part is not working.  If it's a problem with your data model rather than your user interface, the unit tests will catch it.

Next time I'll be talking about all the different ways of making an interface on the same models.

Thursday, September 8, 2011

Operation HackMaster Crit Tables, episode 1

This post is about a project I recently did for fun.  Although the project itself has extremely limited application, it inspired me to do something I've been meaning to do for a long time, namely upgrade the web server for my apollowebworks.com domain to something which supports Java applications with Tomcat.  (I chose a company called Arvixe based on scanning the features they offer and reading a bunch of reviews.  Shout out to my boyz at Arvixe!)

Because I'll be touching on a wide range of topics, I'll split them up into multiple posts, and that should keep me from neglecting this blog for a little while.  So, partly to tell you what's coming and partly just so I can keep track for myself, here's a road map of the topics I plan to hit with this discussion.

  • General geekery about using programming to automate complex tasks.
  • Building a project from the ground up, starting by visualizing the data structures instead of just diving in blindly.
  • How separating interface from implementation makes it easier to translate your program to multiple platforms.
  • Good riddance to the bad old days: How the web has made program content delivery easier.
  • A primer for noobs on what web servers do, and why I bought another one.

First let me explain the problem.  My fiancee, Lynnea, has gotten into paper-and-pencil roleplaying games.  She has been running a light Dungeons & Dragons campaign occasionally for me and my son Ben over the last few months. She also plays with a group of friends one night a week.  For my part, I've played RPGs a few times before but never been a strong part of that scene, so I just listen to the stories of her sessions.  Currently they're playing with a rules system called "HackMaster."

As I understand it from skimming a few chapters of the rulebook, HackMaster was written by someone who hates doing things the easy way.  When D&D was first published in 1974, it was at first an ever-expanding set of complicated rules involving tons of die-rolling for all kinds of special situations.  Or as a German exchange student my family hosted in high school put it, "D&D isn't a role-playing game, it's a roll-playing game."  Har.  Har.  Very droll, those gamers.  (Oh hey, how are things going, Max? ;)

Still, as the years went by, D&D started to reverse the trend and become more streamlined, or so I've heard.  The latest release, fourth edition rules, was clearly heavily influenced by World of Warcraft, and reduces a lot of the unnecessary choices in favor of more interesting combinations of focused options.

The HackMaster author just hates that.  Not that I would recognize the difference, but I have the impression that if anything, he's aggressively chosen to make every little action even more complicated than it would have been under old-school D&D, to the point where a party can spend thirty minutes meticulously checking a single room for traps before seeing any combat.  And the critical hit tables are an utter monstrosity.

Critical hits (or "crits") for you non-gamers, means that for every attack there is a chance (1 in 20 under D&D rules) that it will be a super-strong attack which does extra damage.  In WoW, this is handled automatically by the game; you can build up gear that will increase your crit chance, but usually there's a flat formula that says "If you crit, your strike does twice as much damage."  Rules in 4th edition D&D are pretty close to the same.

Not HackMaster.

In HackMaster, you roll a number between 1 and 10,000 for the body part where your blow lands, and there are all kinds of "realistic" outcomes that result if you land a powerful blow on that body part.  Furthermore, rolling a 20 is just your cue to pull out a ginormous, six page tables full of teeny little numbers and two accompanying rules pages.  You then roll another number that might range from 1-24 to see just how badly your crit hurt the monster (or the monster's crit hurt you).

For instance, if you get hit on the top of the head, the crit damage can range from "8 extra damage" to "twice normal damage AND you lose some hit accuracy AND you lose some dexterity AND you fall down and drop everything you're carrying"... to "brain goo."  Do not pass go.

Each one of those individual clauses, by the way, is represented in the table by a little symbol like "dX" which you have to look up on a smaller table of effects.  I think you have to look at a sample to see what I'm talking about.

(Click for a larger image.)

Not to put too fine a point on it, this sounds like a game that I would personally hate playing.  But no accounting for taste, you know?  Even so, problems of managing huge sets of data are piles of fun to solve with a computer.  NO, that's NOT sarcasm, you non-programmers, that's fun.  Shut up.

So when the DM tentatively asked if it would be possible to write a program that could handle the die rolls and just spit out some nice, clean output, I said "Piece of cake!"  I wouldn't even accept his offer to pay for it.  Just like when I wrote a Sudoku solver, sometimes figuring out how to automate gameplay is more fun than actually playing.  (Disclaimer: I used to claim that Sudoku is a fun math problem and a crappy game.  Now I like playing it.  It's my Android Evo's fault, damn it... it's the perfect game for a handheld, and it has built in strategy advice.  Once I started improving at harder puzzles, there was no escape.)

And so it began.

To be continued...

Thursday, February 11, 2010

Angle math

I've got a new applet posted on my web page, which I wrote for my son Ben. He is seven. It is a demonstration of how angles work. You can drag the points of the triangle around, and it will continuously update the display of numbers showing what angle is formed at each point. It also gives a little readout showing that the three angles will, indeed, always add up to 180 degrees.

I like to do a little graphical application every once in a while just to stay in practice. There are a lot of concepts from trigonometry that have to be applied. Debugging graphics is sometimes a tricky affair, because if you don't do the right thing then you might wind up with nothing but a blank screen, or a line might appear wildly out of place. Finding the angles required remembering what sines and cotangents and such represent. (SOH CAH TOA! That's one that never leaves your memory, but I got sin and asin mixed up for a while.)

I also had to fudge the numbers a little bit. For instance, one angle might be 70.14 and another might be 50.34. The third angle should be 59.52. However, if you reduce those to one significant figure, you find that 70.1+50.3+59.5 = 179.9. So I had to fake the third angle (a3) as displaying 180-a1-a2.

The hardest challenge came after I decided to change "nearly" right angles into true right angles. Notice that if you drag one corner so that it forms an angle between 80 and 100 degrees, it will automatically snap to the correct position so that it is 90 degrees. I had to put some thought into making that work, and here's the solution I wound up with.

  1. Write an expression of the line segment opposite the point being moved.
  2. Find a vector perpendicular to that line.
  3. Project the moved point along that vector to find where it intersects the opposite segment.
  4. Find the actual distance that the point must be from the segment in order to make a 90 degree angle.
  5. Move the point there.

I had originally used only a "Point" class and a "Triangle" class to represent the problem space; I soon realized I needed a "Vector" class as well (one which could be used to offset a point, normalized, reversed, or made perpendicular to another vector). Then I had to make yet another class, "Line," in order to properly calculate where intersections can be found. I borrowed a lot from this page, and found out just how long it had been since I needed to do that math -- I had a totally incorrect idea of how a line formula is expressed.

Basically the key to correcting your math mistakes -- and I made a lot! -- is to create either a printout or a visual representation at every step. For instance: I think I've normalized the vector correctly, better print out the coordinates and make sure the length is really 1. I need to draw an extra line to make sure it really goes through this point. I need to draw an extra point to make sure it really intersects that line. Do these two lines LOOK perpendicular to me? And so on.

If I had remembered the math better then some of this rigor wouldn't have been necessary. But really, caution and constant testing while coding eliminates the need to be a perfect math whiz. Coding is both theoretical and experimental, you see.

Wednesday, March 11, 2009

Count on this

Let's switch things up a bit and just do something for fun.  How high can you count on your fingers? Ten, you say? Amateurs. I'm going to teach you how to count much, much higher... without even taking your shoes off.

However, you're going to have to learn to count in binary first. Again, this is a very basic topic to computer science students, but I hear that there are plenty of non-programmers who read this blog. For their benefit, I'm going to give a primer. If you already know binary, feel free to skip down to the next bold header.

How to count in binary

When you count by tens, the digits can be represented as wheels on the odometer of your car. The right-most wheel goes:
  • 1, 2, 3, 4, 5, 6, 7, 8, 9…
Then what happens? There is no "10" printed on the wheel. So where do we go next? The rightmost wheel flips from "9" back to "0", and as that happens, it also pushes the next wheel up by 1. So you have a 1 and a 0, and that's ten.
  • 11, 12, 13, 14, 15, 16, 17, 18, 19…
Then the first wheel again flips over from 9 to 0, which in turn advances the second wheel from 1 to 2. Twenty. Right? Don't tell me this is hard, my son Ben understands this and he's in first grade.

So anyway, things are pretty much the same from here on out, until we get up to:
  • 97, 98, 99…
And now? Well, the first wheel flips to zero, which in turn advances the second wheel. But the second wheel is already maxed out at nine, so it flips to zero, which also advances the third wheel, so now that wheel reads "1". 1, 0, 0. A hundred. Got it?

Okay, that's base 10. Binary is a similar system, except that it's got a severe shortage of numerals. Whereas we were using all the numbers from zero to nine, in binary you only have two possible values: one, and zero. Like a light switch: on, or off. Circuit open, or circuit closed. That's how a computer works. But with just ones and zeroes, you can represent every positive integer if you have the patience.

Let's imagine we have an odometer like before, but this one has very small wheels. They flip from 0 to 1. Then they flip from 1 back to 0. When they flip to 0, they advance the next wheel. Okay?

So your odometer reads:
  • 0: 00000
Advance the rightmost counter by one:
  • 1: 00001
Advance the counter again, and it flips to zero while dragging the second wheel along:
  • 2: 00010
So that's two. Ten is two, in binary. Makes perfect sense, right? Advance the right hand wheel one more.
  • 3: 00011
Next time we advance, both of the first two wheels will advance the next one over.
  • 4: 00100
One hundred is four. I think you can take it from here.

In base ten, every digit represents a value that is ten times the previous digit. So the first digit is worth one, the second digit is worth ten, the third digit is worth a hundred, the fourth is worth a thousand, and so on.

Similarly, in base two, every digit represents a value that is two times the previous digit.
  • 1 -> 1
  • 10 -> 2
  • 100 -> 4
  • 1000 -> 8
  • 10000 -> 16
Makes sense, right? You can write out any string of ones and zeroes and figure out what number they represent in binary by adding up the digits. For example,
  • 10110 = 16 + 4 + 2 = 22
Okay, here's the fun part.

How to count to 1,023 on your fingers

  • Hold out your hands, palms upward. Now make them fists. No fingers are extended. That's zero.
  • Extend your right thumb. The right-most digit is now set to "on". That's one.
  • Close up your thumb, but extend your right index finger. That's two.
  • Extend your thumb again, and also leave your index finger out. Three.
  • Close up your thumb and index fingers, but then extend your middle finger. That's four. It is also an obscene gesture to most people, so if you're in public, make sure your hands are under a desk or something.

That's really all there is to it. The highest you can go with this system is 1111111111 in binary, which is 1,023 in regular counting (210 - 1).

Other numbers that form obscene gestures to Americans: 128; 132

Numbers that may be obscene to Europeans: 6; 384; 390. They may also be interpreted as peace signs or a Richard Nixon impression.

What can you do with this? Not much. You can kill about ten to twenty minutes. You can also probably perform a cheap mind-reading trick if you have an accomplice who can also do it. ("I'm thinking of a number from one to a thousand." "583. I certainly wasn't paying attention to the funny way you're holding your hands.") And finally, you can waste a perfectly good afternoon writing a silly blog post.

By the way... if you DID take your shoes off, you could count to 1,048,575.