Introduction

• Visit the LDJam page if you participated in Ludum Dare 55!
  • https://ldjam.com/events/ludum-dare/55/blakulla
• Download the game from itch.io if you want to play!
  • https://windmillgames.itch.io/blakulla

Discovery Phase

This picture I found on Google (actual source) I feel inspired me the most to continue with the approach I did, which I explain in detail further on:

Here's an animation of the algorithm in action, which I found here:

• $1 Unistroke Recognizer
• Shape Matching - Algorithms Lab

How It Works - Overview

• Mouse movements are captured into a list of XY coordinates, in screen-space
• Screen-space coordinates are passed into an algorithm to simplify the shape to make further computations easier
• List of simplified coordinates is normalized into a unit square
• The list of pre-made drawings is iterated over. For each shape, the points of the user drawing are scored on their proximity to points within the template. The sum of these proximity scores is the "similarity score" for that specific pre-made drawing.
• The pre-made drawing with the lowest similarity score is chosen, contingent on that score being lower than a sensitivity threshold.

How It Works - The Nitty Gritty

Calculating the drawn path

1: 
toSimpleNormal = function(self)
2: 
	local simplePoints = simplifyPath(self.points, SIMPLIFY_TOLERANCE) -- Ramer-Douglas-Peucker
3: 
	local simplePath = Path(simplePoints)
4: 

5: 
	local minx, miny = math.huge, math.huge
6: 
	local maxx, maxy = 0, 0
7: 
	simplePath:forEachPoint(function(point)
8: 
		minx = math.min(minx, point.x)
9: 
		miny = math.min(miny, point.y)
10: 

11: 
		maxx = math.max(maxx, point.x)
12: 
		maxy = math.max(maxy, point.y)
13: 
	end)
14: 

15: 
	local xscale = maxx - minx
16: 
	local yscale = maxy - miny
17: 

18: 
	local simpleNormalPath = Path()
19: 
	simplePath:forEachPoint(function(point)
20: 
		local px = (point.x - minx) / xscale
21: 
		local py = (point.y - miny) / yscale
22: 

23: 
		simpleNormalPath:addPoint(px, py)
24: 
	end)
25: 

26: 
	return simpleNormalPath
27: 
end,

And here's an example screenshot from development that shows a drawn shape in white, and its normalized counterpart in yellow. The blue shape is the first template I coded up, which was there to prove that normalized shapes were located and scaled correctly.

Comparing the drawn path to the templates

Before I hit you with a wall of text and math, here's a screengrab from development which illustrates what we're working towards. I find this helpful to refer to to help follow along with the calculations and logic being performed:

A screenshot I took early in development, before this left-and-right check was implemented, may help to visualize the problem:

While the shape was correctly identified in this example, note how in the furthest-right example, the midpoint of the hourglass-looking shape is associated with many points that aren't connected to each other in the drawn path. The diamond and square shapes are also poorly recognized, with the corners being completely ignored. I found this ultimately has the effect of skewing the totalDistance in a way that makes a misrecognition more likely.

• 0 points missing = 0 added to totalDistance
• 1 point missing = 1 added to totalDistance
• 3 points missing = 27 added to totalDistance
• 5 points missing = 125 added to totalDistance ...and so on.

1: 
compareTo = function(self, other)
2: 
		local closestPoint, closestPointIdx
3: 
		local totalDistance = 0
4: 
		local touchedPointIndexes = {}
5: 

6: 
		self:forEachPoint(function(point)
7: 
			-- Find the closest point in the path
8: 
			closestPoint, closestPointIdx = other:findNearestPoint(point.x, point.y, closestPointIdx)
9: 
			if closestPoint then
10: 
				local distToClosestPoint = wx.math.distanceBetween(point.x, point.y, closestPoint.x, closestPoint.y)
11: 
				totalDistance = totalDistance + math.pow(distToClosestPoint, 2)
12: 

13: 
				-- Mark this point as touched
14: 
				touchedPointIndexes[tostring(closestPointIdx)] = true
15: 
			else
16: 
				-- Edge case - doesn't actually happen but I need to put something here
17: 
				totalDistance = totalDistance + math.huge
18: 
			end
19: 
		end)
20: 

21: 
		local unusedPointCount = #other.points
22: 
		for _ in pairs(touchedPointIndexes) do
23: 
			unusedPointCount = unusedPointCount - 1
24: 
		end
25: 

26: 
		local adjustedTotalDistance = totalDistance + (unusedPointCount ^ 3)
27: 
		return adjustedTotalDistance
28: 
	end,

How Did We Decide On The Shapes?

At one point Simon and I got together on a call and just streamed Paint.NET to each other and drew shapes to see what we came up with. Here's a collection of some of the shapes we came up with in that session:

Simon, who I think had been programming for 14-15 hours at this point, was so tired. Out of nowhere he quietly goes "...what about this" and shows me this:

Integrating Path-drawing Into The Game

I created another class, PathAnimator, which can take a Path and animates it. This is how you can see the spell path "tutorial" appear when you hover over cards. Here's how that looked early on:

Conclusion

PS - Thanks to the entire Windmill Games team for helping to make Blakulla as great as it is. Simon is a wizard programmer who makes player control and enemy AI look effortless. Belle is simply magical with her artistic abilities - I always think she has outdone herself but then she goes and does it again on the next game. Daniel is a musical genius as always and really knows how to set the tone for our games. And this time around we had a new SFX person, Felipe, who knocked it out of the park with work is just astounding in my opinion. I love everyone I get to work with and I love everything that we've made. I'm beyond lucky to be able to work with such an amazing team <3