Advent of Code 2018 - My Journey of Day 15

Advent of Code is a yearly advent calendar of code challenges. The idea that you get a new code challenge from the 1st through 25th of December. Each day has a part one, and a part two. Part two builds on part one, and depending on how you solved part one it can be easy or hard to figure out. Advent of Code started in 2015, and has continued every year since. I’m still in progress on finishing 2018, but have completed the other three years.

There have been days/problems in the past years that were quite challenging for me. One where I first got to learn about breadth first search. Another Where I got to use A* pathfinding algorithm. Overall, the more i’ve done them, the better I’ve gotten at advent of code.

For the most part I would say that rings true for this year. Though many of the problems have had little nuanced difficulties, and very specific rules that can trip you up. Day 15 is no exception to this. Though generally speaking I did enjoy the problem.

Warning this blog post will contain spoilers on how to solve this problem. So if this is something you wish to solve yourself, maybe come back to read this after you do.

You can read the full problem here: https://adventofcode.com/2018/day/15, but here is a rough description.

The idea is you have two teams of units, goblins vs elves. They’re in a top down, 2d map of tiles. Where units can move & attack in four directions. (Up/Down/Left/Right). Tiles are either:

  1. occupied by a unit (elf or goblin)
  2. open
  3. unpassable (wall)

The map is always surrounded by a wall, but has walls in the middle of the map as well. The idea is you need to simulate combat and determine what team won, and with how much left over HP, and in how many turns. (goblins and elves both start with 200hp, and deal 3 damage per attack).

Order of turns being taken is done by what’s called the “reading order”. The reading order is you essentially sort by [y, x] of a given unit. So units in a lower Y coordinate go first. For any ties by the lowest y coordinate, fallback to lowest X coordinate.

Once you have a unit that takes a turn, it needs to find the closest enemy. Instead of targeting an enemy directly though, you target the 4 surrounding tiles around each enemy (if they are open).

You then find the shortest travel path to these adjacent tiles. If there’s a tie in distance, you then follow the path which is first in the reading order. So if two paths were equal distance from 0,0 to 10,10. One starts at 0,1 the other at 1,0. You would take the one that does 1,0 as it’s first in reading order.

The unit moves only one tile per turn.

Now if the move a unit took moves puts it in range of an enemy (it must be adjacent to a unit), the unit attacks. If there are two or more enemies in range, the enemy with lowest HP is chosen. If there’s a tie with the HP, you fall back to reading order of enemies.

Likewise at the start of a turn, if the unit is already within attacking range, it does not move, it just does the attacking logic described above.

The answer is then remaining hp * rounds.

Counting rounds is a bit strange, and this tripped me up for a while. A round is counted when all units on both teams have taken their turn. So if there are 3 elves and 1 goblin, if elf #2 kills the goblin, and elf 3 hasn’t gone, the round counter does NOT increment. But if elf 3 were to kill the goblin, after elf 1 & 2 took their turns, the round would count.

The journey of development

My first approach was to use A* path finding. There are reasons why this didn’t work, but I also ignored the importance of finding the distance to the adjacent tiles, and instead targeted the unit itself. This was a mistake.

I stored two hash maps for the units, goblins and elves separately. HashMap<(x, y), Unit>. Unit would store the type (elf/goblin), as well as the HP it had. I would then create two lists of Vec<(x, data-preserve-html-node="true" y)> of Elves & goblins from these two hash maps. I would check if either one had zero length (meaning one team lost), and then count the hp sum * rounds, and exit the game.

If the game didn’t end yet, I combined the two vectors into one, and sort them by reading order. Iterating them from there, I would pull either the goblin or elf out of the respected hash maps, and have it select a target.

The select target used A* with the manhattan distance heuristic. If the distance (path length) was greater than zero, it would move to the spot before the end of the path (how i hoped to handle the adjacent tile thing), and then keep track of the path by its distance length. So each target would be checked, and the path with least distance would be selected. Of course if there was a tie, I would check which one won in the reading order, and then replace the min distance target with those x & y values.

After that was done, if the target was 1 away, it would choose to attack. This code I got mostly right, and it didn’t require much change throughout the work on the program. The only thing I missed was to exclude dead units from taking their turn. Do’h! My code here for selecting reading order was convoluted and hard to understand, so i’m glad I had to re-write it since!

Anyways when running the examples, I kept getting wrong answers. I would see that the units would sometimes move in the wrong direction, and i figured out why. Manhattan distance does not work for this problem. A path could be equal distance, but maybe a unit moves from 3,1 to 3,2 instead of to 2,1. Even though they have the same distance (because of a wall), 3,2 is closer to the target down at 5,5. But 2,1 is before 3,2 in reading order.

From the example set, here’s round 24 & 25. The only elf is at the bottom right, so the elf at 3,1 wants to move to 5,5. It should move to 2,1 as shown in round 25, as 2,1 and 3,2 will take the same distance.

After 24 rounds:
#######   
#..G..#
#...G.#
#.#G#G#
#...#E#
#.....#   
#######   

After 25 rounds:
#######   
#.G...#
#..G..#
#.#.#G#
#..G#E#
#.....#   
#######

But mine looked like:

After 25 rounds:
#######
#...G.#
#..G..#
#.#.#G#
#..G#E#
#.....#
#######

Basically both goblins ended up moving wrongly.

So I had to abandon A*. I would read on the sub reddit about folks using Breadth First Search, and someone at work also doing this problem used BFS as well, so I decided to go that route.

That said, I kinda did it wrong at first.

Breadth First Search (or Depth First Search by accident)

This solution was done using recursion, which what led me down the wrong path. As neighbours for a tile would be found, I would call the find_paths() on those neighbours instead of adding them to a stack. Meaning it would go far down a single path, and find the end, even though it might be the wrong way.

Another problem I had was performance. In the recursive calls, I would clone my scanned list, meaning other branches in the DFS would not know if another coordinate was scanned already. I did this on purpose, as I was worried that I would not cover all cases. However, this leads it to run a crazy number of iterations, unnecessarily. What fixed this was changing get_neighbours to return me the neighbours of a tile in reading order. I could then keep a single HashSet of scanned

pub fn get_neighbours(
    scanned_coords: &HashSet<Coord>,
    pos: &Coord,
    tiles: &Vec<Vec<TileType>>,
) -> Vec<(usize, usize, TileType)> {
    let mut neighbours: Vec<(usize, usize, TileType)> = Vec::with_capacity(4);

    // we push coords in reading order
    if pos.1 > 0 && !scanned_coords.contains(&(pos.0, pos.1 - 1)) {
        let tile_type = &tiles[pos.1 - 1][pos.0];
        if *tile_type == TileType::Open || *tile_type == TileType::Unit
        {
            neighbours.push((pos.0, pos.1 - 1, tile_type.clone()));
        }
    }

    if pos.0 > 0 && !scanned_coords.contains(&(pos.0 - 1, pos.1)) {
        let tile_type = &tiles[pos.1][pos.0 - 1];
        if *tile_type == TileType::Open || *tile_type == TileType::Unit
        {
            neighbours.push((pos.0 - 1, pos.1, tile_type.clone()));
        }
    }

    if pos.0 < tiles[0].len() - 1 && !scanned_coords.contains(&(pos.0 + 1, pos.1)) {
        let tile_type = &tiles[pos.1][pos.0 + 1];
        if *tile_type == TileType::Open || *tile_type == TileType::Unit
        {
            neighbours.push((pos.0 + 1, pos.1, tile_type.clone()));
        }
    }

    if pos.1 < tiles.len() - 1 && !scanned_coords.contains(&(pos.0, pos.1 + 1)) {
        let tile_type = &tiles[pos.1 + 1][pos.0];
        if *tile_type == TileType::Open || *tile_type == TileType::Unit
        {
            neighbours.push((pos.0, pos.1 + 1, tile_type.clone()));
        }
    }

    neighbours
}

You might also notice in this code sample, i’m allowing the coordinate to be a unit. This was initially left over from it being a target, but I used that for finding local targets to attack too. So when scanning for paths to move to, if i found a neighbour that was an enemy unit, i would then have a unit not longer worry about path finding, but instead go into attack mode, collecting the potential attackers, and priortized based hp -> reading order.

fn take_turn(empty_map: &HashSet<Coord>, tiles: &mut Vec<Vec<TileType>>, unit_collection: &mut HashMap<Coord, Unit>, targets: &mut HashMap<Coord, Unit>, unit_coord: &Coord, min_distance: &mut usize, distances: &mut HashMap<usize, SelectionData>) {
    let mut attack_targets = Vec::new();
    for (target_coord, target) in targets.iter_mut() {
        if target.hp == 0 {
            continue;
        }

        let neighbours = get_neighbours(&empty_map, target_coord, &tiles);
        for neighbour in &neighbours {
            // if unit is next to a target ATTACK!!!!!!!!!! ⚔️
            if (neighbour.0, neighbour.1) == *unit_coord && neighbour.2 == TileType::Unit {
                attack_targets.push(target_coord.clone());
                break
            }

            // no need to do expensive path finding
            if attack_targets.len() > 0 {
                continue
            }

            // potential check here to
            if neighbour.2 == TileType::Open {
                select_target(
                    &tiles,
                    unit_coord,
                    &(neighbour.0, neighbour.1),
                    target,
                    target_coord,
                    min_distance,
                    distances,
                );
            }
        }
    }

    if attack_targets.len() > 0 {
        attack_targets.sort_by(|a, b| {
            let target_a = targets.get(a).unwrap();
            let target_b = targets.get(b).unwrap();

            match target_a.hp.cmp(&target_b.hp) {
                Ordering::Equal => reading_order(a, b),
                Ordering::Less => Ordering::Less,
                Ordering::Greater => Ordering::Greater,
            }
        });

        let attack_target = attack_targets.get(0).unwrap();
        attack(tiles, targets, attack_target, unit_collection.get(unit_coord).unwrap());
    } else {
        perform_move(
            tiles,
            unit_collection,
            unit_coord,
            &min_distance,
            targets,
            &distances,
        );
    }
}

The perform_move still does complex logic on tracking min distance, whether it moves into attack range, etc. But this code I was starting to feel happy with.

The match stuff in rust is also quite awesome. The fact that I could put reading_order into a utility function that works with the Ordering trait is just awesome.

But still, this was depth first search, so I need to move away from that.

find_paths moved away from being a recursive function. Instead, I had a complex Vec<> type where it would store the path. I would grab each neighbour, and push it to the stack. Along with it, i would clone the current path, and push that neighbour coord to the path. So when the stack pops that coordinate, it knows what the path is including that coordinate.

If the coord that comes off the stack is the target, it would set the minimum path length using the min function, and push that path to the possible paths Vec<>. If the current path exceeds the length of the minimum path, it exits from that coordinate, as we’ve already beat it.

fn find_paths(
    tiles: &Vec<Vec<TileType>>,
    coord: &Coord,
    target: &Coord,
) -> Vec<Vec<Coord>> {

    let mut scanned_coords = HashSet::new();
    scanned_coords.insert(coord.clone());

    let mut paths = Vec::new();

    let mut stack = vec![FindNextData::new(scanned_coords.clone(), vec![coord.clone()])];

    let mut min_path_length = 10_000;

    while stack.len() > 0 {
        let current = stack.remove(0);
        if current.get_coord() == target {
            min_path_length = cmp::min(min_path_length, current.path.len());
            paths.push(current.path.clone());
            continue
        }

        if current.path.len() > min_path_length {
            break
        }

        let neighbours = get_neighbours(&scanned_coords, current.get_coord(), tiles);
        for neighbour in &neighbours {
            scanned_coords.insert((neighbour.0, neighbour.1));
        }

        for neighbour in &neighbours {
            if neighbour.2 == TileType::Unit {
                continue
            }
            let neighbour = (neighbour.0, neighbour.1);
            let mut path = current.path.clone();
            path.push(neighbour);
            stack.push(FindNextData::new(current.scanned_coords.clone(), path));
        }
    }

    paths
}

At this point a lot of the code started getting more organized. Keeping track of the data for which target spot is “winning” became easier, and so did finding the targets. Though I’m still cloning the scanned coords HashSet.

Part One working

The remaining piece to get part one working was the round counting, as well as fix that cloned HashSet problem. So each unit by coordinates would store if they took a turn. This also got a bit tricky, as i mentioned I had two HashMap<(x, data-preserve-html-node="true" y), Unit> for goblins & elves. I kept those up to date, but if the sorted coordinate list was then going into a coordinate where a unit died in, and another unit moved into, a unit could up going twice. So when looping through those coordinates to take turns, I would check if took_turn on the Unit was false or not. Then when the unit goes through moving/attacking, the flag would get set to true.

Part Two

After working on part one for over a week, I was able to move on to part two. The idea of part two was to find the lowest amount of damage that elves could do (they start with 3) where they win without taking losses. Instead of simulating it by doing 4 damage, 5 damage, 6 damage, etc. I decided to pick an arbitrary number of 20, with the last damage of 0 (for simplicity) and check if it was a win or loss. The “game” would also exit if a single elf dies. If the game won, it would go to the half way point between current damage & last damage. If it was a loss, it would increase by the current damage rate, which was 20. Basically I was doing a binary search to find the number faster.

And that’s it! Whew, it was quite the problem, frustrating at times, but I learned more about Rust as I went through it.

Thanks for reading, and Happy New Year!

https://github.com/agmcleod/adventofcode-2018/blob/master/15/src/main.rs

Energy Grid Released

This week I released Energy Grid. It's out now for Windows, Mac, and Linux. You can find it here.

The last couple of changes included tweaks to the settings UI, creating an end screen, which tells you how many cities you supplied power for. A number of bug fixes, mainly with the tutorial. As well as working on the music.

Check it out, and let me know what you think. Happy New Year!

Energy Grid Update - Nearing The End

After my last update, I have since balanced a lot of the numbers, giving the player a choice in how to collect resources. Pollution in the game exists as a way to punish the player for building unclean energy gatherers. Pollution has been changed to be a tax percentage rather than a flat amount. Pollution as a flat amount could cripple the player at the start, and not matter later. Now it scales much better. This means that as your gatherers collect resources, and those resources are sold, pollution tax is deducted from that income as a percentage.

Another major change is infinite upgrade. The upgrades that increase the resources gatherers get per tick have this feature enabled. As you research the upgrade, the cost goes up by 10% each time. This can really allow you to take the game far.

After making these changes, I noticed an issue. As you would collect resources the power bar would show a number. This number is power demand - power output.

power-bar.png

When it’s in the negative, you’re slowly running out. When it’s in the positive the number is filling up. When you would hit the positive, the game would add another city which increases the power demand, putting it back into the negative. As the player goes through the game and more cities get added, the rate of power consumption would keep increasing. Eventually it would consume faster than I could click sell. So what I decided to do was get rid of having you click the button to sell, and make it part of the gather operation. This means that when resources are gathered, they are sold immediately. To better illustrate this, I updated the side panel UI to show gathering rates and income.

gathering-ui.png

To keep the UI updates in sync, I had to update the games systems to do the calculations of gathering, pollution, selling, and power provided in a single pass, rather than across multiple systems. Without this, even with the automated selling, you’d hit a lose condition from the power demand getting too fast.

Further more, I added a button in for you to add another city to provide power too, rather than it being automatic,. So you can control the difficulty as you progress.

UI improvements around pollution

Another nice little improvement I worked on recently, is showing the player which tiles will be effected by pollution as you build different gatherers. You can see the effected tiles below in red.

pollution-selection.png

What’s next?

The game is getting fairly close to done. I’m working on the menu screen, and am looking to make adjustments to the settings UI. Then work on an end game screen as well.

I also plan to take another pass at the music, as I haven’t updated it since the original Ludum Dare entry.

Energy Grid Map Generation

As i've been balancing the numbers for the game. I realized that the way to win was to tech up as fast as possible, and just put solar panels everywhere. This just didn't have much in terms of strategy. I want the positioning of your gatherers to matter more. The simple way to do that is reduce the number of places you can build them.

The existing map generation is really simple. It finds an open 3x3 grid on the map where it can build a set of tiles, using a random number. The tile types currently in game are: Swamp, City, River, Open. The center of the 3x3 would always be something other than Open, and the surrounding tiles would be dependent on the center. Rivers more likely around a city, swamps more likely around a river. To reduce the available space problem, I tried increasing the number of 3x3 grids, but i could only do up to 4. A number of instances the game would never start as it couldnt find enough space for 5. So I decided to rethink how I generate the map.

The first option was to use the same 3x3 generation, but break the map out into 5 sections so it could reliably do this. Much like so:

sections.png

Then 5 3x3 grids would be able to fit, so long as they confine to the section they're in. However when I started filling out different patterns, I wasn't feeling too keen on it as a solution.

sections-painted.png

This scenario for example leaves some large chunks of space, not really creating confined areas that the user is forced to place in gatherers. The idea of constricting the space is so the user has to consider how much pollution they create. So I had another thought. What if I set the open space using defined shapes? What about the letter L. I keep the width of the L set to two spaces, using a variable length for the long part and the short foot of the letter. I then also sketched out some on how this might look, going with the assumption I would apply four "L"s to the map.

lshapes-painted.png

I realize this looks confusing, as a number of the "L"s overlap there, but the yellow space is blocked, the open space is where you can build. In most cases, you're almost always touching protected space. Meaning pollution is hard to avoid. But there's still enough squares for you to work with to get enough energy.

To pull this off in code, the main piece was tracking horizontal & vertical "L"s to ensure i dont have them overlap 100%. So if a vertical rotated L sits on more of the left side of the map, make sure the next one sits  on the right side somewhere. Otherwise it was just a matter of mapping the X & Y values to these Ls to build out the list of open squares.

Then the yellow space is filled with protected tile types. Some remaining code to sort out is generating those protected tiles more logically. As right now it's a bit of a mess!

ingamemap.png

Spring update on Energy Grid

Back in the fall I started on a roadmap for Energy Grid, to figure out where take it. The main components that I set to focus on was rendering the tech tree. This led me to having to build out a number of systems, which led me to new challenges such as font/text wrapping.

Here’s where I’m at in the road map.

  • [x] Replace original tech upgrade system with 3 nodes in the tech tree, one for coal, oil, and solar power. With coal already being researched. As you sell resources, you receive money. Money should be able to be used to upgrade the other two types.
  • [x] Show tile researching in game menu
  • [x] Create new tile types: Cities, Rivers, Swaps/lakes. Update the map generation to place these in little hubs. Coal, oil, and solar have to be built on blank tiles.
  • [x] Add hydro power, only buildable on river tiles.
  • [x] Add the pollution system. Coal & Oil pollute adjacent tiles with rivers, swaps, or cities in them. Hydro pollutes the river tile it is on. The more tiles polluted, the more amount of money you get taxed on per second.
  • [ ] Implement the rest of the tech tree nodes. The tech tree itself is layed out, but many of the bonuses do not work yet. The remaining bonuses to be implemented can be seen in my last update.
  • [ ] Sell solar panels for money. Enabled via the tech tree, but acts as another source of income, instead of being a passive bonus.
  • [ ] Additional cities to power. This is to ramp up difficulty as you progress
  • [ ] Create final assets for the game.
  • [ ] Create menu screens
  • [ ] Create tutorial/intro to the game

Here’s the game in action as of today:

spring_update.gif

Technical challenges

Drawing the Tech Tree

With the tech tree having over a dozen nodes, with connecting lines, I wanted to accomplish two things:

The first, manage the tech tree with a data file. Managing positions and all the information in code would have been tricky. Given the ECS library I’m using has a bit boilerplate to create a new entity with a set of components, managing this with a dataset instead would be easier to adjust and make changes.

To make this happen, I created an upgrade struct, and decorated it with serde so JSON can be deserialized into it.

#[derive(Serialize, Deserialize)]
pub struct Upgrade {
    pub buff: Buff,
    pub time_to_research: f32,
    #[serde(default)]
    pub current_research_progress: f32,
    pub cost: i32,
    pub status: Status,
}

Then in the JSON file, if a given object has an array of children, my rust code would iterate through that to establish the parent/child relationship. As the research system completes an in progress upgrade, it checks this tree of parent/child to update the status of the child upgrades.

The position of each node in the tree is based on simple number values in the JSON objects. The Y depth I initially tried to do it based on node depth in the JSON tree, but that led to some rows being too packed. So instead I define the Y value as a tier. 1, 2, 3, 4, etc. This is then multiplied to position them in a nicely spaced out way. X is 0->1 value, where 0 is the furthest left in the tech tree container, 1 is the furthest right. Determining the numbers here required a bit more consideration to position the nodes evenly.

The second thing: create an arbitrary shape drawing API. Because I’m using a wrapper of code around OpenGL, I need to draw things with triangles. For a rectangle this is pretty straight forward to put together, but for a polygon with 7 sides, knowing how the triangles should make up the shape becomes complicated. This is known as tessellation. Thankfully Lyon has a tessellation crate to give me this information. I was able to use it to produce the vertices I need to draw an arbitrary shape.

The recursive function that goes through determining the x & y coordinates of each node, this is then used to determine the 4 points of each line, going from node to node.

let last_half_x = last_position.x + SIZE_F / 2.0;
let last_half_y = last_position.y + SIZE_F / 2.0;
let half_x = x + SIZE_F / 2.0;
let half_y = y + SIZE_F / 2.0;
let points = vec![
    Vector2::new(last_half_x, last_half_y),
    Vector2::new(half_x, half_y),
    Vector2::new(half_x + 2.0, half_y),
    Vector2::new(last_half_x + 2.0, last_half_y),
];
let entity = world
    .create_entity()
    .with(Shape::new(points, [0.7, 0.7, 0.7, 1.0]))
    .with(Transform::visible_identity())
    .build();

The Shape struct is my piece of code that leverages lyon to do the tessellation. Building out the vertices is done via:

let mut path_builder = Path::builder();
for (i, point) in points.iter().enumerate() {
    let p = lyon_point(point.x, point.y);
    if i == 0 {
        path_builder.move_to(p);
    } else {
        path_builder.line_to(p);
    }
}

path_builder.close();

let path = path_builder.build();
let mut buffers = VertexBuffers::new();

// Create the tessellator.
let mut tessellator = FillTessellator::new();

// Compute the tessellation.
tessellator
    .tessellate_path(
        path.path_iter(),
        &FillOptions::default(),
        &mut BuffersBuilder::new(&mut buffers, VertexCtor { color }),
    )
    .unwrap();

Then i use the buffers variable inside my renderer, and pass it along with the Color data to my shader.

Map Generation

Procedural generation is not something I’ve done very much of. I knew that just looping through the 10x10 grid and selecting a tile type based on a random number would not be ideal, and would likely lead to not fun scenarios. So I started thinking about how one can make small dense areas on the map of the different types.

It got me thinking of a map with small hills, where ground level would be empty, ground+1 would be swamps, ground+2 rivers, ground+3 would be cities. To keep it simple, why not pick a node with the 8 surrounding nodes free, pick a random value between 2-4, and set the tile based on that number. Then set the 8 remaining tiles 0-(n), n being the value the center tile was. So it cannot be higher than the middle tile, but it can be lower, even empty.

let mut x = 0;
let mut y = 0;
// find the center first
loop {
    x = rng.gen_range(1, 9);
    y = rng.gen_range(1, 9);

    let mut all_nodes_free = true;

    'check_nodes: for i in 0..3 {
        for j in 0..3 {
            if set_nodes.contains_key(&(x + i, y + j)) {
                all_nodes_free = false;
                break 'check_nodes;
            }
        }
    }

    if all_nodes_free {
        break;
    }
}

First, I just do a naive random check to find an open set of 9 nodes.

Then i choose the value of the center node. These random numbers I am likely to change to better balance the map generation.

let weight: u32 = rng.gen_range(0, 101);
let mut highest = 1;
let tile_type = if weight >= 90 {
    highest = 4;
    TileType::City
} else if weight >= 75 {
    highest = 3;
    TileType::River
} else {
    highest = 2;
    TileType::EcoSystem
};

EcoSystem is what I called the swamp internally.

Then it was a matter of looping through the 3x3 grid in this 9 tile space to select the new types. Just using some random numbers for the different values.

for i in 0..3 {
    for j in 0..3 {
        if x + i == center_x && y + j == center_y {
            continue;
        }
        let tile_type = if highest == 4 {
            let weight: u32 = rng.gen_range(0, 101);
            if weight >= 90 {
                TileType::City
            } else if weight >= 75 {
                TileType::River
            } else if weight >= 55 {
                TileType::EcoSystem
            } else {
                TileType::Open
            }
        } else if highest == 3 {
            let weight: u32 = rng.gen_range(0, 101);
            if weight >= 75 {
                TileType::River
            } else if weight >= 50 {
                TileType::EcoSystem
            } else {
                TileType::Open
            }
        } else if highest == 2 {
            let weight: u32 = rng.gen_range(0, 101);
            if weight >= 60 {
                TileType::EcoSystem
            } else {
                TileType::Open
            }
        } else {
            TileType::Open
        };

        set_nodes.insert((x + i, y + j), (tile_type, None));
    }
}

We skip center, as that is already set. Then a different set of random numbers are used depending on what the center number was. The reason it’s done in a long set of if statements is so that it is easier to adjust. I could use an array of numbers to make this cleaner in code, but I didn’t want to couple the generation with the implementation when it’s still relatively easy to follow.

What's Next?

The next major focus is implementing the tech tree passives, and then testing them out. See how things work out balance wise, and how the game feels around the changes. After that, I will work towards making the city tiles what you are powering, and reserve tiles on screen for other cities to require power.

Taking My Jam Entry Further

My last post on here was about an archery game I started. That’s still a game I want to build, but at the end of July I decided to participate in Ludum Dare. Knowing I could re-purpose components and systems I built for the archery game, I felt confident that I could do a game jam with Rust.

You can play the game I created here: https://ldjam.com/events/ludum-dare/39/energy-grid

Somethings went smoothly, others not so much. I had to figure out how to include things like fonts and sound in an async context when neither of those are thread safe. The short answer is to not include them in an async piece of code at all! The Rust compiler is pretty good at making sure you avoid race conditions, so really it’s best to listen to its errors, and re-think your design. In the end I had moved the actual font texture creation & playing the music into the main loop, which runs synchronously. The game systems written on top of Specs - Parallel ECS would simply flag data as being ready to draw new text, or play new sounds.

After completing this, and making some improvements to the draw code, I ported those back into the archery game. While my overall score in the game jam wasn’t that great, I had some really encouraging comments on my entry. So I’ve since then decided to expand it.

I’ve spent the last couple of months implementing their feedback, as well as my own changes:

  1. Allowing one to make any of the researched gatherers.
  2. Changing the selling energy concept to give you money, which you use to create more gatherers, or advance in tech.
  3. Implemented a proper scene graph.
  4. Gave the game a proper restart, instead of just exiting the process.

Now that I have the game in a good spot, I figured it’s time to start working on a proper game design. While I’ve always valued planning when it comes to projects at work, it’s not something I’ve done in depth for a side project. My game Snowball Effect was done at a high level when I worked on V2, but I didn’t have it all flushed out from the get go, I did it in a very agile way. So I’ve decided to really dive deep on this game, and not just figure out what the features are at a high level, but really think it through, even the numbers.

The map instead of just one tile type will have multiple. Ones that you can’t build on, can’t pollute, ones that you can only build certain types next to, etc. This will be used to create a new random map whenever you start a new game. Meaning saved games will also be a thing.

There will be a tech tree of how to go to other technologies, and how to research passive bonuses. The numbers in the below tree are place holder, I’ve worked out more accurate numbers that roll over better (to avoid remainders). I’m sure beyond that it will still require balancing.

EnergyGridTechTree.png

I’m in process on figuring out a road map, and the UI design for the tech tree, along with new features. I look forward to sharing the gameplay of these changes once it’s ready.

Tilemap Parsing, Ground Detection

The past few months have been a fair bit of learning on doing graphics programming, and how to use some of the existing libraries with Rust. Now that I have some foundation, I've been able to start on actual logic needed for a game.

The first steps of this game has been getting tile map rendering working, and interacting with that tile data. I'm a fairly big fan of using Tiled. It's a fairly versatile editor, and a number of engines have direct support for it. In this case I'm working with the data more directly, as there's no real core support for tiled in popular Rust libraries. I'm using an awesome crate called tiled to parse the data into types, so I have that covered. It gives me layers in an array, each layer containing the tile IDs, right from the XML data. Tiled exports a number of formats, and I'm using CSV format. For example:

<layer name="back" width="30" height="20">
  <data encoding="csv">
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5
</data>
 </layer>

The layer is placing a number of tiles in various coordinates. It's one long list, but because the tilemap stores its number of tiles by width and height, it can keep track of what number is in what row & column fairly easily. From there, it's a matter of grabbing the 5th and 6th tile from my tileset. My tileset is an image of 92x64, with the tiles sized at 32x32, so that means 5 & 6 are on the 2nd row. Writing some simple code with division & modulous operators, one can map the UVs pretty easily:

let iw = image.width as u32;
let ih = image.height as u32;
// how many tiles is it wide & high? In this case it's 3x2
let tiles_wide = iw / (tileset.tile_width + tileset.spacing);
let tiles_high = ih / (tileset.tile_height + tileset.spacing);
// how much from 0-1 does the 32x32 take up of the source image
let tile_width_uv = tileset.tile_width as f32 / iw as f32;
let tile_height_uv = tileset.tile_height as f32 / ih as f32;
// cell is the number 5 or 6 from the example above
// subtract 1 to make it zero indexing. Then it's the same math for x & y. Just use width vs height, and modulous vs division.
let x = ((*cell as u32 - 1u32) % tiles_wide) as f32 + tileset.margin as f32 / iw as f32;
let y = ((*cell as u32 - 1u32) / tiles_wide) as f32 + tileset.margin as f32 / ih as f32;
let i = index as usize;
let tiles_wide = tiles_wide as f32;
let tiles_high = tiles_high as f32;
// now we just map the quad against those coords, i being the current index for the quad
vertex_data[i].uv[0] = x / tiles_wide;
vertex_data[i].uv[1] = y / tiles_high + tile_height_uv;
vertex_data[i + 1].uv[0] = x / tiles_wide + tile_width_uv;
vertex_data[i + 1].uv[1] = y / tiles_high + tile_height_uv;
vertex_data[i + 2].uv[0] = x / tiles_wide + tile_width_uv;
vertex_data[i + 2].uv[1] = y / tiles_high;
vertex_data[i + 3].uv[0] = x / tiles_wide;
vertex_data[i + 3].uv[1] = y / tiles_high;

That's the background layer, the next layer is the ground. This goes through the same code to figure out the drawing, but i've added some additional logic so we can build out a set of data for movement.

 <layer name="ground" width="30" height="20">
  <data encoding="csv">
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
2,2,2,2,2,2,2,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,2,0,0,0,0,0,
2,2,2,2,2,2,2,2,2,2,0,0,0,0,0,0,0,2,2,2,2,2,1,1,1,2,2,2,2,2,
1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1
</data>
 </layer>

0 value tiles are simply empty. They are full on ignored. So I just have a few tiles for a platform higher up, and then a base ground. In this game, i'm looking at making the movement point to click, so therefore use pathfinding, much like how you might make an AI go from point A to B. Initially I had a meta layer, where I placed a tile for each spot the player could move to, but that means for each new type, I'd have to add additional tiles, such as ledges, higher up areas that you should jump to, etc. So instead, why not create this data programatically?

When parsing a layer, the code is going in a top-down direction, so we iterate each row, then each cell across the columns for that row. This means that when parsing the ground tiles, we can track the open tiles above them to build a set of walkable areas.

The first step is walking through and building out this data.

let mut tile_map_render_data: Vec<PlaneRenderer<R>> = Vec::new();
// For the ground tiles, they will be stored x by y, in order to be able to group them. This is explained further down in this blog post.
// You'll note usage of LinkedHashMap. This is from a crate, not the standard library. It gives us an ordered map, so we can preserve the order we parse the ground tiles, and group them.
let mut ground_tiles: LinkedHashMap<i32, Vec<i32>> = LinkedHashMap::new();
// Storing the data y by x, as that's the order the layer is parsed in from a hierarchy perspective. Rows = y, cols = x
let mut unpassable_tiles: HashMap<usize, Vec<usize>> = HashMap::new();
for layer in map.layers.iter() {
    // I mentioned the meta layer earlier. Not in use right now, but keeping this around as it might come in handy still
    if layer.name != "meta" {
        // just building the render data
        let tilemap_plane = TileMapPlane::new(&map, &layer);
        tile_map_render_data.push(PlaneRenderer::new(factory, &tilemap_plane, tiles_texture, target));
        // collision layers being a static array that contains "ground"
        if COLLISION_LAYERS.contains(&layer.name.as_ref()) {
            // a simple function i created for iterating through a layer.
            for_each_cell(&layer, false, |x, y| {
                // building out the map of impassable tiles
                if unpassable_tiles.contains_key(&y) {
                    let mut xs = unpassable_tiles.get_mut(&y).unwrap();
                    xs.push(x);
                } else {
                    unpassable_tiles.insert(y, vec![x]);
                }
                // if not the first row, as nothing will be above it!
                if y > 0 {
                    // if above row above has collision data, hence the y - 1
                    if let Some(xs) = unpassable_tiles.get(&(y - 1)) {
                        // if it does not contain one for this column
                        if !xs.contains(&x) {
                            add_column_above_to_ground(x, y, &mut ground_tiles);
                        }
                    // or if it has zero collision data
                    } else {
                        add_column_above_to_ground(x, y, &mut ground_tiles);
                    }
                }
            });
        }
    }
}

fn add_column_above_to_ground(x: usize, y: usize, ground_tiles: &mut LinkedHashMap<i32, Vec<i32>>) {
    // it is open, so let's add it
    // we track x by y instead of y by x, as we need to go in that order for the tile grouping of grounds
    let x = x as i32;
    let y = (y - 1) as i32;
    if ground_tiles.contains_key(&x) {
        let mut ys = ground_tiles.get_mut(&x).unwrap();
        ys.push(y);
    } else {
        ground_tiles.insert(x, vec![y]);
    }
}

With that data together, we can break it down into groups. The reason for building out the ground_tiles as X by Y instead of Y by X, is to parse each column one at a time. This ensures that when checking a single tile, we can check the full range of the previous column to know what group it falls into. If you go Y by X, you have the current row's data as you go left to right across it, but you won't know if the row below is accessible by the current tiles.

// still storing Y by X, to keep it consistent
let mut groups: Vec<Vec<(i32, i32)>> = Vec::new();

for (col, rows) in ground_tiles.iter() {
    for row in rows {
        let mut found = false;
        let mut temp_row = 0;
        let mut temp_col = 0;
        let mut target_group_index = 0;

        // find whichgroup of (y, x)s can be used
        for (i, group) in groups.iter().enumerate() {
            let last_cell = &group[group.len() - 1];
            // if the X (col) is 0 or +1 to the right. If the Y (row) is between +1 and -1 from the last
            if (col - last_cell.1 == 0i32 || col - last_cell.1 == 1i32) && row - last_cell.0 < 2i32 && row - last_cell.0 > -2i32 {
                temp_row = *row;
                temp_col = *col;
                target_group_index = i;
                found = true;
                break
            }
        }

        // when its found, it means it can be added to a previous group, as it is within walkable range
        if found {
            groups.get_mut(target_group_index).unwrap().push((temp_row, temp_col));
        } else {
            groups.push(vec![(*row, *col)]);
        }
    }
}

With that data sorted out, we can then turn it into our usual Y by X map. Just faster to retrieve the data we need.

let mut hash_groups: Vec<HashMap<usize, Vec<usize>>> = Vec::new();

for group in groups {
    let mut coords: HashMap<usize, Vec<usize>> = HashMap::new();
    for (y, x) in group {
        let y = y as usize;
        let x = x as usize;
        if coords.contains_key(&y) {
            let mut xs = coords.get_mut(&y).unwrap();
            xs.push(x);
        } else {
            coords.insert(y, vec![x]);
        }
    }

    hash_groups.push(coords);
}

Snowball Effect Skins

As the game gets closer to release, I've worked on a few skins that you'll be able to purchase, and use to your heart's content. I wanted to make some that were a bit out there, and out of place, to make things more fun.

Since animating a rotating sphere proved difficult, I decided to make a flat texture, and leverage blender to make some of the frame by frame animations for these. First time doing 3d texturing in well over a decade, UVs are hard! I give much respect to those who work on 3d games, and animated motion pictures.

Here's the first skin I completed:

It's a large rock that gains & shrinks just as the normal snowball. I experimented with more of a golf ball type look, but felt it didn't give the look I want. So I ended up using a low poly sphere.

The next skin is a bowling ball.

The type of ball that most of us have rolled along a surface at some point. Bowling balls come in a range of patterns and designs. I wanted a nice blue one to keep with the existing colour theme. Then lined it with red, purple, green, orange bits so you can see it spin. Along with the typical three hols to grip the ball with.

To follow the trend of games that you play for a fun night out:

I naturally had to add an 8 ball. Making the texture for this was pretty straight forward, but as I mentioned earlier, getting the UVs right so it wasn't stretched was a challenge. I'm fairly happy with the result now, and I hope you like it.

By far my favourite skin though is this one:

I generally haven't caught on to the retro + pixel art trend going on in games, but I understand the appeal. I decided to give this a try, and I'm really happy how it turned out. I initially tried the same base colour as the standard snowball, but I found white worked better. I also added square versions of the little spots that wrap around the snowball.

Game Progress

As far as the state of development, I'm on the final touches of the game now. I'm working on getting game music complete, as well as working on an android build. Look out for a release coming soon!

Revive item implemented - Snowball Effect

This latest update includes the system for purchasing items, and the implementation of the revive item. So after doing a few runs and collecting coins, you can then buy yourself one or more revive items. If you have any avaialble, you'll see an additional button upon death

Using this will then bump up your snowball size immediately, and allow you to continue the game where you left off.