Wednesday, September 24, 2014

Remote code evaluation

Sending code over the wire isn't really that scary - it happens a lot more that is obvious at first glance, just gussied up under a different name like "rule evaluation" or "targeting engine" or "modding interface" or "extension scripting" or something.

I've heard of multiple projects that try to address a requirement for user-specified behavior in some way, and I actually worked directly on one of them for several years.  Usually it starts out really innocuous and simple, like allowing a service consumer to pass in some kind of expression like:

given condition A, perform action X

That's fine, and doesn't really deserve any kind of special runtime evaluation engine, and can easily be represented by some simple XML or JSON or YAML format...  but then the feature creep starts.  Somebody wants boolean logic, or wants an expression to perform two actions instead of one, or nested expressions, or custom variables.  Pretty soon your XML format starts looking like this:

<rule>
  <name>
uk_senior_discount</name>
  <condition>
    <and>
      <equals>
        <extract_value>$user.country</extract_value>
        <value>UK</value>
      </equals>
      <greater_than>
        <extract_value>$user.age</extract_value>
        <value>64</value>
      </greater_than>
    </and>
  </condition>
  <action>
    <show-ad>
      <template>uk_senior_discount</template>
    </show-ad>
  </action>
</rule>


One upon a time I had to do work in a swampy jungle of design patterns spanning thousands of lines of java code that implemented the runtime engine to evaluate something disturbingly similar to the above.

At this point, you could rearrange your format to not require the closing tags, swap out the angles for regular parens, and get this:

(rule
  (name "uk_senior_discount")
  (condition
    (and (= (user :country) "UK")
         (> (user :age) 64)))
  (action
    (show-ad
      (template "uk_senior_discount"))))


Now run it through a Lisp evaluator with the proper functions and macros defined, and it will do all the heavy lifting for you.  Forget about writing all of those thousands of lines of code to parse, represent, and evaluate user-specified custom behaviors.  No need for a veritable explosion of OO classes to cover every possible element, just implement a "rule" macro, and a few functions: "name", "condition", "user", "action", "show-ad", and "template".  The rest are already implemented for you.

It may sound scary to evaluate arbitrary code from an untrusted source, but that's solved by sandboxing.  In Clojure, you could do this with a two-layer solution:

1.  Use Clojail to absolutely prevent any side effects from happening on the host system (https://github.com/flatland/clojail)
2.  Run the code in a custom namespace that *only* exposes functions and macros that you explicitly whitelist.  You can hide everything else, including all of the stuff in clojure.core 

Honestly, just one of the above would probably be sufficient, but I would implement both layers just to be sure.

"What does this buy me over giving my consumers the ability to pass in Javascript or Lua or something?"

I'm glad you asked.  The lisp syntax is a tree structure, really not all that different from XML or JSON, as demonstrated above, so it is easy to parse and traverse if you want to do anything with it other than just evaluate it.  For example, you might want to present a slick drag-and-drop interface for people to build these rules.  The parsed tree structure can be used as the model layer of the UI.  Good luck doing that with arbitrary Javascript or Lua.

"What if my consumers don't want to learn yet another format?"

Replace the parens with square brackets, quote all of the functions, and tell them it's JSON ;)

Ok...  so maybe it got kind of ranty, but I hope my point comes across the right way.

Friday, February 7, 2014

Ode to Review Board

Of all the things I've introduced
of all ideas I've brought
One stands out as my favorite
ne'er to be forgot.

It is definitely not jQuery
though at first I was inquisitive
jQuery was adopted because of
another developer's initiative

Hudson was a "great success"
but hasn't been quite the same
since they renamed it to Jenkins
(I know, it's just a name)

It isn't the eccentric Clojure
though I love it like my own
Hardly anybody even considered it
(which to this day I still bemoan)

'Tis Review Board!
Our former review darling
of code and collaboration
She was a beautiful, swift starling.

Others tried to court her.
Oh how they tried to woo,
but she played hard to get!
Their advances wouldn't do.

They thought that she refused
the bug number and hg bundle,
but it wasn't really her!
It was mercurial-reviewboard that fumbled

So with sword drawn and helmet donned
I crossed the threshold of that lair
of Python code and REST services
and wrote two patches, what a dare!

Thus she was ours and part of us
she freely served us well
For code reviews and comments back and forth
'til the changes came, pell-mell.

The enterprise must roll on!
Its grinding cogs must churn.
We must migrate to Atlassian!
Like a witch at the stake, Review Board would burn.

'Tis for the best, they reassured,
All integrated, it's a suite!
Nevermind that their products are all acquisitions,
cobbled together like sausage meat.

Nevermind their inconsistent editors
Which all require different markups
Nevermind that each product takes
a different query language for lookups.

So now we work with Crucible
and endure his bitter glare,
his unfriendly user interface,
and slow loads that make us stare.

Gone is Review Board, and with her
the nice handling of multi-file diffs
and clear commenting on multiple revisions
without any ands, buts, or ifs.

But she escaped!  She got away!
She was not broken asunder
She left for greener pastures
But now I'm left to wonder...

Review Board, Review Board
oh beautiful Review Board
to where hast thou gone
oh lovely Review Board?

Is there some other Java team
with an enterprise to serve
giving you the attention and love
that you so need and deserve?

Or some upstart team using Python
(the version that's plain vanilla)
convinced that they are CRUSHING
their eight-hundred-pound gorilla?

I hope you're well, ReviewBoard
I miss you, I must say
You really were delightful
Perhaps we'll meet again some day.

Tuesday, May 28, 2013

Running NRepl in a Spring application - Unable to resolve symbol: original-ns

Recently I tried modifying a large Java project with Spring dependency injection such that it would start a repl server with the default namespace pre-populated with all of the Spring beans:
@Configuration
public class NReplConfiguration implements ApplicationContextAware {
  private static final Logger LOG = LoggerFactory.getLogger(NReplConfiguration.class);
  private static final String NREPL_INIT =
    "(use '[clojure.tools.nrepl.server :only (start-server)]) (start-server :port 7888)";

  @Override
  public void setApplicationContext(ApplicationContext context) {
    Class.forName("clojure.lang.RT");
    Compiler.load(new StringReader(NREPL_INIT));
    for (String name : context.getBeanDefinitionNames()) {
      RT.var("user", StringUtils.uncapitalize(name), context.getBean(name));
    }
  }
}
Then trying to use leiningen to connect to the repl server, I got this error:
$ lein repl :connect 7888
REPL-y 0.1.10
Clojure 1.5.0
CompilerException java.lang.RuntimeException: Unable to resolve symbol: original-ns in this context, compiling:(null:1:12355) 
reply.eval-modes.nrepl=> 
Adding this line to NReplConfiguration right after initializing the repl server made the error go away:
RT.var("complete.core", "original-ns", Symbol.create("user"));

Monday, April 22, 2013

Pyramids

"Most people who graduate with CS degrees don’t understand the significance of Lisp. Lisp is the most important idea in computer science." -Alan Kay

"Most software today is very much like an Egyptian pyramid with millions of bricks piled on top of each other, with no structural integrity, but just done by brute force and thousands of slaves." - Alan Kay

...and that's the guy that invented SmallTalk!

Everybody is so concerned about carving giant stone blocks, and mixing sand with muddy clay to make mortar.  While that's going on, a few of us have discovered that there's a way to automate the creation of ceramic bricks.  When one of us comes back with excitement to the mud pits and passionately proclaims that there's a fundamentally better way to do things, the response is merely a passing glance of scorn at the machine, and then a lot of yelling.

"WHAT ARE YOU DOING!?  You can't make pyramids with that thing! We don't have time for this, and nobody understands what you're doing anyway!  Look at all of those turn knobbies and buttons and stuff, how is anybody expected to actually use this thing?"

"But but...  this is just a prototype!  It's just what I was able to put together in a little bit of time to demonstrate.  If we could get everybody to understand this, then we could build a really nice brick press machine, along with a brick-laying crane. Then when we're not spending all of our time making and placing bricks, we can think about better materials, and fundamentally new ways to architect our buildings!  We can smelt ore, make steel, and once we've figured that out I hear there's this concept called an I-beam that..."

"CRANES!?  Sure, maybe you can do that to lift your puny ceramic bricks, but you can't make a machine that will lift 10 ton blocks!  It'll topple over!  We have a team that uses the time-proven tradition of pushing our blocks on rolling logs up massive earthen ramps.  THAT'S the way to construct great buildings.  We've seen what happens when you try other ways - the folks over in the PHP kingdom make all of their stuff out of lumber.  Sure, it's quick to harvest, cut, and build, but you know what happens when their buildings catch fire."

"No!  You're missing the point!  Stop thinking in terms of giant stone blocks, or even lumber, and look at what we can do with steel I-beams.  Once we have the infrastructure in place to manufacture them, we can then create buildings ten times as tall as our pyramids, in 10% of the materials, in a fraction of the time, with significantly less slaves.

"BWUAHAHAHA!  You expect us to believe that?  Preposterous!  Look, we have work to do, if we don't get back our competition will crush us.  Why don't you use your silly brick machine to make a nice kennel for the royalty's hunting hounds?"

Monday, August 27, 2012

Status Update

It's been a while since the last post, and there's been plenty of improvement.  Here is a brief list of things I've worked on in the last couple of months:
  • The "scent maps" aka "dijkstra maps" discussed in the last blog post.
  • Predator/prey relationships based on each entity's dijkstra map.  Predators are attracted to prey, prey are repelled from predators
  • Reproduction.  Entities of the same species with opposite genders can reproduce, given a sufficient attraction factor.  After gestation, a new entity is born.  This isn't really obvious because when I prototyped it, the gestation time was instant, and pairs that can mate were almost always attracted to each other over anything else - you can guess how that turned out.  After creating an attraction factor and a gestation time depending on the species, it has made the reproduction system rarely noticeable.  Unfortunately I don't have any infant sprites yet, so offspring look fully mature for now.
  • Simple jobs - characters can now build walls (left click for now), and remove parts of the terrain (right click for now).  The characters are attracted to jobs based on the jobs' dijkstra maps.
  • Underground view - You can "slice" the terrain view using the middle click on a location, also spinning the scroll wheel up and down adjusts the slice level up and down.
  • Terrain overhaul - There are new terrain sprites with a 2:3 iso ratio, making most of the back slopes visible.  Along with that, each type of terrain now has 16 different sprites instead of 5, making much more cohesive terrain contours.
  • Minimap - This renders pixels representing the terrain, and works with the "slice" feature mentioned above.  It doesn't respond to clicks yet, but I would like to make it center the terrain view on the given location when clicked.

Tuesday, July 10, 2012

Thoughts about game entity AI

I've been thinking a lot about how to implement the behavior of entities (people and creatures).  Many mainstream strategy games involve the player giving specific orders to everybody under their control, and the entities subsequently use an A* path-finding algorithm to navigate toward the area indicated until they are in range to do their assigned task.

One important aspect of A* is that it requires a specific destination.  That's fine for giving specific orders to entities, but I want to avoid making a micro-management game.  I'd rather have general commands like "I need people to hunt over here", "cut down lumber here", "build a wall around this area", "plough these plots and then plant cabbages"...  Then each entities decides what to do, given several potential jobs to do, hazards to avoid, and their own set of skills, likes, dislikes, fears, etc. 

From what I understand of AI, this kind of behavior boils down to the following:
  1. Determine what options there are to choose from.
  2. Calculate a "score" for each option.
  3. Choose the option with the best score.
If I were to use A* path-finding, the entities would have to first choose a destination.  This could be done by looking up choices in close proximity, but that would exhibit what I call the "great wall" problem - An entity may find something interesting to do within a distance of just a few steps, and decide that it is the most compelling goal.  However, if there is a large barrier in between (a wall, a deep river, etc), it will potentially take the entity much longer to get there and finish the task than something else that is a further distance away.

One possible solution would be to divide the map into "sectors" of some sort, so that opposite sides of a wall are in different sectors, but then there's the problem of splitting, merging, and otherwise updating the sector table as the entities modify the environment (mine through the mountains, build walls, et. al.)

The other possible solution is to have the decide-what-to-do function do a traversal of the area around the entity to find things of interest (probably using Dijkstra's algorithm), but that defeats the purpose of A*, since its whole point is to do an optimized traversal toward a specific destination (A* is really just a modification of Dijkstra's).

So at that point in my thinking, A* was out, and it seemed like Dijkstra's might work.  Dijkstra's algorithm does an even breadth-first traversal.  It could be implemented to take a number representing how much depth to explore, then collect information about things found within the explored space.  The entity could then take the list of potential things to do, along with the path to each thing.  It would make a decision based on some math to score each option.  If the chosen destination is adjacent to the entity's current location, do the task (attack, build, mine, sow, whatever), otherwise move along the calculated path.

Let's say there are multiple things about an entity's environment that will influence its behavior.  For example, assume that an entity can have a "hunter" skill.  Further assume that there exist a hostile creature (say a dragon) that can be successfully hunted by a group, but is likely to defeat a lone hunter.  How does a hunter know whether it's a good idea to pursue the dragon?  There's a risk/reward balance to be struck here - certainly it would be a good thing to fill the storehouse with cured dragon steaks for the winter, but it would be a bad thing to be roasted by the dragon.

Using the traversal algorithm, the decision algorithm invoked for a hunter could determine that there are multiple other hunters in the area.  It could do some math to determine how likely the hunt is to succeed, and could make a decision to advance or retreat (maybe throwing in the specific hunter's fear of dragons and taste for dragon steaks - fight or flight syndrome).  The advance or retreat would further influence the other hunters' behavior.

Ok, so far it's feasible.  The advance just means taking a step toward the dragon, as previously determined by the path-finding algorithm.

But what about the retreat?  The entity has a clear indication of how to advance, but not necessarily how to retreat.  It would be nice to have an obvious way to determine how to get away.

Somewhere in this thought process, two things came to mind, both related to emergent behavior.  Years ago I did an implementation of Boids in Python.  Also, at some point in the past I read a blog post about how the pac-man ghosts' behavior was implemented (sorry, no link, I don't remember where it was, but it's been discussed quite a bit, google around for more info).

For more info about Boids, read the wiki article, but basically it is an algorithm that simulates a flock of birds by emergent behavior - Each bird's movement is influenced by three factors:  try to maintain general proximity to the center of the flock, try to match the average velocity of nearby birds, and try to avoid immediate proximity of other birds (avoid collisions).  Giving each entity a few simple rules results in some really interesting overall behavior of the flock.

The discussion about implementing ghost behavior in pac-man centered around the concept of pac-man leaving behind a "scent" that dissipates over time.  In persuit mode, the ghosts would simply move to whatever adjacent location had the highest "scent", or make a random decision at intersections if there was no scent to follow.  In retreat mode, they would do the opposite.

So this lead me to think, what if every entity in the game has a "scent".  I think I would do it different than the pac-man example - the scent would be calculated by traversing a certain distance away from each entity, periodically updated to account for changes in entity locations and how the environment can be traversed.  Then, each entity can make immediate decisions based upon calculations made to the scents around them.  In the hunter example, each hunter would observe the scents for each location adjacent to their own.  Assume that a hunter finds that the dragon scent is strongest in front of him.  If there is insufficient scent from other hunters, the math that scores the location will determine that it is not a compelling choice.  Further, the most compelling adjacent location will be the one that leads further away from the dragon.

I think that the "scent" concept will work for a variety of things.  People could enjoy being around each other, but avoid crowds.  Somebody with skills as a miner and a blacksmith might have to decide between working on a project at the anvil or hollowing out a new found coal vein.  I imagine that there could be a situation in which one entity really doesn't like bunnies, but bunnies really like him, so in the absence of hunger or other such pressing needs, the bunnies end up chasing him around.

There is still plenty that needs to be worked out.  The concepts of "likes", "fears", etc., and how those attributes influence the scoring logic will be interesting to work on.

Saturday, June 16, 2012

Terrain Discovery

I implemented terrain discovery based on the people's locations.  Right now it just uses a cheap range calculation around the person's location, so it is possible for them to see things even if they don't have a line-of-sight on it.

As always, find the latest revision at http://bitbucket.org/willismichael/terra-incognita







Here is the function (found in /src/model/update.clj) that determines the visibility from a given location:

(defn- visibility [[x y z]]
  (let [h-range (range -6 7)
        nodes
        (for [dx h-range dy h-range dz [-2 -1 0 1 2]
              :let [x (+ x dx) y (+ y dy) z (+ z dz)]
              :when (< (+ (* dx dx) (* dy dy) (* dz dz)) 36)]
          [x y z])]
    (zipmap nodes (map (partial world-get @wrld) nodes))))

It's quite terse, but don't let that scare you.  The first line takes a location as a parameter, and deconstructs it into x,y,z coordinates.  Next, it creates h-range, where (range -6 7) is just short for [-6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6].  Those are the horizontal coordinates relative to the viewer.  The "for" statement evaluates for every possible combination of relative coordinates that we're interested in, from -6,-6,-2 all the way to 6,6,2.  These are filtered using the distance formula (so that visibility has a radius of 6, rather than being a square)

Finally, all of the coordinates that meet the criteria are used to pull information from the world.

One thing you could play with is the visibility range and radius.  For example, if you want to change horizontal visibility from 6 to 20, change (range -6 7) to (range -20 21), and change 36 to 400 (that's 20 squared).  Or, if you want them to be aware of several layers in the ground beneath them, change dz [-2 -1 0 1 2] to dz (range -20 2)