Pathfinding is the main feature in our ldjam45 entry, Gargolite.

In this top down shooter, you protect an orb located in the center of the screen, from gargoyles that walk towards it from the edges of the screen around you.

When you shoot a gargoyle, it becomes a block that the other gargoyles must bypass on their way to the center. Effectively, we must calculate a path to the center for each gargoyle, one that does not goes through any wall; and we must recalculate it each time a wall is added and the environment is changed.

This calculation must be fast, otherwise it will lag the entire game.

The problem

The entire map is built on a grid. Each game element fits in one cell: A gargoyle, the player, the walls, the orb, and even the floor tiles. This means that the granularity of the path can be at the resolution of the grid. This helps to simplify the calculation.

Each path segment is between two grid cells. From each cell, the gargoyles could move in 16 directions: 4 primary directions (up, down, left, right), 4 diagonals, and 8 secondary diagonals (similar to a knight in chess). See the figure below - the a gargoyle located in the yellow cell can move directly to any of the gray cells (no need to allow movement to the black cells, because each of them is composed of two steps to a gray adjacent cell).

This 16-direction solution did not yield the absolute optimal paths, but it was enough to give a natural feel to the gargoyles movement.

I wanted to find the path which was composed of these segments, and is the shortest (in distance, not in number of steps).

I started with one approach to calculate a path with the traits above, but later moved to a different one that worked faster. I'll explain these approaches and will show you some of their awesome results.

Approach 1 - A* algorithm for each gargoyle

A* algorithm (pronounced: A-star) is a pathfinding algorithm that finds the shortest route between a source and a target. It is probably the one that your GPS app uses when you navigate with your car.

Pros: 1. Optimizes the path using both the source and the target 2. Can work on an infinite graph (the game area is infinite, and A* works without problem on that. It searches the entire area and stops when it finds a target)

Cons: 1. Relevant only for a single source (i.e. one gargoyle) 2. Though efficient for paths where going in the general direction for your target is a good guess (e.g. map of New York), becomes less efficient when the area becomes more maze-like, with many dead ends.

When using A*, the game worked fast at first, but later when the area became like a little maze, and there were more and more gargoyles on the screen, the game started lagging for each wall added. After all, it was a more complicated calculation, calculated numerous times for each invocation.

I did some optimization that helped (e.g. for each wall added, recalculate the path only for gargoyles that had the new wall blocking their previous path). But then I thought of approach 2 which solved many of my problems:

Approach 2 - One Dijkstra from the center

Dijkstra is a relatively simple algorithm that finds the shortest path from one node to every other node in the graph. Meaning that starting from the center, I could find the shortest path from each point on the map, to the center.

For each point I also saved the 'parent' node, that is the next node through which the shortest path should go through.

When a gargoyle steps on a grid cell, it starts walking towards its 'parent' cell. When it gets to the next cell, it walks towards that cell's parent and so on, until it reaches the center.

Pros: 1. One calculation is good for all gargoyles 2. Not less efficient even if the paths have a lot of turns and dead ends 3. No need to save the path for each gargoyle; they can figure out their next move based on their current location only.

Cons: 1. Not using the source (i.e. gargoyle position) for optimization 2. Not relevant for the infinite area but only for the areas I precalculate.

This algorithm turned out to be more complicated than calculating the path for only one or two gargoyles; but once I had it I could find the path for all gargoyles, meaning that the game would not get laggy as the game area gets more crowded.

Once I succeeded in packing this calculation into one frame, it was good for early and late-game as well.

One caveat is that it is only relevant for the area I precalculate, not the entire infinite screen. If I calculated too much area - the game started lagging. Luckily, most of the gameplay is near the orb in the center. Get too far, and a gargoyle may surprize you from the other side. Therefore, a quite small square covering a little more than the screen (roughly around the paved area), was enough to make the game feel realistic. Gargoyles which are outside this area will walk directly to the direction of the center until they pick up a 'calculated' grid cell.

Another upside of this approach, is that Dijkstra can also find that the center is blocked (and induce a gem-emitting explosion), without any additional cost! Each time this algorithm find a wall, it saves it; then when the graph seems blocked, all the marked walls explode and emit gems.

I visualized some of the graphs found by this algorithm, and it led to surprisingly beautiful results. All hail math! Gargoyles would always walk in the direction of the white arrows to reach the center.

A snowflake pattern of the clear map:

A corridor. See how it is clear where is the line that defines whether you better go up or down:

A cool spiral.

Just some random walls to help you get the hang of it:

The algorithm

```

This is a Gargolite-specific version of dijkstra algorithm:

dist[center point] = 0.0 queue = [center point]

while queue is not empty: current = pop the queue for the cell where dist[cell] is the smallest mark current as done

for each neighbor of current (see 16-direction fig. above):
    if neighbor is marked as done, skip it.
    if neighbor is outside play area, skip it.
    if neighbor is a wall skip it (but first mark it as 'reached').

    check if the way between current and neighbor is clear of walls
    (this includes all the cells in the rectangle blocking these cells)
    if way is not clear, skip this neighbor.

    # Now we know that neighbor is a valid cell, and there is a free way between current and neighbor.

    new_dist = dist[current] + distance(current, neighbor)
    if dist[neighbor] is not set, or new_dist < dist[neighbor]:
        dist[neighbor] = new_dist
        parent[neighbor] = current

    if neighbor is not in queue:
        add neighbor to queue

# At this point, we have dist and parent set for all cells reachable from the center.

if not reached edges of play area:
    # Found a circle blocking the center!
    explode all reached walls and emit gems

```

Hope you enjoyed this post!

See Gargolite entry at https://ldjam.com/events/ludum-dare/45/gargolite

Hi there! Our game Mount Ookie is all about the wasps. Chasing wasps, picking them up, and throwing them at each other, at obstacles, or into the Ookie's mouth.

Wasps are arriving randomly and land at the Ookie's huge body, in a gradually growing pace. Since each landed wasp drains the Ookie's life, the game also becomes gradually harder.

In the post I want to share how the wasp mechanic work, and how we used it to make the game challenging yet fair, random but with a sense of progress.

Let's start!

Part 1 - WHERE the wasps land?

See the following blue-ish recrangles on the Ookie's body:

(This is the editor of Godot Game Engine)

The wasps are allowed to land only inside these rectangles. When a wasp is scheduled to arrive, its final location is randomized by the following algorithm:

1. Calculate the enclosing rectangle of all the areas (that is the tightest rectangle that contains all the small ones). Do this once at the beginning of the game.
2. Calculate a random point on the rectangle.
3. If the random point is NOT inside any of the allowed areas, try again (i.e. go back to phase 2)
4. Snap the point to grid (e.g. so the wasp will be aligned with the platform.

After the wasp final location is picked, then the wasp is created at a random point near the top border of the world.
Then its location is interpolated (i.e. the wasp goes 5% of the remaining path in every frame) until it arrives slowly but surely to its final point; then when it almost at a full stop, the wasp digs into the Ookie's body. You can follow the wasps in this gif to get the hang of it:

Alternatives

Initially, the wasps could land on the entire body of the Ookie. This made the game harder because some places were hard to reach without platform below (e.g. to the top and left of the Ookie's head), or were directly below platforms which required a drop-and-catch maneuver which was a little to much to ask from Jam players that make a quick look on every game. So I altered it to (as you can see in the image above) - only directly above platforms or in a jumpable area from platforms.

An alternative to the location-choise algorithm would be to pick a rectangle in random, then pick a location on it. I could make it a weighted random by the size of the square. This would save the recalculation of randomness when you "miss" the allowed area and must try again; but the current algorithm worked well and never caused frames to "get stuck" because of recalculations, so I kept it.
Also, picking a rectangle would not allow me to use overlapping areas, which was the case at start (when I used the entire Ookie's body as allowed area).

Part 2 - WHEN the wasps come?

The wasps arrive at random intervals. After each wasp comes, the time until the next wasp is calculated with the following formula:

rand_range(1, max(5, 8 - game_time*0.03))

And in people's language:

The time is a random value between 1 sec and a number that depends on your progress in the game. At the beginning, the time is between 1 and 8 seconds (meaning an average of 4.5 seconds, a slow pace that is easy to handle). Over time, the wasp pace becomes faster. It's still random, and can still have larger or smaller gap, but the average time gets faster. That is up until time 1:40, then the pace settles on random between 1 and 5 seconds, meaning an average of 3 seconds between wasps, which is quite fast. This pace is kept until the end at 2:30.

See an example timeline (left to right) of when the wasps are spawned:

Note that: - The pace is always random, but still has a controlled average that gets faster. This makes a nice distribution, where are some natural "clusters" of wasps that arrive quite close together, and sometimes large gaps between them; - The pace is getting faster very gradually. Because it's still random, it's hard to put a finger on it; but players will still feel the tension built. This feeling is familiar to anyone who had worked at a food stand, and saw the tired dripping of customers gradually becomes a fast flow when lunch time gets closer.

Alternatives

Usually, good defense games have waves. This will allow building of tension, then letting the player have time to gather their strength before the next one.
Maybe Ookie could use some waves in it; however it was intentionally a short game, probably not short enough to split it to several waves. I'd like to see it as a game with waves, but only one of them :) If we were to extend this game further, we would definitely do some waves!

Another thing we could do is not to make the pace grow gradually faster, but make some specific points where we let the player know that the pace "escalates". This could help build the tension; but could also be distracting and hurt the "zen" like feel of the game. Eventually we chose the gradual way because it means that we only have one parameter to balance (the final pace) which was easier to experiment with at the time of the Jam.

Hope you liked this post! Have a go at Mount Ookie and let us know what you think of the wasps behavior and balancing. Enjoy!

Hi folks!

Two years ago @stavu and @jakier made Alchemize - a completely original strategy board game for two players. I was their entry for Ludum Dare 42 - "Running out of Space".

After making a game together for the latest jam, Stav, Yakier and I joined forces for an Alchemize remake - now with improved graphics, new sounds, and the ability to play against the AI, providing a complete single player experience for the first time.

There are four difficulty levels, from Easy for casual play, up to Insane, which is for experts only!

Play Alchemize remake!

And please share your thoughts on this new version. Enjoy :)

tl;dr:
I wrote this post about how to approach writing AI players for board games, and how I did a unique player to play Alchemize. Check it out!

Two years ago @stavu and @jakier made Alchemize - a completely original strategy board game for two players. It was their entry for Ludum Dare 42 - “Running out of Space”.

Recently we released a new version of Alchemize, with the ability to play against AI, in 4 different difficulty levels.

I wrote a post about how I wrote Alchemize AI Algorithm, explaining the challenges of creating AI for a unique board game. I describe the solutions I chose, taking into account strategy, speed and player experience.

Read Post about Alchemize AI

Play Alchemize vs AI

Or just sit back and see how Insane AI (blue) beats the crap out of Hard AI (red): https://youtu.be/faTwYKsK7v8

Hello there jammers,
Please check out Autumn Hike, a short top-down adventure.
A snail goes out for an autumn hike. But he would have to search deep inside himself...

Play Autumn Hike now in your browser

I created a dithering shader for that zooming effect in our game Autumn Hike.

Before (with transparancy/grayscale):

After (with dithering, only black and white pixels):

What do you think?
Soon I'll upload a post about how I implemented this.

Play Autumn Hike (web)

Hi everyone!
I wanted to talk a little bit about the dithering effect and shader I wrote for our game Autumn Hike, why I wrote it and how I implemented it.

Our Game

Autumn Hike is in 1-bit style, meaning that this game is low-res, and has only two colors, black and white.

According to the "deeper and deeper" theme, protagonist Mr. Snail can enter some small spaces, which are then zoomed in to the entire screen.

The Problem

In the first released version, the zoom-in effect looked like this:

I think it looked quite neat, and communicated well the fact that you got inside this small area that now takes the entire screen.

However, something still bothered me - our game is black-and-white, but in this transition effect we use transparency, resulting in gray pixels! Take, for example, this intermediate frame between two screens:

It has different grayscale colors all over the place, which breaks the consistency of the style, and would not be possible in the imaginary gameboy-like device on which our game runs (at least that we aimed for...)

The Solution - Dithering!

To keep this effect and still use only two colors, I wanted to implement dithering, which is a method that allows expressing a scale between two colors, using only pixels of these two colors (in this - all grays between black and white).

Implementation

I implemented it by writing a simple screen-space shader, which takes the current screen "output" of the game, and overrides it with calculations based on the current pixels. I was using Godot game engine, but this method is possible with every modern engine.

The implementation goes roughly like this: - Divide the screen to pixels based on the game's resolution - Divide all pixels to 4x4 squares - For each of the 16 pixels in the square, set a different [0.0 to 1.0] "threshold". If the "original" color in darker than the threshold, final color would be black; otherwise it would be white. I chose thresholds of 1/16, 2/16, 3/16, ... 16/16 and scattered them in a nice pattern inside the 4x4 square.

That's it, actually.

Choosing different thresholds for different pixels in each 4x4 square makes sure that lighter gray colors would "paint" more pixels white and less black; while a darker color would paint more pixels "black" and less "white", resulting in the overall impression of a darker color while still using only two colors.
Needless to say, a "completely" white input (value 1) is above the threshold of all pixels in the square, and would result in the same white square. Similarly with black (value 0).

The pattern I chose is the following, with the goal of having similar-colored pixels as far away from each other as I can, to make it look more "scattered":

Square 1 has the threshold of 1/16, square 2 has 2/16 etc. Note that a 50% gray would paint only 1-8 squares white (because it is above (or equals, in that case) 1/16 to 8/16), and would result in a nice checkers-board pattern.

I could have chose any other pattern, but I think this one fit best the theme of the game.

Results

This grayscale gradient would become this after applying the shader:

This is how it looks like, zoomed in around the center (see the "checkers board" pattern around the 50% gray):

Before and after:

Before

After

(I like how the environment "dissolves" when switching to a new area)

What do you think? Do you like the new dithering or do you prefer the previous look?
Please let us know if the post was helpful for you! And don't forget to play Autumn Hike!

Thanks,
Ori and Autumn Hike team :)

Play Shaky Shack now on your browser

Hi Folks!

Check out our LD49Jam entry, Shaky Shack! A puzzle-memory game where you keep your unstable cauldrons from exploding by mixing magical ingredients, using your Spell Book.

Please check out Chicken Dinner, a game where you play a chicken trying to escape the hungry farmer, and delay the inevitable 🍗

Play Chicken Dinner now in your browser

(please ignore, posted by mistake and don't know how to delete)

RandoBots is a VS arena game we built for Ludum Dare 51.

Two players are on the game field - one is a turret shooting bullets, and one is a "race car" drifting and trying to avoid these bullets. The attacker and avoider switch roles every 10 seconds - the car becomes a stationary turret and the turret becomes a car.

It's basically a symmetric two-player game. But a human companion is not always available! So we wrote an AI algorithm controlling one of the players, allowing you to play against the computer.

In this post I'll explain these algorithms and elaborate on the technical part and also on the game-design aspects of coding an AI player.

Turret AI

Let's start with the simpler one - the turret, its goal is to shoot at the player.

Turret AI consists of two phases:

First we need to decide the desired turret direction. The obvious is - towards the other player! But since bullets take time to reach their target, in that case all the opponent needs to do is to keep moving.

A better option is to shoot where the car is headed. For that case we came up with the following calculation:

target_position = car_position + car_velocity * (distance(car, turret) / bullet_speed) * 0.75

In human words:
Predict where the car will be when the bullets hit it; consider the time it will take to bullets to reach the car (distance / bullet speed), and multiply it with the car velocity to get the difference you need to "add" to the current car position. These bullets would almost certainly hit the car if it keeps going in the same speed in the same directions.

But hey, what's that 0.75 factor at the end? Well, after some playtesting, we figured that an AI that is perfectly able to predict your position is not very fun. It was too hard, it felt like it's "cheating", and somewhat inhuman. This "avoider" optimal experience should be - driving fast, drifting around and avoiding. But with this "perfect" turret (before applying the 0.75 factor), the best strategy is to make small moves and avoid each bullet "matrix style" which is much harder. But with the 0.75 correction, speed is your friend. As long as you are going fast enough you can still avoid the bullets, which turned out to be more fun!

We used Godot input system, and the AI mocks actual player keystrokes. The turret would turn right or left, whichever will bring it closer to the target; And if the angle is close enough to the target, it starts shooting (we didn't want the turret to shoot if pointing too far from the target. Nothing wrong with it strategically, it just felt messy).

The result - A "smart" AI turret that follows the player. The white crosshair is the turret's target:

Car AI

Here's the real challenge. The car needs to avoid bullets, but also drive through an ever-changing environment, with walls appear and disappear all the time.

1. Choose target position

Similar to the turret, first of all the car needs to decide where it wants to go. It determines the target point that is the farthest from all the following: - enemy (turret) position - bullet positions - current car position - screen corners

The first two are obvious - you want to get as far as you can from things that kill you.
Then, the car chooses a point that is farthest from its current position. It assumes that the enemy probably already shoots at where you are, and the best thing to do is to keeps moving .
These rules might push the car to choose one of the screen corners, which is not a really good idea, because it can get, well, cornered there... So adding the corners as points to stay away from solved that.

So, we got a target! But how will the car get there?

2. Flow field

Once we have a target position, we need the car to get there. We could just calculate the shortest path (overcoming walls) and let the car go through this path. But - what if the car accidentally slides away from this path? What if it gets hit by bullets on the way and moves out of this path?
That's why we chose flow field pathfinding. We split the game area to 16x16 pixel tiles, and used a form of BFS to calculate for each tile in what direction that would bring the car to the target in the shortest path.

3. Control the Car

Now that we know how to navigate from every point of the screen, we need, again, to mock user input. We calculate on which tile the car is on. Then, according to the tile's calculated direction, we both accelerate and steer the car towards the tile's flow direction.

4. Choose a new target.

Once the car is close enough to the target, we choose a new target according to step 1. The fact that the target is farthest from the car's current position makes sure that the new target is far enough.
If the target is "behind" the car, then it makes a nice tire-screeching drift, as the car quickly turns around towards the new target.

The result:

The car navigates towards the target, bypassing walls, always accelerating towards the fastest route to the target.

I could think of ways to optimize this, like recalculate the flow field every time a wall is destroyed (and potentially find a faster route), or actively avoid bullets. But the current behavior was unpredictable and was quite challenging to beat, which was definitely enough for the jam, so we kept it.

Did you enjoy RandoBots AI? Did you find any glitches or bugs in the AI? How would you approach this problem? Please let us know!

And most importantly,

Play RandoBots now in your browser!

Sincerely yours,
Ori and RandoBots team.

In this post jam version of RandoBots, we added an option to compete with either 2 or 4 robots in the game field (jam version only had 2).

Two of the players are either humans or bots, the other two are always bots (though we can add human inputs for these two, if anyone wants, with gamepads or so...).

Enjoy!

Play RandoBots now in your browser!

Get Prickle now on Steam!

(or try the free demo)

Hi Everyone!
We are excited to announce that our game Prickle, which started as a LDJam54 entry, is now available as a full game on Steam!

After the great feedbacks we got from you on our jam version of Prickle, we felt that we can do more with the game. We felt that the game mechanics and concept had a lot of potential, so we decided to turn Prickle into a "full" indie game!

Now, after a a year+ of work, Prickle is finished and available to purchase on Steam (with a launch discount).

Prickle is a grid-based, Sokoban-style puzzle game with a laid-back, wholesome vibe. You play father hedgehog in a quest to bring home all your prickly hoglets. The hoglets stick to you, forming a Tetris-like shape. The challenge is to build the Prickle correctly so you can navigate to the end of the level.

A hell lot of content! - 48 levels (Jam version had 12) - More unique mechanics, spread across the 4 seasons of the game - More story bits and cutscenes - Enhanced art and sound - Many quality-of-life features (e.g. controller support, translations, accessibility features and more)

So if you enjoyed the jam version, or consider yourself a puzzle game lover, you have to try this one out.

Prickle is available now with a launch discount on Steam, so grab your copy now (or try the free demo!)

Peace!

Get Prickle now on Steam!

(or try the free demo)