• 7 Day Roguelike 2016: Procedural Generation

    This is my second attempt at a procedurally generated space ship. The first attempt involved generating the hull first by starting with a large rectangle and stripping smaller rectangular pieces away until I got something roughly hull-looking. I would then attempt to fill the hull with rooms. Adding rooms to a preexisting hull proved messy and prone to difficult edge cases.

    Here's what it looked like at the point where I gave up:

    This shows my attempt at adding hallways on the inside of the ship. I was going to use some sort of binary partitioning scheme to split the space either side of the hallways into rooms, but I spent several hours making very little progress so I elected to sleep and try something else the next day.

    So the next day I started the ship generator from scratch. The new plan was to start with rooms, and compose them in a ship-like way. Specifically, I start with a few long hallways a reasonable distance apart. Then I "grow" rooms around the outside of the hallways. Rooms can also be grown from the edge of existing rooms. There are a simple set of rules that prevent rooms from growing into other rooms, and for opportunistically adding doors between pairs of rooms, and adjacent rooms and hallways.

    Here's an example of the output:

    It's still not completely finished. I still need to add windows around the outside of the hull, add items and NPCs, find a starting room for the player to begin in, and add some sort of goal room or stairs to the next level.

    My plan at the moment is:

    • tomorrow:
      • complete level generator (windows, items, NPCs, stairs)
      • make the game winnable
    • rest of week:
      • play test, polish, maybe add more weapons and enemies
  • 7 Day Roguelike 2016: Day 1

    It's one day in. Here's my progress so far!

    Completed features (from the plan I posted yesterday):

    • guns
    • shooting the hull can cause a breach and vent the atmosphere from connected parts of the ship
    • as atmosphere is vented, characters and items are sucked towards, and possibly out of, the breach
    • flamethrower that doesn't penetrate the hull but only works in atmosphere
      • flamethrower is implemented but it works in a vacuum

    Guns have a "spread" parameter that determines how quickly bullets spread out. This screenshot was taken directly after firing a shotgun at the zombie. You can see the bullets in flight:

    We hit the zombie but we also hit the hull. The red tint indicates that that section of the ship is currently being vented into space. Venting takes place over several turns, during which things are sucked towards the hull breach. Note that items and characters have moved since the first screenshot. This was the most complicated mechanic to implement. It uses dijkstra maps to determine which way entities move.

    After all the air has vented from a section of the ship, it changes to blue tinted and things stop getting sucked out. Eventually being it vacuum will drain oxygen from your suit, but this feature is not implemented yet.

    If you open a door of a pressurized section of the ship that's facing vacuum, that section starts venting.

    If you make it inside the venting room and close the door, atmosphere returns.

    Coming soon:

    • you need oxygen in your suit to survive in vacuum
    • oxygen drains while you're in vacuum, and recharges while you're in atmosphere.
    • make the flamethrower only work in atmosphere

    Additionally, as this needs to be a game and not just a tech demo, I'm also planning on implementing:

    • procedurally generated ship
    • different NPCs
      • something that explodes when killed so players have to think about whether killing it will breach the hull
      • something that can only be killed by getting sucked into space

    The most interesting bug I've encountered so far is when shooting the hull with a machine gun, if the hull is breached while bullets are still leaving your gun, there's a chance you will be sucked towards the hull, in front of bullets that haven't been fired yet, resulting in you getting shot by your own bullets.

  • 7 Day Roguelike 2016: Plan

    The 7 Day Roguelike Challenge is a game jam where participants make a roguelike in 7 days. This year I'm making a game called "Skeleton Crew" where you fight undead things on a spaceship. I'll post updates to this site as I make progress.

    The Plan

    I'm going to start with the glacial codebase. I plan to implement the following features:

    • guns
    • shooting the hull can cause a breach and vent the atmosphere from connected parts of the ship
    • you need oxygen in your suit to survive in vacuum
    • oxygen drains while you're in vacuum, and recharges while you're in atmosphere.
    • as atmosphere is vented, characters and items are sucked towards, and possibly out of, the breach
    • flamethrower that doesn't penetrate the hull but only works in atmosphere
  • Encoding Rules for Turn-Based Games

    A key consideration when designing a game engine is how rules of the game will be encoded. The engine needs a way of enforcing statements such as "Doors can only be passed through if they are open", and "If a burning character walks into a pool of water, it stops burning". The expressiveness of a game engine's rule-encoding is important, as it dictates the limitations of mechanics that can be implemented in games. Nobody wants to discover late in development that their engine can't be used to efficiently implement a certain feature.

    This post will describe the framework I developed to encode rules in two games I recently made: Glacial and Bugcatcher. It's based on the idea of an Entity Component System (ECS), extended with the abstraction of Actions.

    Entity Component System

    Every object in the game (walls, characters, doors, bullets, etc) is represented by an entity. An entity is simply a container for storing components. Components store information about objects in the world. The fact that an object is solid, that an object is opaque, that it has health or that it can take actions are all examples of components. The key idea of ECS is that all the information about the state of the world is stored in components, and each entity is simply a collection of various components.

    The rules of the game are represented by various systems that operate on components of entities. An example of such a system is a collision detector, that checks if an entity with a Collider component is about to walk into an entity with a Solid component, and stops the movement from going ahead. Another example is a system that applies burning effects. Periodically, it loops through each entity with a Burning component and a Health component, and reduce their health by some amount.

    This should serve as sufficient background in Entity Component Systems. The previous paragraph was intentionally vague about the details of how systems work. Rest assured that a more concrete explanation will follow. To learn more about ECS:

    Actions

    So far I've explained how wold state is represented - as a collection of entities made up of components. What's missing from the picture is how the world state gets updated. This engine is specifically designed for turn-based games, so the world is updated in discrete, sequential steps. This is where actions come in: an action is a description of a change in the world state. More concretely, actions can:

    • change the parameters of components (of entities)
    • add/remove components to/from entities

    The only way the world state can change is by an action being committed.

    Systems

    There are several different types of systems for encoding different types of rule:

    • Reactive Systems respond to actions
    • Continuous Systems run periodically to simulate continuous processes
    • Passive Systems don't affect the world state, but may update other parts of the game (e.g. a renderer). The don't encode game rules, but rather behaviour of the game itself. As they aren't particularly interesting in the context of this post, this is the last I will say about them.

    Reactive Systems

    Systems can register an interest in certain types of actions. When an action is proposed, interested systems can examine it, and possibly cause additional actions to occur in response, or cancel the current action. If after all interested systems have had the chance to respond to an action, the action hasn't been cancelled, the action is committed, and the change it describes actually occurs. If during this process, a system caused additional actions to be scheduled, these actions go through the same process.

    As an example, consider a Walk action. When the action is proposed (by a character's AI or the player), it contains information about how the walk will occur, such as the start coordinate, the destination coordinate, the direction and the entity (character) who is walking. The Collision system has registered an interest in Walk actions. When it sees one, it checks to see if the entity who is walking has the Collider component (indicating it's not, say, a ghost who can walk through walls), and if the destination coordinate contains any entity with the Solid component. If these conditions are met, the Collision system cancels the Walk action.

    If an action is canceled, it is still presented to all other interested systems. Systems have the ability to check if an action has been cancelled, so if multiple systems conflict, this can be resolved in the systems themselves, and by the game designer specifying the order in which systems run. Consider a SpiderWeb system, that when presented with a Walk action where the walker is stuck in a spider web (which can be represented by their entity having a StuckInWeb component), the walk is cancelled and another action is scheduled that breaks the spider web. If a character who is stuck in a web walks into a wall, the first system to run out of the StuckInWeb system and the Collision system will cancel the action. It wouldn't make much sense to have the player struggle in the web, not moving, but then to also bump into a wall. The decision of what should happen in this situation is up to the game designer, and they are free to order systems as they please, and to check if an action is cancelled before processing it.

    Continuous Systems

    Continuous systems simulate continuous processes, such as recovering health over time. At the end of each turn, all continuous systems are invoked with the amount of time that has passed since they were last invoked. This information, coupled with a rate of change, can be used to change values in away that appears continuous.

    What actually happens when a continuous system runs is up to the implementation. Typically, it will iterate over all entities with some component, and schedule an action for the entity based on a rate of change specified by the component, and the time delta since the last time the system ran.

    Consider a mechanic where characters that are on fire take a certain amount of damage each second. An OnFire component could be used to signify that an entity is on fire. It could be parameterized with a rate, indicating the damage taken per second. A Burning continuous system would iterate over all the entities with an OnFire component, and for each entity, schedule an action where the entity takes timeDelta * damageRate damage.

    Schedule and Game Loop

    The engine uses a schedule to keep track of the order of turns. Tasks can be added to the schedule, along with a relative time at which they should occur. The schedule can be queried for the next task. It keeps track of the current absolute time, which increases as tasks are retrieved from the schedule. The game loop is based solely on the schedule, and isn't particularly interesting:

    while the game is not over {
        get next task from schedule;
        do task;
    }
    

    More interesting, is the contents of tasks that are scheduled. The engine schedules two types of tasks: turns and immediate actions.

    Turn

    During a turn, an entity produces a Turn object, consisting of:

    • action: an action to perform
    • time: the time this action will take
    • reschedule: whether the entity should be rescheduled on the current schedule

    Entities that can take turns have the TurnTaker component. This component contains a function that returns a Turn object describing what the entity does on its turn. For NPCs, this function constructs a turn based on the behaviour of the entity. For the player character, it returns a turn based on the player's input.

    A turn progresses as follows:

    takeTurn(entity) {
    
        turn = entity.getComponent(TurnTaker).takeTurn();
    
        for each reactive system {
            run the system on turn.action;
        }
    
        if turn.action has not been cancelled {
            turn.action.commit();
        }
    
        if turn.reschedule {
            schedule turn for entity in turn.time;
        }
    
        for each continuous system {
            timeDelta = schedule.getTimeDelta();
            run the system with timeDelta;
        }
    }
    

    Immediate Actions

    If during a turn, a character's action caused additional actions to be scheduled, they must be processed before the next character's turn. A naive way to implement this would be to schedule the actions at the current time. This won't necessarily work, as it's possible that the next character's turn is also scheduled for the current time. The schedule breaks ties by choosing the first task to be scheduled out of all those with equal times, so this will result in these actions being processed after the next character's turn.

    Scheduling actions with negative relative times would result in them being retrieved from the schedule before anything else. This would lead to further complications, as the absolute time tracked by the schedule would appear to be going in reverse.

    The solution I implemented was to add an immediate flag to scheduler tasks. Tasks with this flag set to true will be scheduled before tasks with it set to false, regardless of their scheduled times. To prevent complications with tracking absolute time, the schedule ignores immediate tasks when updating the absolute time. The scheduled times of immediate tasks is used solely to specify the order in which tasks will be retrieved from the scheduler.

    An immediate action is a task that applies an action, after passing it to each reactive system.

    Optimizations

    In order to write efficient systems, it's important to consider how entities and components are stored.

    Entity Implementation

    An entity consists of an array with one element for each type of component in the game. Each component type is assigned a unique identifier (an integer) which is used as an index into this array. Each element of the array corresponds to a particular type of component. To add a component to an entity, a reference to the component is placed in the array element corresponding to the component's type. To remove a component, the element is set to null. This allows components of entities to be retrieved in constant time. A limitation of this representation of entities is that each entity can have at most one of each type of component.

    Spacial Hashing on Position

    As with all information, an entity's position is just another component. For games that take place within a 2D grid, the Position component is parameterized by an (x, y) coordinate. As it is a common operation to check what is at a particular position within the world, storing all entities that have a Position component in a spacial hash table, keyed by their position, is a useful optimization.

    Each cell of the spacial hash table is a set of entities. A common operation performed by systems is checking if any entity at a given coordinate has a certain component. For example, when checking for collisions, it doesn't matter which entity at the destination coordinate is solid, as long as at least one is solid. To prevent having to loop over a cell's contents to search for a given component, each cell in the spacial hash table maintains a count of which components are there. When an entity enters or leaves the cell, the count for each component is updated based on that entity's components.

    Components can be added and removed from entities, and entities can be added and removed from the game. Additionally, entities can move around. All these operations need to be dealt with to keep the spacial hash up to date.

    Each component is given onAdd and onRemove methods, which are called when the component is added to and removed from an entity respectively. By default, these are used to maintain in each component, a reference to the entity it is currently a part of. These methods can be extended for the Position component to add or remove the entity possessing the component from its current cell in the spacial hash table.

    If an entity is removed from the game, the onRemove method of each of its components is called. If an entity that isn't currently part of the game has a component added to it, the call to onAdd is deferred to when the entity is added to the game, at which point the onAdd method of each component is called.

    The coordinates stored in a Position component are updated by a method call, rather than setting properties of the component directly. This method takes care of removing the entity from its previous cell in the spacial hash table, and inserting it into its new cell.

    Continuous System Storage

    To optimize continuous systems, a set of entities each system is currently interested in is maintained. For each continuous system, there is a component such that the system is interested in an entity if and only if it has that component. The adding and removing of entities from a system's set of interested entities is done by the component's onAdd and onRemove method.

    Conclusion

    Everything in the game is an entity, and an entity is just a collection of components. Everything that happens in the game is an action. Reactive systems react to actions by scheduling more actions, and continuous systems schedule actions that simulate continuous processes. These abstractions are expressive enough to encode complex game rules, and can be implemented efficiently.

    An implementation of all the abstractions described in this post can be found in the source code of Glacial.