UVTC's Blog

2012-08-07

On irc last night, casion asked a question about functional programming and how it might be used to model a battle between two characters in a game. amalloy produced this, reproduced here as well:

(defn fight-one-round [[a b :as fighters]]
  (let [ticks (apply min (map :cooldown-remaining fighters))
        damage-dealt (fn [fighter]
                       (if (= ticks (:cooldown-remaining fighter))
                         (:dmg fighter)
                         0))
        tick (fn [fighter]
               (update-in fighter [:cooldown-remaining]
                          (fn [cdr]
                            (if (= cdr ticks)
                              (:cooldown fighter)
                              (- cdr ticks)))))]
    [(tick (update-in a [:health] - (damage-dealt b)))
     (tick (update-in b [:health] - (damage-dealt a)))]))


(defn fight [a b]
  (first
   (drop-while (fn [fighters]
                 (every? pos? (map :health fighters)))
               (iterate fight-one-round
                        (for [fighter [a b]]
                          (assoc fighter :cooldown-remaining
                                 (:cooldown fighter)))))))

;; Example use:
;;
;; (fight {:health 45
;;         :cooldown 86
;;         :dmg 6}
;;        {:health 160
;;         :cooldown 144
;;         :dmg 10})

I thought I’d take a moment here to add a rather verbose explanation of the code. Hope it’s useful to you!

A fighter is represented by a map. Fighters have :health, :cooldown, and :dmg values. :health is “hit points”, :dmg is how much damage that fighter does when they hit, and :cooldown is how long a fighter has to wait after hitting before they can strike again.

In the fight function — where you pass in two fighters: a and b — there’s a for loop that runs through the list of them (which is a list of only two) and generates a new list of two fighters; same as the list we started with, except that each fighter now has a new attribute: :cooldown-remaining. The value of :cooldown-remaining starts out the same as their :cooldown value.

Now that that’s set, iterate makes a lazy list, applying fight-one-round to that list of two now-augmented fighters. What iterate returns is a list that looks like this:

a b,
(fight-one-round a b),
(fight-one-round (fight-one-round a b)),
(fight-one-round (fight-one-round (fight-one-round a b))),
etc...

(which is just “initial states”, “results of round 1”, “results of round 2”, and so on.)

If you glance at the fight-one-round function, you’ll notice that it always returns a list of two fighters, so it works fine to call it on the result it itself produces.

So, back to iterate: it produces that list. Each result is the state of the fighters after they’ve fought a round.

drop-while looks at this list, at each item in turn, and drops values in the list that cause the anonymous function there

(fn [fighters] (every? pos? (map :health fighters)))

to return true. It stops when it can find one where the function doesn’t return true; leaving you the rest of the (as-yet-not-fully-realized) infinite list.

This little anonymous function takes our 2-item list of fighters. It first turns that list of 2 fighters into a list of 2 healths. Then it asks “Is every item in the list positive?” (i.e., “are both fighters still fighting/healthy/ok?”).

So drop-while run through our list of two fighters checking that both have :health > 0. Once one (or both) drops below 0, it returns the rest of the list of states of the fight.

first then hands you the first item of that list and discards the rest (which haven’t even been realized — nor do they need to be). This is the state of the 2 battlebots at the end of the fight.

###

We know that fight-one-round is handed a list of two fighters, and that it computes and returns the new states of these two fighters.

Back up and have a look at fight-one-round. You pass it a list of two fighters and it uses destructuring to name the first fighter a and the second one b (and the list of both of them is named fighters).

It then sets up a few locals (in the let), doing some computing in the process. Once those locals are set up, it returns a 2-element vector — the new states of the two fighters.

The locals that get set up are ticks, damage-dealt, and tick.

ticks is an int. It’s the result of:

  1. taking the list of the 2 fighters
  2. turning that into a list of their :cooldown-remaining values
  3. taking the lesser of those two values

So, ticks is “min cooldown remainings” of both fighters. I’ll get to why it’s named “ticks” in a minute.

damage-dealt is a function. You pass it a fighter, and it checks if that fighter’s :cooldown-remaining is equal to the min between the two of them. If it’s equal (that is, if this is the fighter with smaller :cooldown-remaining right now), then this fighter’s damage-dealt is the usual. Otherwise it’s 0. Again, more on what this means in a moment.

tick is also a function. You pass it a fighter and it returns an updated fighter — it’s :cooldown-remaining value is what gets updated. The formula for updating it is: if it’s :cooldown-remaining is equal to the min-cooldown-remainings, then update it to be the same as this fighter’s :cooldown value. Otherwise, update it to its current :cooldown-remaining minus the min-cooldown-remainings. Why do this? Just one more moment. :)

Now that fight-one-round has these three little items all set (ticks, damage-dealt, & tick), it can return the results of this fighting round:

[(tick (update-in a [:health] - (damage-dealt b)))
 (tick (update-in b [:health] - (damage-dealt a)))]))

The first call to tick returns an updated player a, and the second and updated player b.

###

Here’s what going on:

Each bot knows how long it must wait until it can strike again. ticks figures out which bot has the minimum :cooldown-remaining. That is, which bot gets to strike next. fight-one-round is efficient: it skips intermediate “ticks” (time units, for example, seconds) and just jumps to, “ok, who gets to strike next”.

damage-dealt checks if a bot is able to do damage when it hits. That is to say, every bot hits every time through fight-one-round — except that only one gets to do any damage (so it’s as if only that one got to hit this round).

tick is a verb. It updates the fighter bots to their next state. If a bot just had its turn to hit (that is, if it had the lowest :cooldown-remaining), its :cooldown-remaining gets reset to its max value: :cooldown. The other bot (who didn’t get to hit) just gets its :cooldown-remaining reduced by the amount we fast-forwarded for the current hit to take place.

###

Pretty clever, I think! My initial thought about how to simulate this might’ve been to keep a global “tick counter”. As time passed (looping and incrementing the counter), it would check if it’s a player’s turn to strike yet, if the player was struck, and so on. But amalloy’s method here is very efficient, and — I think — elegant. :)