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.

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)
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)
    f.Letter AS FromLetter
    , t.Letter AS ToLetter
    , md.minDist
    , md.direction
FROM dbo.LetterSequence AS f
CROSS JOIN dbo.LetterSequence AS t
            WHEN f.SequenceNo >= t.SequenceNo
                THEN f.SequenceNo - t.SequenceNo
            ELSE ((@maxLetterSeqno + f.SequenceNo - t.SequenceNo) % @maxLetterSeqno)
            WHEN t.SequenceNo >= f.SequenceNo
                THEN t.SequenceNo - f.SequenceNo
            ELSE ((@maxLetterSeqno + t.SequenceNo - f.SequenceNo) % @maxLetterSeqno)
) AS distance (MoveMinus, MovePlus)
        CASE WHEN distance.MoveMinus <= distance.MovePlus
            THEN distance.MoveMinus
        ELSE distance.MovePlus
        CASE WHEN distance.MoveMinus <= distance.MovePlus
            THEN 'DOWN'
        ELSE 'UP'
) AS md(minDist, direction)

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

FROM dbo.LetterDistance AS ld
    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.

    @wordFrom char(6)
    , @wordTo char(6)
    WITH unpivotLetters AS
            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)
        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
        SELECT ld.Distance, ld.Direction
        FROM dbo.LetterDistance AS ld
            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)

    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)
 (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
    , WordFrom
    , WordFromDescription
    , IdTo
    , WordTo
    , WordToDescription
    , TotalDistance
    , 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 */
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.

    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
    SELECT TOP (1)
        @IdTo = wc.IdTo
    FROM dbo.WordCombination AS wc
        wc.IdFrom = @IdFrom
            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

    , 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

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.