This post describes some of the challenges faced while creating a TI-BASIC version
of Bejeweled for the 84+CSE

Cross-posted by request of Kerm from https://ukl.me/pushing-ti-basic-to-its-limits/
As such, many of you will already be familiar with the information regarding TI-BASIC
prestented in this post. Skip to Creating a Match-3 Game if you are already familiar
with TI-BASIC.

TI-BASIC
TI-BASIC is the unofficial name for the programming language included on the stock operating systems
of the TI-83 and TI-84 Plus series of calculators. This includes a large set of calculators, the
most popular these days being the 96x64 monochrome TI-84+SE, the 320x240 16 bit color TI-84+ Color
SE (referred to as the "CSE"), and the newly released TI-84+CE which features a LCD which is
signficantly faster to access than the CSE and a processor upgrade from a z80 to an ez80.

The 84+ and 84+CSE use z80 processors clocked at roughly 15mhz. This is an old CPU
architecture, with no modern features like caching, out of order execution, floating-point units, or
even pipelining. As a result of the CPU limitations, the slow interpreter, and the fact that all
numbers in TI-BASIC are 9 byte floats, programmers may find that even the simplest of games they
make run too slowly to be playable. Many turn to projects like the Axe Parser to provide a faster
compiled language. Some bite the bullet and learn how to program games in assembly. However, those
that continue with TI-BASIC learn the ins and outs of the language, and how to make it work for
them.

Quirks of TI-BASIC
TI-BASIC has a few things that should be known before reading the following code. All numeric
variables are one letter. Valid variables include A-Z and θ (theta). There are also one dimensional
List variables such as L₁ and two dimensional Matrix variables such as [A]. List and matrix
indices are in the range of [1,Length]. Matrix values are accessesed with [Matrix](Row,Column).


Creating a Match-3 Game
One of the first problems anyone who creates a match-3 game (like Bejeweled) runs across is
detecting matches. Matches need to be detected wherever they may lie on the board, so that chain
reactions can occur from tiles falling in. One of the simplest solutions works just fine for
anything written to run on modern hardware.

Code:

This works for removing tiles for matches greater than or equal to 3 in length. It removes all
horizontal matches; row and column can be switched to find vertical matches. The problem is that
this code is somewhat complex, and as a result the TI-BASIC version of it runs fairly slowly.

Code:


Experienced TI-BASIC developers will notice that this version is written for clarity over speed or
size. Even with all the micro-optimizations that can be added to the code, it runs too slowly to be
useful, as shown in the included recording. From the time that the cursor disappears to the time it
reappears, the player can't do anything but stare at the screen. The displayed version also has the
added optimization that it won't check columns or rows which could not have changed since the
previous check, since no changes implies no matches, but it's still not enough to be playable.

So what can be done to make this program run better? Up until this point I had thought of the
problem solely as counting the number of matching tiles, but it can be thought of another way, one
which the calculator has built in functions to deal with. They key lies with the DeltaList()
function.

DeltaList(), or ΔList() as it's displayed on the calculator, takes a list and returns a new list
with the difference between the elements of the source list. The result will be one element shorter
than the source list, since there is no element preceding the first to subtract from. Therefore
DeltaList({1,3,3,3,2,4}) results in {-2,0,0,-1,2}. If the difference between two elements is
zero, they are equivelant! Applying DeltaList twice to a list should then place zeros only at the
end of matches of three, indicating exactly where matches exist with no counting being done in
TI-BASIC code.

Code:


Dealing With False Positives
Unfortunately, there's a flaw with simply using DeltaList(DeltaList()) on our input. What if we
provide the list {6,1,2,3,5}?

Code:

We get a false positive. That simply won't work for the game, but the solution isn't difficult:
Raise the source list to a power. Raising to the power of two results in two possible sequences that
give false positives, {7,5,1} and {1,5,7}, but raising to the power of three results in none.
Even with this extra calculation, the speed still beats out calculating matches in TI-BASIC. The new
matching code (minus optimizations) looks something like this.

Code:


Not only is the code faster, it's also much simpler. In TI-BASIC, the less code running the better,
and here all the code does in the inner loop is a simple If and a mass set to zero. The result is
a much more playable match-3 game. The recording shown is a more complete version with a scoring and
level system, but it displays the speed advantages when making matches quite well. Not everyone is
lucky enough to be able to reframe their problem in a way that fits the language so well, but these
sort of tricks are what really allow people to continue to create impressive games in this
incredibly restrictive language.

Hidden Complexity
To the untrained eye, it may seem that I've removed the loop necessary to count the number of
matching elements in a row or column. Not only have I _not_ done that, I've increased the amount of
work that needs to be done. DeltaList(DeltaList()) has to take the difference of the input list, and
then further take the difference of the differences. Additionally, the input list has to be cubed
first! In reality, I've simply hidden the loop by moving the work out of my code and into the
interpreter's code. DeltaList() is implemented in assembly, while my naïve solution is not. All the
operations being performed on a particular row or column are still O(n), but the assembly is able to
work so much more efficiently that it results in a noticeable speed up.

Game-Over Detection
Every good match-3 game needs to be able to tell the player when the game is over. Otherwise, they
may spend a long time staring at an unsolvable board, before finally getting frustrated and
quitting. Unfortunately, checking if a game is still playable is a rather long process. My initial
plan was to perform a bunch of pattern matching using more DeltaList(). The code builds a list by
reading different patterns of 3 tiles from the board that, if they all contain the same tile,
indicate a potential future match. This strategy works, but it's extremely slow. To solve this
problem, the matching can be staggered. On every repetition of the main game loop, the game
processes key input and then performs one step in the game-over detection. There are 48 total steps.
If the 48th step is reached, and returns no solutions, the game is over.

Saving the Game
Saving the game is a fairly simple process. A few variables are saved to a TI-BASIC List, and loaded
at next start-up. This presents two problems: How can the program handle an archived (unaccessable)
list, and how can it verify that the data is valid? To handle archived lists, it tries to access the
list very early on in the program, ensuring that if the list is archived the program will fail
quickly, without wasting time. To verify data correctness, an error detection code is calculated
from the other 4 values in the list. If the error detection code stored in the list does not match
the code calculated from the saved values, the game resets to its default state. As an added bonus,
this means that the game can simply create the list if it doesn't exist and read in the zeroed out
list to load the game. It will fail the error detection, forcing the game to the proper initial
state.

A Note On Graphics
Anyone who has even lightly touched on using TI-BASIC knows that the level of graphics displayed in
the two recordings above simply isn't possible in pure TI-BASIC at that speed. To work around this
problem, people have developed shells for launching these TI-BASIC programs that provide routines
the programs can call for graphics, advanced key input, and other various utility operations.
Unfortunately they can't fully solve the speed problems of the language, but they're certainly a leg
up on pure TI-BASIC. The library I'm using for the demos above is called xLIBC, written by tr1p1ea
and included in the DCSE library created by Christopher Mitchell.

Wow! That is a very detailed writeup. I don't have time to read it now, but I'll try to read it when I have time.

Although I'm not really active anymore, I just wrote up this explanation of game-over checking for JWinslow23's monochrome version of Bejeweled on tibasicdev, and I thought I would post it here.


Code:


It's a somewhat complicated speed optimization. All of these operations (vectorized list operations at 1ms per element, {{DeltaList(}} at 1.5ms, {{sum(}} at roughly 1ms per element added) are very fast compared to {{For(}} loops, which take about 1ms per iteration **and** require 1.5ms list accesses multiple times in each iteration. Furthermore, multiplication is especially fast when the right operand has a small digit sum, which is true in the first line.

L1 and L2 are two adjacent rows (or columns, but let's say rows for now) of the matrix representing the Bejeweled board. Gem type 1 is stored as the number 10^1 = 10, gem type 2 as 10^2 = 100, and so on up to 10^7.

The "If" returns true if a horizontal three-in-a-row can possibly be formed. Without counting symmetries, there are three formations that can lead to a three-in-a-row, where {{x}} is a certain color and {{.}} is not that color:


Code:


3x2 checking

The first two lines and {{.3≤max(max(fPart(Ans/L₁),fPart(Ans/L₂)))}} checks for the first two cases (3x2). The snippet I just quoted checks if the same power of ten has been added to three adjacent columns of {{Ans}}, where {{Ans}} contains, for example, 1010 where L1 is 100 and L2 is 10000 or vice versa, and 10 where L1 and L2 are both 100. Imagine that the gem types in the two lines being processed are:


Code:


We want to detect the possible three-in-a-row in columns 5, 6, and 7. How?

The first line adds together the elements from L1 and L2, except when they're equal, in which case it just uses the element from L1. This will give us the following (line breaks for ease of reading)


Code:


The second line adds these numbers together in pairs. In this case, we get {{sum(Ans,5,6)}} in position 7, or the number {{0001201}}. This number contains a 2 in the tens place, since the fifth and sixth columns of the row each contained the same number 3. When we divide 0001021 by the corresponding number in L1, we get 00010.21, of which the fPart( is at least 0.2. The max( means that the code will detect whether *any* fPart( is at least 0.2, and therefore whether there was a 2 in the correct position in the list, and therefore whether there were two matches of a gem in the two columns before, and therefore whether a 3x2 move exists.

4x1 checking

{{max(.3010299957=abs(DeltaList(log(abs(DeltaList(DeltaList(L₁}} checks for the last case (4x1). This is done by checking if any two adjacent numbers in the second differences of L1 differ by a factor of +-2 or +-1/2. Say the numbers corresponding to gem types on four consecutive spaces in a line are {{a b c d}}. Take the second differences to obtain the following:


Code:


Solving the equations {{abs(d+b-2c) = 2abs(c+a-2b)}} or {{abs(d+b-2c) = 1/2*abs(c+a-2b)}}, using information that all numbers are powers of ten, leads to the fact that {{a=d}} and ({{a=b}} or {{a=c}}).

How does one check for adjacent numbers in a list whose absolute values differ by a factor of two? First, we take the {{log(abs())}} of it, then adjacent numbers in the new list must differ by not a factor, but the constant value {{log 2}}, which is hardcoded as {{.3010299957}}.

Note that 0 would throw an error as an input into {{log()}}. Why doesn't this happen? Second differences of a list are constant when there are three consecutive terms in an arithmetic sequence. This only happens with powers of ten when they're constant, and since there are no threes-in-a-row left in a list once a move is completed and game-over checking begins, there are no constant blocks of three values.

{{ln(}} would work equally well, but it's slower—I think the TI-83+ series calculates {{ln(}} by multiplying the value from {{log(}} by a precomputed {{ln(10)}}. I'll explain this more tomorrow as well.

Now that I look at it, there are a couple of bugs and a suboptimality:

* it won't check the first row and column, and would probably give game over when there are only moves in the first row or column
* {{.1(L₁+L₂)(L₁≠L₂}} should be {{.1(L₁+L₂*(L₁≠L₂}}. I initially wrote this wrong, forgetting the {{*}}, and I guess the mistake stayed.
* The {{sum(Ans,1,3),...}} part can actually be optimized by 9ms per line by changing it to {{sum(Ans,1,2),sum(Ans,2,3)}} etc., and changing {{.3}} to {{.2}}, but by the time I tested that JWinslow23 had already released the game.

So the code should actually be


Code:


With another change to the surrounding code to check the first row and column.

Let JWinslow23 know if you find any further optimizations; this code, along with the gem-moving algorithm, is the bottleneck, as it runs after every move and takes a couple of seconds.

Oh, lirtosiast, I actually integrated the check a bit differently than you did there. As in, both of the checks are written in a weird way inside the code. Nice to see not only an improvement, but rather how I was supposed to do it. I completely don't understand this a little less now