Home About EIS →

Space Invaders Enterprise Edition

Arghh! Space Invaders in suits!

Space Invaders Enterprise Edition

Languages: This article is also available in Belarusian and German (thank you Patric and Anastasyia!)

I’m pleased to announce that I’ve released Space Invaders Enterprise Edition (Java, cross-platform executable, ~9mbs due to Drools dependencies, source code here), the first prototype program from my newly announced research direction, Zenet.

Space Invaders EE is a clone of code of Space Invaders from Coke and Code, which is a Java tutorial for how to create games. However, it’s not the game itself we’re interested in (although it is pretty fun, and big thanks to Kevin for releasing his code as open-source!)

The magic of Space Invaders Enterprise Edition is actually under the hood. I’ve separated out the game logic from the Java source into a file parsed by a rules engine. This means we can easily view the game design, without it getting muddled with too much implementation code.

Rule engines are commonly used in enterprise-level companies to decide things like how much your car insurance premium will be. Let’s start using this for something more fun!

A description of how it all works is after the jump.

Here’s a snippet from some of the rules file, written for the Drools rule engine:

Hopefully, this is sort of readable, even to the non-programmers out there. Let’s start with the first rule, which reverses the aliens. The aliens, by default, keep moving every tick a certain amount horizontally. The rule says “find me an alien, where there is an alien somewhere in the game that has hit the edge of the screen. Then swap that alien’s movement direction and move it down by 10 pixels.” The rule repeats for all the aliens in the game, eventually being fired on every one and reversing the direction for all of them.

To help illustrate the value of this, compare the “Process bullets hitting aliens” code, to the original:

Ouch! Not too readable! Unfortunately, such code is common and unavoidable in game programming. What’s happening here? Well, the code has two loops. The first loop gets all the objects in the game. The second loop does the same. When the first element of the first loop is tried, it then tests that object against all the other objects in the game to see if they have collided. Eventually, all the objects in the game will be tested against each other. If they do collide, there’s some code elsewhere to decide what to do (a bullet and an alien colliding results in them both being removed from the game).

This is exactly the same behavior at the user-visible level (thanks Andrew for the clarification) as the collision code in the rule file gives. I much prefer the rule engine implementation, and I hope you do too. Double loops are hard enough for programmers to understand, let alone game designers who we can’t assume are able to understand all the nuts and bolts of modern games programming (which is very difficult).

Space Invaders Enterprise Edition offers a different approach. By separating the game logic from the implementation, we have a game design specification that we can give to programmers and game designers, that we can read easily and be able to spot any bugs in it. Try spotting a bug in that double loop code!

I haven’t even begun to scratch the surface of the power of the Drools rule engine yet. That’s for another post, and what forms the basis of the Zenet project that I am working on. There’s more to come!

As with all my announced work, the code is open-sourced under the BSD license, so you can see how it works, modify it and re-release it without any limitation whatsoever. It’s all hosted at GitHub. It’s easy to build with Maven, and once you get going, try changing some of the rules, or adding new ones, and see how easy it really is.


About the author:  Chris Lewis is a British PhD student researching the intersection of software engineering and video game development.

This entry was posted in Academics, Games and tagged , , , , , . Bookmark the permalink. Both comments and trackbacks are currently closed.

34 Comments

  1. Michael
    Posted February 15, 2010 at 1:36 PM | Permalink

    Hey cool, thanks for sharing this code. Like it.

    Cheers!

  2. Will
    Posted February 15, 2010 at 11:43 PM | Permalink

    Sorry, but being more familiar with standard Java than the Drools framework, I definitely prefer the non-rule engine implementation. In the Drools code, we have an entirely new syntactical structure (‘rule/end’ and ‘when/then’, ‘exists’, ‘eval’) that is equally ‘unreadable’ to anyone not familiar with the Drools syntax or the underlying algorithmic concept of a production rule system. (And itself probably more complex than the Space Invaders game in its entirety!)

    Here is your Java code snippet cleaned up a bit, using modern syntax:


    for(Entity me : entities)
    for(Entity him: entities)
    if(me.collidesWith(him)) {
    me.collidedWith(him);
    him.collidedWith(me);
    }

    Not to say that Drools doesn’t offer real advantages for writing cleaner business/game logic, but they’re not self-evident in such a small comparison – I’d be interested in some more specific examples how its rule-production system enables a cleaner separation between game design/specification and implementation for large and complex projects than otherwise well-written object-oriented code would allow.

  3. Posted February 16, 2010 at 12:06 AM | Permalink

    Familiarity with Java is great! But what if you weren’t? The idea is that the rule file is given to someone with little programming experience at all. The Drools language is concise enough that you can be taught to read most rules (if not write them) in about an hour or so.

    That said, I agree it’s not the best rule file. The eval is bad, and I am a bad person for doing it (I’ve already had my wrists slapped by the Drools lead developer :) ), but I think “exists” is fairly self-explanatory. The method names could be cleaned up, and even more logic could be extracted out if I continued. The idea was to show to myself that I could do this on existing codebases, not built from the ground up. I think what I’ve implemented is a step forward, if not the leap ahead possible if a rule engine was integrated throughout the development process. I don’t advocate going all the way to rules engine extremes, I think there’s a happy medium. If you’re interested in what the extreme might look like, check out the entirely rules-based implementation of PacMan.

    Large, complex projects are definitely where the power is going to be seen. Think about cross-cutting concerns, like counting how many times an enemy is killed using a chainsaw for an achievement. Where do you put that? In the object for the enemy? In the weapon? In some score counter? Nothing is very satisfying in an object-oriented approach. A quick Drools counter would concisely express the high-level intent at a high-level, not buried in the general code.

    Think about other forms of monitoring… and if you don’t want to think, wait for my next post about the Zenet project :)

    Unfortunately, getting large game code bases is hard, so we do what we can. I looked into doing something with the Jake2 system a while ago, and could do with revisiting it.

  4. kostas
    Posted February 17, 2010 at 3:37 AM | Permalink

    Rule engines, are nothing more than interpreted languages. In fact they are less cause before the altar of abstraction, they sacrifice even more performance than your average interpreted language.
    Their sale points are totally fake, if you think that a problem at the end of day, will ALWAYS be solved by some technician (that will know Awk, C, Perl, Java, Drools or whatever) and not the management guy that somehow got convinced by some other management guy that with such a tool he will be able to solve all his problems. He won’t, not cause the tool is bad – whichever tool. He won’t cause he is not interested in the first place. He is not payed for that. He doesn’t have the time to think and analyze his problem, the details of it and possible solutions. He does another job. So he passes the problem to us.
    Which in turn will have to use a collection of tools to solve it. Whether it is writing “objects” in Java, editing XML files, compiling C sources, writing Awk scripts, “designing” on a workflow engine, it is still work. Work which barely anyone outside our domain will understand, and at the end of day, what matters most is the time spent on it. And sorry but i don’t see how these rule engine / workflow systems make the time aspect any better.
    Another thing that all these pro-rule engine people like to remind us all the time is that we are writing code and (be careful while reading this next word cause mystical powers may contact you and consume your soul) *compiling* it and how evil we are for doing so, instead of following the holy path of XML editing and workflow designing…
    Now, a bit more seriously, all i see we managed with rules engines is that we try to solve problems on a more abstract interpreted language which generally is a bit awkward, if you think that it doesn’t try to be a full programing language, accompanied with an abstract (and awkward as well) data model that typically resembles the name-value pairs idea. All that while looking down the “functional focused programming of the past”. It’s not rocket science neither it will gonna save the world.

  5. Lorenzo Gatti
    Posted February 17, 2010 at 6:17 AM | Permalink

    I’m also not impressed by the nonprogrammer-friendliness argument. Drools rules might be terse, but they are no special help for the simple algorithms needed in a game and they are still based on the usual programming language abstractions: objects (not intuitive objects, Java objects), arithmetic, sequential and conditional control structures.
    Most iterative control structures (such as processing each alien in the example) are hidden and implicit, but I think this feature might be an hindrance to code comprehension.
    The Pacman example shows even more complexity, advanced concepts and contorted idioms: the value of rule systems clearly lies in sophisticated applications that involve automatic reasoning and planning, not in basic game engine scripting.

  6. Eivind Eklund
    Posted February 17, 2010 at 7:16 AM | Permalink

    @kostas:

    Rule engines are not necessarily interpreted – take the Mercury language (http://www.mercury.csse.unimelb.edu.au/) for an example of a declarative language that’s not interpreted.

    Whether it’s easier to design this way or not, I don’t really know – I’ve not tried to work with this.

  7. MikeL
    Posted February 17, 2010 at 8:16 AM | Permalink

    Thanks for the great post. Having toyed around with programming games since my days of Basic on the Apple IIe, I know EXACTLY what you are talking about. It is inevitable that one will become lost in a morass of loops and if-then statements.

    I think the rules engine is a fantastic idea and I had thought about extracting out these sort of rules myself to make game design more simple. I spend the majority of time coding in Ruby right now, which is not really geared for games. However I think that creating a rules engine in a language like Ruby would probably be even easier to implement and make it easy to create readable rules compared to Java (though likely slower).

    This is great. Looking forward to see how it comes along.

  8. Douglas Livingstone
    Posted February 17, 2010 at 8:28 AM | Permalink

    Quick comment: “750″ and “+ 10″ look like implementation details to me – could they be expressed in terms of the game? Something which expresses “aliens reach right hand side of the board” instead of the implementation, “aliens 750px from left hand edge”.

    (Also, if you get a captcha wrong, your comment gets deleted and you have to retrieve it with the browser back button…)

  9. Posted February 17, 2010 at 10:42 AM | Permalink

    Yeah, that was a quick and dirty bit, good catch :) If you notice the commit times in the source, I haven’t looked at this code in a long time as I was waiting for some papers to be accepted, so there’s definitely some clangers in there that make me wonder what the heck I was thinking. This is one of them!

    I’m sorry about the captcha problem… the spambots got out of control, so the captcha at least limits it to the meatbots, but I didn’t know that was the behavior. I’ll have a look. Thanks for the bug report!

  10. passerby
    Posted February 17, 2010 at 10:58 AM | Permalink

    > Familiarity with Java is great! But what if you weren’t?

    Then the wisdom of employing you as a Java programmer is surely open to some question…

  11. Posted February 17, 2010 at 11:02 AM | Permalink

    It seems that you have issues with rule engines that I never discussed, but I’ll let you know why I went to rule engines for this domain:

    1. Cross-cutting problems: As I mentioned in my previous comment, lots of issues in game design cross-cut the implementation, and a good abstraction helps the code to be comprehendible, as well as leave special cases out of general case code.

    2. Speed: The RETE algorithm employed by many rule engines, including Drools, is, at its simplest form, an optimized version of a giant if-then tree. Don’t discount the value of automagic optimization!

    3. Temporal handling: This is the big one for me. Drools has a Complex Event Processing module called Drools Fusion. This lets you specify rules that have conditions over time, say “If an event happens 7 times over the next 3 seconds.” This is huge for games, as almost all games can be represented as having clock ticks (Drools lets you specify a pseudo-clock, so you could even use this for a non-real-time game like Poker). Temporal handling in imperative code is non-trivial at best, Drools makes this easy.

    They’re the three main points for me. Also, don’t discount interpreted yet… Drools loads its knowledge base into memory when its run, so you pay an upfront “compilation” cost (for want of a better word), but after that you don’t get a performance hit. But there’s a lot of value in interpreted here, you could change rule files dynamically, so if there’s a level which has significantly different gameplay, you can just swap in a new rule file rather than writing one with lots of special conditions to exclude the odd level. Or how about a game where the rules are negotiable with the player? We could invent some other GUI abstraction to Drools, and the gameplay could involve the player modifying rules of the game world to continue.

    I do agree that I don’t think game designers are going to write the rules, and I will be getting to that in a later post. My idea is that programmers write them, hand them over to a game designer and say “this is what your game does, let’s talk it over”. Right now, games of any complexity are a black-box to the designer, and that’s not a great way of working. If the game designer knew what the implementation was really doing, then she would be able to help spot problems. More eyes, shallow bugs, and all that!

    Like all aspects of software engineering, rule engines are not a panacea. You won’t see anyone advocating that (not even the Drools developers), and I don’t either. However, for my use case, I think this has been very useful indeed.

  12. Andrew Wild
    Posted February 17, 2010 at 11:21 AM | Permalink

    I’d just like to comment/caution on the comment “…This is exactly the same behavior…”. At the risk of being pedantic this isn’t ‘exactly’ the same more the perceived external behavior is intended to be the same. Having played both ways the trouble I’ve seen with rules based approaches has always been the unintended interaction of rules usually stemming from an unanticipated temporal re-ordering of when rules fire.

  13. Posted February 17, 2010 at 11:35 AM | Permalink

    Game designers aren’t employed as Java programmers. They design games. Programmers program.

  14. Posted February 17, 2010 at 11:40 AM | Permalink

    Yes, you are correct. I’ll go back and change that in the body.

    Designing rules effectively in this paradigm is something I intend to research as I continue on, I have some ideas (such as loading rules in and out dynamically), but they all need testing.

    I agree that rule engines are not without their intricacies, particularly about reordering. I have found that one can limit such things by using a workflow to try and ensure orderings are as you expect.

  15. Posted February 17, 2010 at 11:41 AM | Permalink

    I’m glad you liked it! Thank you for the kind words, I appreciate it.

  16. Posted February 17, 2010 at 11:45 AM | Permalink

    No, I don’t advocate Drools for the whole program, and I agree that the Pacman example shows an extreme that I wouldn’t necessarily go to. I know that Mark, who wrote it, finds it more readable to him, and so it could be one of those cases where some people just grok different styles, just like functional/imperative. As you can see in the code, I leave a lot of the original Java in there to actually perform the tasks of the game running, it’s simply the game logic I’m trying to extract, so we can present it to the game designer.

    The iterative control structures implicit nature is something I actually prefer, much as I prefer SQL to process data. I don’t think a lot of stuff that originally had value is being hidden here, I think removing things like double for-loops just makes my life easier.

  17. passerby
    Posted February 17, 2010 at 12:59 PM | Permalink

    Obvious joke is apparently not obvious after all. Oh well.

  18. Kirk
    Posted February 17, 2010 at 1:07 PM | Permalink

    Great post! It shows another use of rule engines. You can even use DSL to make the rules more human-friendly.
    If you have to choose between a huge if-else structure and a rule engine then choose the if-else structure. But when your logic/requisites started to change and your if-else structure becomes a if-else-switch-if-elseif-for-if-while-if-else structure then you will say “…. well, a rule engine wasn’t a bad idea after all.”.
    Of course that I’m an assembler programmer… Java is nothing but another “interpreted” language… :P

  19. James Hofmann
    Posted February 17, 2010 at 1:14 PM | Permalink

    The game appears to be buggy at low frame rates, letting the invaders “push down” multiple rows at a time.

    I tried drinking this particular form of koolaid for a time, but I’ve moved away from it. My own experience with scripting languages is: You use them so that a designer can iterate without a programmer, or to attack gameplay with higher-level constructs. Regardless, sooner or later, the designer will want…..

    …to do timed, scripted events.
    …to have several enemy types with similar properties.
    …to have enemies that break the rules in certain situations to achieve an effect(think of bosses)
    …to have fine control over the state of enemy behavior.
    …to have various groups of enemies, each group independently choreographed.

    Games like Space Invaders and Pac Man aren’t quite big enough to discover the scalability of any one approach towards all of those kinds of user stories, but the path of least resistance inevitably pushes design implementation towards a general-purpose “mutable algorithms” language. An example of how another paradigm(functional programming) finds itself getting twisted to fit: http://prog21.dadgum.com/23.html

    That said, domain-specific approaches like functional programming, a lazy-evaluated “narrative plan,” state-machine-based AI, timeline scripts, rules-based programming, etc. are useful to improve iteration over small, specific elements. And the problem with using all of this approaches simultaneously is in making them integrate with each other. “No silver bullet” seems to be a truism regardless of how powerful the concept is.

  20. caff
    Posted February 17, 2010 at 1:18 PM | Permalink

    “Double loops are hard enough for programmers to understand”

    Why would you say this? Double loops are not hard to understand. Even programmers with no formal education have no problems grasping them.

  21. David Beaumont
    Posted February 17, 2010 at 1:34 PM | Permalink

    While I agree that game designers are not hired to be programmers, I don’t see how something like ‘drools’ improves this. The example you give is hard-coding all many of magic constants into a non-Java file that cannot be refactored with the same tools as the rest of the source code. This seems like a really bad thing to me. What’s more, it hasn’t even cleanly split anything out, it’s still tying syntax (pixel position) and semantics (should we change direction).

    > Large, complex projects are definitely where the power is going to be seen.
    > Think about cross-cutting concerns, like counting how many times an
    > enemy is killed using a chainsaw for an achievement. Where do you put
    > that? In the object for the enemy? In the weapon? In some score counter?
    > Nothing is very satisfying in an object-oriented approach.”

    Only because you are making the (all too common) mistake of assuming that ‘objects’ in OO programming should have real world analogies.

    Unfortunately the space invaders example is just too trivial for real analysis as you would never need to enumerate all aliens for things like hit calculations or screen edge detection. For detecting a hit, each bullet can be mapped directly to a ‘target’ alien (or a miss) via some simple modulo arithmetic.

    In the more general (ie, complex) case where many independent agents interact with each other, you shouldn’t ever need to code directly between them, you would go via your world model and an event system of some kind.

    Counting the damage taken is a syntactic thing where you just listen to DamageEvents for each player/enemy and record the appropriate total somewhere. However this doesn’t deal with what damage ‘means’.

    You get back to ‘high level intents’ by clearly distinguishing syntactic and semantic events. Recording that you lost 10 health is a syntactic thing, but saying that when if falls below 25% you are ‘injured’ is semantic one. Keep this sort of thing neatly separated and the high level stuff will naturally bubble up to the top.

    class BasicPlayerHealthRule implements PlayerDamageChangeListener {
    void handleDamageChange() {
    if (player.getDamageAsPercent() A quick Drools counter would concisely express the high-level intent at a
    > high-level, not buried in the general code.

    With good OO design, nothing high-level should be “buried in the general code”.

  22. David Beaumont
    Posted February 17, 2010 at 1:38 PM | Permalink

    Rats, that ate my code snippet:

    class BasicPlayerHealthRule implements PlayerDamageChangeListener {
      void handleDamageChange() {
        if (player.getDamageAsPercent() < 25) {
          // this will fire off another semantic event.
          player.setState(INJURED);
        }
      }
    }
    
  23. Posted February 17, 2010 at 1:57 PM | Permalink

    Thanks for the comments, James, I’ll take them on board.

    How did you push Space Invaders down to a lower frame-rate? I can certainly buy that it probably has some nastiness when things get bogged down, and I’d like to try it out myself to see if there’s something inherent in the design that needs attention down the road.

    Thanks!

  24. Posted February 17, 2010 at 1:59 PM | Permalink

    The DSL route is definitely something I want to investigate, and its just another layer of power that Drools offers without me needing to worry, which is great.

    Great point about the if-else-switch-elseif conundrum :)

  25. concerned developer
    Posted February 17, 2010 at 2:12 PM | Permalink

    Is this a joke or not? Me and a bunch of other developers honestly can’t tell. See: http://www.reddit.com/r/programming/comments/b362h/space_invaders_enterprise_edition/

    If it is not a joke, please, for the love of god and all that is holy, find another profession.

    If it is a joke, well played, sir.

  26. Posted February 17, 2010 at 2:25 PM | Permalink

    Hmm, I went through and read all those comments. They’re interesting. To avoid having to wade into hostile territory…

    Some of the shots taken:
    * “A double for-loop is not hard” – Lots of our programming undergraduates do find it difficult to read. A throwaway comment to show some humility is not an admission of failure :)
    * “Programming is still programming” – Sure it is, but some languages more succinctly specify the domain than others.
    * “The game is crap” – I stated it was based on a tutorial on how to code Java games… I never commented about the quality, just the approach.
    * “I’m trolling” – In what way? I present an approach to writing game logic. I don’t see who I’m intending to troll here. The name is a joke referencing Drools’ normal usage.
    * My personal favorite: “He’s a British PhD student. I’m assuming he’s used to being somewhat condescending about anyone who opted to, you know, earn some money.” – Not sure how to respond to that one :)

  27. nick
    Posted February 17, 2010 at 2:25 PM | Permalink

    5 years ago, I worked at a large company who developed a system where non-programmers can manage a website. I have to say, it was fucking stupid. You’ll introduce bugs and oversights –they ended up being a group of shitty programmers.

    What if you don’t know Drool? learn it, but don’t teach it to non-programmers or someone not dedicated to programming in some way.

  28. Tobias Kuipers
    Posted February 17, 2010 at 2:56 PM | Permalink

    If rule based game design is like rule based enterprise software here’s what’s going to happen: the non-programmers do not understand or care about your rule language. So you need to get people in to write the rules. These are not developers, nor are they domain specialists. So the specialists write their “rules” in “English” and the rules team writes them in rules. And they will not perform. At all. So a third team will be hired (hopefully one of formally trained developers) to manually rewrite the rules into code that will perform. And if your lucky, it may even do what the first team intended. But I wouldn’t count on it.

  29. Scoob
    Posted February 17, 2010 at 7:58 PM | Permalink

    @kostas – I seriously disagree with your post. I work for a large corporation and developed a rule development and maintenance environment for business users. Once implemented, the business users managed HUNDREDS of rule changes through the environment WITH NO TECHNICAL INVOLVEMENT. This implementation significantly reduced turnaround time on changes from weeks/months to days, reduced costs by moving the “work” from expensive IT resources to less expensive business resources, and reduced errors because writing business rules is MUCH MORE intuitive than writing code – and no one needs to “translate” the rules to tech-speak which can also be error prone.

    I’ve dealt with people within my organization that had that attitude. Once implemented, the environment was expanded from 1 set of rules to 15 in a short period of time. Best yet, no one seems to question using a Business Rules Engine anymore.

  30. Scoob
    Posted February 17, 2010 at 8:02 PM | Permalink

    Thanks for sharing. I very much appreciate the work you’ve done…it is very cool and pertinent to something I’m working on right now.

    I’ve been actively involved in developing Business Rule Applications for 18+ years, from Expert Systems “back in the day” and have been exploring open source products. This makes Drools even more interesting than it was when it was just a professional pursuit….

  31. James Hofmann
    Posted February 17, 2010 at 10:20 PM | Permalink

    To reproduce: I had Firefox open and running five instances of Youtube in the background. That wasn’t how I produced it the first time(I had some other 100%-cpu Flash thingy locking down one core) but when I went to confirm that it was framerate spiking, that did the trick.

  32. Carsten Schlipf
    Posted February 19, 2010 at 12:58 AM | Permalink

    If you would know Drools, you won’t have posted that comment. This posting shows less than half of the functionality of Drools. There is much more behind it. Using a DSL in combination with the Drools Eclipse plugins makes defining rules very, very easy. Every Manager can do that then.

    Chris showed only the low level language of Drools. For end user that’s like using Assembler instead of a High Level language.

  33. Exdee
    Posted March 3, 2010 at 10:15 PM | Permalink

    You’ve got enough people disagreeing with you that I think you must be on to something.

  34. Craig
    Posted August 4, 2011 at 8:39 PM | Permalink

    Great post. I love Drools and highly recommend people to look into it if they haven’t already. It takes a little time to get into the right mindset but once you understand it its great.

2 Trackbacks