The Wonders of Winged Edge
Have you ever looked at a problem and thought to yourself, “This will be easy, I just need to do this and that and it’ll be done”? I often look at the broader problem without giving the details much thought until I’m already waist deep in code, and working on BOCO was no different.
I was recently approached by Binary Cocoa to work on their newest game, BOCO. BOCO is a simple strategy board game where you try to fill a game board with coloured pieces to encircle your opponent’s pieces. You can encircle just one, or several pieces to win. The board is a simple grid of triangles, squares, and rectangles. Conceptually, this sounds like a pretty simple game to implement. The catch is that a player can only play their piece adjacent to other played pieces. This complicates things.
My first attempt at mocking up BOCO ended up being very fragile. I quickly threw together a demo and while it worked, it wasn’t extendable in any way. Instead of hardcoding the grid and which shapes were neighbouring others, I needed a more elegant solution that wouldn’t fall apart if we want to expand the game. After some extensive research, I found the perfect solution: the Winged Edge Data Structure.
Winged Edge is a data structure that gives each vertex, edge, and face of an object descriptive information about the the other vertices, edges, and faces neighbouring them. What this means in layman terms is that each piece of an object knows which other pieces are connected to it.
As you can imagine, this is an incredibly useful data structure and fits perfectly with my needs. Using Winged Edge, I could determine both where a player can put their piece, and if a player wins or loses. There was one problem, though. No one had bothered to implement Winged Edge using Lua, the language I was using to write BOCO. Before I could begin working on BOCO, I needed to write a Winged Edge library.
My Winged Edge library, aptly named “Lua Winged Edge”, is a pure Lua implementation of the Winged Edge Data Structure. Any program or game engine that uses Lua can use this library. I’ve also licensed it under the MIT license which allows anyone to use, modify, and distribute both personally and commercially without royalties. The only stipulation is that the original license file remains in tact.
The first step in creating my library was to determine the simplest way to get the original data that needed describing. I opted for two methods:
- Allow the user to create a table filled with data that is formatted in a particular way
- Import the data from a Wavefront Object file
I wrote a quick and dirty Wavefront Object Loader in Lua that would parse an object file and spit out a formatted table. This loader is again written in pure Lua and all of the above licensing information applies. I am a huge fan of open source software, and try to do my part to provide useful tools where there are none. By using this loader, I was able to quickly mock up BOCO’s game board using Blender, a free, open source 3D modeling suite.
With the board data sitting inside an object file, I was able to quickly load it into a Lua table and then use that table to create the Winged Edge structure. The Winged Edge structure is as follows:
WEobject = {
vertices = {},
edges = {},
faces = {}
}
The vertices, edges, and faces tables each hold a long list of their respective data. Each data point has information about all other data points that are connected to it. For example, if face 1 is a square, it has four edges and four vertices:
local face = {
vertices = { 1, 2, 3, 4 },
edges = { 1, 2, 3, 4 }
}
Each edge and vertex also has similar data. Each vertex has positional data to indicate where on the grid it stands, and each edge has data so that it knows which edge came before it, and which edge is after it in an edge traversal:
local vertex = {
edges = { 1, 2, 3, 4 },
position = { x, y, z }
}
local edge = {
vertices = { 1, 2 },
faces = {
1 = {
prev = 4,
next = 1,
},
5 = {
prev = 7,
next = 5,
}
}
}
Now that we have our Winged Edge structure set up, what can we do with it? Well, let’s say a player clicks on a tile in a grid to play their piece on the board. We need to know if the play was valid or not. How do we do that? First, we must triangulate each tile to break it down from any shape into a bunch of triangles. Next we cast a ray where the player clicked on the screen and check each tile to see if the ray intersects a triangle. Once we get our intersection, we know which tile was clicked. We can then run our validation check against that tile to ensure the play is valid. The validation check is very simple, we must ensure that the tile is adjacent to a tile that has already been played. What we do here is traverse through the clicked tile’s edges and check each edge to see which other tile it is connected to. If that tile is has already been played at some point, the move is valid.
-- get the click point and the ray cast direction
-- in this case, straight through the z-axis
local point, direction = Vec3(mouse.x, mouse.y, 0.0), Vec3(0, 0, 1)
local intersect = false
-- loop through all the faces in the board
for i, face in ipairs(game_board.faces) do
local hit = false
-- cut the face into triangles
local triangles = WE.triangulate(i, game_board)
for _, triangle in ipairs(triangles) do
local tri = {}
-- get each vertex from each triangle
for _, vertex in ipairs(triangle) do
local x = game_board.vertices[vertex].position.x
local y = game_board.vertices[vertex].position.y
local z = 0.1
table.insert(tri, Vec3(x, y, z))
end
-- cast the ray through the triangle
hit = WE.intersect(point, direction, tri)
if hit then
local valid = false
-- if the clicked tile has not been clicked before
if game_data[i] == 0 then
-- get all the adjacent faces
local adjacent = WE.traverse(i, self.board)
-- loop through them
for _, f in ipairs(adjacent) do
-- if tile has already been played,
-- the move is valid
if game_data[f] > 0 then
Signal.emit("send_play", i)
end
end
end
end
end
end
The above code has been cut down to get the main point across
Now that we have our valid move, we must check to see if the player has won (or lost!). The win/lose checks use recursion to propagate outward from the clicked tile to check if it has encircled the enemy, or is encircled by the enemy.
-- for this example, we will use tile #5 as the clicked tile
local intersect = 5
-- if we haven’t checked this face yet, check it
if not checked[face] then
checked[face] = true
else
-- if the tile has been played and checked,
-- return true, else false
if game_data[face] > 0 then return true end
return false
end
if game_data[face] == enemy then
local f = game_board.faces[face]
-- number of adjacent blocks
local perimeter = 0
-- grab the edges from each tile
for _, edge in ipairs(f.edges) do
local e = game_board.edges[edge]
-- grab the faces from each edge
for _, eface in ipairs(e.faces) do
-- if the face is the other face on the edge,
-- run the recursion
if eface.face ~= face then
local recursion = check_encircled(eface.face, grid)
if recursion then
perimeter = perimeter + 1
else
return false
end
end
end
end
-- if all of the faces in the current recursive branch are true
-- start unraveling the recursion
if perimeter == #f.edges then return true end
-- if they aren't all true, no win/lose and
-- the recursion is done
return false
elseif game_data[face] == player then
-- We are checking a piece right next to the intersect,
-- so this is not a win, no enemy piece between
if intersect then return false end
-- we've hit the outer wall of our encircle check,
-- start unraveling
return true
end
The above code has been cut down to get the main point across
This code might be a bit difficult to understand if you are not familiar with recursive functions, but the gist of it is that you start with the clicked tile, you check each adjacent tile to see if it pas been played and by whom. If the tile has been played by your enemy, you call the function on itself with the new tile and keep branching outward. Once a recursive branch hits one of your own tiles, you know that you’ve reached a point where you might have encircled the enemy’s tiles so you start unraveling the recursion and send that data back. If at any point you find a tile that has not been played yet, you know that it is impossible that encirclement could have happened and we just kill the whole process.
In the end, loading the game board from an object file and using Winged Edge to manage the whole game was absolutely the right choice. BOCO’s code is in a state where we could potentially add new game boards with different tile shapes without needing to adjust a single line of code. Creating new game boards in Blender takes minutes instead of hours allowing for quick and simple testing of new board designs and new strategies. Developing BOCO was a surprising yet fun challenge and working with the Binary Cocoa team has been a privilege.
