Efficient Cheating at Lego Video Games

Page content

Foreword πŸ”—︎

I’ve started to play Lego Video games with my daughter, and since it’s one of her first games, it can be a little frustrating.

Even though there are no high stakes (you can’t lose in those games), I thought maybe playing with the cheats might make a better experience.

If you are not familiar with the games, you enter cheats via an interface like this:

A six-position combination lock in initial state

Despite playing on a computer and with a perfectly usable keyboard, I cannot type the input directly.

Instead, I must use this six-position combination lock that uses letters and numbers.
It’s cyclic and goes from A to Z, 0 to 9 and back to A again.
Up goes forwards; Down goes backwards.

I thought about finding an efficient way of input because it’s not enough to enter and unlock the cheat once.
You have to reenter the cheat for every new game session.

The plan πŸ”—︎

  1. I’ll create a table representing one dial with letters and numbers in sequence.
  2. Then I’ll generate all possible combinations and calculate the shortest distance. Is it faster to change from M to 5 going up or down?
  3. Now that I can calculate the distance for letters, I’ll create a function that does the same but for the whole cheat codes.
  4. I’ll generate all code combinations.
  5. Finally, I will use a greedy algorithm to find a short path.

The code πŸ”—︎

Create the LetterSequence πŸ”—︎

First, we’ll create the database and table to hold our sequence.

CREATE DATABASE LegoCheats
GO
USE LegoCheats

CREATE TABLE dbo.LetterSequence
(
	SequenceNo tinyint IDENTITY NOT NULL INDEX IX_SequenceNo UNIQUE
	, Letter char(1) NOT NULL CONSTRAINT PK_LetterOrder PRIMARY KEY
)

I wish I had the STRING_SPLIT parameter enable_ordinal, but at the time of writing, it’s available only on Azure SQL and is planned for SQL Server 2022.

So I’ll have to use the target table Identity to simulate that.
To get the string, I wrote abcdefghijklmnopqrstuvwxyz0123456789 and then used RegEx to add a separator.
Find \B, Replace ,

INSERT INTO dbo.LetterSequence (Letter)
SELECT UPPER(value)
FROM STRING_SPLIT('a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,0,1,2,3,4,5,6,7,8,9', ',')

Create the LetterDistance πŸ”—︎

Now we calculate the shortest distance for each combination.

After creating the table, I’ll grab the maximum sequence number (36).
When I cross the boundary between the start and end of the sequence, I’ll add the @maxLetterSeqno and use the modulo operator (%) to wrap around.

When the distance is the same both ways (like 0 or 18), I’ll pick the direction as DOWN because it doesn’t matter.

CREATE TABLE dbo.LetterDistance
(
	LetterFrom char(1) NOT NULL 
	, LetterTo char(1) NOT NULL 
	, Distance tinyint NOT NULL
	, Direction varchar(10) NULL
	, CONSTRAINT PK_LetterDistance PRIMARY KEY (LetterFrom, LetterTo)
)

DECLARE @maxLetterSeqno tinyint = (SELECT MAX(SequenceNo) FROM dbo.LetterSequence)

INSERT INTO dbo.LetterDistance 
(LetterFrom, LetterTo, Distance, Direction)
SELECT 
	f.Letter AS FromLetter
	, t.Letter AS ToLetter
	, md.minDist
	, md.direction
FROM dbo.LetterSequence AS f
CROSS JOIN dbo.LetterSequence AS t
CROSS APPLY
(
	VALUES 
	(
		CASE
			WHEN f.SequenceNo >= t.SequenceNo
				THEN f.SequenceNo - t.SequenceNo
			ELSE ((@maxLetterSeqno + f.SequenceNo - t.SequenceNo) % @maxLetterSeqno)
		END,
		CASE 
			WHEN t.SequenceNo >= f.SequenceNo
				THEN t.SequenceNo - f.SequenceNo
			ELSE ((@maxLetterSeqno + t.SequenceNo - f.SequenceNo) % @maxLetterSeqno)
		END
	)
) AS distance (MoveMinus, MovePlus)
CROSS APPLY 
(
	VALUES
	(
		CASE WHEN distance.MoveMinus <= distance.MovePlus
			THEN distance.MoveMinus
		ELSE distance.MovePlus
		END
		, 
		CASE WHEN distance.MoveMinus <= distance.MovePlus
			THEN 'DOWN'
		ELSE 'UP'
		END
	)
) AS md(minDist, direction)

Here’s the answer to the earlier question (shortest path from M to 5)

SELECT *
FROM dbo.LetterDistance AS ld
WHERE 
	ld.LetterFrom = 'M' 
	AND ld.LetterTo = '5'

Shortest path from M to 5 is 17 down

Calculate word distance πŸ”—︎

Now that I can calculate the individual letter distance, I’ll move on to the whole words.

I’ll create an Inlinable Table-Valued Function (ITVF) where there are two words as an input and a total distance + instructions as an output. I’m not counting the movement required to switch between the dials.

CREATE OR ALTER FUNCTION dbo.WordDistance
(
	@wordFrom char(6)
	, @wordTo char(6)
)
RETURNS table
AS
RETURN
	WITH unpivotLetters AS
	(
		SELECT
			SUBSTRING(@wordFrom, cj.Position, 1) AS letterFrom
			, SUBSTRING(@wordTo, cj.Position, 1) AS letterTo
			, cj.Position
		FROM (VALUES (1), (2), (3), (4), (5), (6)) AS cj(Position)
	)
	SELECT 
		SUM(ca.Distance) AS WordDistance
		, MAX(IIF(ul.Position = 1, CONCAT_WS(' ', ca.Distance, ca.Direction), NULL)) AS Letter1
		, MAX(IIF(ul.Position = 2, CONCAT_WS(' ', ca.Distance, ca.Direction), NULL)) AS Letter2
		, MAX(IIF(ul.Position = 3, CONCAT_WS(' ', ca.Distance, ca.Direction), NULL)) AS Letter3
		, MAX(IIF(ul.Position = 4, CONCAT_WS(' ', ca.Distance, ca.Direction), NULL)) AS Letter4
		, MAX(IIF(ul.Position = 5, CONCAT_WS(' ', ca.Distance, ca.Direction), NULL)) AS Letter5
		, MAX(IIF(ul.Position = 6, CONCAT_WS(' ', ca.Distance, ca.Direction), NULL)) AS Letter6
	FROM unpivotLetters AS ul
	CROSS APPLY 
	(
		SELECT ld.Distance, ld.Direction
		FROM dbo.LetterDistance AS ld
		WHERE 
			ld.LetterFrom = ul.letterFrom
			AND ld.LetterTo = ul.LetterTo
	) AS ca

Score word combinations πŸ”—︎

To test this out, I have prepared a list of cheats for the Lego Batman: The Videogame that I want to apply.

I will generate all combinations (except with itself), calculate the word distance and save them into a WordCombination table.

/* Prepare the tables */
CREATE TABLE dbo.WordCombination
( 
	IdFrom tinyint NOT NULL
	, WordFrom char(6) NOT NULL
	, WordFromDescription varchar(70) NULL
	, IdTo tinyint NOT NULL
	, WordTo char(6) NOT NULL
	, WordToDescription varchar(70) NULL
	, TotalDistance int NOT NULL
	, CONSTRAINT PK_WordCombination PRIMARY KEY (IdFrom, IdTo)
)

CREATE TABLE #CheatCodes
(
	Id tinyint NOT NULL
	, Word char(6) NOT NULL
	, CheatDescription varchar(70) NULL
)

/* Insert the cheat codes, I include the starting point as well */
INSERT INTO #CheatCodes (Id, Word, CheatDescription)
VALUES 
 (01, 'AAAAAA', 'Initial position')
,(02, 'ML3KHP', 'Extra Hearts')
,(03, 'JRBDCB', 'Faster Batarangs')
,(04, 'EVG26J', 'Faster Piece Assembly')
,(05, 'ZOLM6N', 'Faster Walking')
,(06, 'D8NYWH', 'Flaming Batarangs')
,(07, 'XPN4NG', 'Frozen Batarangs')
,(08, 'HJH7HJ', 'Heart Regeneration')
,(09, 'JXUDY6', 'Immunity to Freeze')
,(10, 'WYD5CP', 'Invincibility')
,(11, 'ZXGH9J', 'Minikit Detector')
,(12, '9LRGNB', 'Multiply Score')
,(13, 'KHJ544', 'Piece Detector')
,(14, 'MMN786', 'Power Brick Detector')
,(15, 'N4NR3E', 'Score Multiplier x2')
,(16, 'CX9MAT', 'Score Multiplier x4')
,(17, 'MLVNF2', 'Score Multiplier x6')
,(18, 'WCCDB9', 'Score Multiplier x8')
,(19, '18HW07', 'Score Multiplier x10')

INSERT INTO dbo.WordCombination
(
	  IdFrom
	, WordFrom
	, WordFromDescription
	, IdTo
	, WordTo
	, WordToDescription
	, TotalDistance
)
SELECT 
	f.Id
  , f.Word
  , f.CheatDescription
  , t.Id
  , t.Word
  , t.CheatDescription
  , wd.WordDistance
FROM #CheatCodes AS f			/* from */
CROSS JOIN #CheatCodes AS t		/* to */
CROSS APPLY dbo.WordDistance(f.Word, t.Word) AS wd
WHERE f.Id <> t.Id /* all combinations except itself */

/* Check the result */
SELECT *
FROM dbo.WordCombination AS wc 
ORDER BY wc.IdFrom, wc.TotalDistance

Word combinations with calculated distance

Finding efficient path πŸ”—︎

Ideally, I want to enter every cheat from my #CheatCodes temp table with as few moves as possible. That’s 18 entries (the first row is the initial state).

I’ve chosen to use a greedy algorithm that uses a loop, for simplicity.

I will start on the AAAAAA position and pick the first word with the lowest distance until all words have been visited.

CREATE TABLE #FinalPath
(
	SeqNo tinyint IDENTITY NOT NULL
	, IdFrom tinyint NOT NULL
	, IdTo tinyint NOT NULL
)

DECLARE @LoopCounter tinyint = 1
DECLARE @IdFrom tinyint = 1 /* AAAAAA */
DECLARE @IdTo tinyint
DECLARE @maxId tinyint = (SELECT MAX(cc.Id) FROM #CheatCodes AS cc)

WHILE @LoopCounter <= @maxId
BEGIN
	SELECT TOP (1)
		@IdTo = wc.IdTo
	FROM dbo.WordCombination AS wc
	WHERE 
		wc.IdFrom = @IdFrom
		AND NOT EXISTS 
		(
			SELECT *
			FROM #FinalPath AS fp
			WHERE fp.IdFrom = wc.IdTo
		)
	ORDER BY wc.TotalDistance

	INSERT INTO #FinalPath (IdFrom, IdTo)
	SELECT @IdFrom, @IdTo

	SET @IdFrom = @IdTo
	SET @LoopCounter += 1
END 

SELECT
	  wc.WordFrom
	, wc.WordTo
	, wc.WordToDescription
	, SUM(wd.WordDistance) OVER () AS TotalDistanceSum
	, wd.WordDistance
	, wd.Letter1
	, wd.Letter2
	, wd.Letter3
	, wd.Letter4
	, wd.Letter5
	, wd.Letter6
FROM #FinalPath AS fp 
JOIN dbo.WordCombination AS wc
	ON fp.IdFrom = wc.IdFrom
	AND fp.IdTo = wc.IdTo
CROSS APPLY dbo.WordDistance(wc.WordFrom, wc.WordTo) AS wd
ORDER BY fp.SeqNo

Path to enter all 18 codes

I have to test it on the real thing, of course.

Code entered in game

Optimal path πŸ”—︎

I’ve used the word “efficient” instead of “optimal” on purpose. That’s because this is a famous computer science problem called Travelling salesman problem.

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

And finding the optimal path would significantly increase the scope of this blog post. There is always a brute force solution, but the number of combinations ramps up quickly.

I’ve tried brute-forcing the solution for the first 12 rows (1 starting position + 11 cheats), and it took my pc 1 hour and 6 minutes to come up with the best path 1-3-9-12-7-10-11-5-2-8-4-6 for the total distance of 409.
The greedy algorithm came up with 1-3-8-4-11-5-10-7-12-9-6-2 (total distance = 456), which is good enough for me.

It is an interesting problem, so I might revisit it in a future blog post.