Heroes of Arcadia progress update

Playscape Games mobile Strategy-RPG Heroes of Arcadia (renamed from ‘Arcadia’) has been 3 years since inception to date. I suspect some friends and observers of the project, quite understandably, wonder (a) what we’re doing all day, and (b) if we’ll ever finish.

Well, I’m hard at work. Making a quality RPG, on any platform, involves a large investment of effort is a wide variety of areas.

To convey a sense of the many little details that go into it, here’s my notes for a source code commit spanning 9/3/08 – 31/3/08, about 6 man days of development time on my part-time schedule. Apart from demonstrating a lack of discipline when it comes to regular source control checkins ;), I’m quite happy with the steady progress we’re making.

As for a “release date” – sorry, I cannot estimate that accurately enough to speculate on. However, we’re aiming for a second beta release mid year.

Numerous enhancements and fixes (too long between commits):

Hero class removed, replaced by ExtendedUnit
HeroType removed, heroes become regular UnitTypes

Added/updated sprites:
-Animated structures
-Increased size potions, fixed tombstone
-Shadows removed

TargetSelectionRequestor
-Merge with its interface, removal of dead code
-becomes a Runnable task
-Less filtering of invalid target applied by UI
-MapViewInputHandler greatly simplified by moving target selection logic to TargetSelectionRequestor

Remove World methods delegating to Zone

MapView
– Health bar goes yellow/red when wounded
– Fixed bug where sprites faced wrong way in combat
– Made ranged/melee attack code pathways more uniform
– Removed turn counter from the HUD
– Removed “Cannot enter” warning when attempt move to impassable location

IOManager
-Fix: Zone added to read table when deserialized
– Better exception handling when content script init fails

Textwindow
-Globally enforce rule requiring use of task queue to display text boxes

Scripting:
Completed northern wolves quest
Completed forest shrines quest

Removed remaining resource rules code

Party leader passes baton on death, new leader selection dialog

Big speed up in Faction invoke code
-NPC factions serially called from Zone
-Zone runs from Task queue, World dosnt anymore
-NPC Factions not intersecting player faction are only run periodically
-Faction class no longer runnable, PlayerFaction remains runnable, code diverging alot.

Relationships
-Added 5th alliance state Neutral, renamed old neutral to “wary”

Pathing & Movement
-Replaced Breadth-First Search with AStar pathfinder
-AI now prefers not to paths thru other npc factions

boost AI aggression to pevent units fleeing too much

Introduced consistent unit targeting rules and added AI
-Melee: defender nominates defender
-Ranged: attacker nominates defender

New AddTrigger command for scripting

Remove obselete Abort- and Contiue- TargetSelection commands

New LocationFunction types: Location -> int, used in pathfinding

Fixed bug in unit’s cached event history causing party escorts not to
attack

Fixed divide by zero bug when finding minimum threat locations

Quests now award XP on completion

Advertisements

Situationist Game AI

I have just become aware of Game-Developer/Philosopher Adam Russell through his thought provoking article on Situationist Game AI in Game AI Wisdom 4. I look forward to reading more of his work in the near future.

Reductionism vs Constructionism

The article lucidly describes one of the key design tensions in designing any game with story:

  • Reductionism: You want your world to be filled with interesting, autonomous agents that the player can interact with
  • Constructionism: You want to choreograph these agents in a very controlled, predictable way when required to tell the story

These tendencies are conflicting; for example, through interacting freely with an agent you might move, re-align or even kill it, which compromises the ability to use the agent to advance a pre-conceived story. He gives a nice exposition of how this tension has been handled, or more correctly, “worked around”, in various games to date. Its the best explanation Ive yet read of a tension that has plagued me during the developement of Heroes of Arcadia.

The beginnings of a solution

Adam’s response is to advocate a hybrid approach dubbed Situationist game AI. Unfortunately, this solution is much less precisely articulated than the problem. But he starts down the road with vigour. He draws parallels with debates about local vs global influence in sociology and psycology, and finds middle ways in both fields where an autonomous agent’s environment strongly conditions and shapes its response.

He then sketches how these ideas might be applied in game animation, perception of the environment, and in layering of multiple action-states in an agent’s behavioral representation. Little that’s directly usable at this stage, but I do hope it spurs other more practically-minded developers to make advances in this area.

Audiosurf

Check out Audiosurf, an incredible and inspiring indie game and rags-to-riches story that has gone from a IGF finalist at GDC 2008 in February to the number one most downloaded title on Steam in March! Because it’s so good.
Theres a free demo through Steam. An unmissable experience for gamers.

Modelling Calculations with Objects

A recurring issue I seem to encounter is how to best model non-trivial Calculations in software; tasks that take multiple input parameters, do some computation, and provide a result object with multiple fields.

Some real examples from my career:

  • For a customer with a loan contract, calculating the amount they must pay to payout the loan early and terminate the contract. Typically there are extra fees/charges to end a loan early. Also, we will want to know not just the final figure, but a breakdown of it into components.
  • In a game world, finding the best path(s) a unit should take to a goal location, with some input constraints on where that path should go, using for the A* search algorithm. We might also specify constraints how much CPU time or memory the search is allowed to consume.
  • To obtain an accurate numerical prediction function, we perform a Genetic Algorithm (GA) search to find optimal input parameters for it (there are many of these) over some training data. We might start with an existing function as input and improve it, or from scratch. Configuring a GA itself is complex. And the result object may contain data on performance during training, as well as the desired function params themselves.

Storing The Inputs and Results of a Calculation

The simplest calculations typically return a number, a date or an object. But it doesnt take very long before we find ourselves wanting extra details about the result, or about how the result was derived. A Calculation Object (sometimes: Result Object) groups together all of the results of a calculation, and is almost always recommended.

I also find that its very useful to record (or identify) the inputs to a calculation in the same calculation object. They may be required as a historical record for audit purposes, or so the calculation can be repeated, or for verification of its correctness.

Who Owns the Calculation’s Logic

If a Calculation Object ends up holding all the input state for the calculation, and all the results, should it also end up with behavioural methods for doing the calculation?

new PayoutCalculation(contract, payoutCharges, payoutDate)
payoutCalculation.calculate()
payoutCalculation.getPayoutDueAmount() //calculated field

The above style is object-oriented, but I have come to prefer a separate Calculator object, a Factory that performs the calculation logic and creates Calculation objects as its products…

payoutCalculation = payoutCalculator.calculatePayout(contract, payoutCharges, payoutDate)

…for three reasons:

  • A calculator can vary polymorphically and is less coupled to the Calculation Object and the client code.
  • Calculation objects become stateless – they are only given to the client once all their fields are filled in.
  • Often calculators need significant internal datastructures used during calculations, that are not part of the result.

Calculator API

In the payout example above, the three input parameters needed to calculate a payout are provided in a single, atomic method invocation that performs the calculation. This is the neatest, preferable case.

Sometimes, a calculation has many overrideable defaults for inputs. For simpler cases, this can be solved through overloading…

payoutCalculator.calculatePayout(contract, payoutCharges, payoutDate)

//default payoutCharges, date = today

payoutCalculator.calculatePayout(contract)

…but as the inputs get more numerous, or when a calculation has many mandatory parameters, it becomes impactical to provide everything as individual parameters to a method call. Then, your options are to:

  • Build up the inputs on the Calculation object itself, then pass it to the Calculator to have its outputs filled in. You lose the statelessness of the Calculation this way.
  • Create a Recipe object and pass that to the Calculator.
  • Bake the inputs into the Calculator itself, so that every Calculation it produces picks up its parameters.

Calculator State
Complex calculators often need lots of state while they are running. For example, A* pathfinding maintains two Sets of nodes, one with additional ordering requirements. Where to store it?

  • Storing it inside the Calculator means it becomes stateful, and so cannot be shared across threads. Care needs to be taken to reset the calculator before next use. This choice is appropriate when you have a known, single-threaded audience, and/or calculator state is havy and expensive.
  • Throwaway calculaltors are created/obtained by each client as needed, used once, then discarded. Obviously thread-safe.
  • Calculators that have multiple copies of the required state, one associated with each client request, tracked eg by an record in a hashtable.

Be aware that if the calculator is asynchronous and long-running, there may be concurent, overlapping calculations running even in a single threaded scenario.

SimpleDateFormat is perhaps an example of inappropriately handled statefulness. Its in a Java API widely used by experts and beginners alike, with an immutable-sounding name, and yet its (unintuitively) stateful, so that if multiple threads access the same format, they can get crosstalk between their formatting jobs.

Automated Testing 2: The Test Pyramid

A colleague of mine, Rob Capretto, introduced the idea of a Test Pyramid. Its like a Food Pyramid – everything has its place in moderation, but to stay healthy, there are certain types of tests you should have more of, and others you need only in small amounts. Here’s my pyramid:

testpyramid.png

Notice that

  • The majority of tests are mock-based unit tests. In a perfect world, these would be all you need. However, due to both gaps in coverage and subtle inter-object interactions, in practice its wise to put your pieces together sometimes in an integration test.
  • We have some subsystem integration tests that test parts of the system.
  • We have external integration tests that test software & services created by other people/providers that we rely on, and your infacing to them. How important these are depends on how much “surface area” your system has – if its largely glue, these might predominate.
  • We have a few whole system functional tests that test the fully operational system as a user might use it. These should be very few in number, and just serve as sanity checks that when everything is combined, there aren’t any weird interactions or incompatiblities that prevent it working as intended.

Two tests Good, Four Tests Better…. NOT!

A key point is that, just like in a Food Pyramid, you can easily have too many functional, integration and even unit tests if you’re not careful. Not only are they expensive to create, but having too many test quickly become a maintenance burden when you refactor software. The longer your projects runs for, the more pain you will feel from maintaing tests, because tests tend to multiply inevitably over the lifetime of software, and they become brittle, decayed and obtuse if uncared for, just like application code.

In fact, you have to be sparing in the creation of tests. More testing is not automatically better.

Its really the same principle as application code: you want the most effective code in the least number of lines. For tests, “effective” means detecting bugs and undesired change, whilst minimally obstructing desired change.

(The title is a reference to a favorite line of of mine from George Orwell’s novel Animal Farm, implying overly simplistic dogma: “four legs good, two legs bad”)

Automated Tests Make Brittle Codebases

A provocative subtitle, but it’s literally true! If you take heavily automated-tested code and change almost anything, the test suite will break somewhere. Of course, the breakage is intentional, but dont forget that autoated testing is a special kind of deliberate & detectable brittleness added to code. That brittleness protects against entropy, but it can also obstruct you when you add desired change to the codebase. Ive experienced cases where a small change applied into a large codebase can require ten times more effort to fix breaking existing tests than it does to add the new change and its unit test.

Mechanics of Turn-Based Videogames

Most turn-based videogames use non-simultaneous turns, where one unit of one player or side moves at any time.

Simltaneous turns are more difficult as they raise lots of concurrency issues, and I will not discuss them here.

See also this blog article at Gone Gaming for a broader discussion of turn-based game mechanics.

Non-simultaneous turns come in at least 3 common flavors:

Units on each side Chunked together

1. Each side moves its units in turn. Individual units make a move/action once per turn. Examples: Advance Wars, Ancient Empires, Many Board Games.
2. Each side moves its units in turn. Individual units can interleave their moves & actions arbitrarily within the turn, changing focus in between. Examples: Civilisation, Arcadia

I see option 1 as really a lite form of 2, where the mechanics are simplified because a unit is never in a partially moved state, and there’s less need for controls to cycle between active units.

Individual Turns

3. Each unit in the game moves separately from others on its own side. Different side’s unit’s actions are interleaved. Examples: Final Fantasy Tactics Advance.

    Variable Action Frequency

    What Indivudual Turns allows that Chunked approaches cannot, is the ability for fast units to act more frequently than slow ones. Their turn can come up more often. I really like it, its quite realistic and better matches real time games. However, I dont think it scales well to losts of units that need to execute team maneuvres, because their individual turns are scattered through time. Hence, that mechanic tends to be used in Tactical style games featuring a small number of participants. In Strategic games like Civ, where you control many more units concurrently, having all your unit moves happen at once makes it easy to execute large plans of action.

    Chunked approaches often struggle to model different unit speeds of in a meaningful way. Typically, units can move different amounts but are allowed one attack, spell or similar action per turn.

    Movement Points In Arcadia

    In Arcadia, we are trying to meet the challenge of variable action frequency via variable number of Movement Points (MP) allowed to each unit.

    • A unit can attack, cast spells or any other action multiple times per turn, if it has any points remaning. (So MPs are really Action Points.)
    • Different actions have different costs; movement in the open costs 1; a melee attack costs 3.
    • If taking an action would result in a negative MP balance (eg Unit with 1MP attacks, costing 3MP), we allow that! But, we store up the debt and repay it, in effect an overdraft, so that next turn the unit will be able to do less.

    Where this approach is really nice is its robustness to MP-reducing effects. For example, imagine a Slow spell reduces a unit’s MP-per-turn to 1. Without an overdraft, it would struggle to every attack, as attacks cost 3. With an overdraft however, it can attack ever 3rd turn, which feels just.

    The Relationship between the Domain and Services

    There is a school of thought, prevalent today, that says: A Domain model should always be independent of (and thus never call) the Persistence- (aka Repository) or Service- layers. I dont yet know of an established name for the architecture implied by the rule, so I shall refer to it as a Independent Domain and the reverse, architectures where the domain model references Repositories (or the like) a Co-dependent Domain.

    I dont subscribe to the view that Co-dependent Domains are bad or prohibited. While Independent Domains work well in many situations, there are times where its practical, or just plain tractable, to back a domain-object method with a query to a repository. Other times, we would like a domain object to emit an domain event to a subscriber in the service layer, who might convert it into an email. In fact, rigid adherence to an Independent Domain rule can cause harm by encouraging domains to become Anemic.

    Assumed Context

    • Rich Domains with classic object-oriented encapsulation are desirable. In such a system, the service layer is thin and virtually all code lives on the domain objects.
    • An architecture loosely like diagram (dotted arrows denote “depends upon” or “knows about”).
    • In an Independent Domain, the red arrow is not present, and thus generally the blue arrows may aquire extra reponsiblities to compensate.

    domaindependencies.png

    • Repositories (loosely as described by Evans or Fowler) are the main interfaces through which the upper part of the system interacts with the ORM layer.
    • We’re mainly talking about data reads here, ie database queries.

    [Notice that there are a lot of one way relationships between adjacent tiers; we developers have learned that the mssing depedencies are extraneous. But nonetheless, the reason for every missing (prohibited) relationship needs to be understood and justified. Its is not sufficient to reflexsively ban them to make the diagram “pretty” or “symmetric”.]

    Survey of Existing Views

  1. Christian Bauer and Gavin King’s Hiberbate in Action are (to their credit) clear about their position: they advocate an Independent Domain and give two reasons why (pp 306, 310):
    1. If domain objects depend on Repositories, they cannot be used in tiers/contexts where there is no open session to the persistence layer.
    2. Domain object depedency on persistence makes unit testing them more difficult
    • In Jimmy Nilsson’s Applying Domain Driven Design, an overview diagram on page 116 depicts a Independent Domain, though he doesnt say why.
    • In Fowler’s enterpise patterns book, the example code for Data Mapper uses a Co-Dependent Domain (ie Albumn Finder).
    • In Javas J2EE 5 model, Entity Beans represent the Domain Model, Session Beans the service layer, and EntityManagers provide a gateway to the ORM layer. Sessions Beans can have the Entity Manager injected, but Entity Beans cannot, so clearly EJB 3 advocates the Independent Domain principle. Part of the reason, I think, is that J2EE promotes an Anemic Domain as a core principle, so they like to put business logic into their service layer, and make domain objects Dumb and Passive. Eg JBoss’s Bill Burke inEnterprise Java Beans 3.0: “Session Beans … are the appropriate place for business logic”. Its not my preferred architecture, but I’ll explore and evaluate the reasons they did that in another post.
    • Bill Evans Domain Driven Design book supports a Co-Dependent domain, though he’s not entiely explicit and it required some careful reading to discern his positon.
    • Some of my workmates favor an Independent Domain. I think the motivator is the appealing idea that a domain model should be able to exist in isolation. Certainly appealing, but is it workable in all cases?
  2. Thats all Im aware of now. So Im left unsure if there are other any reasons. If anyone knows of more, good arguments for prescribing an Independent Domain, please send them to me.
    I have yet to read any explicit argument outlining where Co-Dependent Domains are best – hence the need for this article.

    When should Domain Objects access Repositories?

    When they need to get references to other objects they interact with, and main alternative, traversal of the domain model relationships, doesn’t work well.

    In an Independent Domain, where entities cannot query repositories, how will they get references to other objects?

    1. They have OR mapped relationships, set by the ORM layer when it loads the entity. If they need an object they dont have a reference to, they must traverse a path through intermediate relationships. This is the normal way that most entities communicate. Now, recall that object relations are unidirectional, in contrast to databases where with appropriate indexes, relations can be treated as being bidirectional. So there is the likelihood that our system’s domain model, even though fully connected, will not allow us to traverse everywhere within it, unless we deliberately create bidrectional relationships in the domain.
    2. They get passed them in method calls as parameters from the Service Layer. This just adds extra work for the calling code and leads to bloated method parameters.

    Limits Of Domain Object Traversal

    There are things you cannot do efficiently by traversing domain object pointers:

    • Traversing a relationship with a high multiplicty, and then narrowing down the related domain object by some criteria. By High Multiplicity Relationships, I mean a many-to-one relationship between two entities, where the many side is numerous. It becomes impractical to traverse from the one side to the many side in the domain layer. Typically, we’re not interested in whole collection, just a small subset of them, so we dont want to have to load them into memory just to search through.
    • Finding sums and similar aggregate functions of many small object. This is much more efficiently accomplished directly in the database.

    Loose Coupling and Interface-Based Design

    One of the reasons people advocate Indenpendent Domains is that they fear that referencing persistence- or service- layer classes will couple their domain to its application environment. It seems to me this confuses interface and implementation.

    Your domain should access other layers through interfaces that are meaningful within the domain. When accessing the persistence layer, use a Repository interface that models the concept of “the collection all domain objects of type X in the world”, that could be backed a hashtable for all the domain knows. Similarly, when pushing events to the service layer, use a listener interface that does not reveal that the listener is outside the domain.

    Linking the Domain to its Surrounding Layers

    A co-dependent domain can be tricky to link to surrounding layers. Domain objects are usually created by the persistence framework (eg Hibernate), so injecting services into them before first use by the app requires interception of the create or load event.

    Spring’s recomended approach require use of AspectJ class weaving to intercept the calling of domain objects constructors.

    Most persistence frameworks should provide an on-load eent that can be hooked into (Hibernate does).

    An alternative is to use a globally (ie statically) accessible Service Locator that the domain can use to lookup dependencies. It will work, but dependency injection is preferable.

    Automated Testing 1: Goals of Good Software Tests

    There are certain skills in software development that are very subtle. They seem to take years of experience to really appreciate and learn to apply well. One of them is writing good automated software tests.

    The “ideal” set of software tests should:

    1. [Strong] Always fail in the presence of bugs (the classic definition of a “good test”)
    2. [Cheap] Require little effort to build
    3. [Informative]The cause of a test failure is obvious
    4. [Flexible] Never fail as a side effect of desired change to the system

    The above goals are conflicting. Increasing any of them tends to reduce the other others. Thus the subtlety in finding the correct balance.

    When I first leart to unit test, I only knew about Strength and Cost. And I think I focused my attention on improving Strength more than Cost.

    Then, I learned that you can achieve decent Strength and Cheapness by coarse integration tests. However, such tests arent Informative, nor Flexible.

    Flexiblity is very subtle, because it counters the simple heuristic: “more test, more good”. The negative effects of low flexibility take time to perceive.

    This is the first of several posts on Automated Testing. In them, I hope to describe the guidelines I use to optimize all four goals.

    [But for the impatient, it really comes down to “use mostly fine grained unit tests, including lots of interaction tests (probably using Mocks)“.]

    Improving visibility rules for Java & C#

    The visibility concept (eg public, protected, private, etc) is overdue for a complete overhaul.

    Visibility specifies what code can see/invoke other code, and by doing so, can helps define module boundaries in software.

    The four level system used in Java/C# [public, protected, package/assembly, private] is based on an outdated one-dimensional spectrum between self and other. Furthermore, the protected modifier is fixated on the (now declining) importance of class inheritance.

    Multiple APIs for Multiple Audiences

    In typical enterprise-scale code I work with today, different partly-overlapping sets of methods on a class are called by:

    • Application code
    • Test Code
    • Hibernate persistence code
    • Spring Dependecy Injection code

    Different methods of a class are written with a particular client, or audience, in mind. The current visiblity systems, which deliniate a spectrum between self and other, cannot express this.

    We need a way to say “my persistence layer and my unit tests can call setId() on my domain object, but on one else”.

    Make protected a configurable, multi-audience modifier

    The idea behind protected is to make the member visible to a priviliged subset of code in the ‘outside’ world, ie subclasses. But nowday, there are so many other reasons why outside code should have differeing levels of access: architectural layering, infrastructure vs application code, aspects such as serailisation or transactional behaviour. In practice, we make everything public and eschew the useless protected level.

    We can fix this by making protected accept parameter(s) specifying what code is included or excluded from access.

    //equivalent to protected(Subclass)

    protected

    //can be called by any package or subpackage of com.mycompany

    protected(com.mycompany.**)

    //can be called only by packages com.mycompany or com.myothercompany

    protected(com.mycompany, com.myothercompany)

    //can be called by anyone except subpackages of com.mycompany

    protected(exclude(com.mycompany.**))

    Of course, writing the allowed calling classes out above every method would be tedious. Aliasing is needed:

    Hibernate = protected(org.hibernate)

    In fact, the Java tool Macker enforces visiblity above the language level, because the language-level mechanisms are no longer up to the job.

    private is the default

    The default visiblity of a member should be private, not package (Java) or internal (ie assembly in C#), to match the default setting most developers actually use in reality.

    Its probably too late for Java/C#, but improvements is needed in the next generation.

    Java Continuous Integration: Hudson Rules!

    It’s surprised me just how fast everybody has realized that Hudson is a better Continuous Integration tool than CruiseControl.

    It reminds me of 2002, when JIRA overtook Bugzilla in the Issue Tracker tool space (while Scarab bleated lamely from the sidelines about being nearly ready)

    I have used both Hudson, Cruise, and Anthill. I like Hudson best by a wide margin. Derogatory remarks here about Cruise removed -Ed.

    Hudson is developed by Kohsuke Kawaguchi of Sun, lead dev of JAXB. I suspect he may be quietly brilliant.

    « Older entries