Wednesday, June 30, 2010

Entity system in Java: an early prototype

I have been intrigued with entity systems (ES) since reading Adam Martin's series of posts, and I started tinkering with an ES implementation since reading his Android example. I started with a game concept  using OpenGL on Android, but the mobile environment and my rustiness with OpenGL made this project slow to a crawl. A few days ago, I was inspired to revisit one of my favorite game ideas, and after about two or three days of tinkering, I have a nice framework put together.


Just about four years ago, I led a seminar on game engine design. My inspiration that Summer was to explore the interplay between design patterns and game development. To this end, I created EEClone, a simplified clone of the incredible and addicting Every Extend. EEClone's design explicitly features patterns, although I was careful not to wedge pattern reifications where they did not belong. I consider this project a success, and it led to a series of scholarly articles and a fascinating research direction. I have been considering ES for a project with potentially much greater impact, and so I decided to revisit my cloning of Every Extend gameplay, now with the purpose of exploring ES implementations.


Here is what it looks like in action.





The entity manager is very similar to Adam's, and I'm grateful for his implementation sharing. For me, the most significant challenge was determine how to slice the problem up into components and systems. Keep in mind that in an entity system, components are "dumb" data objects and systems operate over components.


These are the components that I used. [EDIT: I did some refactoring the morning after this post, and the changes are reflected below.]
  • Explodable is a tag component that indicates that the corresponding entity should explode if it hits an explosion.
  • Exploding indicates that an entity is exploding. Contains the max explosion radius, rate of expansion and decay, and whether the explosion is expanding or collapsing.
  • InputExplodable is a tag component that indicates that the corresponding entity can be blown up by direct player input.
  • InputMovable indicates that the entity can be moved by direct player input.
  • PhysicsMovable holds a vector that represents the direction an entity is moving.
  • Position is a position in space, consisting of x, y, width, and height.
  • PrimitiveRenderable has a shape code and a color, indicating that the entity should be drawn with graphics primitives.
  • Renderable has an Image and indicates that the entity should be drawn as an image sprite.
These, then, are the corresponding systems:
  • ExplodingSystem processes Exploding things, scaling them to the right size (i.e. changing their Position), handling the transition from expanding to collapsing, and removing the corresponding entity when the explosion is complete.
  • ExplosionCollisionSystem looks for intersecting Exploding and Explodable entities, replacing the Explodable ones with Exploding ones.
  • KeyboardInputSystem monitors the keyboard and processes InputMovable and InputExplodable entities accordingly.
  • PhysicsMovementSystem goes through all the PhysicsMovable entities and updates their Position based on the their PhysicsMovable velocity vector.
  • PrimitiveRenderSystem draws PrimitiveRenderable entities at their Positions based on the shape and color in the PrimitiveRenderable component.
  • RenderSystem draws images at the corresponding Position baed on the image reference in the Renderable component.
Obviously, some of those names are ripe for refactoring, but this is an accurate representation of the build in the video. To give you an idea of what the implementation feels like, here is the code that creates the crazy guy you control with the keyboard (Boognish), using some method chaining:
manager.createEntity() 
        .add(new Position().x(320).y(240)) 
        .add(new Renderable().image("boognish.png")) 
        .add(new InputExplodable()) 
        .add(new InputMovable().speed(120))
        .add(new KeyboardExplodable());

I started writing this code a two weeks ago or so. Then based on the comments in my other post, I decided to try the Game Object Component System (GOCS) approach described by Chris Stoy in Game Programming Gems 6. In a nutshell, GOCS hits the same pain point as ES, but in GOCS, game object components are regular "smart" objects with their own methods, so there is not the ES distinction between the component and the system that processes it. As I started working on the GOCS code, I kept coming back to the arguments for ES and ended up along the path to simply re-creating my incomplete ES demo. GOCS is now back on the shelf, and I feel like after weeks of off-and-on contemplation and a few days of coding, there's something about ES that has clicked with me.

I am considering spending another day or two with this code to try to make a more compelling example, a real playable game that I could use as a case study in my class next semester. However, even coming this far, I feel like I have a better grasp on how to decompose game elements into components and systems, perhaps well enough to begin work on the technical specification of the Morgan's Raid game.

Saturday, June 26, 2010

Agile methods and project management: the design of a project-oriented undergraduate game programming course

Earlier, I wrote about software architectural concerns for a course I am teaching in the Fall. In this 15-week course, I will be directing a team in the production of a history education computer game intended for Indiana's fourth graders. Specifically, the game explores Morgan's Raid of Southeastern Indiana. The game has already been designed, and I'm in the midst of writing the technical specification now. This tech spec will be used by the students involved in the game's production in Fall.

I am approaching this project with a modicum of trepidation. I have taught game programming courses in the past, managing teams of (if my memory is correct) five, four, and nine students. I have 30 students enrolled in Fall, an order of magnitude beyond the size of any team I have managed before. Beyond the sheer number of students, the distribution is not ideal: there will be ~30 Computer Science majors in the formal class and one Art major producing graphics. The artist is supported as an Honors Fellow and so can work up to 10 hours per week. Rather than dwell on what I would like to have, I need to focus on what to do with hand I have been dealt.

I have engaged in many conversations about this course, and I have received some wonderful ideas from both friends and friendly strangers. I am writing this post in order to foster further discussion with any interested parties and stakeholders, but before I go into the advice I have received and am considering, it is worth listing the invariants:
  • There will be 30 undergraduate CS majors and minors of mixed experience level. They will have taken at least the standard foundations courses for my department: CS1 and CS2 in Java, Discrete Math, Calculus, and Data Structures & Algorithms, also in Java. Most will have taken some upper-level courses, but very few (maybe only one) will have taken software engineering. By my guess, about one-third of the students will have been involved with a semester-long software development project in the past, mostly from either software engineering courses or my HCI course.
  • The class is scheduled for one-hour meetings at 2PM three times a week: Monday, Wednesday, Friday.
  • The class is scheduled to meet in a conventional classroom. Thirty people in one of those rooms is very tight, making group discussion awkward though not impossible. We do not have any single lab where the class could meet regularly.
  • I have to assign grades to the students.
  • I cannot "fire" a student who satisfies the prerequisites and is enrolled, though students may drop the class without notifying me, until about halfway through the semester.
  • We do not have a dedicated persistent space, although there are CS major labs that can comfortably sit 10-15 students at a time.
  • I do not have tenure.
In addition to the invariants, there are some possibilities:
  • We may be able to occasionally use the Schwartz Digital Complex learning pods room, which has six long tables for meeting and the capability to share screens across tables.
  • I may be able to recruit some additional artists and musicians through colleagues' courses in other departments, or potentially on-the-side work by students who want to enhance their portfolios.
  • There is a lab being renovated this Summer for use by students doing research-oriented coursework, primarily undergraduates involved in independent studies. We may be able to co-opt some of this space, but we would not have exclusive use of it (e.g. there are lots of whiteboards in the labs, but we cannot assume that what we write there will stay there for long).
I have not yet finished the technical specification, but right now, these are the specific technologies that I would like to incorporate:
Without further ado, here are some of the project management ideas that have come up in my discussions. More accurately, these are the distillations of numerous discussions as well as readings and previous teaching experience.


The students are working for me.

On the first day of class, I intend to inform the students that they are working for me, and they are obligated to work a minimum of 10 hours per week on this class. Experience has shown that students often balk at this, though I mention it in all my classes. The math is simple: 12 credit-hours is a full-time student; 40 hours per week is a full-time job; this is a 3 credit-hour class. What they get in exchange for their effort, of course, is involvement in a very cool software development project that will be distributed throughout Indiana and beyond.

A colleague in Art runs a true studio-based learning environment. He was concerned that, although his students had developed significant technical skill, they had not yet understood deadlines and time management across projects. His solution: pink slips. Early in the semester, in order to establish the tenor of the class, if a student did not meet expectations or deadline, he would literally give them a pink slip and tell them that they lost their job and will be replaced by someone who respects the team. Of course, this was really a teaching moment---he could not actually fire students any more than I can. However, he said that students understood the message and, from then on, worked more explicitly at managing their time.

Along these lines, I am still considering the educational implications of the quotation from Alistair Cockburn that I wrote about earlier:
Use an agile process with the smallest number of people possible to get the job done; let the rest of the people do anything they want just so long as they don’t interfere with the progress of the development team. (From Agile Software Development: The Cooperative Game, second edition. Emphasis in original.)
Several colleagues whose teaching I admire have recommended naming the group to remind the students that this is not a conventional class, but rather a collaborative production effort. To this end, I would like to have a catchy name for our studio along with a professional-quality logo. It would be nice to have student input on this name, but it's not worth the time it would take to hold a class discussion. I see two possibilities:
  1. Come up with a name and a logo this Summer and introduce students to it on the first class meeting. This will go along with the mental model of the students' being hired into the studio.
  2. During the first week of class, push all of this discussion into Google Wave, including gadgets for voting. This will get students used to using Wave for collaboration, including the use of extensions.


Students, teams, and roles

Students will work in teams, because that's how software is built. The bad news is that approximately half of the students will have no team work experience. The good news is that most of those who have worked in teams did so in my HCI class, and so they had a trial by fire.

Ship It provides very straightforward advice regarding a critical team component: have a tech lead, someone who has one foot in management and one foot in technical implementations. As for who is the tech lead, I plan to have students apply for the position. I have not met with anyone who has tried this approach in an undergraduate class, but the concept has met with approval of respected colleagues who teach project-oriented courses. I will need to clearly articulate what a tech lead's responsibilities will be, of course, so that students know what they are getting in to. Also, since I cannot pay them any more, I need to make it clear what the benefit is, both in terms of investment (e.g. resume-building) and short-term gains (e.g. grading policy). For example, one of the tasks of a tech lead would be to provide his/her own team members with periodic formal evaluations: these should be incorporated into the grade of both the evaluator and the evaluated.

I am currently torn between social or functional team formation. (These are terms I am making up; let me know if there is a more standard expression for this, PMs out there.) A socially-formed team would be formed by students who know each other or believe they can get along. This is appealing since efficiency and effectiveness of communication seem to be the main bottlenecks in software development. Socially-formed teams could decide amongst themselves what kind of tasks they would like to tackle. Functionally-formed teams would be formed of students who share a common interest, and that interest would determine what tasks they take. For example, students interested in the game UI could work together on the "UI Team", and there is now a more obvious development of team expertise in one area of the production. One of the complication of functionally-formed teams is that it presupposes that I know the relative efforts required for various game features, which I don't. All the advice I have found is industrial and so focuses on the relative numbers of people needed to get the job done; none deal with the university oddity of having to deal with whoever signs up for the course.

A colleague in architecture suggested that there are two clear ways to promote progress with student teams: competition and collaboration. In a purely collaborative model, each team has a part of the solution, and their desire to create and to be good citizens leads to success. In a competitive model, teams work on the same parts of a solution, and the best among them is chosen for the deliverable. With 30 developers, it should be possible to adopt a competitive model, but I worry that those students whose solutions are not incorporated into the milestones will lose heart. On the other hand, if a team is given a module that is required for the milestone, and that team fails to contribute anything useful, then the collaborative spirit of the whole team is brought down. So I am left with the question, how much redundancy is appropriate?

Team size is another issue on which I am uncertain. I need to have clear communication with all of the tech leads, and so there cannot be too many of them. For example, if every team had three members including one tech lead, then I would still have ten tech leads to meet with and ten teams bidding for tasks. Of course, teams can easily get too large as well. There is an agile solution here, which is to allow for team reformation and role swaps during the semester, but I would like to have a starting condition that is representative of good practice.



Agile and Scrum.

There are too many unknowns not to be agile. I previously wrote about Alistair Cockburn's statement that, given a team of all novices, agile is practically the only way to secure success.

Last time I taught the class, I managed the team of nine students using Scrum, following the advice from The Scrum Primer. We managed our product backlogs and sprint backlogs using an OpenOffice spreadsheet, and we started each class meeting with a "daily" (twice weekly) stand-up. This worked well with nine students in a twice-weekly, 75-minute metings, but it will not scale to 30 students in thrice-weekly, 50-minute meetings. Fortunately, Google Docs is here to save the day. Its seamless sharing of documents gets us as close to a public, persistent information radiator as we can get. We used Google Docs in my HCI class last semester to share MSF-style risk matrices within teams and with the instructor and teaching assistant, and it was a fantastic experience.

One of the professional developers I met at Google I/O referred to the "bidding" process of Scrum, with which I am not familiar. The way we handled tasks in my previous offering of the class was informal: whoever spoke up first got it, unless someone else challenged it. If I understood this developer correctly, though, they used a model where individuals or teams would bid on the number of hours it would take them to complete, and whoever gave the best estimate got the task. This is an interesting idea, but it assumes that the bidders have reasonable estimates. Conversely, one of the best results of the last game programming class was that students got better at estimating: they were quite poor at the beginning, and most had never had to formally estimate effort before. This learning was evidenced by the product burndown charts, which started very erratic, but did actually approach linearity towards the end of the semester.

One of the most overt practices in many agile methodologies --- and Scrum in particular --- is the daily stand-up meeting. Unfortuantely, it is impossible to enforce daily stand-ups among student teams, especially with class scheduled MWF. My hope is that teams will conduct informal stand-ups via Wave or other communication technology on Tuesdays and Thursdays, and that proper face-to-face stand-ups can be held within each team during regularly scheduled meetings. This is another area where Google Docs comes to the rescue: it's straightforward to put sprint burndown charts into spreadsheets and have students update their estimates each day. Team managers can keep track of whether their team is updating their estimates, and as an instructor, I can easily scan a column and see if any team has a pattern of failing to update their estimates and take action. Failure to update an estimate also has very little impact on the overall project management process, since an empty cell can be assumed to have no change since the previous estimate.

During face-to-face meetings, individuals will be responsible for giving their stand-up reports to their tech-lead-cum-Scrum-Master, and these students will give their stand-up reports to me. This allows for a convenient filtering of obstacles: if a student tech lead has an inkling of how to remove an obstacle from the team's path, he or she is free to do so. If not, then it gets quickly reported to me, and I can design an appropriate intervention.

In this model, I share the role of Product Owner with my research collaborator and project co-director Ronald Morris, but I also serve as a sort of Scrum Master of Scrum Masters. I attended a workshop at CCSC:MW a few years ago in which Dean Sanders described using Scrum in a systems analysis and design class, and he would literally wear a different hat depending on whether he was acting as professor, Scrum Master, or Product Owner. (Incidentally, this was the first time I heard about Scrum and its use for agile teams in CS education. CS education conferences are a great place to share these ideas, so I'll see you all at CCSC:MW 2010. Why yes, I am publicity chair of that conference.)

Thanks to Google, I serendipitously came across Clinton Keith's new book, Agile Game Development with Scrum, and my copy is already in the mail. Hopefully it will contain some more tips that I can adapt into the university environment.


I am the lead architect.


Even though we're agile, there is no misconception that assumes the absence of documentation or architecture. I am still doing significant design work up front regarding the core system architecture. This comes from Tim Ryan's advice for game design documentation, which I have also written about before. A lengthy discussion of software architectural concerns can be found in my previous post.

I am also planning on providing some boilerplate code for the architecture, which will provide a concrete example of good programming practices, including documentation, modular design, and unit tests. As mentioned before, these concepts will be new to many students, and so providing this code will allow for bootstrapping for less-experienced students. For example, I am considering leaving out some simple functionality from the code that I provide specifically so that teams can explore the space where the various technologies meet and also achieve a "little win" to build their confidence. This follows more advice taken from Cockburn's Agile Software Development book: start with a task that you know you can complete, then build an end-to-end prototype (i.e. walking skeleton), then prioritize by story points.


 Class Meetings


A future post will explore pedagogic implications of these designs, but allow me to say for the time being that this learning experience is being designed according to principles of project-based learning, along the lines of studio-based learning and 

legitimate peripheral participation. To me, one of the most inspiring aspects of legitimate peripheral participation is that apprentices learned more from practice with masters than from any explicitly didactic methods. 
With this in mind, then, class meetings are simply team meetings, and what we have to learn is completely reified in what we have to do.


Even though I believe that this is the best approach for this learning experience, it makes me a little nervous due to the departmental and university culture. Although the administration has made laudable efforts to promote the "Immersive Learning" brand, many faculty members --- including my departmental colleagues --- have different philosophies of education. Studio-based methods within pure project-based learning environments may cause ripples in the year that a decision is made about my tenure!


Closing Remarks


I am grateful to all those people who shared course design ideas with me, and I am excited about integrating some brilliant ideas about both software development and the science of learning into this experience. This novella of a post has taken me hours to write, but it has allowed me to crystallize many of the ideas that have been floating around my mind, and to identify the areas in which I still am uncertain.

I welcome feedback on all aspects of the course design. Loyal readers will be treated to a few more posts during Summer planning, and then regular reflections during the Fall semester.

Friday, June 25, 2010

Entity System vs. OO Game Engine: Considerations for teaching undergraduate game programming

In Fall 2010, I will be teaching CS315: Game Programming. The course is already full, with 30 undergraduate Computer Science majors enrolled. This Fall, the course will be a continuation of my History Education Game Design research project --- a collaboration with Ronald Morris in the History Department --- and the students will be implementing the Morgan's Raid game.

Last Spring, Ron and I led an honors colloquium in which students contributed to the design of the game. The results were not ready to move directly into implementation, and so I have invested significant effort this Summer revising the design documentation and writing the technical specification. These are both works-in-progress, although the design documentation is nearing completion. I have postponed writing the technical specification until I have been able to settle a major design decision: whether to use an entity-based or an object-oriented implementation strategy.

The object-oriented approach is the conventional approach, a common road to take and also the way I have always taught the class in the past. In fact, the whole course was created as an exercise in teaching design concepts through game development. For the past several semesters, we have written games in Java using Slick, and these technologies promote an OO approach. (More information on this approach can be found in my paper, "An experience report and analysis of Java technologies in Undergraduate game programming courses.")

The complications of the OO approach are well articulated in Mick West's article, "Evolve Your Hierarchy." Briefly, one tends to end up with overloaded game logic objects and complex inheritance hierarchies. That's why West advocates the Entity System (ES) approach.

I first read about ES development on Adam Martin's blog, where there is an excellent series of articles on ES for MMOG development. More recently, he posted an example implementation of ES on Android, which I found compelling enough to copy into a little hobby project to get my feet wet with this approach. The core tenet of an entity system is that each game logic object is implemented as an entity, which has a unique identifier and nothing else. An entity manager associates components with entities, where a component is a "dumb" data object that holds just enough information for it to be processed by a system. For example, consider rendering: those entities that can be drawn have a Sprite Image and Position component, and the list of such entities can be sent to the Rendering System, which draws the corresponding image at its indicated position. There is an intentional similarity to relational databases, where: the entity is the primary key; each component type has a table of component-tuples; selection of entities with specific components is a query; and the systems are the procedures that operate on the query results.

That's a rough overview of what ES is, but not much about what it's good for. The main benefit of the ES over the non-ES approach is that there is a clear separation of concerns: there is no overloaded GameObject class that can do everything under the sun: update position, render itself, simulate physics, score points, blow up, execute scripts, etc. It's important to realize -- and explicitly pointed out in Adam's post -- that the ES approach is not non-OO. Rather, all the benefits of OO design can still be reaped, but it's done in the design of the systems, not the design of a game object class hierarchy. This is one of the most appealing things to me, as a member of the "extends is evil" camp. That is, I always prefer to use and to teach delegation and interfaces over inheritance. However, I am still a novice with the ES approach, compared to my years of study, teaching, and practice with OO and patterns, and so I am uncertain how to most effectively design ES components and systems. Searching the Web, I have found a few scattered discussions on ES development but nothing remotely close to the maturity of discourse regarding OO design principles.

I am very interested in creating an ES system so that I can learn more about it. I'm not confident in my ability to write an accurate technical specification based on ES design methodology. It is worth noting that the game itself will be a 2D game in which the player clicks on cities on a map to move Morgan from city to city. There are not a lot of moving parts, and so the scalability of ES is not critical.

It is useful to look at the perceived benefits and disadvantages of these two approaches for this particular project with my students.

OO Advantages

  • It's what the students ostensibly know.
  • There is a wealth of information on how to design OO systems.
  • I have significant experience using and teaching OO approaches.
OO Disadvantages
  • The student's don't really know OO. They think they do, because their intro text books talk about OO, but except for the handful of students who have already done their senior software engineering course, they will hold a strong misconception that they know OO. This means that students will likely make lots of mistakes without knowing they are making them.
  • Using OO for the game objects can -- and probably will -- result in an overloaded GameObject that some team of students will have to maintain, or that multiple teams will get into inconsistent states. Even a good source management system is not as good as avoiding conflicts in the first place.
ES Advantages
  • The various parts of the game can be separated into systems, and each student team can be given a different system to work on. Because ES systems are architecturally orthogonal, this makes it easy for each team to work within a relatively safe sandbox. I can also use this to encourage unit testing of systems prior to integration testing.
  • Because the systems will still follow OO design principles, we inherit the benefits of OO.
ES Disadvantages
  • Because the systems will still follow OO design principles, we inherit the disadvantages of OO, except for game object overloading.
  • Because the systems will still follow OO design principles, we have a multiparadigm system. Many of the students have only been programming for about 1.5 years, and they have only seen one language and approach. Dealing with the ES + OO, as well as the other tools I intend to use such as unit testing and continuous integration, may be cognitive overload. This is not a certainty, but it is an identifiable risk with negative consequences, namely leaving us without a completed system to field test in Spring.
I had hoped that writing this would help me come closer to a decision, but I think it has shown me that I have been leaning towards ES all along, primarily because of the first advantage that I mentioned. The prospect of leading a team of 30 novices in a significant development endeavor is unsettling, but it seems that the ES architecture gives rise to a natural separation of teams. My other concerns about dealing with such a large team will be addressed in a future post on software development methodologies and project management techniques.

I welcome any feedback that people have about the ES v. OO issues, both from game implementation and teaching perspectives. I found blogging to be an excellent venue for reflective practice on teaching last semester, and so you can expect regular status reports in the Fall, regardless of which approach we take.

Blog Hop

Back in November 2009, I decided to start a blog as a form of reflective practice, particularly for my teaching. The advice I read at the time said to go with either Wordpress or Blogger, and I chose Wordpress. That blog is available at paulgestwicki.wordpress.com. While I found it a good place to do some writing, I did find some of the editing tools to be awkward.
This post marks the beginning of an experiment with Blogger. I'll have to try writing something more substantial --- especially something with formatted source code --- to see if I like this any better.