#smartmonsters

[triadcitydevelopers-blog]

Migrating SmartMonsters to the Cloud. Part Two: Breaking Up the Bots.

TriadCity’s robots Death, Help, Marvin and Oscar are AIML-based chatterbots architected monolithically, meaning each bot is an individual application, fully vertically integrated: TriadCity client code, AIML interpreter, AIML files, plus each bot’s thin layer of hardwired individual behaviors, packaged independently of each other, deployed separately, where each deployment has its own directory hierarchy, and so on. This is not some massive scalability bottleneck.  We’re only talking four bots.  With a little work we can even semi-automatically update their AIML without having to fully rebuild each application. But, there are advantages to decoupling their AIML brains from their TC client code:

 Simpler to develop a new generation of bots hosted on different platforms, where these new bots can access a central shared AIML brain via different protocols and devices.  For example, we can access Oscar’s newly RESTful brain from mobile devices, Web sites, Twitter feeds, and the existing TriadCity bot without having to maintain separate AIML repositories for each client.  AIML updates become independent of the Java code for these multiple platforms, doable in real time without rebooting the bots.  The AIML service can scale independently, becoming fully elastic in The Cloud.

Easier to harden our AIML implementation.  Today we rely on each developer to get it right.  This is a problem, because the XML parser is brittle.  If an AIML topic is rejected, subsequent loading from that file stops: all the following topics are ignored.  This means that from a file containing 15,000 topics, only the first few hundred might be loaded if there’s a simple XML typo like forgetting a closing angle bracket.  Also, notice to developers is non-automated: someone has to read the logs.  If by contrast we deploy the AIML interpreter as its own service, we can use standard CI to validate new AIML centrally, independently of developers, in multiple passes.  Like this: check in new AIML —> Jenkins fires a build —> the AIML is validated with the same SAX parser the interpreter uses at runtime —> if the validations fail, the build stops and developers are notified; if the validations succeed, a remote script triggers a pull from SCM, updating the runtime AIML —> the app is redeployed, invisibly to end users, without downtime —> a final round of functional tests written in the SoapUI tool validates the AIML rules at runtime, catching any regressions.  This is really pretty nifty.

Easier to swap-out or enhance AIML interpreters without having to rebuild and redistribute an army of dependents.  Specifically, we’re unhappy with the “Program AB” reference implementation, which is brittle and poorly performant.  We’re likely to either replace it or fully rework it soon-ish.  Decoupling that engine from its clients helps to future-proof.

Enables the AIML engine to become fully “elastic” in The Cloud: scaling out or in automatically under load.  Nice!

Here are the migration steps:

Pull the AIML interpreter out of the bot code, into a standalone application accessed as a RESTful service running in The Cloud.  Very super minorly tricky, because the off-the-shelf AIML interpreters for Java are file-centric, reading from and writing to directories requiring access.  Granted we’re not interested in re-writing the interpreter to be more flexible, this rules out Google App Engine, which has no concept of file system.  So, Elastic Beanstalk.  With a little bit of hoop-jumping we can make that work.  A shell script in the ec2-user’s home directory pulls revised AIML from SCM; Jenkins will fire that shell script remotely.  Alternatively, we could package the interpreter code and AIML files together in a single WAR which we'd redeploy with every change.  Although this is simpler, I decided against it since our AIML developers are used to accessing their source files in a separate location in SCM.  It may be necessary to revisit this, as updates to EB now rely on knowing the underlying EC2 instances’ DNS addresses, which of course can change elastically under load.

Redesign the AIML interpreter to serve all of the bots.  Our legacy vertical monoliths were each-bot-integrates-its-own-interpreter.  Here, we’ll serve all AIML from one central RESTful service on Elastic Beanstalk.  The REST API will be super-simple: a GET call parameterized with the bot name and the input String.  Return an easy-peasy JSON object.  That’s really it.  Whip it together in JAX-RS and there it is.  Let EB scale it if that ever becomes necessary.

Remove the AIML interpreter from the Web site, having the appropriate JSPs now RESTfully GET their conversations from the service on EB.

Remove the AIML interpreter from the TriadCIty bots, having them similarly call into the service.  I decided while I was at it to consolidate the four existing bots into a single JAR rather than continuing to build each as a separate project.  This is simpler, and there’s very little Java code distinguishing the bots, really just some hard-wiring of default responses and some variation of the circumstances in which they’ll intervene in chats.  A configuration file determines which bot to run; the consolidated code figures out which bot-centric classes to load.

Configure Jenkins to manage Continuous Delivery.  The CI build fires when updates are made to the central SCM.  The build lifecycle now includes two cycles of AIML validation.  A first pass ensures XML correctness before changes are pushed to production; a second pass validates the AIML rules by comparing expected to actual outputs.  If we were a larger company I’d break CD into a deployment pipeline where we'd push first to a functional test environment to run these SoapUI-based tests, acting as a quality gate to production. I may circle back and do this at a later time.  For now we’ll just do it in production, and send ourselves an email when a test fails.

Now let's add some PaaS sugar.  We can log inputs which fail to match any AIML rules, triggering default responses.  This feedback will let our botmasters know what their users are interested in, and how their bots are performing.  Since we’re on AWS, let’s log to DynamoDB, with a super simple schema: bot name, <input>, <topic>, <that>.  Then let’s schedule a job to report on these failures, say, weekly.  Coolness!  Let’s additionally modularize and abstract this logging so that we’re not 100% married to AWS; we’ll do that with the standard OO Strategy Pattern, via an Interface with a Factory delegating to concrete implementations servicing different environments.  Later if we want to bolt from AWS we can simply implement a new Strategy class for wherever we go without untangling miles of upstream code.  Check. The migration took two working days, following the steps above.  AWS basics are straightforward, with intuitive controls.  To my surprise, DynamoDB logging required a full third day.  I struggled to get connected - turns out the published Developer Guide is missing one key point, and incorrect on another.  To connect you have to specify the AWS region, duh.  And, Integer keys are not necessary, Strings are fine, and there's a handy "@DynamoDBAutoGeneratedKey" annotation in the Java SDK which'll auto-gen the key for you.  Nice.  Pleased to get it going: I'd very much prefer NoSQL solutions, especially when the data are inherently non-relational, as these records unavoidably are.

One more area of enhancement seems obvious.  Writing these log messages directly to db is synchronous: our RESTful API server will block during the transaction.  Let's put a message queue between the API server and the database: we'll fire the log messages and forget them.  Easy-peasy: add a "worker tier" to the application; call the write-to-DynamoDB logic from its POST method; implement a new Strategy object which writes log messages to SQS instead of database.  Half a day. The platform is now in place upon which we’ll build a new generation of bots more advanced than these.  There’s an upcoming project to rebuild our QA bots via the Drools rules engine - QA bots seem a natural venue for rules-based AI and with Drools we can invent a Domain Specific Language for QA, enabling simple-ish future expansion.  Let’s get on it. The next Cloud migration step will be SmartMonsters’ fully-dynamic Web site.  More to follow.

[triadcitydevelopers-blog]

Migration notes: from RDBMS to MongoDB

The relational paradigm maps poorly to OO design.  Objects don’t have relations.  When you use an ORM for CRUD you end up with a denormalized schema lacking the core point of *relational* databases.  If your OO design relies on inheritance you can potentially end up with absurdly large numbers of tables.  In TriadCity we have hundreds of Item subtypes with varying properties; mapping these to traditional normalized RDBMS would result in spaghetti schema.  Somebody has to win: you end up with either a lousy database or lousy OO design.  Because MongoDB is schemaless these problems don’t arise.  You can put all those hundreds of Item subtypes into the same MongoDB Collection, no worries.  And you can report on them in a perfectly granular way,  Schemalessness removes the impedance mismatch between the two views of the world. Our migration turned out to be a far larger project than my initial tests led me to expect.  It was trivial to migrate game object persistence as noted above.  Without hyperbole, an hour or two.  But of course, we do vastly more with data than merely game CRUD.  For example, we're beginning to use rich data analytics of 14 years of in-game auctions to enable AI driven characters' bidding behavior: when to bid, how much, what ceiling.  Previously that logic would have lived in a vendor-specific stored procedure, and would have been much less comprehensive at runtime than what we can achieve now; today instead it’s a combination of MongoDB plus Neo4J for real-time lookups.  I’m happy as can be to have this logic live in Java inside the game engine, rather than a proprietary stored procedure language in the database.  But, implementation in the new technology took some effort. I chose not to merely replicate our previously relational schema in MongoDB.  It would have been incrementally easier to simply map tables to Collections 1-for-1 via some down-and-dirty little Java snippet, and that would have been that.  Instead, I chose to try to take advantage of MongoDB’s JSON-based ability to store related information in a single record via nested arrays.  Here’s an example.  Our RDBMs used normalized tables to relate basic user account information to: demographics; settings and preferences; security roles and access restrictions; a listing of bounced email addresses; and a table of locked accounts.  So, a parent table and five children, related by the unique ID of the parent account.  Perfectly reasonable in a SQL world.  In MongoDB, it makes better sense to keep all of this related information in a single record.  So our MongoDB JSON Person record has an array field for demographics, another for roles and privileges, another for settings and preferences, and simple boolean flags for bounced emails or global account lock.  Easy-peasy.  This consolidation is straightforward to code to, and appealingly enough it results in a human-readable document easily browsable in your favorite administrative GUI.  Nice.

Almost as a side effect, the need for transactional guarantees simply goes away. In a SQL world most transactions are second-order: they’re really artifacts of the relational technology itself, where an update to a Person per above might require writes to multiple tables. Post-migration we literally have not a single use case where a transaction is necessary. We do rely on write and replication guarantees in MongoDB: our writing Java thread blocks until it receives an appropriate write acknowledgement. Usually we ask for a write-plus-replicate acknowledgement. I suppose that’s sort of the MongoDB analogy to relational transactions but they’re conceptually different and simpler in practice. The Java driver for MongoDB handles them automagically.

Object-oriented queries in MongoDB's Java API turn out to be super simple to internalize.  They read like almost-English and they make perfect sense.  Here’s an example and its SQL equivalent. This looks up the most recent sale price of a Player’s in-game house.  MongoDB:

    DBObject where = new BasicDBObject("playerHouseID", playerHouseID);     DBObject fields = new BasicDBObject("price", true).append("timestamp", true);     DBObject sort = new BasicDBObject("timestamp", DESCENDING);     DBObject found = this.mongo.db.getCollectionFromString("PlayerHouseSales").findOne(where, fields, sort);     if (found == null) { // this player house has never been sold         return -1;     }     return (Long) found.get("price");

The SQL equivalent minus whatever framework boilerplate you employ would have been something like:

    "SELECT * FROM (SELECT price FROM player_house_sales WHERE player_house_id = ? ORDER BY timestamp DESC) WHERE rownum = 1"

Personally, I find the OO version vastly easier to conceptualize. Object-oriented queries like these make it straightforward to eliminate the 200 or so stored procedures which had tied us to one specific RDBMS vendor.  Nearly all of these stored procedures existed because it’s easier to implement branching logic in a stored procedure language than in SQL.  Typically the branching test was whether a row already existed, thus insert or update.  The MongoDB Java driver’s save() method handles upsert for you, automagically converting between insert and update as the case warrants.  A few circumstances which are marginally more complicated are easily handled in Java.  I experience this as a huge gain.  All of our data persistence and analytics logic are now in Java in a single location in a single code base - no longer scattered among multiple languages and disparate scripts in different locations in SCM.  Nice. I don’t know what the best practice is for sequences.  Sequences aren’t recommended for _id unique keys.  But, there are circumstances where an incrementing recordNo is handy.  For example, I like to assign a recordNo to each new Room, Exit, Item and so on.  A dynamic count() won’t do for this, because these objects are occasionally deleted after creation, e.g., a world author changes her mind about a Room or series of Rooms.  I’d nevertheless like to know the grand total of how many Rooms have ever been created, without keeping a separate audit trail.  It seems straightforward to create a sequence record in the database with one field for each sequence; you then call the $inc operator to do what it sounds like.  Since this is not the _id unique key we're talking about, I ran with it.

I'd like to see more syntactic sugar in the query API.  Common operations such as summing or averaging columns are cumbersome today.  There's a new-ish Aggregation Framework seemingly designed for large-scale offline reporting ala your favorite SQL report writer.  For ad hoc in-game queries, I'd prefer the Java API, and would like to have common operations like summing or finding max or min values highly runtime optimized, as they are in the RDBMs we're replacing.  There are corners of the MongoDB programming world which to me seem immature, like these.  Development seems very active, so hopefully these gaps will be filled soonish.

I've encountered one problem not yet solved.  Sparse unique indexes don't seem to work.  Inserting more than one record with a null value into a field with a sparse unique index fails with a duplicate value error on the null, which the "sparse" part is supposed to finesse.  Google suggests others have experienced similar glitches.  For the time being I've turned off the index, and am continuing to research.  Really do want this working. Runtime performance is excellent.  Superior in most cases to the SQL equivalent.  For example, loading 18k Rooms from RDBMS including their default Items and Mobiles typically required about 40 seconds; with MongoDB it’s usually 15 seconds or thereabouts.  On my MacBook Pro with 8 cores and 16gb RAM, a complete game boot in the SQL world took around 60 seconds; it’s half that with MongoDB.

[For a client, I’ve subsequently done a shootout of very high-volume write processing between MongoDB and Oracle, where “high-volume” means hundreds of millions of writes. MongoDB was an order of magnitude faster under serious load.]

MongoDB’s system requirements are more demanding, though.  MongoDB likes to put the entire data set into RAM.  It assumes a 3-node replica cluster with several gigs memory per node.  Our data set really isn’t that big, so we’ve got it shoehorned into t2.small instances in three regions on AWS.  Without a lot of hands-on lore, I can’t say yet whether we’ll turn out to need to bump up these instance sizes, or if they’ll be fine.  Film at eleven. [Update 2014.10.31: instance sizes unchanged.  All's well. Your mileage will vary.] MongoDB’s automated replication is pretty nifty for high-availability and for offloading queries from the writeable system.  We run our analytics queries using map/reduce against mongodumps taken from one of the secondaries, freeing the primary for production writes.  Nothing’s necessary to enable this behavior, it works out of the box.  For very large data sets, sharding is easy-peasy.  There's a handy connector linking MongoDB with Hadoop, for our offline map/reduce queries.  The database is designed for these topologies, which in many RDBMS worlds are cumbersome to achieve. Now for the interesting future.  Granted our enhanced ability to easily analyze our 14 years of comprehensive log data, we can begin to enable vastly more powerful and realistic in-game AI.  Here’s an example.  The data show us which Items sell most frequently at auction; what the most successful starting prices are; what the average, minimum and maximum final auction prices are for each Item type; how many bids are common; upper and lower bounds on all these things; medians; distributions; curves; etc. etc.  They can help us predict which Players or AI-driven characters might be interested in buying which things.  By pulling the “big data” from MongoDB and graphing it with Neo4j, we can enable super-zippy real-time queries like, “Should I bid on the current auction Item?  If yes, how much?  What should my top bid be based on the bid history so far?  If I buy it at the right price, will I later be able to profit from re-auctioning it?  When’s the best time to re-auction?  Are there any Players currently online who may be interested in the Items in my possession?  Are there any robots or other AIs who might be interested?”  This has far-reaching implications not only for the quality of in-game AI, but also for our ability to expand and make the in-game economy more rich and realistic.  Along with in-game merchants who buy Items from Players, we can now have AI-driven characters buy and sell from auction, creating another sales channel from which Payers can benefit.  Sweet.

A note re Mongo and JSON. If your company models its business objects in JSON, Mongo or another highly-performant JSON database makes great sense. It’s far more straightforward than shoehorning JSON into a relational model that was designed for an earlier world, and belongs there.

SmartMonsters now is almost-but-not-quite entirely post-SQL. We’re using “polyglot persistence”, as the hip term has it: the principals are MongoDB, Neo4J, DynamoDB, with our legacy third-party forum software still trapped on PostgreSQL. Very much looking forward to a world where AWS offers a managed MongoDB service which we don’t have to provision and monitor for ourselves.

[triadcitydevelopers-blog]

NPC movement with Neo4j

TriadCity’s sophisticated “subsumption architecture” for NPC behaviors depends on accurate, comprehensive knowledge of game world geography.  Unlike traditional MUDs where NPC movement is statically confined to home zones and is largely random, TriadCity is alive with highly individualized NPCs capable of purposeful navigation throughout the City. For years the code enabling this directed movement has been a simple homegrown weighted graph mapping all possible paths from every point A to every other point B.  Weights were based primarily on movement costs by alignment.  Separate graphs were computed for Evil, Good and Neutral paths, plus specialized graphs for Cops and for residents of the Capitoline neighborhood - two categories of NPCs with restricted movement possibilities.  The graphs were computed at server boot, following instantiation of all Rooms and the Exits linking them.  They were static: unchanging after initial computation, essentially freezing NPC knowledge of world geography at the state of its existence at boot.  And they were monolithic: an NPC could look up a path from the Neutral graph, or the Cop graph, but not a hybrid NeutralCop graph.  For a long time this was “good enough for now”.  While inflexible, it enabled accurate if not always subtle NPC navigation from any arbitrary origin to any chosen destination.  NPCs simply looked up their path and, following Dijkstra, off they went. TriadCity eventually outgrew this simple design.  We want to be able to accurately model arbitrary restrictions on NPC paths, for example, excluding NPCs from certain streets based on Role, or gender, or other classification.  It's important for NPCs to react to more than one category of restriction.  And we want their movement behaviors to be as “human” as possible, so, not necessarily always taking the shortest possible path, if the shortcut for instance leads through someone’s private garden, or in one pub door and out another.  Usually real people would go around the garden, or stay on the sidewalk outside the pub.  We grew especially frustrated with our simple system's inability to track dynamic changes to the game world at runtime.  It would have required a major project to extend our down & dirty proprietary code to handle these features. Instead, we’ve chosen the excellent NoSQL graph database Neo4j as our solution.  While the approach is essentially the same - a weighted graph based on Dijkstra - Neo4j’s comprehensive query-ability allows us enormous flexibility at runtime.  It easily enables the kinds of ambitions described above, with impressively little code. We run Neo4j in embedded mode.  Easy-peasy, since our server’s written in Java.  The database is populated during server boot after Rooms and Exits are loaded.  Nodes are Rooms, Relationships are built from outbound Exits leading to destination Rooms.  The algorithm’s straightforward.  Iterate the Rooms, define a Node for each; iterate a second time, catalog each Room's outbound Exits, look up the destination Room each Exit leads to, find the Node representing that destination, and define a Relationship between the origin and destination Nodes.  We only need one RelationshipType: LEADS_TO.  As each Relationship is defined we flag it with boolean properties representing the restrictions we want to impose: isNoCops, isNoBeasts, isNoHumans, isNoDeathSuckers, isPerformerOnly, isCapitoline, hasDoor, and so on; these properties belong to Exits and destination Rooms, so we simply look for them and set the flags appropriately.  At runtime, NPC path lookups are via a PathFinder built by passing GraphAlgoFactory’s static dijkstra() method a custom CostEvaluator which looks for the boolean property flags defined on Relationships and totals costs accordingly.  For example if the calling NPC has the Cop Role, and a Relationship is flagged isNoCops, the CostEvaluator will assign a prohibitive cost to that Relationship - we arbitrarily use 100,000 - effectively removing it from consideration.  When PathFinder searches for the least-cost path it’ll choose one which bypasses that expensive Relationship.  Managing the scenario where we want NPCs to go around a pub although the shortest path leads through it is straightforward: we simply assign a cost of 100 to all Relationships flagged hasDoor, so that generally NPCs will prefer not to move through doors unless they’re the only paths available.  Nice. Implementing Neo4j required just a single class of about 300 lines, and took about half a working day including time spent tuning the costs. Runtime performance is excellent.  The Neo4j solution takes longer to bootstrap - about 5 seconds for 18,000 Rooms on my MacBook Pro, compared to just a few milliseconds for our deprecated home baked version.  But, its runtime lookup performance is superior.  We judge overall AI processing load by tracking average completion times of our one-per-second Behaviors pulse which triggers Behaviors throughout the game world.  Average Behavior computation on my laptop was steady in the range of 120 to 150 milliseconds with the old grapher; with Neo4j it’s been consistently around 80, an efficiency gain of 50% or better.  Memory use looks about the same. So far, runtime movement appears to be perfect.  Everybody goes where they’re supposed to, and they now do it with the subtle enhancements highlighted above.  Importantly for us, it’s now very easy to tune movement by simply adding new property flags to Relationships and looking for them in our custom CostEvaluator.  And, we can easily enhance the system to adapt to runtime changes in the game world itself, for example when builders add new Rooms or 4d mazes rearrange themselves.  This now sits high on the priority list. I’m impressed with how easy it’s been to include Neo4j in our project.  The API is intuitive and very nicely documented.  I was able to take and tweak a Dijkstra example from the Neo4j web site with very little effort.  Very pleased! Along with Neo4j, we’re currently migrating away from SQL to MongoDB and Hadoop for game object persistence and analytics.  Watch this space!

[triadcitydevelopers-blog]

All AI in TriadCity is Event-Driven. Actually, Pretty Much Everything in TriadCity is Event-Driven.

All NPC behaviors in TriadCity are event-driven.  Not just NPC AI, but all change everywhere in the virtual world, from the motion of subway trains to room descriptions morphing at night, is event-driven.  Here's a quick sketch of some TC event basics. In TriadCity every action is encapsulated in an Event object.  This is straightforward in OO Land.  Take for example player-generated actions.  Player Commands are expressed in the server code as Strategy Pattern objects encapsulating the necessary algorithm.  Each Command will generate one or more Events as its outcome(s).  For example, the Steal command generates a ThiefEvent, which it parameterizes differently depending on success or failure.  Commands instantiate the appropriate Event type at the appropriate moment within their algorithms, handing off the new Event instance to the current Room, which propagates it wherever it needs to go.  Read on. Here's the basic structure:

public Interface Event {         public long getID();         public long getEventType();         public long getVisibility();         public String getSourceID();         public String getTargetID();         public String getRoomID();         public String getMessageForSource();         public String getMessageForTarget();         public String getMessageForRoom();         .... }

The Steal command will instantiate an Event type called ThiefEvent, populating it with the information shown above and a ton more.  The eventType will vary depending whether the Steal succeeds or fails; the assigned visibility will be computed depending on the Thief's Skill level and multiple variables.  The messageForSource will be: "You steal the silver coins from the drunken Texan", or "You fail to steal the silver coins from the well-dressed man, and are detected."  Appropriate messages are computed for the target and for bystanders in the Room.  When complete, the ThiefEvent is passed to the Room, which in turn passes it to everybody and everything currently present. What happens next? Up to world authors. One form of NPC behavior is triggered when Events are received.  The Behavior instance tests the Event against its triggering conditions.  Am I supposed to fire when the Event is a ThiefEvent and its getEventType() == STEAL_FAILS_EVENT_TYPE and the NPC I'm assigned to is the Event.getTarget()?  Or in English, did someone just try to steal from my NPC and fail?  If the world author has assigned the TriggeredAttackBehavior to an NPC and given it those trigger conditions, then the Thief will be attacked when those conditions are met.  This is a form of rule-based AI, expressed in OO patterns. Who'll see what happened?  Depends on their SeeSkill and other attributes.  If observers are skilled enough, they may be able to watch Thieves stealing from victims.   The victim won't see it happen, but observers with high enough SeeSkill might.  One of many many forms of character subjectivity in TriadCity. OO allows TriggeredBehaviors to be niftily flexible.  Behaviors can be triggered if they receive any MovementEvent, or only if the MovementEvent.getEventType() == BOW_EVENT_TYPE.  So: any movement in your Room and you'll jump to your feet on guard.  But, you'll only Bow if someone Bows to you first. All Behaviors are Event-triggered, even ones which appear random, for instance pigeons moving around the Gray Plaza.  Although their movement Behavior is indeed semi-random, it's triggered by a worldwide pulse called the DoBehaviorsEvent, which is propagated everywhere in the game world once per second by an Executor running a background Thread.  Every Behavior tests that DoBehaviorsEvent: do I ignore it, or randomly do something, or do something not randomly?  TimeEvents trigger actions such as closing shops and going home, and so on. Events are integral to Player subjectivity.  One form this takes is that Player objects include a Consciousness Strategy object via composition.  That Consciousness object acts as a filter on the Events passed through it.  It has the ability to modify or ignore the Event.getMessageForXYZ() methods it encounters, or generate entirely new ones.  This is one of the ways we can make you see things which maybe aren't even "there". Events in TriadCity are like the chemical "messages" flying around your brain, telling you when to breathe and fire your heart muscle and decide to go online to play games.

[triadcitydevelopers-blog]

Lotso Mazes

I suppose that mazes are a staple of the MUD tradition.  Starting with Adventure, you're underground and you're lost.  Throw in some orcs and you're in Moria.  Whatever. We follow the tradition with lotso mazes, but, we try to make them interesting.  This post'll be about the technology rather than the content, but, we really do try to make the content interesting too. TriadCity Maze types are implemented via the Strategy OO pattern.  There's that word "Strategy" again.  We do a lot of that.  A Java Interface called Maze defines the contract; multiple concrete implementations can be swapped out at runtime.  Among the implications: world authors not only have a ton of maze algorithms at their disposal, but we can actually swap out algorithms at runtime whenever that seems the thing to do. TwoDMaze is a simple x/y grid of Rooms, always in a rectangular pattern.  World authors can specify how many Rooms wide versus tall, and the Builder tools will prompt them if they provide the wrong number of Rooms.  Thus a TwoDMaze defined as x=7 y=5 has gotta have 35 Rooms assigned, no more, no less.  TwoDMaze puts the Rooms in consistent order across the grid, that is, Room 1 will always be the upper left corner, and the Rooms will be assigned in left-to-right order at every server boot.  Exits between Rooms will be assigned dynamically according to what maze-drawing algorithm is chosen by the world author.  You guessed it, these algorithms are again Strategy objects.  We've got Kruksal, Prim, Depth-First, and a pile of others.  Exits will be computed and distributed around the maze at server boot. Add a z dimension and it's a ThreeDMaze.  Have the Exits dynamically reassigned at random or semi-random during server uptime and it's a FourDMaze - think Harry and Cedric racing for the cup. We can vary all of these by not assigning the Rooms in consistent order.  Just shuffle the Room[] before laying out the grid.  Now there'll always be a Room 1, but it won't always be in the upper left corner.  It could be anywhere, meaning that special fountain or other object of interest will have to be searched for anew after every server boot.  Or shuffle them every hour, or shuffle the grid and the Exits and really confuse people. But wait, there's more.  We don't have to always assign ordinary FreeExits - the Exits that allow movement between Rooms without impediment.  They can be RandomDestinationTeleportationExits or any other Exit type we like, in whatever proportion we like.  Yes, there's one extremely notorious maze full of nasty critters with pointy sharp teeth offering only a single teleporter to get out - no way you're going back the way you came.  Bring a large party with supplies.  Find that teleporter before you run out of grenades. More still.  Authors can assign Behaviors to the Rooms or the Exits, making things even more interesting.  TelGar's writing a big slag heap you have to climb to reach something valuable.  The slag heap kicks up tonso dust so there's no telling exactly where you are, and because the ground is loose, you're constantly being forced downward as the earth slides out from under you.  It's a compelling adventure, enabled by combining a dynamically-changing Maze type with a SlideRoomBehavior which forces you to move in a certain direction, like a slide in a playground.  You can eventually get to the top, but it's a struggle. These Strategy Pattern objects allow the server code to remain tidy and easy to maintain, while putting a lot of power into the hands of world authors.  Authors can assign whatever crazy algorithm best suits their thematic purpose.  Just how lost do you want the punters to get?  You've got lots of options.  Somebody invents a new maze-generation algorithm?  Great, we'll add it.  Easy-peasy. Death to mazes like Moria, --Mark

[triadcitydevelopers-blog]

We Use the "Strategy" OO Design Pattern for Player Subjectivity

Uniquely to any "game" we're familiar with, TriadCity imposes elaborate subjectivities on its players. This means that if you and I walk our characters into the same Room at the same time, we might see it described differently depending on our characters' attributes, skills, moral alignment, history, and other variables.  The type and degree of subjectivity is largely controlled by the world author who wrote the Room.  Most authors tread lightly, but there's no reason they can't make things wildly different if that makes sense for their context. It also means that one of our characters could be Schizophrenic.  We can impose any manner of "unreal" experiences on characters, from highly distorted Room descriptions to conversations with other characters who don't actually exist. The code which enables these two forms of subjectivity is pretty simple.  Both forms rely on the Strategy OO pattern, applied in different places.  I'll briefly sketch them both. Rooms, Items, Exits, Characters all share common attributes inherited from their parent class, WorldObject.  These include Descriptions, Smells, Sounds, Tastes, and Touches.  I'm capitalizing the nouns because these are Java Interfaces which WorldObject possesses by composition.  A code snip for illustration:

public abstract class WorldObject extends Object() {           protected Descriptions descriptions;           protected Smells smells;           protected Sounds sounds;           protected Tastes tastes;           protected Touches touches;           public final String getDescription(WorldObject observer) {                     return this.descriptions.getDescription(observer);           }           public final String getSmell(WorldObject observer) {                     return this.smells.getSmell(observer);           }            public final String getSound(WorldObject observer) {                     return this.sounds.getSound(observer);           }            public final String getTaste(WorldObject observer) {                     return this.tastes.getTaste(observer);           }            public final String getTouch(WorldObject observer) {                     return this.touches.getTouch(observer);           } }

Descriptions, Smells, Sounds, Tastes and Touches are Strategy Pattern Interfaces defining the simple contract which will be implemented by a rich hierarchy of concrete classes.  At runtime, the correct implementing class is assigned to each WorldObject according to the directions given to that WorldObject by the author who wrote it. For example, a world author may write a Room and choose to have its descriptions vary by hour of day.  Using our authoring tools, she assigns it the TimeBasedDescriptions type, and writes a description for dawn, dusk, day, and night.  At server boot, that Room will be assigned the type of Descriptions she specified, and populated with her writing.  The TimeBasedDescriptions class has the responsibility of figuring out what time it is whenever its getDescription() method is called, and returning the right one. That's not subjective, though.  Although the descriptions vary by time of day, the same description will be shown to every character who enters the Room.  If she wants to, our world author can be more adventurous, assigning concrete Description types from our library.  She could choose AlignmentAndTimeBasedDescriptions which will show descriptions which vary by both time of day and character moral alignment; or Descriptions which vary by Gender, or health condition, or attribute status.  Each concrete implementing class knows how to calculate the description which is appropriate for the observer.  As you can see, the code for WorldObject remains extremely simple. A second and often more radical flavor of subjectivity is implemented by a Strategy Interface called Consciousness.  Each character has a composed Consciousness object which acts as a filter, transforming messages received via game Events, or not, according to its logic.  The TriadCharacter class includes these snips:

public abstract class TriadCharacter extends WorldObject() {           protected Consciousness consciousness;           public boolean proccessEvent(MovementEvent evt) {                     return this.consciousness.processEvent(evt);           }           public boolean proccessEvent(SenseEvent evt) {                     return this.consciousness.processEvent(evt);           }            public boolean proccessEvent(SocialEvent evt) {                     return this.consciousness.processEvent(evt);           } }

Concrete Consciousness implementations include SleepingConsciousness, FightingConsciousness, SchizophrenicConsciousness, IncapacitatedConsciousness, and many others.  Their job is to analyze incoming Events and determine whether to pass along the messages associated with those Events unchanged, or changed.  A simple change might be to simply squelch an Event if the character is asleep.  A radical one might be to change a ChatEvent or TellEvent, or even concoct entirely new ones, if the character is experiencing SchizophrenicConsciousness.  In these cases, the Consciousness type is assigned by the server at runtime, not by world authors, and it'll be swapped out for a different one as circumstances change.  So these transformations are extremely dynamic. Using the Strategy pattern via composition allows the class hierarchy to remain reasonably flat and really very simple.  It would be possible for example to create a massive class tree resulting in things like TriadCharacterWithDescriptionsThatVaryByAlignmentAndTimeWithSchizophrenicConsciousness.  But for obvious reasons that would be a nightmare to maintain.  Composition keeps the WorldObject tree simple; Strategy objects chosen at runtime provide the rich library of behaviors.

[triadcitydevelopers-blog]

"Subsumption" Architecture for NPC AI

We use a pile of different AI strategies to drive NPC behaviors in TriadCity.  Most of these are quite simple, AI being in my opinion far more artificial than intelligent.  One of our most successful strategies to date is based on Rodney Brooks' "subsumption architecture" which we've borrowed from robotics.  Here's a short description of how we use it in TriadCity. Briefly, subsumption architecture rejects the approach of modeling intelligence via symbolic representation, choosing instead to mimic lifelike behaviors by building high-level behaviors from layered libraries of low-level components.  Lowest-level components might be as simple as "I hit something"; the next layer up might include several avoidance strategies such as "back up and try a slightly random vector", or "move left several inches and try again"; a higher level still might abstract from particulars to "explore the world".  The idea is that behaviors become more abstracted from details the higher they are in the hierarchy, which in the end looks something like a pyramid, with "behave like a human" at the top. In TriadCity we implement subsumption by composing higher-level abstract behaviors from an increasingly vast library of detailed lower-level ones.  Low-level examples are "open the door", "look around the room", "pick up an object".  You'll note that these correspond neatly to TriadCity's library of player-typable commands.  An intermediately abstract behavior might be "move from current location to the Virtual Vegas Casino", which involves querying a directed graph, moving along the retrieved path, opening any doors encountered, and so on.  A higher-level behavior might be "play slot machines in the Virtual Vegas Casino", which would require successfully moving to the correct location in the game world and executing the Playslot command.  Higher still might be "gamble in the Virtual Vegas Casino", which would allow a randomized selection between playing slots or roulette or etc.  World authors don't need to interact with the subsumed low-level concrete behaviors.  They just assign the abstract high-level ones and the architecture manages the details. A common example in TC is the assignment of weighted "behavior groups" based on time of day.  Let's say you assign your NPC two behavior groups, one for the dawn, day, and dusk hours, and a second for night time.  Your daytime group may include sending the NPC to work, or having it hunt slave killers in Zaroff Park, or eat lunch at a favorite restaurant, or watch the chariot races in the Circus Maximus.  You'd assign each of these possibilities a weight determining its likelihood of being chosen, plus a weight determining its likelihood of being swapped out for a different one.  By night you might have your NPC eat dinner somewhere, go see a movie, go shopping, go back to hunting its favorite slave killers, or go home to sleep.  The result is really quite rich.  If you follow this fellow around, he performs his varied activities with a lot of human-like unpredictability.  He won't simply circle the same static course over and over, and so for example if there's some NPC you'd really like to stalk, you'll have to go find him first because he could be all over the place doing things that are appropriate to his character.  This is very easy for world authors to work with, allowing rich individualization of non-player characters without a ton of effort.  It puts a pile of AI sophistication into play without forcing authors to interact with it. These "subsumption" behaviors contribute a good deal of verisimilitude to the game world.  In TC you don't get a lot of NPCs standing around waiting to be killed.  We even send our judges home from court at night.  There's continual motion and variation: you can stand on a popular street corner people-watching NPCs on their way to and from jobs and hobbies and murders and freeing slaves.  This is one of the aspects of the TriadCity project I'm most proud of.

[triadcitydevelopers-blog]

Scalable Command Routing Via the Strategy and HashedAdaptor OO Design Patterns

TriadCity's command vocabulary is far larger than the 400 or so commands typed by players.  Every Admin and Builder action is implemented as a command, so there are tens of thousands altogether. In C, you'd probably route user input through a simple switch() statement.  CircleMUD does this.  The parser and command router are tightly coupled inside one master controlling statement which switch()es on the user's first word of input.  Logic can be parceled out to functions, or handled right there inside the switch() statement itself.  This is fine for a couple of hundred commands, but growing it to tens of thousands would be a performance and maintenance disaster. We ensure infinite command routing scalability for TriadCity by combining the Strategy and Hashed Adapter OO patterns. Strategy encapsulates an algorithm as an object, allowing algorithms to be selected and substituted at runtime.  In Java you'll typically implement Strategy via an Interface defining the algorithm's contract.  Classes implementing that Interface define the available algorithms.  In TriadCity we have a Command Interface defining our Strategy contract:

public Interface Command {           public abstract boolean doCommand(<multile-args-go-here>); }

And we have many thousands of classes implementing that Interface, for example, Chat, which implements the doCommand() method to iterate all NPCs and logged-in Players, sending the arguments to the chat channel. The Hashed Adapter pattern achieves scalable routing by stashing these concrete Command instances in a HashMap keyed by command name.  Each concrete Command is a Singleton; we populate the map with command names as keys, instantiated Command Singletons as values.  The resulting routing algorithm is super-simple:

Command command = this.commands.get(commandName); command.doCommand(<multiple-args-passed-here>);

There's other logic wrapped around these lines, for example authorization checking for security. But that's the idea. By using Hashed Adapter this way, routing scales infinitely without performance degradation.  Server processing is very efficient, and for developers there's no nightmare switch() statement of ten million lines to maintain.  By using Strategy, it's very easy to do the file housekeeping necessary to keep tens of thousands of Command implementations easy to navigate.