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
In Dreamiverse, you paint the world around you to discover it and evolve in it !
First I cut out the cushion. Easiest way although not always perfect is the magic wand tool in PS.
Next I adjust colours a little bit. Usually saturating them works very well.
Then I apply a cut palette filter to simplify shapes and reduce the number of colours.
The 
https://ldjam.com/events/ludum-dare/45/ignis-universia-eternal-sister-saga
https://ldjam.com/events/ludum-dare/45/spooky-the-one-who-lost-everything
https://ldjam.com/events/ludum-dare/45/vegan-farmer
https://ldjam.com/events/ludum-dare/45/new-start-at-n-o-t-h-i-n-g-ltd
(You can play our game in browser)
Take a look at the current version of the game and please send us feedback on what you would like to see in the game. We will be very grateful XD
https://ldjam.com/events/ludum-dare/45/untitled-sandbox-game-where-you-throw-sticks
