##
Detecting Splits

Here's a little diversion. I thought it would be fun to try out the SDK’s pathfinding APIs to detect splits. Although this doesn't have any direct impact on gameplay, I think that the game's ability to acknowledge celebratory moments (e.g. strikes, doubles, etc.) as well as cringeworthy ones (e.g. gutterballs, splits, etc.) will give it an empathetic voice and create a stronger emotional connection for the player. At the very least it should add to the atmosphere and sense of authenticity.

Wikipedia defines a split as:

…a situation in ten pin bowling in which the first ball of a frame knocks down the headpin ("number 1 bowling pin") but leaves standing two or more non-adjacent groups of one or more pins.

##
The Approach

That sounds like a graph problem! Restated in graph terms, we basically want to determine whether the set of pins that remain standing when the headpin is struck represent a fully *connected graph*, or contains two or more disconnected subgraphs. Some graph APIs have built-in facilities for determining this, which would make our job easy. Alas, Playdate does not. Its graph API, understandably, is focused on finding paths between nodes as would be useful in tile-based games or games played on a regular board.

No big deal; all the primitives we need are still there. The basic approach is to do a "flood fill" of the graph from an arbitrary standing pin in order to see if we can reach all of the others. If we fail to reach one or more pins, that means there must exist at least one pin which is fully disconnected from the subgraph we started from, and hence, a split!

##
Constructing the Graph

Before we can traverse the graph, we need to construct it. Bowling pins are arranged in a triangle. If you consider the 5 pin in the middle, it's clear that their layout actually represents a hexagonal grid, as it is adjacent to the 2, 3, 4, 6, 8, and 9 pins — a total of 6. The API provides convenience initializers for regular 2D grids (with or without diagonals — so, with 4 or 8 adjacencies) but none for graphs of degree 6.

Here’s the code used to construct the graph connections. It iterates through the rows and, for each node, creates connections to the node to its right as well as the nodes in the next row just to the left and right. This is sufficient since all connections are made reciprocal. The IDs for the nodes match the numbers of the pins. (Note that these directional references pertain to a rack oriented with the head pin facing downward, so you'll have to imagine the above image rotated 90º CCW. Note also that the graph has already been initialized and populated with nodes for each of the 10 pins before this step, which only happens once.)

```
local n = 1 -- the current pin number
for i = 1, NUM_ROWS do
for j = 1, i do
if j < i then
self.g:addConnectionToNodeWithID(n, n+1, weight, reciprocal) -- right
end
if i < NUM_ROWS then
self.g:addConnectionToNodeWithID(n, n+i, weight, reciprocal) -- behind left
self.g:addConnectionToNodeWithID(n, n+i+1, weight, reciprocal) -- behind right
end
n += 1
end
end
```

The weight is always 1 (the pins are equidistant, although this doesn't matter for our purposes) and all connections are reciprocal. While it would be possible to update the graph in real time by adding and removing connections as pins are struck and reracked, in practice that felt like unnecessary effort with a risk of error. Instead, I reconstruct the graph based on the currently standing pins each time `isSplit()`

is called by removing the connections for all struck pins from the fully connected graph we created above:

```
-- remove connections for pins which have been struck
local startPinID
for i, pin in ipairs(self.pins) do
if pin.struck then
self.g:removeAllConnectionsFromNodeWithID(i, true)
else
startPinID = i -- doesn't matter which, just any standing pin
end
end
```

In the process, we capture a reference to a pin to start the traversal from. It doesn't matter which pin we start from — any standing pin node will do. After removing the nodes, we'd have a graph that looks something like this example split:

##
Traversing the Graph

A flood fill can be achieved with either a depth-first or breadth-first search of the graph. I chose a depth-first approach, which can be easily implemented as a recursive function.

```
-- a simple depth first visitation function which returns the visited nodes
local DFS
DFS = function(node, visited)
-- avoids the need to pass an empty visited list before recursing
visited = visited or {}
-- bail out if we've already visited or node is nil
if not node or visited[node] then return visited end
-- mark the node visited
visited[node] = true
-- visit all directly connected nodes
local connections = node:connectedNodes()
for _, c in ipairs(connections) do
DFS(c, visited)
end
return visited
end
```

Let's break it down.

```
local DFS
```

First, we declare the local variable which will hold the reference to the function. This enables us to call the function recursively from within its own body.

```
DFS = function(node, visited)
```

The `DFS`

function takes a `playdate.pathfinder.node`

and the list of visited nodes which builds up as we traverse the graph.

```
visited = visited or {}
```

This line isn't strictly necessary. It provides an empty list of visited nodes by default, which means that the second argument may be omitted when calling `DFS`

directly.

```
if not node or visited[node] then return visited end
```

This is the base case. If we've already visited the node, we bail out, otherwise we'd recurse infinitely. Checking for a nil node also handles the case where, for instance, there are no standing pins so we couldn't find a pin node to start from, avoiding the need to check for this outside the function.

```
visited[node] = true
```

We record visited nodes by inserting them into the table as *keys* with a value of `true`

. This makes the lookup O(1), which doesn't matter much for such a small graph but still feels like the best approach, and also makes it possible to utilize the visited nodes later on.

```
local connections = node:connectedNodes()
for _, c in ipairs(connections) do
DFS(c, visited)
end
```

Next, we fetch the list of all nodes connected to the current node. We iterate over those nodes, recursively calling `DFS`

on each with the current list of visited nodes.

```
return visited
```

In the end, our traversal function returns the list of visited nodes. There are lots of other forms of visit functions we could create, including some that apply a function to each visited node, but the list of visited nodes is sufficient for the purposes of split detection. (In fact, we could have just counted them, but this approach seems more generically useful.)

##
Putting It To Use

Time to call it! We start the traversal from the node with the ID of our arbitrary standing pin. Once we have the list of visited nodes, all that's left is to compare the number of visited nodes to the number of standing pins. One gotcha here is in counting up the visited list. In Lua, the `#`

operation is only well-defined for numerically indexed tables. Our visited list uses nodes as keys, so we have to use `pairs`

(*not* `ipairs`

, which also works only for numerically indexed tables) to iterate through them and come up with a valid count.

```
-- do a DFS over the pins starting from our standing pin node
local visited = DFS(self.g:nodeWithID(startPinID))
-- count the visited nodes
numVisited = 0
for node in pairs(visited) do numVisited += 1 end
local numStanding = #self:standingPins()
-- if we didn't visit every standing pin, it's a split!
return numVisited < numStanding
```

##
Implementation Notes

This approach works well for my needs. It’s worth noting that using the nodes as keys means that the resulting visited list doesn’t reflect the order in which the nodes were visited. It might also be nicer from an API perspective to return a numerically indexed list of nodes instead of the map, but that requires extra bookkeeping or an extra step with a helper function, and just didn’t seem worth it for my simple use case.

##
Summing Up

In ~40 lines of Lua code, I was able to implement my `PinDeck:isSplit()`

function, which I call after each roll in order to show feedback to the player in the event of a split. That’s a little more code than I’d expected going in, but it works like a charm.

I could take this a step further and devise a way to detect specific types of splits too, such as the dreaded 7-10 or "goal posts" split (perhaps by defining bitmasks for each to compare with a bitmask representation of the standing pins?), but that can wait. I need to stop finding excuses to avoid the impending scene management work…