• 7 Day Roguelike 2016: Ending

    Tonight I implemented stairs and an ending for the game. You must reach the teleporter on the 3rd floor of the ship, and teleport to safety. I also added some more flavour text, fixed some bugs, and balanced some characters. At this point the game is largely complete. I'll spend some of tomorrow playtesting and adding any remaining polish and balance I think is necessary. I also want to add a rocket launcher which shouldn't be too complicated given I already have projectile weapons and explosions.

    This screenshot shows the teleporter at the end of the game:

  • 7 Day Roguelike 2016: Polish

    Tonight I finished the level generator, adding weapons and items. I fixed a bug in my recursive shadowcast implementation causing strange behaviour when looking at the edge of the map. I tweaked a couple of mechanics, namely:

    • explosions destroy nearby walls regardless of whether one side is pressurized
      • this is unlike bullets, which only damage walls if one side is pressurized and the other isn't
    • flames from the flamethrower don't stop when they hit an enemy
    • doors can't be closed if there is an enemy standing in the way

    I spent the rest of my time tonight polishing the game's UI.

    Here are some death screens from playtesting!

    Shooting a bloat at point-blank range. Never a good idea.

    Tried to kill some zombies by blowing up a nearby bloat. Didn't end well.

    Getting sucked out of the ship as a section decompresses due to a hull breach.

  • 7 Day Roguelike 2016: Pathfinding

    The most notable change from tonight is that I turned on pathfinding for NPCs for the first time. Up until now they had been stationary, and could be injured or killed, or affected by vacuum, but could never observe the world or take actions. Enabling AI is scary because it greatly increases the amount of work the computer is doing between human turns. The vision system is now running once per NPC turn as well as the player. Then there's the additional cost of pathfinding for each NPC. I use Dijkstra maps for pathfinding which are explained in detail on roguebasin. This post is about solving a performance problem introduced by all the extra characters.

    With AI turned on, there was a noticeable increase in the time between player turns. Benchmarking revealed most of the time between player turns was spent in the vision system.

    Vision System

    The vision system uses the Recursive Shadowcast algorithm which I wrote about earlier. Detecting visible cells is relatively fast. The problem was what how this information was being used.

    NPC pathfinding and the renderer don't work on the canonical world representation. This game uses an ECS-based engine described in a previous post, so more concretely, AI and the renderer don't directly access entities or components. Instead, each character maintains a representation of the world based on what they have observed. A character's knowledge is represented by "shadow entities", made up of "shadow components". These were designed to be frequently updated by setting data in shadow components from "canonical" reference components without allocating any new objects. This was a technique I learnt while solving performance problems in a game I wrote earlier.

    At the start of a character's turn, the vision system runs and updates that character's knowledge of the world by updating shadow components. It was this knowledge updating process that was taking up most of the time. Knowledge is updated in the following way. It relies on a spacial hash of entities, and an analogous spacial hash of shadow entities in the knowledge representation of characters.

    for each coordinate visible according to recursive shadowcast:
        knowledgeCell = get knowledge spacial hash cell for the coord
        cell = get canonical spacial hash cell for the coord
    
        knowledgeCell.clear() # remove all shadow entities from the cell
        for each entity in that cell:
            knowledgeCell.see(entity) # makes a shadow entity
    
    

    Knowledge cells re-use shadow entities and shadow components to prevent invoking the allocator on each cell that is seen. Despite this, this process was still taking too long. A key insight for optimization was that most entities in most cells don't change most of the time. The only time a knowledge cell needs to be updated is when an entity has entered or left the corresponding canonical cell, or an entity in the cell changes in a "knowable" way (ie. a way that will be represented in a character's knowledge).

    With this in mind, the loop becomes:

    for each coordinate visible according to recursive shadowcast:
        knowledgeCell = get knowledge spacial hash cell for the coord
    
        if knowledgeCell.isDirty():
    
            cell = get canonical spacial hash cell for the coord
    
            knowledgeCell.clear()
            for each entity in that cell:
                knoweldgeCell.see(entity)
    
    

    The isDirty() method compares a "last modified" timestamp on the canonical spacial hash table cell with a "last observed" timestamp on the knowledge cell. A knowledge cell is now only updated if the cell has been changed more recently than it was last observed. A complication this change introduced is now the "last modified" timestamps must be updated whenever a cell's contents is changed in a meaningful way.

    Windows and NPCs

    I've updated the level generator to include windows and NPCs. It also places the player in a sane starting position, and determines a sane goal position (though there currently isn't anything there).

    Still to do is adding items (weapons and healthkits), and stairs. I still haven't decided how the game will end, though the current plan is to have some emergency beacon that needs to be activated before the ship-full-of-zombies arrives in a populated area.

  • 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