Sega Genesis/Megadrive emulator – Kickstarting the project

Standard

The project

I wanted to start writing a new console emulator for some time now. There’s still work do on my other projects — could add some fun features to Boyo.js and mr.system has not been updated in a while — but I need something fresh. I chose to try to emulate the Sega Genesis/Megadrive since it was my first game console and it’s a bit special to me.

Technically, the Genesis is renowned for its performance compared to the other game systems of its time so I will have to pay particular attention to this aspect (Boyo.js was not on the fast side). I won’t use Javascript to emulate the chips, it was too much trouble last time (no byte type, no unsigned type, needed to mask every computation by 0xFF…). However, I’d love for this project to be rendered in the browser with a nice UI for the debugger.

My first choice is to write the emulator modules in C and to compile them to JS with emscripten to benefit from ASM.js optimizations. The user interface and rendering will be done in Javascript. We’ll see how this go.

Motorola 68000 emulation

I’ll start by coding the Motorola 68000 CPU (m68k). The first step is to look at some documentation. I found a nice table with all its opcodes and this seems more manageable than the GameBoy’s Z80.

I need to think about a nice way to emulate all those instructions. Writing all the opcode variations by hand would take weeks and be no fun at all.

In my earlier GameBoy emulator, I abstracted addressing modes and instructions to factorize all the existing variations (eg. one add() function compatible with a set of addressing mode proxies). It was ok but the virtualization was bad for performance and I may not get away with this approach on this particular project (gotta go fast!).

In my unfinished Master System emulator, I generated C++ code in Python. The Python part inspected the chip’s specs and outputted all the instruction variations. Going back and forth being generator and generated code was a pain when debugging. I’d prefer a nicer workflow.

The m68k’s opcodes are coded on 16 bits so there are only 65536 possible instructions. I could generate each one of them and store them in some sort of jump table. Pseudo-code:

The generate(opcode) is the tricky part. There, I would need to parse the bit pattern of opcode and return a function executing this particular variation, with constant operands and no branching. In C# I would use code generation. In Javascript, I could use some neat tricks with closures. How to do that in plain C? I guess I’ll learn function pointers.

I looked at other m68k implementations and Musashi, a reference emulator used in Mame, seems to take this approach (see build_opcode_table). I’ll start experimenting.

 

Switching our RTS to the Entity-Component-System Pattern

Standard
This post was originally published on Insane Unity’s devblog, with both english and french versions. There, you’ll find other technical articles about Win That War!, our upcoming RTS game.

This post describes the switch of our gameplay codebase from a class hierarchy to an architecture based on the Entity-Component-System pattern (ECS). It will first explain why we undertook this refactoring and then present the new ECS framework with which we are currently developing Win That War!. The description is accompanied by some code samples as this post is voluntarily geared towards readers who are curious about the technical details of such an implementation.

The old ways

The Win That War! team is growing and the scope of the game has evolved towards a richer design than originally planned. Concretely, this means that we now need to support new game mechanics as well as new units with some unanticipated characteristics.

Some months ago, at the core of Win That War!‘s code was your typical class hierarchy. A base GameObject implemented all the shared behavior. Additional sub-classing then progressively added new functionalities to create specialized types (Fig. 1). This was all fine and dandy, until our game designer got loose and imagined fancy units such as the Command Unit. Here is an excerpt from its specifications:

The command unit is both a building and a unit that materializes the player’s presence on the game map. The player’s buildings can only operate within the range of a Command Unit and its destruction triggers the player’s defeat.

In other words, this unit must be able to anchor itself on the ground, like a building, but also to take off in order to establish new bases on any other point of the map. Behold the first flaw of the class tree, the dreaded diamond: due to the tree-like nature of our architecture, we got to a point where it was impossible to share antagonist behaviors such as being both a static building and a mobile unit.

Simplified representation of the initial architecture. The new Command Unit does not fit in this hierarchy.

Fig. 1 — Simplified representation of the initial architecture. The new Command Unit does not fit in this hierarchy.

At this point, we had two options. Option 1 was to go deeper into the rabbit hole and create a new subclass of GameObject (imagine a StaticButSometimesMobile class alongside Mobile and Static). Option 2 was to think ahead and switch to a more flexible architecture. Given the loads of other units and mechanics that are planned, it became obvious that we really needed to look at alternatives. After some consideration, we chose the Entity-Component-System pattern.

In the meantime, we settled for a quick hack: two versions of the Command Unit were coded, a mobile one and a static one, and we swapped them when landing/taking off. Let’s just say that we were only moderately satisfied with this approach. Some code had to be duplicated and having this very specific swapping logic for a single  type of unit did not sit well with us.

Composition over inheritance

The Entity-Component-System pattern is an alternative to the canonical class hierarchy. The three ingredient of the ECS recipe are:

  • Entities: the concrete instances of our game objects. For example, units, buildings, decor elements and cameras can all be entities. Conceptually, an entity can be seen as a bag of components.
  • Components: the pieces of data that represent specific aspects of the entity that they belong to. For example, position, physics parameters, 3D models and health could all be components. It is the aggregation of components that defines the nature of an entity. We call this set of components the entity’s composition. A strong characteristic of the ECS pattern is that components should only contain data and no logic.
  • Systems: the modules that govern the logic of specific parts of the game by manipulating related components (Fig. 2). For example, a Drawing system could examine the Position and Model components of entities in order to render them. A Physics system could examine Velocity components to mutate Position components. Another strong characteristic of the ECS pattern is that all the game logic should reside in systems and that systems are responsible for the interaction between components.
Entities (Top) can be seen as “bags of components”. Systems (Bottom) update them. There is a clean separation between data and logic.

Fig. 2 — Entities (Top) can be seen as “bags of components”. Systems (Bottom) update them. There is a clean separation between data and logic.

ECS is a component-based pattern with a strict separation of data and logic. The Unity game engine often comes into the discussion when speaking of components. However, the vanilla Unity approach is looser in its definition: a component (MonoBehaviour) contains both the data and the logic. Some libraries do provide an ECS layer for Unity, such as Entitas.

Here are the benefits that we expect from ECS:

  • Flexibility: it will be trivial to dynamically alter the nature of our entities. Want to temporarily buff a unit? Simply change the data in the appropriate component or swap it with another component altogether. Similarly, systems can be enabled/disabled at runtime, which is extremely useful to un-complexify the game for testing/debugging or to reproduce Minimal Working Examples.
  • Data-driven: because ECS is so strict about the separation of data and logic, we should naturally end up with a more data-oriented application. Hence, it will be more straightforward to deserialize our on-disk game data (authored by the game designer) into game entities. Similarly, it will be easier to sync this data over the network without resorting to an intermediary form.
While it was not the reason for this refactoring, ECS is also known to be performance-friendly because the underlying data structures are often layout in a way that corresponds to their processing. That is, same-type components that are processed sequentially by logic systems are contiguous in memory. Thus, the CPU cache is happy.

Practicalities

The new architecture had to mesh well with most of the code that was already in place. To this end, we designed the central data store for entities and components (the Entity Manager) to expose them in different forms to the “legacy” code and to the “new” code (which will reside in Systems).

The gist of it is that the legacy code uses stand-alone Entities with a similar API as the old stand-alone GameObjects. However, the new ECS systems leverage a more sophisticated approach in which they process views on entities that match certain compositions (each system has it own criteria).

Fig. 3 gives an overview of this architecture. Each part will be discussed in the following sections.

Our ECS architecture. The game data is exposed to the “new” code and to the “legacy” code in different forms.

Fig. 3 — Our ECS architecture. The game data is exposed to the “new” code and to the “legacy” code in different forms.

Components

We use an interface to mark a class as being a component. Notice that there is no internal references to the entity that owns the component. This is a voluntary design choice: not exposing the owner forbids indelicate programmers to access unrelated data (eg. myTransform.Owner.AnUnrelatedComponent). Even more importantly, not exposing the owner prevents to add any logic to the components that could mutate them from the inside, since their context of execution (the “neighbor components”) is unknown. The way in which logic systems do access this context in order to make components interact will be discussed in a further section.

EntityManager

The entity manager contains the meat of our implementation. It has the following roles:

  1. Managing the entities lifetime. Users have control over the creation and destruction of entities. On creation, an entity is given a unique ID by the manager. Under the hood, entities are stored in a map in which they are indexed by this ID.

2. Composing entities. Users can create, destroy, and query components. Components are stored in a matrix-like structure where rows correspond to the various types of components, and columns correspond to entities. Querying component X of entity Y is a matter of looking at element (X, Y) in this map. Tab. 1 illustrates the kind of data that can be found inside the matrix if you were to inspect its content (this article provides a nice illustration of this layout).

3. Categorizing entities with respect to their composition. The last job of the manager is to keep track of which entities match a set of user-defined compositions. In this way, logic systems can process only a subset of the existing entities and only consider components that are consistent with their work. This mechanics is detailed in the Logic Systems section.

Tab. 1 — The game data is stored in a matrix-like structure that associates component types and entity IDs. Rows correspond to component types. Columns correspond to individual entities. Changing the composition of an entity simply consists in filling its slots with other components.
ENTITIES
#1
(tank)
#2
(resource)
#3
(decor element)
#4
(factory)
Transform
  • x: 0
  • y: 5
  • z: 1
  • x: 0
  • y: 0
  • z: 3
  • x: 0
  • y: 0
  • z: 5
  • x: 3
  • y: 10
  • z: 10
RigidBody
  • type: dynamic,
  • mass: 1000
  • type: static
  • type: static
Model
  • name: "tank"
  • name: "crystal"
  •  name: "tiny_rock"
  • name: "factory"
Weapon
  • effect: "laser"
  • dmg: "5"

This structure is a good illustration of the flexibility provided by ECS. It really favors experimentation and quick iteration because, once all our components are defined, we can design entities with novel behaviors in a pinch. For instance, it’s trivial to weaponize a factory (give a Weapon component to #4) or to make some decor elements interactive (switch the RigidBody of #2 from static to dynamic) so that players can play with them.

Entity

An IEntity instance exposes methods for mutating and inspecting a specific game entity. In practice, this interface is mostly used by legacy code that has not been converted to ECS. Because its usage closely resembles that of the previous architecture (a stand-alone GameObject held all the data of a single unit/building/game thingy), we kept a similar API, which significantly reduced the amount of code rewrite.

Manipulating entities is straightforward:

The concrete Entity class that we use acts as a facade for the EntityManager. It also adds a layer of cache in order to reduce queries for the most used components, plus game-related metadata that we had to keep for legacy reasons.

Logic Systems

The last part of the architecture deals with the logic systems that update the entities’ components and run the game simulation. Let’s start by looking at the type of code that we wanted to avoid writing:

We did not want to iterate blindly through all entities (there could be thousands), filtering them away with some predicate, only to process a fraction of them. Instead, we needed a way for each system to express which types of entities it is interested in ahead of time, so that it would only process those.

This mechanics is made possible by the formulation of compositions. A composition is a user-defined class with a number of fields of type IComponent, as well as a reference to an entity that possesses said components.

A composition instance, or node, can be seen as a view on an entity, exposing only components of interest. Their creation is handled by the entity manager who is already responsible for mutating the entities and thus provides the best place to also inspect them when a change in composition happens. Basically, for each existing composition type TComposition,  the manager has an internal collection CompositionNodes<TComposition> containing one node for each entity that matches TComposition (see code sample below).

The logic systems can access those node collections via the EntityManager.GetNodes<TComposition>() method that was seen previously. They can also subscribe to two events: OnNodeCreated(node) and OnNodeDestroyed(node). The collection raises OnNodeCreated when an entity matches the composition and it raises OnNodeRemoved when an entity does not match it anymore. In this way, systems do not need to consider an entity during its whole lifetime, but only when the entity’s composition is relevant to its work.

Here is an example of a physics system written with this strategy.

In this example, the system reacts to new entities having both a Transform and a RigidBody, and it manipulates nodes exposing only those two components. A benefit of this approach is that a programmer does not need to know the inner workings of our ECS implementation by heart to write new systems. The entity manager does all the bookkeeping by tracking which entities match which compositions, and systems just have to listen to the events that it raises.

This notion of expressing subsets of entities to work on can be found in other forms in established ECS libraries. For instance, Artemis-odb lets users formulate aspects and the Ash framework lets users define nodes in a way similar to ours.

Results

After spending several months coding gameplay within this new architecture based on ECS, some conclusions can be drawn.

  • Unavoidably, refactoring a sizable codebase such as Win That War!‘s was several week’s work. Switching to this new “philosophy” also required a bit of getting used to from everyone in the team. So, all in all, the move to ECS took a bite in our schedule. However, the promise of ECS is to make up for this lost time with greater speed and flexibility during the rest of the development. It seems that ECS is already paying dividends as we now iterate more quickly on new features.
  • We had to make some compromises during the switch to ECS and chose to convert specific parts of the codebase in priority. Some aspects of the game logic still adhere to the old ways of doing things and will probably not be updated due to lack of time. And this is fine, because these parts interface well with the Entity facade that we described. In any case, the code that has been converted — as well as new code — feels cleaner. It’s just simpler to write clear, explicit code, and a lot of complex use cases just seem to sort themselves out naturally.
  • Finally, the ECS favors isolation, which is precious for testing/debugging purposes. For instance, we obviously don’t want to pull all of the game rules in our unit tests and some game mechanics that would be constraining in this context (eg. the need to be close a relay for a unit to be active) can be trivially disabled by turning off the systems that handle them.
Some components actually used in Win That War! for different units.

Fig. 4 — Some components actually used in Win That War! for different units.

To conclude, switching Win That War! to the Entity-Component-System pattern required a significative amount of work but we are already reaping some benefits. The gameplay code is more modular since various aspects of the game are now neatly decoupled from each other. Most importantly the game code feels clearer and gives us a better sense of control. For the curious, Fig. 4 shows a screenshot of Win That War! with some of the components that are actually used under the hood.

About this Command Unit trick that we had to resort to (the building version sneakily swapped for the mobile version): now we just give our unit a Building component when it lands. When the unit takes off, we replace the Building with a Motion component and all is well in the ECS world!

References

Retrogaming frenzy in Tokyo

Standard

Working in Tokyo for two months left me with some free time to explore the place. Here are some notes on the video game shops that I visited to try and expand my collection.

Super Potato(スーパーポテト)

Super Potato is located in front of the Akiba Culture Zone. Prices are generally on the high side but this place is as much a shop as it is a museum and you ought to yourself to pay it a visit. The last floor has several older arcade cabinets that you can play for 100¥ a game while munching on game-themed snacks.

Nice finds: boxed Golden Sun (GBA) in perfect condition.

Also seen: cheap broken consoles if you’re handy — a lot of game-related paraphernalia.

Retro Game(レトロげーむ)

Situated on Chuo-dori, Akihabara’s main street, Retro Game was often packed with tourists. Prices there can be downright exorbitant though. For instance, nude Pokemon cartridges are priced at 1800¥ (they sell for ~100¥ in less crowded areas of Tokyo!). It’s still fun to rummage through the shelves while listening to the ambient game soundtracks but don’t expect to find a rare forgotten gem in here.

Nice finds: boxed Yoshi no Tamago for 200¥, not so good condition but, hey, it was cheap.

Also seen: large choice of Game Boy consoles — many occidental hits (Zelda, Street Fighter, every possible Mario game), this shop really targets foreigners — a junk bin in front of the store contains items with damaged boxes, this is the only section with reasonnable prices.

Trader(トレーダー)

Trader #2 in Akihabara (picture by Diana Schnuth - https://www.flickr.com/photos/dianaschnuth/).

Trader #2 in Akihabara (picture by Diana Schnuth).

There are several Trader locations around Akihabara but the first floor of store #2 is the place to be (climb the other floors for a peek at a very open-minded Japan). Prices were generally okay and they had a lot of choice. Bonus points for the constant flow of buyers/sellers, which ensured a renewed inventory each time I came by.

Nice finds: boxed Zelda Oracle of Seasons and Oracle of Ages (GB) in perfect condition for 500¥ each.

Also seen: SEGA games, which are less common — several limited edition consoles (costly, though).

Friends(フリンズ)

Friends is a two-story shop hidden between Akihabara and Ueno. There is no store front and it’s really easy to miss if you pass the small sign on the sidewalk. On the first floor, there are many games only released in Asia that are not exactly catered to the international audience (derby and pachinko, mainly), and the second floor is dedicated to game guides and soundtracks. Reaching behind the counter to go through the boxes full of unsorted cartridges is tempting but the old lady who manages the store is likely to disagree.

Nice finds: dozens of Game Boy protection carts for 30¥ each!.

Also seen: “rarer” game consoles (Neo-Geo, Virtual Boy) — a lot of game guides.

Mandarake(まんだらけ)

Mandarake does not focus on video games but their toys are cool.

Cool toys at Mandarake.

Mandarake is a chain of stores that sells vintage toys and cultural products including video games. The Akihabara and Shibuya locations have decent game selections but prices were rather steep. Those are still worth a visit, if only for their huge Gozilla collections! If you prefer to focus on games however, try Nakano Broadway where Mandarake is split into tiny shops scattered around a big mall. There, look for Mandarake Galaxy; this one specializes in used games and its prices are quite reasonnable since it’s outside of the touristic areas.

Nice finds: I didn’t buy any games, but I found a cool Bearguy Gundam and dozens of gashapons!

Also seen: Power Gloves, It’s so bad!

Book-Off(ブックオフ)

Book-Off is a nationwide chain of bookstores that also sells used movies and games. It’s really easy to stumble into one of those shops by chance, especially around train stations. There, you may find older games, sometimes under the label “retro games” (meaning that this is going to be expensive) and other times under the label “old hardware” (cheap).  Prices and selection vary depending on the location: the Akihabara one was prohibitively costly and had a poor selection, the Shinjuku ones were nice if a bit costly. The most interesting locations were definitely outside of the city center, far from the other tourists!

Nice finds: boxed Link’s Awakening DX + boxed Pokemon Blue in perfect condition — many nude Game Boy games for ~100¥ each.

Also seen: Heaps of dirt cheap SEGA Saturn and PS1 games (japanese gamers seem very careful and most CDs were impeccable).

Hard-Off(ハードオフ)

Hard-Off is where it’s at! I first visited the Akihabara location by accident, only to find a small bin with four sad Famicom games. I left disappointed but found another store weeks later in the periphery of Tokyo and this was a totally different story: dozens of used consoles, thousands of games, low prices, they had it all! An epic day-long marathon through a dozen of Hard-Offs around Tokyo ensued and I found some really great stuff. Good times.

Nice finds: boxed Final Fantasy 6 for 500¥ — boxed Secret of mana in for 400¥ (gorgeous boxart!).

Also seen: everything, they have everything.

Mak Japan (マッkジャパン)& G-Front(gフロント)

Arcade buttons in Mak Japan. *click click*

Arcade buttons in Mak Japan. *click click*

For the arcade connoisseur, there’s also Mak Japan and G-Front. G-Front is basically a small room with a catalog of inventoried games and a guy bringing you stuff, so you better know what you came for (was not the case for me, cue the awkward “Uhh, metalu sulugu?“).

Mak Japan is a bit more roomy and you are free to rummage a bit but it’s still mostly rows of bubble-wrapped PCBs, not exactly a feast for the eyes! They also sell arcade levers and buttons if you want that real *click click* feeling.


 

In conclusion, go to Super Potato if you just want one or two souvenir games; it’s a great shop with a unique ambiance. If you can spare some time, pass by a Book-off, they are easy to find around the main train stations. If you have more time, try to steer away from the city center and visit Hard-off stores to get the coolest and cheapest stuff!

Here is a recap of some shops I visited.

Blender: Long-running Python scripts

Standard

Blender provides a Python API for extending the editor. It allows us to write operators that apply instantaneous changes to the scene (e.g. generate procedural meshes or spawn objects in a given pattern). However, those operators are synchronous by default and will block the editor while they run. So if you want to do some processing over several frames and use Blender simultaneously, you’re in a bit of a pickle.

In my case, I wanted to animate models with various 3D input devices (think Razer Hydra or Leap Motion) so retrieving their tracking data and updating the scene in real-time was essential.

One intuitive way to make this possible would be to write a minimalist operator that only starts a thread. The thread then handles the connection to the device, the data retrieval and the scene updates. Sadly, Blender is not thread-safe and the editor is doomed to crash as soon as the thread modifies the content of the scene.

A better solution is to use modal operators which modal() method is continuously called as long as it returns {'PASS_THROUGH'} (instead of {'CANCELLED'} or {'FINISHED'}). You could do all your processing in modal() but the frequency of its calls is unclear. I found that the most flexible option is to do the heavy lifting in a thread, at the speed of your choice, while modal() safely updates the scene.

Here is an excerpt from the script that was used in the final implementation to control a hand model with a Razer Hydra, a data glove and a multi-touch tablet (video).