GameDevBlog

Siren Song? Or How I Spent My Weekend.

So I've heard the siren song of functional programming (or functional-programming-like-stuff via STL,anyway) before, and wasn't too happy with my results.  "Ivory tower academic masturbation!"  I declared, and let it be.

Lately, I've heard "functional programming" at least three times in recent memory.  Once is happenstance;  twice is coincidence;  three times is conspiracy.  Clearly I should look into this stuff.  And - maybe my previous annoyance with it wasn't me.  Maybe I was just using the wrong language.  So the siren song begins again:  you will be so much more productive.  You can write an entire game just by hooking up the right algorithms to the right data structures.  Come....come....

So, of the many functional programming languages out there, I decide to learn Scheme.  I figure, if I'm going to learn this stuff, let's try to find a language that does just about nothing else.  Then, once I've learned it, maybe I can apply the techniques in something more game-friendly like Python.  And Joel mentioned it.  And one of my ex-girlfriends used to take a class from one of its inventors.  I don't even know Lisp, mind you.

About a day and a half into it I discovered that the one I was using (MIT Scheme) had a cute little vector graphics library, so I decided to see if I could write Spacewar.  By 11 last night I hadn't finished, but I did get a little rotating spaceship to orbit a sun with a broken model for gravity. 

So, my thoughts, so far?

It seems that just about every language except C++ lets you define your function objects on the fly, as you're writing the code.  With C++ you have to stop, page up, write your function or functor, then go back to your code and reference it.  Doing this breaks my "flow" and I find it...unpleasant.  Even Java lets you write your functions on the fly, although you usually have to write more object-oriented cruft around your function that the function itself, and that's a nice thing about Scheme.  And yes, map, reduce, for-each, and being forced to think recursively, all very nice.

(That's kind of where it ends, though.  I remember back when I switched from assembly to C the joy of discovering that a function might actaully work, as written, the Very First Time I Tried It.  I didn't have that experience with Scheme.  Yes, I'm writing fewer lines of code but they take longer to write.  And it seemed like most of my time was spent counting parentheses.  If I'd written Spacewar in C++ it would be done by now!)

So...where will I go from here?  I'm thinking Python.

For what it's worth, here's my beginnings-of-spacewar in Scheme - with unit tests.  I'm sure you lisp/scheme guys will be horrified at how I'm butchering your language.

(define pi (acos -1))

(define-structure ship pos vel rot)

(define check!
  (lambda (good?)
    (if good? (display ".")
                (begin
                  (display "Test failed!")(newline)))))

(define epsilon 0.0001)

(define approx-equal?
  (lambda (x y)
    (and (> x (- y epsilon)) (< x (+ y epsilon)))))

(define approx-equal?-test
  (lambda ()
    (begin
      (check! (approx-equal? 2.0 (* 4 0.5)))
      (check! (not (approx-equal? 2.0 4.0)))
      (check! (not (approx-equal? 2.0 (+ 2.0 epsilon))))
      (check! (approx-equal? -1.0 (+ -1.0 (/ epsilon 2.0)))))))
(define test-list (list approx-equal?-test)) 

(define vector-approx-equal?
  (lambda (v1 v2)
    (not (memq #f (map approx-equal? (vector->list v1) (vector->list v2))))))

(define vector-approx-equal?-test
  (lambda ()
    (begin
      (check! (vector-approx-equal? (vector 0.0 1.0 -2.0) (vector 0.0 (* 2.0 0.5) -2.00009)))
      (check! (not (vector-approx-equal? (vector 0.0 1.0) (vector 0.0001 1.0)))))))
(append! test-list (list vector-approx-equal?-test))

(define vector2-xform-rot
  (lambda (xy rot)
    (vector (- (* (vector-ref xy 0) (cos rot))(* (vector-ref xy 1) (sin rot)))
            (+ (* (vector-ref xy 0) (sin rot))(* (vector-ref xy 1) (cos rot))))
  )
)

(define vector2-xform-rot-test
  (lambda ()
    (begin
      (check! (vector-approx-equal? (vector2-xform-rot (vector 0.0 0.0) (/ pi 2)) (vector 0.0 0.0)))
      (check! (vector-approx-equal? (vector2-xform-rot (vector 1.0 0.0) (/ pi 2)) (vector 0.0 1.0)))
      (check! (vector-approx-equal? (vector2-xform-rot (vector 0.0 1.0) (/ pi 2)) (vector -1.0 0.0))))))
(append! test-list (list vector2-xform-rot-test))

(define vector-mul
  (lambda (v scalar)
    (vector-map (lambda (element) (* element scalar)) v)))

(define vector-mul-test
  (lambda ()
    (check! (vector-approx-equal? (vector-mul (vector 0.0 1.0 1.5) 2.0) (vector 0.0 2.0 3.0)))))
(append! test-list (list vector-mul-test))

(define vector-add
  (lambda (v1 v2)
    (list->vector (map + (vector->list v1) (vector->list v2)))))

(define vector-add-test
  (lambda ()
    (check! (vector-approx-equal? (vector-add (vector 0.0 1.0 1.5) (vector 1.0 0.5 2.5))
                                              (vector 1.0 1.5 4.0)))))
(append! test-list (list vector-add-test))

(define square (lambda (k) (* k k)))

; too tired & lazy to check for zerovec - good thing I'm never shipping it
(define vector2-normalize
  (lambda (v2)
    (let ((factor-thingy (/ 1 (sqrt (+ (square( vector-first v2))
                                (square (vector-second v2)))))))
      (vector-map (lambda (e) (* factor-thingy e)) v2))))

(define vector2-normalize-test
  (lambda ()
    (begin
      (check! (vector-approx-equal? (vector2-normalize (vector 0.5 0.0)) (vector 1.0 0.0)))
      (check! (vector-approx-equal? (vector2-normalize (vector 0.0 1.1)) (vector 0.0 1.0)))
    )
  )
)
(append! test-list (list vector2-normalize-test))

(define ship-update!
  (lambda (my-ship delta-t)  ; pos += velocity * delta-t
    (let ((accel (vector-mul
                   (vector2-normalize
                     (vector-mul (ship-pos my-ship) -0.1))
                   0.1)))
      (set-ship-vel! my-ship (vector-add (ship-vel my-ship) (vector-mul accel delta-t)))
      (set-ship-pos! my-ship (vector-add (ship-pos my-ship)
                                         (vector-mul (ship-vel my-ship) delta-t)
                             )
      )
    )
  )
)

(define ship-update!-test
  (lambda ()
    (let ((my-ship (make-ship (vector 0.1 0.0) (vector 0.1 0.0) (vector 0.0 0.0))))
      (ship-update! my-ship 0.1)
      (check! (vector-approx-equal? (ship-pos my-ship) (vector .11 .10))))))
;(append! test-list (list ship-update!-test))

(define shape-xform
  (lambda (shape pos rot)
    (map (lambda (v2) (vector-add pos (vector2-xform-rot v2 rot))) shape)
  )
)

(define shape-xform-test
  (lambda ()
    (let ((result (shape-xform
                    (list (vector 0 0) (vector 1 0) (vector 0 1))
                    (vector 1 0)
                    (/ pi 2))))
      (check! (vector-approx-equal? (first result) (vector 1.0 0.0)))
      (check! (vector-approx-equal? (second result) (vector 1.0 1.0)))
      (check! (vector-approx-equal? (third result) (vector 0.0 0.0)))
    )
  )
)
(append! test-list (list shape-xform-test))

(define graphics-draw-shape
  (lambda (gd shape)
    (begin
      (graphics-move-cursor gd (vector-first (first shape))
                               (vector-second (first shape)))
      (for-each
         (lambda (xy) (graphics-drag-cursor gd (vector-first xy)
                                               (vector-second xy)))
         shape))))

(define ship-shape   ; no pun intended.  seriously
  (list (vector 0.05 0.0)
        (vector -0.05 0.025)
        (vector -0.05 -0.025)
        (vector 0.05 0.0)))

(define ship-draw
  (lambda (my-ship gd)
    (graphics-draw-shape gd
      (shape-xform ship-shape (ship-pos my-ship) (ship-rot my-ship)))))

(define turn
  (lambda (gd my-ship i)
     (begin
       (display "turn ")(display i)(newline)
       (ship-update! my-ship 0.1)
       (ship-draw my-ship gd))))

(define delay
  (lambda (msecs)
    (let delay-until ((stoptime (+ (real-time-clock) (internal-time/seconds->ticks msecs))))
      (if( > (real-time-clock) stoptime ) ()
                                        (delay-until stoptime)))))

(define delay-test
  (lambda ()
    (with-timings
      (lambda () (delay 1.0))
      (lambda (run-time gc-time real-time)
        (begin
          (check! (<= 1.0 (internal-time/ticks->seconds real-time)))
          (check! ( > 2.0 (internal-time/ticks->seconds real-time)))
        )
      )
    )
  )
)
(append! test-list (list delay-test))

(define game
  (lambda (numturns)
    (begin
      (let ((gd (make-graphics-device))
            (my-ship (make-ship (vector -0.5 0.5) (vector 0.1 0.0) 0)))
        (let mainloop ((i 0))
          (if (>= i numturns) #f
            (begin
              (graphics-clear gd)
              (turn gd my-ship i)
              (set-ship-rot! my-ship (+ 0.01 (ship-rot my-ship)))
              (delay 0.01)
              (mainloop (+ i 1))
            )
          )
        )
        (graphics-close gd)
      )
    )
  )
)

(define test-suite
  (lambda ()
    (for-each
      (lambda (foo)
        (foo))
      test-list)))
(test-suite)

More On Allocation

Okay, I suppose the previous post could be interpreted to mean "Don't worry about allocation."  Not what I meant, of course.  Why am I always posting and then backpedaling?  It's agile blogging, I guess - get something onscreen, and then iterate to increase value.

Okay, for fuck's sake, yes, worry.  (Hmm...when my daughter's old enough to read am I going to have to go through all my blog entries and take the swear words out?)  Have a plan.  But that plan should involve dynamic allocation on preferably just one heap - and (did I not mention this before?  Sorry.) a way to track those allocations.  Which you don't need to implement right off the bat--that's what I meant by being agile in the previous post--but you will need to implement tracking before you ship. 

And your plan will also probably have some kind of a budget for how much memory you're going to spend where.  For example, you might do some kind of streaming city game, where each block that gets loaded from the disk can take this much K and will be placed in their own fixed areas of memory and all the remaining memory will be dynamically allocated on a single heap, but you're predicting around this many K for textures and that many K for whatever.

Those individual blocks, by the way, aren't fixed pools of textures or meshes - within each block you give the artist the flexibility to decide whether they want to use mostly textures, mostly meshes, or what.

Although fixed pools are nice for cache coherency they suck for the exact thing that the human race invented heaps for - being flexible about how we use our memory.  Just as an example, you may have one level or mission that uses a whole lot of one kind of asset.  And another level or mission that uses a whole lot of another.  Maybe you have flying missions and interior missions, for example.  With fixed pools, you're screwed - your levels/missions will have a fixed sameness in the asset allocation.  You'll only be able to have n clouds for your sky mission and m walls for your interior mission - even though you have no walls in your sky mission and no clouds in your interior mission.

We had a system like that on one game I worked on, and if we blew out one of the budgets for one of the many fixed pools, the smart thing to do was to double the size of the pool and get some breathing room.  Which meant on that particular project, on average, 25% of our allocated memory was going unused.  You can then do a production step where you run the game, find the high watermarks for all your assets, and tune the fixed-pool allocations to allocate just enough.  Which isn't a fun thing to do every build.

So...what about cache coherency?  It is all about cache coherency these days, isn't it?  Or was that last year?  Still, I'd say that hamstringing yourself with fixed pools is a premature speed optimization - if you discover you're thrashing the cache in some tight loop or other, you can make yourself a flexible--not fixed--pool with vector<> (or realloc() if you're anti-STL).  (But then vector<> has the same 25% wasted memory problem unless you do a similar high water-mark production step.  So only use them for the bottleneck stuff!)

So - in short - dynamic allocation good, for flexibility and maximum use of available resources.

Also - I'm not saying leave your allocation woes to the end of the project.  Tackle them as soon as they become a problem;  which will probably be as soon as you have a playable build on the console.  You'll probably find it can only soak for n minutes before you get a fragmentation crash, if you're doing some dynamic allocation using the built-in xbox allocator.  And you'll probably also find it doesn't run at 60 yet.  Now's the time to solve that - optimization is no longer premature.

So I'm really talking about what order you do things in.  The guys on the panel at the conference-formerly-known-as-Xfest were saying build your allocation system first to be cache friendly and to avoid fragmentation, and then get your game to a playable state.  I'm saying get your game to a playable state, then worry about whether it fits on the console, fragments the heap, and runs at 60.  I say that because memory fragmentation and cache coherency are fairly well-understood problems, but "the game isn't fun" isn't a well-understood problem at all.

Oh, and I should have known Andrei would post a comment to the last thing, since he was the main guy who was taking the team's haphazardly allocated & STL'd code and making it run fast.  But he only had to do that with stuff that turned out to be bottleneck - if we had rules in place that said 'never use new' and 'never use STL' I believe the whole team's productivity would have suffered  - it would have been a net loss - not to mention we might not have gotten our proof-of-concepts done on time and who knows what cool features might have been cancelled?  Back to levels?  No swinging system?  The Spider-Man 2 game sold somewhat higher than one would expect, based on movie ticket sales - I can't prove it, but I believe it was because it was a lot more fun than Spider-Man 1 - so, by being agile, and focusing on gameplay/productivity over efficient code, I believe we created business value.  And, hey, we did get it to run at 30 most of the time.  (Thanks to Andrei's - and others - hard work.)

STL & Memory allocation on consoles

I was recently at the Conference Formerly Known As XFest, and one of the sessions I saw had a panel of various heavyweight technical directors weighing in on various things. Some of the things they all seemed to more-or-less agree on:  memory allocation bad, STL bad.

Now, I'm kind of out of the loop with our new multithreaded universe, since I haven't had access to any dev kits for the past several months (but I did just order a multi-core, multi-processor machine recently - it should arrive any day now - so I should be able to catch up soon) but these guys seemed to be opposed to memory allocation and STL on consoles in general - a bias that they've carried with them since PS1 days, it seemed like.

I'd just like to weigh in with my own two cents.  I thought I detected a certain amount of coder machismo in their rants, some Not-Invented-Here syndrome. 

Okay, so it was a Microsoft show, and the Microsoft allocator sucks -- in fact, there was a whole talk basically on working around the Microsoft allocator -- so I can understand why everyone was going "look out for fragmentation, etcetera!" 

I think it was Tony Cox who was the one voice of dissent -- he pointed out that any time you're creating a game entity and deciding where to put it in memory, you're doing allocation, whether it's done by a heap manager or your own custom fixed-pool thing.

So here's my take.  And it's "agile" - use new, delete, malloc, free.  Once you find out they're fragmenting, or not thread-safe, deal with it.  It's quite easy to fix allocation later once you find out it's not working out for you.  My favorite allocator is Doug Lea's malloc - first introduced to me by Wade Brainerd when we found out that the built in allocation on the Dreamcast wasn't doing it for us.  Turned out dlmalloc didn't work that well on the DC either, but it was easily configurable to do what we wanted.  (And I did run across a bug in dlmalloc a few years later, but Doug Lea was very responsive and fixed it in the latest build.  How crusty am I?  "I found a bug in Doug Lea's malloc!"  Almost as good as finding a bug in Donald Knuth code.)  dlmalloc is the allocator that the PS2 SDK used by default - how happy it made me.

Seems like everyone stresses about fragmentation.  Fragmentation is actually a *solved problem* - http://portal.acm.org/citation.cfm?id=286864 - but the default Microsoft allocator doesn't use the low-fragmentation algorithm.  Doug Lea's does.  So as long as you're not doing weird allocations - like allocating and reallocating a block that's an eighth of your entire heap - you're good.

I don't actually know if dlmalloc is thread safe.  It probably isn't. 

And, long story short, there have been many console games that shipped on time, sold millions of units, got high scores on game rankings, and used new and delete and malloc and free. 

On the other hand, I do kind of like fixed pools of entities, only because then I can use indices into the array instead of pointers, and fwrite and fread the entire block to the hard-drive as a savegame without rebasing anything.  That's how we used to do savegame back in the day.  Doing everything with pointers was considered a premature optimization.

Eh, I'll leave my pro-STL thoughts for another day.

Fake Interactivity

No, I'm not talking about linear games.  Sofia's watching TV right now and in three shows in a row the characters have asked the audience questions and then said, "You're right!  Thanks!"  Sofia's too young to get what's going on - she just watches.  But I'm wondering if any kids, at any age, actually fall for this illusion of interactivity?

I'll just take it as an indication that I'm in the right industry.  TV wants to be video games.  Video games already are video games.  Woo!

Blogs

Just updated my blog links;  there are a bunch of game blogs I'm subscribed to on bloglines that I never got around to listing here.  Mostly I did it because I owe Erik Chan at http://blog.doublejumping.com - really hope those guys succeed!

Actually, I'm way behind in my actual blog reading these days, and I'm thankful for the guys who only post every week or two.  Be warned - post too often and you only get skimmed!