david wyatt

Posted on Apr 24 • Updated on Apr 26

Creating a Turing Complete Game in Power Apps

#powerapps #powerplatform #lowcode #gamedev

I was reading about an amazing game called, 'The Game of Life', created by John Conray. It was the first 'Zero player game' (meaning that its evolution is determined by its initial state, requiring no further input), with the premise based on mathematical modelling of cellular automation. It is also 'Turing Complete', which spiked my interest even more, and made me wonder, could I replicate it in Power Apps.

Turing complete means it can theoretically compute anything that any other computer can compute, given enough time and memory. If you want to know more about a Turing Machine jump to the further reading here

So here was my idea, I wanted to do some testing and learning with the new User Defined Functions (UDF), so that would be my main learning aim, and I also wanted to show that LowCode can be powerful.

I want to cover 4 main sections in the blog

Setup Grid
Calculate the neighbouring Squares
Calculate life status of the cell
Running the Game

1. Setup Board

The Game of life works around a grid of squares, it can be any number and any shape. For my version I went with a 10 by 10 grid of squares (also known as cells in the game). To do it I used a Gallery, set to 750 by 750 pixels and wrap to 10.

The gallery items was a collection generated app onStart (I still use this far too much).

Clear(colGrid);
ForAll(Sequence(100,1,1),
    Collect(colGrid,{id:ThisRecord.Value,status:0})
);
Set(vbStart,true);

id was just for patch references, status is if the cell is dead(0) or alive(1)

2. Calculate the neighbouring Squares

The game is focused on the impact of the cells neighbours, so we need to calculate them. That means it was time to use my first UDF 😎. I would pass the cells square id and it would return the 8 surrounding squares.

As its 10 by 10 we can calculate it quite easily, by minusing the below values:


11	10	9
1	Cell	-1
-9	-10	-11

So if the cell was 24,
24 - 1 = 23
24 - -1 = 25

So my function looked like this:

GetCells(cell:Number):Text=(
    Concatenate(
        Index(colGrid,cell-11).status,",",
        Index(colGrid,cell-10).status,",",
        Index(colGrid,cell-9).status,",",
        Index(colGrid,cell-1).status,",",
        Index(colGrid,cell+1).status,",",
        Index(colGrid,cell+9).status,",",
        Index(colGrid,cell+10).status,",",
        Index(colGrid,cell+11).status
    )
)

I created a comma delimited list and return it (current User Defined Functions can not pass objects or arrays).

So if the grid looked like:

the function:

GetCells(24)

would return:
1,0,1,0,0,0,0,0

There was one problem, the edge squares. The game of life really needs an infinite grid, so we create a virtual sphere and wrap the edges. That means, the row above the first row is the last, the column after the last is the first and so on.

Thinking of the KISS principle I went with the simplest approach. I would create 9 patterns, each with there own GetCells function. There would be

Top left
Top
Top right
Left
Center
Right
Bottom left
Bottom
Bottom right

Each would have their own calculation, as example:

Top left corner
The row above is now 91-100
The column to the left is now 10,20,30,etc

So we would have:


100	91	92
10	1	2
20	11	12

which means our new math grid is:


-99	-90	-91
-9	Cell	-1
-19	-10	-11

and the user defined function would be:

GetCellsTopLeft(cell:Number):Text=(
    Concatenate(
        Index(colGrid,cell+99).status,",",
        Index(colGrid,cell+90).status,",",
        Index(colGrid,cell+91).status,",",
        Index(colGrid,cell+9).status,",",
        Index(colGrid,cell+1).status,",",
        Index(colGrid,cell+19).status,",",
        Index(colGrid,cell+10).status,",",
        Index(colGrid,cell+11).status
    )
)

The logic to decide on the pattern would be another UDF (yep you can call other UDF's within a UDF 😎). I just build out the selection logic and call the function, the return is then passed all the way back.

The code looks like this:

GetCells(cell:Number):Text=(
    If(
        cell=1,GetCellsTopLeft(cell),
        cell=10,GetCellsTopRight(cell),
        cell=91,GetCellsBottomLeft(cell),
        cell=100,GetCellsBottomRight(cell),
        Mod(cell-1,10)=0,GetCellsLeft(cell),
        Mod(cell-1,10)<>0&&cell>10&&cell<91&&Mod(cell,10)<>0,GetCellsCenter(cell),
        Mod(cell,10)=0,GetCellsRight(cell),
        cell<10,GetCellsTop(cell),
        cell>91,GetCellsBottom(cell)
    )
);

3. Calculate life status of the cell

We have our neighbours, now we need to figure out if our cell will live or die. The game logic is:

Any live cell with fewer than two live neighbors dies, as if by underpopulation.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by overpopulation.
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

As I said before we can't pass in arrays/collections to a UDF, so we are going to pass our comma delimited list and split it into an array. Spliting creates a default key of Value, which we then reference in our sum.

The logic isn't too complicated, and the UDF looks like:

UpdateCell(neighbours:Text,status:Number):Number=(
    If(
        Sum(Split(neighbours,","),Value)<2,0,
        Sum(Split(neighbours,","),Value)=2,status,
        Sum(Split(neighbours,","),Value)=3,1,
        Sum(Split(neighbours,","),Value)>3,0
    )
);

4. Running the Game

There are 2 parts to running the game, the interaction/start and then the run.

Interaction/Start
Before the game starts the player needs to set the grid up with live cells.

To do this I added a button to the gallery and add a OnSelect parameter. It would check to see if the game was running, if not it would then patch the grid collection (colGrid), updating the items status:

If(vbStart,
    If(ThisItem.status=0,
        Patch(colGrid,ThisItem,{status:1})
    ,
        Patch(colGrid,ThisItem,{status:0})
    )
)

Run
Once the grid is select we want to start the game, which then will run a 'day' cycle updating each cell. My original plan was to loop over the colGrid and update each cell, but that would then impact the next row/cell. So I went with a Blue/Green approach. I would read from the colGrid while updating a different collection, then swap them over.

The code was pretty simple and based on the onStart loading loop.

Clear(colGridNew);
ForAll(Sequence(100,1,1),
    Collect(colGridNew,{
        id:ThisRecord.Value,
        status:UpdateCell(GetCells(ThisRecord.Value),Index(colGrid,ThisRecord.Value).status)
    });
);
ClearCollect(colGrid,colGridNew);
Set(viDays,viDays+1);

And that's it, I added some extra settings like speed of day and day counter and it's all done.

After playing with User Defined Functions I love them, I over used them but I found them so much easier to read and maintain. Having all your key code in one place is also really convenient. It's not perfect, lack of collection/object inputs/outputs is a big one, but hopefully that will come soon.

It's also nice to show that LowCode isn't as limited as some think, with a little imagination you can do anything.

As always the app is available to download here, and if you want to see the original game check it out here.

Further Reading
A Turing machine is a theoretical computational model invented by Alan Turing in 1936 It's essentially a thought experiment that helps us understand the fundamental workings of computation.

Here's how it works:

Imagine an infinitely long tape divided into squares, each containing a symbol (like 0, 1, or blank). A "tape head" reads and writes symbols on the tape, moving left or right one square at a time. The machine itself is in a specific state at any given moment (State A, State B, etc.).There's a set of rules that tells the machine what to do based on the current state and the symbol it reads on the tape. The rules can involve:

Changing the symbol on the tape.
Moving the tape head left or right.
Switching the machine's state.

These simple steps allow the Turing machine to perform complex computations. Despite its apparent simplicity, Turing machines are incredibly powerful.

Universal computation
It's been proven that any computer program can be theoretically simulated by a Turing machine, given enough time and tape. Turing machines are a kind of a universal model for computation.
Foundation of computer science
Turing machines are fundamental to theoretical computer science. They help us understand the capabilities and limitations of computers and define what problems are computationally possible.