Lighters

This one's for you and me, living out our dreams
We're all right where we should be
Lift my arms out wide, I open my eyes
And now all I wanna see, Is a sky full of lighters
A sky full of lighters

Introduction

Inspired by this song, starry night skies, and some interest in creative coding, here is Lighters, a coding experiment in the form of a small interactive app.

Lighters is a small interactive app created using Processing. The sections that follow will go over various techniques and topics used in this project. If you just want to see the finished work, either scroll to the bottom or follow this link.

Without further ado, here are the various features and explainations on how they are implemented. There may also be an optimization section for some of them where I explain what has been done to make the code run faster. Finally, links will be provided to other resources I have used.

Procedural Map Generation

Early experiments with procedural content generation lead to a separate Procedural Dungeon Generator, so check the link for detailed description of various dungeon generation algorithms.

Getting severely side-tracked aside, the Random Room algorithm is used here, since the other algorithms resulted in rooms with a good mix of size and shape that are connected by corridors. The Random Room algorithm in a nutshell is as follows:

Create rooms of random width and height
Randomly place them on the grid (overlap is ignored to create complex room layouts)
Use A* Pathfinding to create corridors that connect the rooms
Randomly dig out a few more corridors that either end up as a dead end or connect to another room

A few changes had to be made when integrating the algorithm into Lighters. The first was to not allow corridors to be placed at the edge of the grid. In the original algorithm, rooms have walls while corridors do not. As a result, when generating wall sprites, the edge corridors are ignored. This can be fixed by changing the corridor generation algorithm, however, in the interest of time (and more importantly, laziness), the no-corridor-on-edge shortcut is taken.

Due to the above shortcut (read: laziness), a new problem surfaced: since corridors no longer appear at the edge, sometimes we get disconnected rooms if a room is placed by the edge. A flood-fill algorithm was added to check for disconnected rooms. When a new map is generated, the flood-fill algorithm picks and tags a random floor tile, then recursively tag its neighbors, until all neighbors are tags. All floor tiles should be tagged if all rooms are connected, so if any floor tile remains unmarked, a new map is generated. Since the likelihood of disconnected rooms is quite low, a good map is almost always generated on the second try.

Optimization

The original dungeon generation algorithm used a 2D array to store grid information (2D for X and Y). During the integration into Lighters, the 2D array was replaced by a 1D array.

Access data: 2D array versus 1D array
2D	number = array[x][y];
1D	number = array[x + y*width];

While on a technical level the cost of accessing data in a 2D array versus 1D array is the same, a 1D array *could* be more useful if you're trying to make a sized-at-runtime, multi-dimensional, but still rectangular array. In the end 2D array is easier to understand visually, so this is really more of a personal preference than serious optimization.

References

Tile Map and Sprites

Lighters is tile-based. After a map is generated, its features are stored in a grid, with each grid cell either marked as a floor tile, a wall tile, candles, etc. It's easy to keep track of where everything is in a tile-based world, and collision detection becomes much easier since collisions can be managed through simple AABB (Axis-Aligned Bounding Box).

After map generation, we go through each grid cell and display an image sprite depending on the tile content (made easy thanks to the use of tile maps). The map sprite sheet consists of several different floor tiles and wall tiles for different wall orientations.

Each floor tile receives a random floor sprite. As for wall tiles, a tile's neighbors are checked, and depending on the position and number of the neighbors, the corresponding wall sprite is drawn. The four wall tiles with pink background, those are the corners with transparent background. Pink pixels become invisible when the sprite is processed.

The agent sprites are stored in an array of images. When the agent is walking, the images are displayed in sequence to create animation. Framerate is used to display the images in sequence. For example, if there are four frames, we use imageArray[frameCount%4] to access each frame. The modulo operator calculates the remainder when one number is divided by another, so at frame 0, 4, 8... (multiples of 4), we get imageArray[0], frame 3, 6, 9, and other multiples of 3 gives us imageArray[3], and so on.

Big thanks to Salt Game for providing the base sprites for the floor and wall tiles.

Optimization

Since the map is static, a simple optimization is to generate and cache the tile map during initialization. When the player moves, we simply display the cached image of the map, and the viewport moves in response to the player's current location.

References

Collision Detection

The orginal plan was use Box2D to handle collisions, but after hours of work, it became apparent that Box2D was overkill, so a custom collision detection algorithm was implemented instead.

Since no fancy physic is needed here, a simple Axis-Aligned Bounding Box is attached to each wall tile and the agent. During gameplay, the engine checks the location of the agent bounding box against each of the wall bounding boxes using a rectangle-rectangle intersection algorithm, and determines whether a collision has occurred.

One area that required some extra attention was to keep track of direction the agent is moving toward when a collision occurs, since if there is a wall to the left, the agent should not be able to move left, but can still move up, down, or right.

Optimization

Several checks are implemented to terminate collision processing early to save time. One optimization that was not implemented is to only check bounding boxes close to the agent instead of cycling through all bounding boxes each frame.

References

http://www.gamasutra.com/view/feature/3383/simple_intersection_tests_for_games.php

Dynamic Lighting and Shadows

Lighting and shadows are some of the most important aspect of Lighters, and the most time-consuming to implement. For lighting, a pre-determined number of light sources (in our case candles) are placed randomly on the map. Each light source has a light radius. When rendering the tile map, pixels around the light sources are checked, if a pixel is within the light radius, a lighter version of it is drawn instead. When all pixels are processed, those within the light radius are brighter than those out of the light's range.

To create shadows, when a pixel is processed, a few extra checks are performed: if the pixel is not a on floor tile, or if there is an object between the light source and the current pixel, then we leave the pixel as is. To accomplish this, we keep track of shadow volumes based on positions of the wall tiles and the agent. When processing pixel lighting, a point-in-polygon algorithm is used to determine if the pixel is inside of that shadow volume.

The idea to have dynamic shadow and much of the final implementation were inspired by this tutorial. In the tutorial, shadows are drawn on top of lighted tiles. In Lighters, instead of drawing shadows, shaded pixels are simply not lighted.

Optimization

A lot of optimization can be done here. Since the shadows are dynamic, the map needs to be checked constantly, if the map is large, this can slow everything down by quite a bit. Instead of iterating through all pixels at every iteration, only pixels within a specific range of the light source is checked, this cuts down the time spent on lighting and shadows to the number of light sources and their light radius.

To take the above idea one step further, only light pixels within the view port are processed. This does not help if all light sources are within the viewing window. However, if only one or two light sources are within the viewport, this will save a lot of processing time.

Another point of interest is the shadow-casting edges of walls. As mentioned here:

[...] If you look carefully at the shadows in the demo you can see that only the lines that are facing away from the light actually influence the shape of the final shadow. This means that we're processing and drawing the shadows for many lines which we don't actually need to.

[...]

You might notice that it's the lines facing towards the lightsource that we don't need to draw shadows from. Using a little vector maths we can quite easily find which lines are facing the lightsource, and so which are worth drawing shadows for.

By doing some simple vector math and making use of dot product, we can determine which side of the edge the light source is on, cutting down the number of shadows we need to keep track of by half!

References

Light Companion

The light companion has its own bounding box, so it cast its own shadows when near a light source. Also, when idle, the light companion wanders around the agent using Brownian motion, an attraction rule is applied to make sure it does not wander too far. When the light companion lights up, it becomes a light source, complete with all the lighting rules.

A special energy parameter is added to the light companion. When acting as a light source, the light companion's light radius becomes smaller as its energy slowly decreases, the energy refills when the light companion is not lit up. Each light source also has its own energy that decreases over time. The light companion seeks out nearby light sources and replenish their energy. Each time a light source has been re-ignited, the rate at which its energy decreases goes up.

Optimization

The light companion checks for nearby light sources by calculating its current distance to nearby light sources, and comparing the distance to a maximum radial distance to determine whether the light source is in range. The distance formula, which contains a costly square root function, is called very frame. By squaring both the distance formula and the maximum radial distance, the square root from the distance formula can be effectively cancelled out.

References

Miscellanea

Overall this has been a fun and educational little project. A lot of times were spent on creating the map generation algorithm, the tile map and sprite engine, the collision detection, and dynamic lighting and shadows. Special thanks to Salt Game for giving us permission to use their floor and wall sprites, Annabelle Kennedy whose work the agent sprite is based on, and finally the song Lighters for inspiration.

Inspiration and Special Thanks
Lighters	The song that started it all
Salt Game	The sprites and the 2D shadow tutorial
Annabelle Kennedy	The original character sprites our sprite is based on
musictomake	Lighters MIDI
Shooting Star	Shooting star
Flashy Programming	Starry night

Results

[ Windows ] [ Mac ] [ Linux ]