Blog Post

Efficient Cheating at Lego Video Games

,

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.

Original post (opens in new tab)

Rate

You rated this post out of 5. Change rating

Share

Share

Rate

You rated this post out of 5. Change rating