Putting some engine under the game

Don’t say I didn’t warn you

It’s time for that post about the actual design of MicrowaveJava as a game that I promised you. If you haven’t read the first post about this tech demo I recommend you read that so you know what this is even about. The gist of it is that MicrowaveJava is an experiment in making Java applet games and running them in modern browsers without Java support. The last post was about doing that, this post is about what I did when I got there.

A Tale of Two Stacks

Starting with nothing but a JVM and an applet frame gave me a lot of freedom in the fundamental design of how I wanted my game to run. This naturally led to me trying out design techniques I’ve wanted to implement for a while. The first of these is the state stack.

The state stack is built on the idea of a finite state machine. If you’ve used RPG Maker and dug into the Ruby code a lot, you’ll know it uses a finite state machine but it calls its states “scenes”. The idea of a finite state machine is that the game is divided into some (finite) states (state), each state defines some game logic, and you can transition between the states (machine). For example, a game might start in the menu state, move to the load game state, which moves you to the overworld state. If you encounter a monster, you move to the battle state.

This works well, but it can fall over when you try to do certain things. For example: if you encounter a monster while you’re already fighting a monster, what happens? You can’t transition into the battle state because you’re already in the battle state. If you did enter the battle state, it would clobber all the internal data of the battle state and lose the information about the battle you were just fighting. And what if you encounter a monster in the main menu? You transition into the battle state, fight the monster, and then transition back into the overworld state. But you weren’t in the overworld state before. The path back through the state machine isn’t preserved, so you can’t know for sure in these situations where to go after a state has concluded.

The stack

The solution for this is the state stack. It modifies the finite state machine by keeping a stack of all running states rather than just keeping track of the currently running state. When you want to transition into a state, you push it onto the stack. When a state concludes, it is popped off the stack and the state underneath continues. Now you start in the menu state, push on the overworld state, encounter an enemy and push on the battle state. Now if you enter a second sub-battle during the battle, you simply push a new battle state onto the stack, on top of the battle state currently running. The sub-battle proceeds as normal and, when it concludes, it is popped off the stack and execution continues in the main battle. When that concludes, it too is popped and the game returns to the overworld state waiting underneath. You exit and the overworld state is popped off returning you to the menu. You press quit on the menu and the menu is popped off leaving an empty stack, indicating that the game has ended and the program should terminate.

This is great, but while setting up new states leaves ample opportunity for a state to pass information to the state it is transitioning into, it doesn’t give a means for an executing state to pass information back to the state that called it when it concludes. You could give each state a resume method which accepts data returned from the state atop it but ideally this data would be passed directly to the point in the code that called the state in the first place. For that you would need a continuation to define where the code left off and how to get back there as well as a means to pass data to that continuation. In fact, you would need a whole parallel stack of these continuations for each state called. Thankfully Java has a built in system for managing a stack of continuations which accept data. It’s called the call stack.

We have stack at home

It’s important to remember when working with stacks that your computer already has the call stack and that the call stack is very powerful. To that end, when pushing a new state on the stack in MicrowaveJava, it does not simply continue executing the update loop on the new state. Instead it starts a new update loop for the new state. The call to runState doesn’t return until the state passed to it concludes, passing execution back to the state below and providing return data back as the result of the call to runState.

Each state is defined as an object extending the class State<T> where T represents the return type of the state. The return type of the state is not the return type of the state’s update method, however. Instead the update method returns Optional<T>. When the update method returns empty, this signals to the engine that the state has not concluded and that update should be called again. If the method returns something, this indicates that the state has concluded and runState can pass the result back to the calling state.

Is that a good idea?

This interesting and apparently circuitous path of execution brings up important questions of why a state stack is needed in the first place, and why flow control needs to be managed by an object separate to the state at all. Why not just call a method on the state that runs its own update loop and returns when it’s done? I don’t have an especially good answer for this. There are some advantages to the current system though. The Game object which manages states and flow control also manages resource loading, input, music, and sound. It also provides a means for the surrounding program to query information about the running state. These aspects are what allows the frame timer and menu bar to function in MicrowaveJava. Additionally, it allows for transparent states like Hell’s GameOver state to render the states below them without any state needing a reference to its calling state.

The true tragedy of the state stack with returns implemented here is that is isn’t really used. The return value of a state is only used once in the entire program. Hell’s game over screen waits for the user to press either fire or exit, and then passes data back to Hell’s game state to tell it whether it should restart or exit respectively based on that input. Other than that simple example, no other state even reads or stores the return value of runState. A feature fit for a more complicated game I suppose.

Breaker: an exercise in brute force and ignorance

There are in essence two games included in MicrowaveJava: Breaker, a primitive breakout clone; and Hell, a primitive bullet hell. Breaker was developed first and based on the principles of brute force and ignorance. The primary goal was just to get something displaying on the screen and something playing on the speakers and for it all to react to user input: the fundamental qualities of a video game.

Breaker has, in essence, no engine and no design. There are no game objects or entities in breaker. There are bricks, defined by their bounding box; balls, defined by their position and velocity; and items, defined by their sprite and the code they execute upon being collected. Early in Breaker’s development, the position and velocity of the ball were stored directly and there was no support for multiple balls. Paddle position and size is still stored this way.

All game logic takes place in a single massive update function totaling over 150 lines of code filled with if statements and for loops. The first thing it does it iterate the array of bricks to see if there are any left. If there aren’t, it regenerates the field, deletes all the balls and items and sets the launching flag to true. The ball you see on the paddle when launching isn’t a real ball, it just renders there when the launching flag is true. After that is input handling. Left and right move the paddle, fire launches a ball when the launching flag is true. Exit exits the game. I tell you this minutia only to highlight the caveman nature of this game code.

After input we get into what is probably the most interesting part of the game: the collision detection. Collision detection uses a circle-AABB sweep that operates by inflating the AABB by the circle radius and sweeping a point against all four sides of the box as line segments. Since the path of a point moving in a straight line is a line segment, this is just a line segment intersection calculation. What all this means is that it is impossible for a ball to pass though an object in the case of lag or fast moving balls. It also means that if a ball heads for a corner of a brick, it will always bounce the right way based on what side of the block it would hit first. It’s almost certainly overkill for this application, but I like a bit of very resilient collision code every now and then. Ask me about my 3d AABB-voxel grid sweep sometime, it’s a lot more complicated than you might think.

Hell: real game design this time

Breaker is implemented using a grand total of 9 classes, 4 of those are for collision alone. Hell uses 34 classes not including nested classes and lambdas. In part this is because Hell is a more complex game. A large part of this is that Hell doesn’t cram everything into a single update method (kind of). The most obvious difference between Breaker and Hell is Hell’s entity component system system. I say system twice because it is a system comprised of entities, components, and systems.

Of Entities, Components, and Systems

If you haven’t heard of ECS, I highly recommend watching Scot Bilas’ 2002 GDC talk A Data Driven Object System as it’s what helped me understand how they work and why you would want to use them. In short, there are entities, components, and systems. Components have data about an entity, systems define behavior for entities, and entities only kind of exist.

A reference-only type

In an ECS, there isn’t actually a need for a concrete representation of an entity. Indeed my implementation represents entities a long which defines its entity id, and Bevy does something similar. The reason that entities can exist, or not exist, in this way becomes clear when you understand how systems interact with components.

Vale pojo qui est faba

Components are just objects. Each entity can have at most one component of any given type, for reasons that will become obvious later. This is the only invariance that needs to be enforced for ECS to work. If you so choose, you could enforce that all components must be Java Beans. This could be useful because it would allow for any component to be serialized and sent over the network in a multiplayer game. Components can hold data but they don’t have to. Dataless components are useful for reasons that will become obvious later as well. Components importantly don’t define behavior. I break this rule a few times in Hell; I can’t get away from the fact that this is a hacked-together tech demo.

The important bit

Systems are the heart of the ECS. They define all your game behavior. The really interesting part of the system is the query: each system looks for a certain combination of components on an entity, that is, when the ECS wants to run a system, it queries for each entity that has a component of each type needed by the system and runs the system for each entity that matches. In my system, this is achieved by a map from the component class to a list of entity id-component pairs. This is why entities don’t need a concrete representation: their id is used to associate some components together, but other than that, the entity doesn’t exist. It’s also why an entity can only have one component of a given type, you can only pass one component to a system as a result of a query. There are probably some workarounds that can allow for more than one component of a given type on an entity but frankly I’ve never seen much need for it outside of very odd and specific circumstances. These queries are also the reason why dataless components are useful: they can be used as a marker on an entity that a system can query for.

What makes ECS really powerful is that a system query doesn’t care or even look at other components on an entity. This means you can just keep adding components to an entity and defining behavior based on those components without this behavior interfering with each other. You can also create new behavior without adding any components by defining new systems that query for existing components. This makes ECS extremely expandable and the obvious choice for any game wanting to support addons of some kind, as the addon can define new components and systems without interfering with any other addons. Optional integration with other addons is practically built in by default by having systems that query for components from that addon which will never run if those components aren’t on any entities because that addon isn’t available. I say practically because you would still need to avoid the JVM trying to load the class associated with the component from the other addon.

Putting it together

A good example of how this works exists in Hell: The system that handles MoveTo. MoveTo is a component that stores only a target position and a speed. This system moves the entity towards that destination at that speed.

ecs.query((e, os) -> {
    Transform t = (Transform) os[0];
    MoveTo m = (MoveTo) os[1];
    Vec2 delta = m.dest.minus(t.position);
    double dist = delta.magnitude();
    if(dist == 0){
        ecs.removeComponent(e, m);
        if(m.then != null){
            ecs.addComponent(e, m.then);
        }
    }else{
        Vec2 dir = delta.normalized();
        double rot = atan2(dir.y, dir.x);
        t.position = t.position.plus(dir.times(min(dt*m.speed, dist)));
        t.rotation = rot;
    }
}, Transform.class, MoveTo.class);

ecs.query takes 2 arguments: the system to run and a variadic argument for the classes of the components which make up the query. The query has to come after the system because variadic arguments have to come as the last argument in Java, a failing many languages share. In my opinion, this issue is solved fairly easily by just ending the variadic argument on the first argument that doesn’t match the variadic type. This would of course require that the argument immediately after a variadic argument be of a type incompatible with the variadic’s type but I digress.

This system queries for 2 components: MoveTo as explained earlier, and Transform which holds a position and rotation of an entity. An entity doesn’t necessarily have a position or rotation, not having one by default. An entity with no components doesn’t have any associated data or any representation in memory. Transform is a regular component just like any other, though it is the one used on the most entities in this game. If an entity had a MoveTo and no Transform, this system would not run on it, as the query would not be met.

The system itself is a functional interface that takes the entity id as a long and the components as an array of objects. If Java supported variadic type arguments (a feature I have never seen a language support), this might be a lot cleaner, but as it is this seems an adequate solution. The first thing the system does is extract the components from their object array prison, a move so natural to Java that it doesn’t even create an unchecked cast warning to do this. Next it does the expected math to move the entity towards the destination but not overshoot it. Once the entity has reached its destination, the MoveTo is removed having served its purpose. This system will no longer run on that entity as it will no longer satisfy the query.

The Future

I think there’s a lot left to be done. These tech demos are fairly primitive and don’t stretch the systems they’re built on very far. I hardly use my special state stack and I don’t feel I used my ECS to its full potential. There are a few things I’d like to try in future projects that build on the technology of MicrowaveJava, though I make no promises on any of them.

Multiplayer

ECS has a lot of potential for multiplayer. You can imagine having some components marked as synced which are automatically serialized and sent over the network whenever they’re modified. You could have a component called LocalAuthority to mark when an entity is owned by the current executing ECS context and thus should be modified and those modifications sent to other parties. The wire format would be as simple as entity id-component pairs that would be integrated in the receiving ECS.

Here’s how I would imagine that all integrating, keeping in mind that I haven’t implemented any of this.

Firstly, synchronized components would be Java bean classes marked with a @Sync annotation. Whenever a system made a query that included LocalAuthority, the ECS would know that it needed to track changes and inform foreign parties (the server if we’re a client, the client if we’re a server, other clients if it’s peer-to-peer). It would do this by looking at components in the query marked with that sync annotation. For each of these it would take a hashcode of it before executing the system. After, it would take another hashcode to detect which components have changed and add changed components to a dirty list. At some point it would iterate this dirty list and send all the changed components to the foreign parties. It could also catch when synced components are added by a system and add those to the dirty list.

This would only allow for whole components to be sent and not deltas or partial components with just the updated parts. This would take up more bandwidth, but I don’t think it would be an issue. Components in an ECS tend to be very small, so any change to them would probably mean changing a significant proportion of the entity. For example, changing the position in a transform changes 2 thirds of the data it stores. You cannot change less than 1 third of the transform’s total data, and the transform only consists of 3 floating point values anyways.

Component based events in an ECS

Bevy handles events in a special manner using event readers and writers which keep track of which systems have read which events and while this system works very well for general global events, I feel they miss out on a good solution for events tied to a particular entity.

Component based events would work mostly like normal components. They would be associated with an entity and systems could query for them like regular components. The only real difference is that they would be cleared out after each system has seen it. How and when to remove the event component gets a little complicated especially with the architecture of the ECS I’m using now. The point of these event components is that a system that queries for the event would be run exactly once for each time the event is fired on a component.

Tangent about control flow

I mentioned that removing the event component was complicated. This is because the ECS I’m using has external control flow; something else queries into the ECS rather than the ECS running systems at its own leisure. This means that the ECS has no concept of a tick, where a tick starts, or where a tick ends. This also complicates mutations to the ECS as the component collections cannot be modified while a system is running. This results in deferred modification of the ECS, which is probably desirable anyways. The issue is when to deffer the modification to, as the ECS is not executing code when it’s not being queried. The solution currently is that all modifications happen in the beginning of a query, before any components are queried and systems are run. This means that within a single tick, systems run after a given system will be able to see modification that system has made. This seems to be the behavior of Bevy so it’s probably fine, and it’s been fine for me, but it won’t work for the events. Events need to be consumed by every system exactly once and then removed.

Internal control flow could solve this issue. With internal control flow, the ECS runs the systems instead of the systems querying the ECS. This means the ECS does have a concept of a tick, and a beginning and end of a tick. All events could be added to entities at the beginning of a tick, and removed from entities at the end of the tick. Every system that wants the event will have run between those 2 points in time.

A workaround to the current system would be to add a tick method to ECS that clears all existing events and replaces them with the new events waiting to be processed. This tick method would be called once every game tick, and it would have the same effect as the internal control flow while keeping control flow external.

The remaining issue is that an entity can only have one component of a given type on it at a time but an event might fire on an entity multiple times in one tick. The solution is to handle events specially. Events would be stored in some other method in the ECS and when a system was looking for an event, it would be run as many times on a given entity within the same tick as there are requested events associated with the entity.

Dynamic music

The music in MicrowaveJava all uses Java’s builtin midi system. All I do with it now is load midi files and play them, but it is much more powerful in theory. To make dynamic music, it should be as easy as subclassing Sequence and emitting channels that provide notes dynamically. I’d be interested in a game that played music in the vein of Bogosort Takes the “A” Train, giving the player an achievement if it did manage to sort the chord.

IDE

This one is a far off dream, but I think it would be really neato to create a game editor using the Eclipse IDE. Despite it being core to the platform, I never really considered using Eclipse to create a custom IDE until I used QNX Momentics as part of a real-time systems course. Since then I’ve been dying for a sufficient excuse for making my own custom Eclipse-based IDE. Of course, the benefits of such an effort seem lacking given my love of code as data making many of the assets Java source code files. Still, Swing UIs are Java source code files and they have visual editors built into IDEs so maybe I’m on to something here. At any rate, I would need a pretty compelling workflow advantage to put in the needed effort and I don’t see that cropping up any time soon.