Planing and designing WorldConquest

I have been using fogbugz from FogCreek to plan and track my previous project, Asteroid Sharpshooter. So called "on-demand" installations are free for single developers. I chose fogbugz over other free alternatives because it's the only platform that I know of supporting a time planning process that has been thoroughly thought out, namely evidence-based scheduling (EBS for short).

One of the dev teams at work is also using fogbugz, but we haven't been able to validate the value of EBS, possibly because I'm the only one interested enough in both programming and planning to follow the process in a disciplined way. One of the problems of the method is that it basically requires a waterfall design process, which isn't very popular these days in professional circles.

I am curious to see whether my use of EBS for the development of WorldConquest will validate the nice ideas upon which EBS is built.

My time estimates for implementing simultaneous turns in the game have shown to be wildly off-target. I thought writing to state update function would take 3 hours. I am now reaching 16 hours, and I am still in the testing phase.

It turned out executing orders in parallel can be tricky due to conflicts. For instance, how do you handle a melee attack order and a regular move order. The first order causes the attacking unit to move towards the targeted unit and attack it when it reaches it. But what happens if the targeted unit has an order to move away? The same kind of issues arise for units embarking and disembarking, if the transporting unit moves or is destroyed.

There are quite a few ways to resolve these issues, solving is really just a matter of deciding. Still, having a clear understanding of the design before implementing it is necessary, and I find that using data-flow graphs really helps. I use yED to draw graphs. This tool can redo the layout of graphs all by itself, a feature I cannot live without. It really beats drawing on paper or drawing on screen without automatic layout.

I ended up with the design below:

Boxes are operations, octagons are data. It's not a very complex process, but trying to implement it without a proper design (as I was hoping to do at first) is not an option.
Here is the implementation of the function that puts all parts together:

let update (gs : GameState) (orders : Order[][]) =
    let damages =
        seq {
            for player in 0 .. gs.player_units.Length - 1 do
                let player_id = PlayerId player
                let attacks = extractAttackOrders gs.player_units.[player] player orders.[player]
                yield! computeDamages gs player attacks |> accumulateDamage                
        }
        |> dict

    let getDamages u =
        match damages.TryGetValue(u) with
        | false, _ -> 0.0f
        | true, x -> x

    let gs = applyDamage gs getDamages

    let dead_units = getUnitDeaths gs damages

    let isDead u =
        dead_units.Contains u

    let player_units =
        [|
            for player in 0 .. gs.player_units.Length - 1 do
                let player_id = PlayerId player
                let units = gs.player_units.[player]
                let orders = orders.[player]

                let isThisDead u = isDead(player_id, u)
                let move_orders =
                    extractMoveOrders units player orders
                    |> filterDeadMoveOrders isThisDead

                let early_disembark, late_disembark = extractDisembarkOrders units player orders
                let late_disembark = filterDeadDisembarkOrders isDead player late_disembark
                let disembark_orders = Array.concat [early_disembark ; late_disembark]

                let embark_orders =
                    extractEmbarkOrders units player orders
                    |> filterDeadEmbarkOrders isDead player
                                
                let units = applyMoves move_orders units

                yield
                    units
                    |> growUnitTree embark_orders disembark_orders
                    |> shrinkUnitTree embark_orders disembark_orders
        |]

    { gs with player_units = player_units }

I have found that comprehensions and the pipeline operator |> are very nice tools to process arrays of units.

My next project: WorldConquest

I started working on a new project during the 2010 Christmas break. It's a turn-based strategy game whose working title is WorldConquest. The final title will differ, as there already are quite a few strategy games with identical or similar names.

The game is loosely based on a game for Atari ST written by Alois Felber from WisiSoft games in 1992.

The new game will feature the same units as the original game. I am planning improvements of my own, some of which are already implemented.

The original game used square tiles, I will be using hexagonal tiles. Although the new game will be turn-based it will use a simultaneous variant where players plan their moves simultaneously. When all players are ready, orders are executed simultaneously. The game will support on-line and hot-seat multiplayer. I have been thinking about and planning AI from day one. Although my experience in this domain
At this point, I have implemented map generation and some parts of AI, namely path finding. Execution of orders is what I am working on now. Design and basic implementation are done, I am testing and fixing bugs.

I am still open about the platforms I will target. The genre should fit hand-held devices such as smart phones and iPad-style tablets. PC and Mac will probably be first, as these are the only platforms that might have the CPU required to run a rough and slow AI. I would also love to publish on Xbox Live Indie Games, but the prospects are uncertain. On one hand this is a genre that isn't much represented on this market, but on the other hand I am not sure console gamers are the right customer base. Moreover, the .Net platform on Xbox features a poor garbage collector which requires code to be written in a very specific way, and I feel designing and implementing AI is challenging enough as it is. Adding constraints on allocation of temporary objects would add to the difficulty, and "optimising" code to work around the weakness of the garbage collector isn't my idea of fun.
To summarize, the platforms will may include the following, ordered by decreasing order of priority and likeliness:

1. PC / Windows using XNA
2. Mac and PC/Linux using Mono and possibly a port of XNA
3. Windows Phone 7 with XNA; although the garbage collector there currently suffers the same problems as on Xbox, announcements were made during MIX11 that the Mango update would introduce a new ephemeral garbage collector
4. Xbox 360 with XNA if the next update includes improvements to the garbage collector. No announcements have been made, but I'm hoping that Gamefest 2011 will bring positive news.
5. Android using Mono. I have no idea what technical limitations Mono on Android has when it comes to efficiency and garbage collection, but I'm hopeful the Mono team will be working hard to lift whatever limitations there might be. Unlike Microsoft's .Net, it's also easier to see where Mono is heading.
6. iPhone and iPad using Mono would be nice, but it does not seem feasible at this time. F# relies on generic virtual methods for function values, which are a corner stone of functional programming. Unfortunately, restrictions on run-time code generation on iPhone (and I guess iPad) make these hard to support. Sadly, this probably means no support for these platforms.

Although the game itself won't be free software, I will update XNAUtils with whatever reusable code I will write. This includes A* path-finding, a UI framework supporting menus and a network component.

I am planning several iterations, steadily moving toward a Civilization-style strategy game. I will release the source code of old iterations as new ones are published.

Using F# scripts for testing and performance measurement

I have just heard about a new project being started by a game developer, NPerformant.

The developer writes

At various times in my “day job/career” I’ve used commercial profilers with varying results, but I don’t want or need to profile the whole application or even a whole library.  I also don’t want to code two solutions into my product in order to let a normal profiler test them side by side in order to remove the loser later.

The problem about creating additional solutions also occurs in testing and when writing small utilities and editors while developing your game.

F# scripts help avoid this issue. You can add number of .fsx files to your project, and executing them using F# interactive (aka fsi) is very easy. For my current game, I have a script to render parts of my engine data using XNA and winforms, and another script to test some of the game logic. I don't know how long I will need these, but the day I lose the use for them, removing them is as easy as removing a single file from your project. Compare that to removing an entire project, which in my case would involve getting out of Visual Studio and using Windows Explorer then TortoiseHg.

Back to the topic of measuring performance, did you know about the #time command you can use in fsi:

> #time "on";;

--> Timing now on

randomTest();;
Real: 00:00:15.761, CPU: 00:00:54.725, GC gen0: 1917, gen1: 2, gen2: 0

Note that you get information about garbage collection too, which is interesting information when developing games for the Xbox 360.

Regarding testing, I just found out yet another case when pattern matching saves the day. In the code extract below, I'm using it to express the expected result of the code being tested.

match gs'.player_units with
    | [| _; [| { health = x } |] |] when x < 1.0f -> true // Injured
    | [| _; [||] |] -> true  // Killed
    | _ -> false

player_units is an array of player units, where players units are represented using arrays of units. My test has an artillery belonging to the first player fire at a helpless infantry of the second player.

The first branch of the pattern matching says: "An array composed of two elements where the first element can be anything, and the second element is a one-element array of units where x is the value of field health, and x is strictly less than 1".

I don't know how I would have written that in C# in a similarly concise fashion.

Informally, my pattern match checks that the unit of the second player was injured or killed.

"I'll Whack Your Fingers"-Oriented Programming

Every now and then, a question about how to transfer data between game screens pops up on the App Hub forums. The source of the problem is that many try to solve this problem using synchronous programming. This does not work because game screens require interaction with users, which cannot be handled in a synchronous manner without freezing the game.

Although F# gives you tools to solve that problem using e.g. async workflows, most people are using C#.

How do you solve that problem in this language? Usually, people use a combination of events and public fields. This solution is fine, but I just don't like events much. They make bugs tricky to track, because I lose track of where handlers fit in the expected flow of execution of my code. Moreover, the only practical way that I know of to pass data from an event handler to the main code is through a shared variable (which I call "I'll Whack My Own Fingers"-oriented programming).

For this reason, I suggested to use Begin-End-style asynchronous programming. This requires an implementation of IAsyncResult if you want to do it in a nice .NET-ish kind of way. I am not aware of any such implementation (EDIT: Here is one, thanks mausch), so I wrote my own:

/// 
 
  /// An implementation of IAsyncResult that wraps result data. 
  /// 
 
  /// Type of the result data. 
  class AsyncResult<T> : IAsyncResult, IDisposable { 
    public AutoResetEvent signal = new AutoResetEvent(false); 
    public bool isDone = false; 
    public T result = default(T); 
 
    public object AsyncState { 
      get { return state; } 
    } 
 
    public WaitHandle AsyncWaitHandle { 
      get { return signal; } 
    } 
 
    public bool CompletedSynchronously { 
      get { throw new NoneOfYourBusinessException(); } 
    } 
 
    public bool IsCompleted { 
      get { return isDone; } 
    } 
 
    public void Dispose() { 
      signal.Dispose(); 
    } 
  } 

Did you notice how I made all fields public? I think many a modern programmer would wince when reading this. What if some careless programmer accessed isDone and modified it? Bad things can follow, and surely we should restrict access to these fields using the private keyword.

I like to call this "I'll whack your fingers if you touch this"-oriented programming. Beside "private" and "protected", which were probably invented to tempt stressed programmers to replace them with "public", enthusiasts of this approach enjoy using "sealed" to punish users who might be tempted to reuse your code.

There are better ways to prevent accidental tempering with an object's internal state: access objects via interfaces.

For instance, here is the code for the Begin-End pair of methods that use my AsyncResult:

/// 
 
        /// Open a MessageBoxScreen asynchronously. 
        /// 
 
        /// The screen manager to which the screen is to be added. 
        /// The index of the player who has control, or null. 
        /// The text of the message to show. 
        /// An object which can be used to wait for the request to complete and retrieve the result. 
        public static IAsyncResult BeginShowMessage(ScreenManager sm, PlayerIndex? player, string msg) { 
          var result = new AsyncResult(); 
 
          var screen = new MessageBoxScreen(msg); 
          screen.Accepted += (src, args) => { 
            result.isDone = true; 
            result.result = true; // User accepted the message box. 
            result.signal.Set(); 
          }; 
          screen.Cancelled += (src, args) => { 
            result.isDone = true; 
            result.result = false; // User cancelled the message box. 
            result.signal.Set(); 
          }; 
 
          sm.AddScreen(screen, player); 
 
          return result; 
        } 
 
        /// 
 
        /// Wait for the user to complete interaction with a MessageBoxScreen opened with BeginShowMessage. 
        /// 
 
        /// The object returned by BeginShowMessage. 
        /// Whether the user accepted or cancelled the message screen. 
        public static bool EndShowMessage(IAsyncResult r) { 
          var result = r as AsyncResult; 
          if (result == null) 
            throw new ArgumentException("Wrong type or null", "r"); 
 
          result.signal.WaitOne(); 
          result.Dispose(); 
          return result.result; 
        } 

Note how BeginShowMessage and EndShowMessage return and take respectively an IAsyncResult. Unless users of these methods really want to take risks getting intimate with AsyncResult, there is no risk of tampering. And if they really want to work directly with the inner parts of AsyncResult, why prevent them to do so?

I wonder, what's the point with "private" and "protected" anyway?

UPDATE:

Thinking a bit more on the subject, I think another overused feature resides in non-virtual public methods (and fields). Anything public in the API of a class should belong to an interface, with the exception of constructors and construction helpers (which maybe should be internal to assemblies).

I would however not advise to use abstract data types in all situations. Navigating in the call tree is a good way to learn a new code base, and typically abstract methods defeat this. One could say abstraction through interfaces is a form of obfuscation, as it effectively hides implementations.