Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I, a Java imperative programmer, would like to understand how to generate a simple version of Space Invaders based on Functional Programming design principles (in particular Referential Transparency). However, each time I try to think of a design, I get lost in the morass of extreme mutability, the same mutability which is shunned by the functional programming purists.

As an attempt to learn Functional Programming, I decided to attempt to create a very simple 2D interactive game, Space Invader (note the lack of plural), in Scala using the LWJGL. Here are the requirements for the basic game:

  1. User ship at the bottom of the screen moved left and right by the "A" and "D" keys respectively

  2. User ship bullet fired straight up activated by the space bar with a minimum pause between shots to be .5 seconds

  3. Alien ship bullet fired straight down activated by a random time of .5 to 1.5 seconds between shots

Things intentionally left out from the original game are WxH aliens, degradable defense barriers x3, high speed saucer ship at at the top of the screen.

Okay, now to the actual problem domain. For me, all the deterministic parts are obvious. It's the non-deterministic parts that seem to be blocking my ability to consider how to approach. The deterministic parts are the bullet's trajectory once they exist, the continuous motion of the alien and the explosion due to a hit on either (or both) of the player's ship or the alien. The non-deterministic parts (to me) are handling the stream of user input, handling fetching a random value for determining alien bullet firings and handling the output (both graphics and sound).

I can do (and have done) lots of this type of game development over the years. However, all of it was from the imperative paradigm. And LWJGL even provides a very simple Java version of Space invaders (of which I began moving to Scala using Scala as Java-without-semicolons).

Here are some links that talk around this area of which none seem to have directly dealt with the ideas in a way a person coming from Java/Imperative programming would understand:

  1. Purely Functional Retrogames, Part 1 by James Hague

  2. Similar Stack Overflow post

  3. Clojure/Lisp Games

  4. Haskell Games on Stack Overflow

  5. Yampa's (in Haskell) Functional Reactive Programming

It appears that there are some ideas in the Clojure/Lisp and Haskell games (with source). Unfortunately, I am not able to read/interpret the code into mental models that make any sense to my simpleminded Java imperative brain.

I'm so excited by the possibilities offered by FP, I can just taste the multi-threaded scalability capabilities. I feel like if were able to grok how something as simple as the time + event + randomness model for Space Invader can be implemented, segregating the deterministic and non-deterministic parts in a properly designed system without it turning into what feels like advanced mathematical theory; i.e. Yampa, I'd be set. If learning the level of theory Yampa seems to require to successfully generate simple games is necessary, then the overhead of acquiring all the necessary training and conceptual framework will vastly outweigh my understanding of the benefits of FP (at least for this over-simplified learning experiment).

Any feedback, proposed models, suggested methods of approaching the problem domain (more specific than the generalities covered by James Hague) would be greatly appreciated.

share|improve this question
1  
I've removed the part about your blog from the question, because it wasn't essential to the question itself. Feel free to include a link to a follow up article when you come around to writing it. –  Yannis Rizos Jan 24 '12 at 7:18
    
@Yannis - Got it. Tyvm! –  chaotic3quilibrium Jan 24 '12 at 16:03
    
You asked for Scala, which is why this is only a comment. Caves of Clojure is imho a manageable read on how to implement a roguelike FP style. It handles state by returning a snapshot of the world which the author can then test. That's pretty cool. Maybe you can browse through the posts and see if any parts of his implementation are easily transferable to Scala –  IAE Jan 13 at 3:04

3 Answers 3

up vote 3 down vote accepted

An idiomatic Scala/LWJGL implementation of Space Invaders wouldn’t look that much like a Haskell/OpenGL implementation. Writing a Haskell implementation might be a better exercise in my opinion. But if you want to stick with Scala, here are some ideas for how to write it in functional style.

Try to use immutable objects only. You could have a Game object which holds a Player, a Set[Invader] (be sure to use immutable.Set), etc. Give Player an update(state: Game): Player (it could also take depressedKeys: Set[Int], etc), and give the other classes similar methods.

For randomness, scala.util.Random isn’t immutable like Haskell’s System.Random, but you could make your own immmutable generator. This one is inefficient but it demonstrates the idea.

case class ImmutablePRNG(val seed: Long) extends Immutable {
    lazy val nextLong: (Long, ImmutableRNG) =
        (seed, ImmutablePRNG(new Random(seed).nextLong()))
    ...
}

For keyboard/mouse input and rendering, there’s no way around calling impure functions. They’re impure in Haskell too, they’re just encapsulated in IO etc. so that your actual function objects are technically pure (they don’t read or write state themselves, they describe routines which do, and the runtime system executes those routines).

Just don’t put I/O code in your immutable objects like Game, Player and Invader. You can give Player a render method, but it should look like

render(state: Game, buffer: Image): Image

Unfortunately this doesn’t fit well with LWJGL since it’s so state-based, but you could build your own abstractions on top of it. You could have an ImmutableCanvas class that holds an AWT Canvas, and its blit (and other methods) could clone the underlying Canvas, pass it to Display.setParent, then perform the rendering and return the new Canvas (in your immutable wrapper).


Update: Here is some Java code showing how I would go about this. (I would have written almost the same code in Scala, except that an immutable set is built-in and a few for-each loops could be replaced with maps or folds.) I made a player which moves around and fires bullets, but I didn’t add enemies since the code was getting long already. I made just about everything copy-on-write – I think this is the most important concept.

import java.awt.*;
import java.awt.geom.*;
import java.awt.image.*;
import java.awt.event.*;
import javax.swing.*;
import java.util.*;

import static java.awt.event.KeyEvent.*;

// An immutable wrapper around a Set. Doesn't implement Set or Collection
// because that would require quite a bit of code.
class ImmutableSet<T> implements Iterable<T> {
  final Set<T> backingSet;

  // Construct an empty set.
  ImmutableSet() {
    backingSet = new HashSet<T>();
  }

  // Copy constructor.
  ImmutableSet(ImmutableSet<T> src) {
    backingSet = new HashSet<T>(src.backingSet);
  }

  // Return a new set with an element added.
  ImmutableSet<T> plus(T elem) {
    ImmutableSet<T> copy = new ImmutableSet<T>(this);
    copy.backingSet.add(elem);
    return copy;
  }

  // Return a new set with an element removed.
  ImmutableSet<T> minus(T elem) {
    ImmutableSet<T> copy = new ImmutableSet<T>(this);
    copy.backingSet.remove(elem);
    return copy;
  }

  boolean contains(T elem) {
    return backingSet.contains(elem);
  }

  @Override public Iterator<T> iterator() {
    return backingSet.iterator();
  }
}

// An immutable, copy-on-write wrapper around BufferedImage.
class ImmutableImage {
  final BufferedImage backingImage;

  // Construct a blank image.
  ImmutableImage(int w, int h) {
    backingImage = new BufferedImage(w, h, BufferedImage.TYPE_INT_RGB);
  }

  // Copy constructor.
  ImmutableImage(ImmutableImage src) {
    backingImage = new BufferedImage(
        src.backingImage.getColorModel(),
        src.backingImage.copyData(null),
        false, null);
  }

  // Clear the image.
  ImmutableImage clear(Color c) {
    ImmutableImage copy = new ImmutableImage(this);
    Graphics g = copy.backingImage.getGraphics();
    g.setColor(c);
    g.fillRect(0, 0, backingImage.getWidth(), backingImage.getHeight());
    return copy;
  }

  // Draw a filled circle.
  ImmutableImage fillCircle(int x, int y, int r, Color c) {
    ImmutableImage copy = new ImmutableImage(this);
    Graphics g = copy.backingImage.getGraphics();
    g.setColor(c);
    g.fillOval(x - r, y - r, r * 2, r * 2);
    return copy;
  }
}

// An immutable, copy-on-write object describing the player.
class Player {
  final int x, y;
  final int ticksUntilFire;

  Player(int x, int y, int ticksUntilFire) {
    this.x = x;
    this.y = y;
    this.ticksUntilFire = ticksUntilFire;
  }

  // Construct a player at the starting position, ready to fire.
  Player() {
    this(SpaceInvaders.W / 2, SpaceInvaders.H - 50, 0);
  }

  // Update the game state (repeatedly called for each game tick).
  GameState update(GameState currentState) {
    // Update the player's position based on which keys are down.
    int newX = x;
    if (currentState.keyboard.isDown(VK_LEFT) || currentState.keyboard.isDown(VK_A))
      newX -= 2;
    if (currentState.keyboard.isDown(VK_RIGHT) || currentState.keyboard.isDown(VK_D))
      newX += 2;

    // Update the time until the player can fire.
    int newTicksUntilFire = ticksUntilFire;
    if (newTicksUntilFire > 0)
      --newTicksUntilFire;

    // Replace the old player with an updated player.
    Player newPlayer = new Player(newX, y, newTicksUntilFire);
    return currentState.setPlayer(newPlayer);
  }

  // Update the game state in response to a key press.
  GameState keyPressed(GameState currentState, int key) {
    if (key == VK_SPACE && ticksUntilFire == 0) {
      // Fire a bullet.
      Bullet b = new Bullet(x, y);
      ImmutableSet<Bullet> newBullets = currentState.bullets.plus(b);
      currentState = currentState.setBullets(newBullets);

      // Make the player wait 25 ticks before firing again.
      currentState = currentState.setPlayer(new Player(x, y, 25));
    }
    return currentState;
  }

  ImmutableImage render(ImmutableImage img) {
    return img.fillCircle(x, y, 20, Color.RED);
  }
}

// An immutable, copy-on-write object describing a bullet.
class Bullet {
  final int x, y;
  static final int radius = 5;

  Bullet(int x, int y) {
    this.x = x;
    this.y = y;
  }

  // Update the game state (repeatedly called for each game tick).
  GameState update(GameState currentState) {
    ImmutableSet<Bullet> bullets = currentState.bullets;
    bullets = bullets.minus(this);
    if (y + radius >= 0)
      // Add a copy of the bullet which has moved up the screen slightly.
      bullets = bullets.plus(new Bullet(x, y - 5));
    return currentState.setBullets(bullets);
  }

  ImmutableImage render(ImmutableImage img) {
    return img.fillCircle(x, y, radius, Color.BLACK);
  }
}

// An immutable, copy-on-write snapshot of the keyboard state at some time.
class KeyboardState {
  final ImmutableSet<Integer> depressedKeys;

  KeyboardState(ImmutableSet<Integer> depressedKeys) {
    this.depressedKeys = depressedKeys;
  }

  KeyboardState() {
    this(new ImmutableSet<Integer>());
  }

  GameState keyPressed(GameState currentState, int key) {
    return currentState.setKeyboard(new KeyboardState(depressedKeys.plus(key)));
  }

  GameState keyReleased(GameState currentState, int key) {
    return currentState.setKeyboard(new KeyboardState(depressedKeys.minus(key)));
  }

  boolean isDown(int key) {
    return depressedKeys.contains(key);
  }
}

// An immutable, copy-on-write description of the entire game state.
class GameState {
  final Player player;
  final ImmutableSet<Bullet> bullets;
  final KeyboardState keyboard;

  GameState(Player player, ImmutableSet<Bullet> bullets, KeyboardState keyboard) {
    this.player = player;
    this.bullets = bullets;
    this.keyboard = keyboard;
  }

  GameState() {
    this(new Player(), new ImmutableSet<Bullet>(), new KeyboardState());
  }

  GameState setPlayer(Player newPlayer) {
    return new GameState(newPlayer, bullets, keyboard);
  }

  GameState setBullets(ImmutableSet<Bullet> newBullets) {
    return new GameState(player, newBullets, keyboard);
  }

  GameState setKeyboard(KeyboardState newKeyboard) {
    return new GameState(player, bullets, newKeyboard);
  }

  // Update the game state (repeatedly called for each game tick).
  GameState update() {
    GameState current = this;
    current = current.player.update(current);
    for (Bullet b : current.bullets)
      current = b.update(current);
    return current;
  }

  // Update the game state in response to a key press.
  GameState keyPressed(int key) {
    GameState current = this;
    current = keyboard.keyPressed(current, key);
    current = player.keyPressed(current, key);
    return current;
  }

  // Update the game state in response to a key release.
  GameState keyReleased(int key) {
    GameState current = this;
    current = keyboard.keyReleased(current, key);
    return current;
  }

  ImmutableImage render() {
    ImmutableImage img = new ImmutableImage(SpaceInvaders.W, SpaceInvaders.H);
    img = img.clear(Color.BLUE);
    img = player.render(img);
    for (Bullet b : bullets)
      img = b.render(img);
    return img;
  }
}

public class SpaceInvaders {
  static final int W = 640, H = 480;

  static GameState currentState = new GameState();

  public static void main(String[] _) {
    JFrame frame = new JFrame() {{
      setSize(W, H);
      setTitle("Space Invaders");
      setContentPane(new JPanel() {
        @Override public void paintComponent(Graphics g) {
          BufferedImage img = SpaceInvaders.currentState.render().backingImage;
          ((Graphics2D) g).drawRenderedImage(img, new AffineTransform());
        }
      });
      addKeyListener(new KeyAdapter() {
        @Override public void keyPressed(KeyEvent e) {
          currentState = currentState.keyPressed(e.getKeyCode());
        }
        @Override public void keyReleased(KeyEvent e) {
          currentState = currentState.keyReleased(e.getKeyCode());
        }
      });
      setLocationByPlatform(true);
      setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
      setVisible(true);
    }};

    for (;;) {
      currentState = currentState.update();
      frame.repaint();
      try {
        Thread.sleep(20);
      } catch (InterruptedException e) {}
    }
  }
}
share|improve this answer
2  
I added some Java code - does it help? If the code looks strange, I would look at some smaller examples of immutable, copy-on-write classes. This looks like a decent explanation. –  Daniel Jan 28 '12 at 9:12
2  
@chaotic3quilibrium it's just a normal identifier. I sometimes use it instead of args if the code ignores arguments. Sorry for the unnecessary confusion. –  Daniel Feb 21 '12 at 0:44
1  
No worries. I just assumed that and moved on. I played with your example code for while yesterday. I think I have the hang of the idea. Now, it has me wondering if I missing something else. The number of temporary objects is humongous. Every tick generates a frame which displays a GameState. And to get to that GameState from the previous tick's GameState involves generating a number of intervening GameState instances, each with one small adjustment from the previous GameState. –  chaotic3quilibrium Feb 21 '12 at 14:41
2  
Yeah, it is pretty wasteful. I don't think the GameState copies would be that costly, even though several are made each tick, since they're ~32 bytes each. But copying the ImmutableSets could be expensive if many bullets are alive at the same time. We could replace ImmutableSet with a tree structure like scala.collection.immutable.TreeSet to lessen the problem. –  Daniel Feb 22 '12 at 1:50
1  
And ImmutableImage is even worse, since it copies a large raster when it's modified. There are some things we could do to lessen that problem too, but I think it would be most practical to just write rendering code in imperative style (even Haskell programmers normally do so). –  Daniel Feb 22 '12 at 1:53

Well, you are hamstringing your efforts by using LWJGL -- nothing against it, but it will impose non-functional idioms.

Your research is in line with what I'd recommend, however. "Events" are well supported in functional programming through concepts such as functional reactive programming or dataflow programming. You may try out Reactive, a FRP library for Scala, to see if it can contain your side effects.

Also, take a page out of Haskell: use monads to encapsulate/isolate side effects. See state and IO monads.

share|improve this answer
    
Tyvm for your reply. I am not sure how to get the keyboard/mouse input and the graphics/sound output from Reactive. Is it there and I'm just missing it? As to your reference to using a monad - I am just now learning about them and still don't completely understand what a monad is. –  chaotic3quilibrium Jan 25 '12 at 22:27

The non-deterministic parts (to me) are handling the stream of user input ... handling the output (both graphics and sound).

Yes, IO is non-deterministic and "all about" side-effects. That is not a problem in a non-pure functional language such as Scala.

handling fetching a random value for determining alien bullet firings

You can treat the output of a pseudorandom number generator as an infinite sequence (Seq in Scala).

...

Where, in particular, do you see the need for mutability? If I may anticipate, you might think of your sprites as having a position in space that varies over time. You may find it useful to think about "zippers" in such a context: http://scienceblogs.com/goodmath/2010/01/zippers_making_functional_upda.php

share|improve this answer
    
I don't even know how to structure the initial code so that it is idiomatic functional programming. After that, I don't understanding the correct (or preferred) technique for adding in the "impure" code. I'm aware that I can use Scala as "Java without semicolons". I don't want to do that. I want to learn how FP addresses a very simple dynamic environment without relying upon time or value mutability leaks. Does that makes sense? –  chaotic3quilibrium Jan 25 '12 at 22:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.