Archive for the ‘Coding’ Category

Infinity Dice Rolling Engine

Thursday, June 19th, 2014

The miniatures game Infinity has some interesting and unique mechanics. The first is that the player who is not currently taking their turn gets to have their models react to the actions of the active player. The second mechanic is that if the action and reaction are directly opposed (for example, the two models are firing at one another), both players roll dice at the same time (called a Face to Face roll). The player who scores “better” wins the contest and their models performs the action.

Let’s take a very simple case of two basic infantry troops shooting each other. The active model is he Fusilier Angus, firing his Combi Rifle with Ballistic Skill (BS) of 12. This weapon lets him roll 3 20-sided dice, which will succeed on a roll of his BS of 12 or less on each die. His opponent is the Zhanshi Wen Liu, firing his Combi Rifle with BS 11. As he is reacting, he only gets a single die, and his BS is lower, so he is looking to roll an 11 or less. They both roll their dice at the same time, and then compare results. First, any dice that missed (rolled above the firer’s BS) are discarded. Then, any successes that rolled lower than the opponent’s highest die are discarded. This leaves at most one player with any successful hits, which are then applied to the target. There are a few more complexities, but this outlines the basic flow. To make it concrete – Angus rolls a 15, 10, and 7, and Wen Liu rolls a 9. Angus’s 15 is discarded as a miss (since he rolled greater than 12), and his 7 is discarded since it is lower than Wen Liu’s 9. Meanwhile, Wen Liu’s 9 is discarded since Angus rolled a 10. The only die left is Angus’s 10, meaning he scored one hit on Wen Liu.

In this basic case, the probabilities are relatively easy to calculate. For each of the active player’s dice, it is easy to calculate the chance that they rolled less than or equal to their target, minus the chance that their opponent rolled higher without going over their own target value. And in fact, there has long been an online tool called Infinity Math to help calculate probabilities where the reactive player is limited to one die.

The calculations get much more complicated when the reactive model is allowed to roll multiple dice. I attempted for some time to come up with a reasonably simple numerical way of calculating these chances, but kept on coming up short. Eventually, I remembered that my personal strengths are not in numerical analysis, but rather in computational and algorithmic optimization. Therefore, I decided to make a program which implements a really simple and straightforward means of calculating these probabilities, and then optimize it until it was acceptably efficient.

Basic Design Overview

The basic design of my dice rolling engine is to enumerate every possible permutation of dice that could be rolled, evaluate the results, and then calculate how likely each possible result is. Since the number of dice required can change for every scenario, my program implements this step using recursion. This allowed me to produce accurate results, but very slowly. Even a moderately complex calculation could easily take several minutes to complete. As such, looked for ways to optimize the algorithm to reduce the time taken.

Optimization – Matrix Symmetries

The first and biggest optimization that I implemented that decreased my running time by several orders of magnitude was to take advantage of symmetries in the matrix of all dice rolls I was generating. In other words, I made sure I never calculated results that varied only by the order of the numbers rolled.

Take this matrix showing all possible combinations of two four-sided dice as a simplified example:

(1,1) (1,2) (1,3) (1,4)
(2,1) (2,2) (2,3) (2,4)
(3,1) (3,2) (3,3) (3,4)
(4,1) (4,2) (4,3) (4,4)

Because a player doesn’t care what order they rolled their dice in (since all dice are rolled simultaneously), we can cut the number of dice rolled approximately in half, by including only those rolls where the second number is greater than or equal to the first.

(1,1) (1,2)*2 (1,3)*2 (1,4)*2
      (2,2)   (2,3)*2 (2,4)*2
              (3,3)   (3,4)*2
                      (4,4)

As you can see, the second matrix doesn’t have any duplicate entries, but does mark the ones that need to be double-counted. As the number of dimensions increases, the multiplicative factor can become much larger than 2, based on the number of repeated values.

As the number of dice increases, so do the number of dimensions of the matrix. In these higher-dimension matrices, the savings from matrix symmetries increase exponentially.

DicePermutationsAfter OptimizationPercentage
12020100%
240021052.5%
38000154019.25%
416000088555.35%

And so forth.

Optimization – Miss Consolidation

The great thing about that optimization is that it always works, no matter what the scenario. The next one I did, however, helps in most common cases, but will occasionally offer little to no benefit.

Since all dice that roll higher than the target number are discarded without being used, it is unnecessary to roll all of them. I let the first failing die through in order to count it in the statistics for failures and misses, and I simply multiply the number of results by how many other failure states I rolled up. From the initial example of Fusilier Angus trying to roll a 12 or less, this:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Becomes this:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 * 8

Obviously, the lower the target numbers involved, the greater the value of this optimization. Due to the way that this optimization stacks with the prior one, it frequently reduces the number of rolls calculated by well more than half.

Optimization – Multithreading

The final optimization I implemented was to make the tabulating of dice rolls multi-threaded. I start one thread for each of the 20 possible values of the first die, and then tabulate the results when all threads have completed. My hosting company gives me access to 2 CPU cores, so the calculation takes approximately half as long to complete. Due to the various optimizations in the prior sections, different threads will take different amounts of time to complete, but how the operating system balances them between the cores evens everything out.

Web App

With that done, I had the time consuming part of the calculations taken care of. The next step was to create a web frontend that allows you to select what sort of scenario you would like to run, and then hands the data off to the back end utility. This has been another significant challenge, but has overall been pretty straightforward. My tool is available here, for you to play around with if such things interest you. I periodically update it with new features and to keep it up-to-date with the latest releases for the game.

Prologue – Numerical Analysis

After I had already mostly completed work on this part of my tool, one of my fellow Infinity players from Maryland took the time to find a solution to this that is as close to closed-form as possible, using Mathematica and my tool to check his results. His description of his method is available in HTML or PDF, if you are interested.

DFHack on the Mac 1: Build Process

Monday, April 16th, 2012

I have decided to see if I can get the incredibly useful dfhack utilities for Dwarf Fortress ported to the Mac. Currently, they only exist for Windows and Linux. I created my own fork of the dfhack project on github, and prepared to follow the building instructions.

Downloading cmake was pretty easy; they have a convenient-to-install binary package for the Mac.

Unfortunately, I ran into errors before I even started compiling. Cmake was giving errors about my gcc’s hash map being broken. I’m working on my laptop, which is running OS X 10.6.8 (“Snow Leopard”). I know it’s a version behind (10.7 a.k.a. “Lion” is out now), but with 10.8 (“Mountain Lion”) just around the corner, I’m not going to bother with the Lion upgrade now. The version of gcc included with XCode 3.2 is:

yuzu:~/src/dfhack jonathan$ gcc --version
i686-apple-darwin10-gcc-4.2.1 (GCC) 4.2.1 (Apple Inc. build 5664)
Copyright (C) 2007 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

I installed a new gcc from source. The process was quite straightforward, and I am not going to document it here.

yuzu:~/src/dfhack jonathan$ /usr/local/bin/gcc --version
gcc (GCC) 4.6.3
Copyright (C) 2011 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

And I told cmake to use that. At that point, I was able to get the Makefiles generated.

From a previous Mac port attempt, there are some _DARWIN defines that control which headers are included. The cmake scripts are setting _LINUX by default, which is breaking on some Linux-specific includes. The first place I’m hitting that is here:

Scanning dependencies of target clsocket
[ 47%] Building CXX object depends/clsocket/CMakeFiles/clsocket.dir/src/SimpleSocket.cpp.o
In file included from /Users/jonathan/src/dfhack/depends/clsocket/src/SimpleSocket.cpp:43:0:
/Users/jonathan/src/dfhack/depends/clsocket/src/SimpleSocket.h:61:29: fatal error: linux/if_packet.h: No such file or directory
compilation terminated.

I edited the CMakeLists.txt files in the dfhack root and the depends/clsocket directory so that if APPLE is defined, to add the -D_DARWIN option instead of -D_LINUX (diff). I have not committed the changes to clsocket anywhere, as I didn’t feel like forking the project just for that one change, plus I’m not entirely confident about how git submodules work.

The next error was the lack of a perl module:

Scanning dependencies of target generate_headers
[ 52%] Generating ../../library/include/df/codegen.out.xml
Can't locate XML/LibXSLT.pm in @INC (@INC contains: xml /Library/Perl/Updates/5.10.0 /System/Library/Perl/5.10.0/darwin-thread-multi-2level /System/Library/Perl/5.10.0 /Library/Perl/5.10.0/darwin-thread-multi-2level /Library/Perl/5.10.0 /Network/Library/Perl/5.10.0/darwin-thread-multi-2level /Network/Library/Perl/5.10.0 /Network/Library/Perl /System/Library/Perl/Extras/5.10.0/darwin-thread-multi-2level /System/Library/Perl/Extras/5.10.0 .) at xml/codegen.pl line 15.
BEGIN failed--compilation aborted at xml/codegen.pl line 15.

I used CPAN to install it.

Next, a missing C library function:

[ 56%] Building CXX object library/CMakeFiles/dfhack.dir/LuaTypes.cpp.o
/Users/jonathan/src/dfhack/library/LuaTypes.cpp: In function ‘void read_field(lua_State*, const DFHack::struct_field_info*, void*)’:
/Users/jonathan/src/dfhack/library/LuaTypes.cpp:463:55: error: ‘strnlen’ was not declared in this scope

This function exists on Windows and Linux, but not OS X. It is basically the same as strlen(), but takes a maximum length parameter, and will not return a value larger than that. I replaced it with a call to strlen() and a manual comparison with the max value (diff). The only way this could backfire is if the string being measured here isn’t NULL-terminated in the case of max length.

Next up comes a template error. I had forgotten how annoying template errors were.

[ 60%] Building CXX object library/CMakeFiles/dfhack.dir/modules/Gui.cpp.o
/Users/jonathan/src/dfhack/library/modules/Gui.cpp: In function ‘void DFHack::Gui::showAnnouncement(std::string, int, bool)’:
/Users/jonathan/src/dfhack/library/modules/Gui.cpp:451:48: error: no matching function for call to ‘min(std::basic_string<char>::size_type, unsigned int)’
/Users/jonathan/src/dfhack/library/modules/Gui.cpp:451:48: note: candidates are:
/usr/local/lib/gcc/x86_64-apple-darwin10.8.0/4.6.3/../../../../include/c++/4.6.3/bits/stl_algobase.h:187:5: note: template<class _Tp> const _Tp& std::min(const _Tp&, const _Tp&)
/usr/local/lib/gcc/x86_64-apple-darwin10.8.0/4.6.3/../../../../include/c++/4.6.3/bits/stl_algobase.h:233:5: note: template<class _Tp, class _Compare> const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
/usr/local/lib/gcc/x86_64-apple-darwin10.8.0/4.6.3/../../../../include/c++/4.6.3/bits/stl_algo.h:4184:5: note: template<class _Tp> _Tp std::min(std::initializer_list<_Tp>)
/usr/local/lib/gcc/x86_64-apple-darwin10.8.0/4.6.3/../../../../include/c++/4.6.3/bits/stl_algo.h:4189:5: note: template<class _Tp, class _Compare> _Tp std::min(std::initializer_list<_Tp>, _Compare)

This is the offending line:

    int size = std::min(message.size(), 73U);

I changed it to 73UL (diff), but I will possibly break it on another system as a result. I will need to revisit this.

There was a missing macro:

[ 58%] Building CXX object library/CMakeFiles/dfhack.dir/Console-linux.cpp.o
/Users/jonathan/src/dfhack/library/Console-linux.cpp: In member function ‘bool DFHack::Private::read_char(unsigned char&)’:
/Users/jonathan/src/dfhack/library/Console-linux.cpp:151:13: error: ‘TEMP_FAILURE_RETRY’ was not declared in this scope

This macro is used under glibc to automatically retry system calls that were interrupted and returned EINTR. The BSD behaviour is to automatically retry, and I believe that this includes Mac OS X. As such, I added an #ifdef _DARWIN and defined a macro that just executes the desired function once and does nothing funny (diff).

Then I ran into an error of the linker including an unnecessary library that did not exist:

[ 52%] Building CXX object library/CMakeFiles/dfhack.dir/Console-linux.cpp.o
Linking CXX shared library libdfhack.dylib
ld: library not found for -lrt

This is the library that, on Linux, provides access to various “realtime” APIs. If I exclude this library, I am not getting any undefined symbol errors, so for the time being I will assume it is either unused, or the relevant functions are already included in another library on OS X. The dependency is defined in library/CMakeLists.txt; I added an IF(APPLE) section where it defines the PROJECT_LIBS variable (diff).

Another somewhat inscrutable C++ error:

/Users/jonathan/src/dfhack/plugins/liquids.cpp:81:15: error: ‘std::string setmode’ redeclared as different kind of symbol
/usr/include/unistd.h:575:7: error: previous declaration of ‘void* setmode(const char*)’
/Users/jonathan/src/dfhack/plugins/liquids.cpp: In function ‘DFHack::command_result df_liquids(DFHack::color_ostream&, std::vector<std::basic_string<char> >&)’:
/Users/jonathan/src/dfhack/plugins/liquids.cpp:257:23: error: assignment of function ‘void* setmode(const char*)’
/Users/jonathan/src/dfhack/plugins/liquids.cpp:257:23: error: cannot convert ‘const char [3]’ to ‘void*(const char*)’ in assignment
/Users/jonathan/src/dfhack/plugins/liquids.cpp:261:23: error: assignment of function ‘void* setmode(const char*)’
/Users/jonathan/src/dfhack/plugins/liquids.cpp:261:23: error: cannot convert ‘const char [3]’ to ‘void*(const char*)’ in assignment
/Users/jonathan/src/dfhack/plugins/liquids.cpp:265:23: error: assignment of function ‘void* setmode(const char*)’
/Users/jonathan/src/dfhack/plugins/liquids.cpp:265:23: error: cannot convert ‘const char [3]’ to ‘void*(const char*)’ in assignment
/Users/jonathan/src/dfhack/plugins/liquids.cpp: In function ‘DFHack::command_result df_liquids_execute(DFHack::color_ostream&)’:
/Users/jonathan/src/dfhack/plugins/liquids.cpp:460:35: error: comparison between distinct pointer types ‘void* (*)(const char*)’ and ‘const char*’ lacks a cast [-fpermissive]
/Users/jonathan/src/dfhack/plugins/liquids.cpp:464:40: error: comparison between distinct pointer types ‘void* (*)(const char*)’ and ‘const char*’ lacks a cast [-fpermissive]
/Users/jonathan/src/dfhack/plugins/liquids.cpp:469:40: error: comparison between distinct pointer types ‘void* (*)(const char*)’ and ‘const char*’ lacks a cast [-fpermissive]

It appears that a file-local static variable named setmode is interfering with the function std::string::setmode(), thanks to the using std::string declaration at the head of the file. Unfortunately, I see no way around this other than not using that namespace (and having to adjust every intentional usage of a string function) or renaming the setmode variable. I opted for the latter, replacing it with set_mode (diff).

And with that, the build was complete.

I am, however, slightly worried about these warnings, which I received many times:

In file included from /Users/jonathan/src/dfhack/library/include/df/map_block.h:17:0,
                 from /Users/jonathan/src/dfhack/library/include/modules/Maps.h:42,
                 from /Users/jonathan/src/dfhack/plugins/lair.cpp:9:
/Users/jonathan/src/dfhack/library/include/df/tile_designation.h:19:38: warning: ‘df::tile_designation::<anonymous struct>::dig’ is too small to hold all values of ‘enum df::enums::tile_dig_designation::tile_dig_designation’ [enabled by default]
/Users/jonathan/src/dfhack/library/include/df/tile_designation.h:27:37: warning: ‘df::tile_designation::<anonymous struct>::liquid_type’ is too small to hold all values of ‘enum df::enums::tile_liquid::tile_liquid’ [enabled by default]
/Users/jonathan/src/dfhack/library/include/df/tile_designation.h:30:34: warning: ‘df::tile_designation::<anonymous struct>::traffic’ is too small to hold all values of ‘enum df::enums::tile_traffic::tile_traffic’ [enabled by default]

At this point, though, I will try and get the library preloading working and see what happens. I expect there will be a variety of interesting debugging to do.

Summer Project: October

Sunday, October 24th, 2010

Status of the Project

Summer has passed, and I took a break from working on the space artillery game. Not because I had other time commitments (although I did find other ways to fill my days), but rather because I just didn’t see how what I was making was supposed to be fun. Fortunately, stepping back for a while let me get my bearings again, and I did some work in the last couple of days and am much closer to having something I’d consider the early working stages of an enjoyable game.

Changes

Now that I’m not doing physics tests all the time, I re-scaled the solar system so that everything is a lot further away and moves more slowly. This fixes the problem I was having where every time your turn came up you were shooting from a completely new position. While the constant orbital motion is supposed to add a challenge, the player needs to have some ability to make adjustments based on what he saw his missile do the prior turn. I also moved the asteroids into a normally-distributed belt beyond the orbit of the last planet. With both of these changes in place, the only time the collision detection actually gets used is when a missile strikes something. While having planets bounce around like billiards balls was amusing, its time has passed.

Proof

I have prepared a series of screenshots that tell a little story of a red and blue planet trying to kill one another:

Red planet about to shoot:

Red planet about to shoot.

Blue fires his shot as well:

Blue fires his shot as well.

Red defends against a prior shot of blue’s:

Red defends against a prior shot of blue\'s.

Red survives; blue lines up another shot:

Red survives; blue lines up another shot.

As you can see, it takes several turns for a missile to arrive at its target, and you so you can have a lot of them on screen at once. The one that red shoots out of the air to protect itself was fired several turns earlier by blue. I’m still working out things like the best speed for the projectiles. But I definitely had a lot more fun playing this round against myself than I had been at the end of September.

Summer Project, Weeks 4-9

Tuesday, August 24th, 2010

Continued from part one, more details about my quest to make a fun game about shooting things into space.

Week 4

Took the week off.

Week 5

I only got a little bit done this week, but it makes things look better. Each astronomical body has a rotational rate that controls how it is drawn, and projectiles always rotate to face the direction of their movement. I know that you actually need an aerodynamic projectile which is inside an atmosphere to have this happen, but it’s aesthetically pleasing, so I’m keeping it for now. I’ll revisit it if I have any clever ideas when I’m making self-propelled projectiles.

Weeks 6 & 7

These two weeks got eaten up preparing for and recovering from Otakon.

Week 8

This week I rejiggered a bunch of the numbers for the solar system I was using so that my planets were actually close enough to one another and large enough that you can actually see them all. Previously I was using values from our real solar system, which gave me a set of stable orbits, but everything was so far apart that I had to assign the planets pixel-based sizes to make them even be visible. I now have a much smaller set of numbers, where everything is in much closer together. I then made a random map generator based on these new numbers. I also added a whole mess of asteroids to the maps so that I can have them swinging around. So that I can get the same random numbers and thus the same map on any platform, I grabbed a Mersenne Twister library to use in the project. No more crappy libc rand() implementations for me.

After that, I started on something a lot cooler – collisions between objects. Objects now bounce off of each other like pool balls, which can result in a fun mess if I send a planet careening through a mass of asteroids. I also had a bit of fun bouncing two planets in the same orbit off of each other, although slight imprecisions in the math resulted in their orbits eventually degenerating into an unusual arrangement, as you can see in these screenshots:

Planets bouncing off of each other Planets in new orbits

Finally, as you may have noticed if you were playing a lot of attention to those screenshots, I ported my work over to the Mac. Now that I have a laptop again, it only makes sense to keep this project cross-platform. Since all the tools and libraries I’m using are cross platform, it was only a minor inconveniece to set everything up.

Week 9

Didn’t get anything done again. I’m rapidly running out of summer.

Summer Project, Weeks 1-3

Saturday, July 10th, 2010

Description

This summer I’ve decided to dedicate some time to working on programming a game. For eight weeks, from June 20th to August 14th, I am planning to put in at least a couple of hours three nights a week. At the end of this time I will evaluate my progress and the state of my project and set further goals.

Now, what is this game that I’m making? At its heart, it’s a 2 dimensional artillery game, like everything from Scorched Earth to Worms to the one with the gorillas that came with QBasic. The twist to what I’m doing is that the entire thing is set in space. Your planet, orbiting the nearby star, is firing upon other planets, also orbiting the same star. Everything is constantly moving. In order to keep confusion under control and to counter the fact that shots aren’t repeatable, I have plans for an interface to allow player’s to simulate where their shots will land. To the best of my knowledge, this sort of game hasn’t been built before. We shall find out if it was for good reason or not.

I’m going to try to post an update on my progress every week or so. Here’s a quick recap of what I’ve done so far.

Indeterminate Past

Before this all started, I decided one day to write an orbital simulator, just for the fun of it. As I played around with it, I started thinking about making it into an artillery game. After I finished my initial project, and could sit and watch the planets of our solar system make their way through the sky, I wrote some game design ideas and set some development milestones, but didn’t do any more coding.

Week 1

I got off to a rather slow start. All I finished in the first week was rearranging my old code some so that it looked a bit less like a weekend hack (which it was) and a bit more like the groundwork for a project that could maybe go somewhere.

Week 2

I’d picked out a few UI libraries I wanted to try integrating things with, so I tried them out to see which to use. At first I tried Agar. I was finding it a bit heavy, and wasn’t sure it was what I wanted, so I decided to try out my other contender, GiGi. I couldn’t even get GiGi to compile (on Windows), so back to Agar it was. I then had to struggle significantly to get my existing Cairo-based drawing code to output things onto a graphics surface Agar was happy pushing onto the screen. Eventually I got all that done and was left with a solar system app that no longer supported any sort of user input and used more CPU than it used to. All around, a success!

Week 3

This week I actually started tackling some of the new functionality I wanted to include. I’ve been pulling items off of my to-do list for a (very!) minimally playable demo. I’m going to stick with the philosophy of getting things “playable” as quickly as I can and then keeping them so at all times. This week I have added a placeholder UI, and established the basis of a turn structure by having the physical simulation hooked up to the “Fire” button. Today I finished up support for loading texture images off disk so that my planets don’t have to be flat colored circles anymore.

As a reward for a job well done I set two planets on the same orbit in opposite directions and watched them pull each other into the sun.