Planet Scheme

I've been a fan of generators for quite some time. But seeing that they were added to the core PLT scheme libraries, I thought they were worth another look.

What I like about generators is their ability to take potentially complex looping problems, and make them a lot simpler and more module. Consider this example that I whipped up in a hurry - I think generators solve the problem in an elegant way, where regular iteration would have gotten messy.

The Problem

I wanted to experiment with generators in a context that showed off their ability to work with large sets of data. And what larger set of data is there than the web? The little I challenge I worked up is this:

Suppose you want to find out how your website ranks for a given search phrase. That is, when you search the web, what page of the results your domain show up on? (if at all)

While I could have solved this with any search engine, Bing has a clever little feature - you can set the format of any search to be xml and instantly get back a well formed XML document you can work with. Google and Yahoo do this too, but they do it through fairly extensive APIs and for my toy example, I wanted something simpler.

The Solution

The first part of the solution was to add the ability to search the web using Bing and to return the results. This has nothing to do with generators, so I won't bother showing the solution here. Though you're welcome to download the code here. It's yet another example of using PLT scheme to grab an XML document off the web and parse it - a trick that every time I do, makes me smile.

With a quick bing library written I can move on to the fun part. What I want to do is to write a function that takes in a search term (aka keyword) and a domain (the website to check), and find the occurrences of when the search result mentions the domain. I wrote the core of the solution in a single function below. Notice that the name ends in /y - this is a hint to me that this function will yield results. I'm not sure this is an ideal standard, but for our purposes it will work. Here's the code:

(require "bing.ss"
         scheme/generator
         (only-in srfi/13 string-contains))

(define-struct  match (url page position) #:prefab)

;; Check for matches of domain when searching for keyword.
;; max-pages says how many results we should look through before we give up.
(define (keyword-check/y keyword domain max-pages)
  (define (offset p) (* p 10))
  ;; This nested function, 'check', does the real work. It checks
  ;; a given page for occurrences.
  (define (check page)
    (when (< page max-pages)
      (let ([results (search keyword #:offset (offset page))])
        (unless (null? results)
          ;; OK, if we made it this far, it means that bing has results for us
          ;; to look through. So let's look at each one.
          (for ([r results] [i (in-naturals)])
            (when (string-contains (doc-url r) domain)
              ;; At this point, our string-contains tells us we have
              ;; a match. Whoo! What do we do? yield the result.
              (yield (make-match (doc-url r) page i))))
          ;; This should look like an infinite loop. We just finished
          ;; checking one page, and are now going onto the next.
          ;; However, we'll only do this if we're asked to give another
          ;; result from our yield.
          (check (add1 page))))))
  (check 0))

The beauty of this code is that it's oblivious to the context that it's called within. When it finds a match, it invokes yield, and the continues looking for additional matches. It doesn't need to worry that the result set it's analyzing may be infinite.

I created a quick wrapper function for keyword-check/y that turns it into a simple generator:

(define (keyword-check/g keyword domain max-pages)
  (generator (keyword-check/y keyword domain max-pages)))

I can now make use of the solution. Say I want to see how my company's website is doing for the phrase Software Idea. I can do that interactive like so:

> (define idea-finder (keyword-check/g "software idea" "ideas2executables.com" 100))

;; idea-finder is now a function that I can invoke to get results from
;; my generator. Note, I'm willing to look through the first 100 pages of
;; bing results.
;;
> (idea-finder)
#s(match "http://www.ideas2executables.com/" 0 8)
> (idea-finder)
#s(match "http://www.ideas2executables.com/" 1 0)
> (idea-finder)
#s(match "http://www.ideas2executables.com/portfolio/" 6 6)
> (idea-finder)
#s(match "http://www.ideas2executables.com/portfolio/" 7 1)
> (idea-finder)
#s(match "http://www.ideas2executables.com/who-we-are/" 15 1)

You can see that it found the website on the first and second pages, then the 7th and 8th and finally on page 16 (notice the 0 indexing).

Finally, I can wrap up the generator in a neat little package like so:

(define (keyword-checker keyword domain)
  (for/list ([i (in-range 0 3)]
             [hit (in-generator (keyword-check/y keyword domain 100))])
    hit))

I can then invoke this function like any other:

> (keyword-checker "Software Idea" "ideas2executables.com")
(#s(match "http://www.ideas2executables.com/" 0 8)
 #s(match "http://www.ideas2executables.com/" 1 0)
 #s(match "http://www.ideas2executables.com/portfolio/" 6 6))

For large data sets, being able to just yield and continue searching for more data, really does make for an elegant programming model.

Here is how to ask Maven to generate Idea project files for you:

mvn idea:idea -DjdkName=1.5

(via Maven)

ParEdit (paredit.el) is a minor mode for performing structured editing of S-expression data. The typical example of this would be Lisp or Scheme source code.

ParEdit helps keep parentheses balanced and adds many keys for moving S-expressions and moving around in S-expressions.

That quote from EmacsWiki really undersells Paredit, though.

Paredit makes it virtually impossible to un-balance parentheses (aka round, square, and curly brackets).

This mode would be especially interesting for folks avoiding Lisp because of the nightmare of balancing parentheses is too much of an obstacle to overcome (in practice of course it really isn’t, even if you don’t use Paredit).

I am in the final development stages of my Scheme game that will initially be released for the iPhone. It's been an incredible adventure to leave my job and pursue this full-time. I have learned so much and I really hope I can continue doing this.

This is one of a few posts I will be making in which I will one, begin showing you my game and two, ask for your assistance. I will be brief this time, but soon I will show you the whole game and explain more of my vision for Scheme and game development.

Sneak Peek

First, here is a video of just one aspect of my game, which is fully written in Gambit Scheme. I couldn't resist sharing it. I won't disclose many details of my game yet, but yes, those are cows, and yes, you are exploding them by shooting them with bolts of lightning!

My game should hopefully be released on the iPhone in the next couple weeks. I will post a much more detailed overview of my game soon when I start my big marketing push.

A Request for Help

Speaking of marketing, that's where I need some assistance. I'm a one-man shop right now with little connections in the game industry. It's going to be extremely difficult to make this game successful. I'm asking for your support by either buying my game when it's released (it will be cheap on the iPhone App Store), or helping me market my game in any way possible. You can either email me ideas or simply tell your friends about it.

Why should you support me? Well, you may want to support small businesses or indie game companies. Or, you may see that I really strive to give back to the game community. I really want more independant people developing games, and I want to make it easy to do so. I will frequently update my blog with useful information and release as many open-source libraries as possible. (I'm even considering releasing the source to my game when I'm done.)

So far, I have written articles about writing apps for the iPhone in Scheme, debugging games interactively, tweening techniques, and more.

I want to expound on these ideas. Although my focus is on Scheme, I hope to offer some cool ideas to the game development community that is good for anyone to think about. But I can only continue doing that if enough people buy my games, and I need help getting the word out!

Something to consider…

“I can’t imagine why anyone would need X” is a statement about your imagination, not X.

(via Dan)

Swing is the GUI standard for Java. Clojure is the awesomeness standard for Java.

(via Stuart)

In this post Alex shares his patch for adding Clojure support to the excellent LaTeX listings package.

Here is an article explaining Eiffel’s new for-each-like syntax.

It is pretty interesting to see how the language evolves… obviously a very different approach then the Lisp-ish “just add the syntax you need” approach.

Addendum:01/30/10

Changed the title as I meant ‘for-each’ and not ‘map’.

Here is a nice review of Scheme modes for Emacs.

• Benchmarks in the PLT sources – vs. Bigloo, Chicken, Gambit, Guile, Ikarus, Larceny, MIT Scheme, and Scheme48; safe operations and generic arithmetic only

• Benchmarks in the Gambit sources – vs. Bigloo and Gambit; generic vs. fixnum-/flonum-specific arithmetic, safe vs. unsafe operations

I want to share something I just finished implementing for my 3d graphics framework in Scheme which I am building my iPhone game off of. Keep in mind that I am not intentionally building a separate 3d graphics framework as a general platform, but I am building only what is needed to get my game out the door, so it is rough and the API is awkward and not well thought out.

Given my custom scene objects which abstract away OpenGL rendering, I built a system for interpolating these objects' properties (such as scale and color) over time, or "tweening." This turned out to be incredibly useful. Here's the story.

(Note: I'm not extremely confident I'm using the word "tween" correctly, but if not, I'm re-defining it.)

What's the problem?

The problem was that I needed a system for presenting the title screen, level titles, and a 2d overlay for my 3d iPhone game. These 2d elements should smoothly fade in and out of the screen over time. I don't need a full GUI toolkit, but I'm more interested in smooth animations when levels change, text appears, etc.

This turned out to be a huge bear in my old system: because of the primitive nature of my Scheme graphics libraries, I had to manually do all the fading every frame for every object. Horrible.

Establishing the Tween

I started re-hauling parts of my system. It started small, only supporting alpha fading of 2d objects. However, as I worked on it more and more, I realized all properties should be tweenable.

So I set out to implement tweening for any object properties, such as position, rotation, scale, color, and anything else. And why not let 3d objects be tweened as well? No reason not to!

It turns out that this is a good way to specify simplistic behaviors of objects. I'm sure anyone experienced in developing games is used to this. I've seen various forms of tweening in game frameworks, especially particle systems. I'm not sure if I've seen it expressed this way though. Is there a formal or established name for this, and any examples of how most engines do this?

Once the system was in place, I implemented many types of tweens such as "linear," "quadratic", "cubic", and "bounce", each defining a different interpolation function based on time. More details about these types, including graphics of each function, can be seen in this documentation.

Examples

Here are some examples from my tweening system. I will show you code and a video of what it does. I will not go into details about the code because it isn't public yet, and it's really rough, but hopefully it will help expose what I'm trying to achieve.

Types of Tweens

Here I show you all the types of tweens my system currently supports. A quick list would include linear, quadratic, cubic, bouncing, and all the variations of applying them at the end or the start of the interpolation.

(begin
  (define (tween-type type)
    (scene-list-clear!)
    (scene-list-add
     (make-tween

      (make-2d-object
       2d-perspective
       position: (make-vec3d .1 (- .5 .025) 0.)
       scale: (make-vec3d .05 (/ .05 1.5) 1.)
       color: (make-vec4d 1. 1. 1. 1.))

      position: (make-vec3d .65 (- .5 .025) 0.)
      color: (make-vec4d (+ (* (random-real) .5) .5)
                         (+ (* (random-real) .5) .5)
                         (+ (* (random-real) .5) .5)
                         (+ (* (random-real) .5) .5))
      scale: (make-vec3d .2 (/ .2 1.5) 1.)
      length: .7
      type: type)))

  (tween-type 'linear))

Queued Tweens

You can queue up tweens as well so that one fires off as another one ends.

(begin
  (scene-list-clear!)

  (define tx (image-opengl-load "survived.png"))

  (let ((obj (make-2d-object
              2d-ratio-perspective
              position: (make-vec3d (- .5 .025) .1 0.)
              scale: (make-vec3d .05 .05 1.)
              color: (make-vec4d 1. 1. 1. 1.)
              rotation: (make-vec4d 0. 0. 1. 0.)
              texture: tx
              )))
    (scene-list-add
     (make-tween
      obj
      position: (make-vec3d (- .5 .025) .75 0.)
      scale: (make-vec3d .4 .4 1.)
      color: (make-vec4d 0. 1. 0. .5)
      rotation: (make-vec4d 0. 0. 1. 90.)

      type: 'ease-out-bounce
      length: 1.5

      on-finished:
      (lambda ()
        (scene-list-add
         (make-tween
          obj
          type: 'ease-inout-cubic
          position: (make-vec3d .8 .1 0.)
          scale: (make-vec3d .1 .1 1.)
          color: (make-vec4d 1. .5 0. 1.)
          length: 1.))
        #f)))))

3d Tween

There's no reason you can't apply tweens to a 3d object as well.

(begin
  (scene-list-clear!)

  (let ((obj (make-mesh-object
              3d-perspective
              mesh: sheep-mesh
              position: (make-vec3d 0. 0. 10.)
              rotation: (make-vec4d 0. 0. 1. 0.)
              scale: (make-vec3d 2. 2. 2.))))
    (scene-list-add
     (make-tween
      obj
      scale: (make-vec3d 6. 6. 6.)
      rotation: (make-vec4d 0. 0. 1. 90.)
      length: 1.
      type: 'ease-out-cubic
      on-finished:
      (lambda ()
        (thread-sleep! 1.)
        (scene-list-add
         (make-tween
          obj
          scale: (make-vec3d .7 .7 .7)
          type: 'ease-inout-cubic
          on-finished:
          (lambda ()
            (scene-list-add
             (make-tween
              obj
              position: (make-vec3d 0. 5. 10.)
              type: 'ease-out-bounce
              on-finished:
              (lambda ()
                (scene-list-add
                 (make-tween
                  obj
                  type: 'ease-out-bounce
                  position: (make-vec3d 0. -5. 10.)))
                #f)))
            #f)))
        #f)))))

Improvements

I'm still wrapping my head around how to implement a full motion system with this. As of now, if you specify a cubic tween between point (x, y) to (x1, y1), it will perform a cubic interpolation on both the x and y as a function of time. The result is that the object moves in a straight line from point A to point B, but the speed of the movement is cubic.

For example, here's a cubic curve:

Even though it is a curve, if I apply cubic interpolation to positions, which are 3-dimensional vectors with an x, y, and z property, the object moves between point A and point B in a straight line, with cubic-varying speed. If we tracked the movement, it would look like this:

What if I wanted the object to curve when moving from point A to point B? Surely I can express that with interpolations? The problem lies in the fact that I've bound my interpolations of multi-dimensional vectors to be constant across each dimension. I would need to support different kinds of interpolations across each x, y, and z axis. This sounds really neat, and I will have to extend my system to support this later.

Now that I think about it, I think the special case of interpolating movement should be handled with splines. In fact, it's probably downright inappropriate for me to interpolate position this way. Splines are on my todo list for research.

Conclusion

Having this simplistic tweening system will make it easy for me to apply smooth animations consistently across my iPhone game. It's feels a lot more polished when I use this to fade in items and slide them off the screen. I wouldn't really have thought of this unless I forced myself to build a real game.

Building a game from scratch has forced me to learn all kinds of things, and I find this experience invaluable. I'm not building something simply because the idea of it sounds cool, but I have to build my framework with certain features so that my game will not only run but look good too. Having this dictate my development forces me to drastically alter my ideals quickly as I learn how games are laid out.

Scheme is a huge support in this kind of simplistic agile development. Between its dynamic type system and functional simplicity, I can constantly re-shape huge parts of the system as if I'm a sculpter removing and adding huge chunks of clay. On top of that, The Lisp methodology of interactive/iterative development allows me to add details extremely quickly. The turn around time for feeling reward from intense coding sessions is really fast and extremely motivating!