Category: Source code

39 Puzzles in C

39 Puzzles in C

Simon Grantham PuzzlesThose of you who have used the Putty utility to connect to a remote computer using SSH might recognise the name chiark. It’s also the home of various puzzles that are coded in C and they’ve made the source code available.  You can read about each puzzle via the online documentation.

The puzzles are one player games and run natively on Unix (GTK), on Windows, and on Mac OS X. As usual I’ve added these to the C code links as well. Puzzles are near enough to games to count! I’ve screen grabbed 15 of them but there are almost 40 in total.

If you like this sort of thing and have an idea for a game, take a look at the devel page. The puzzles are split into three parts, front, middle and back ends. If you want to implement a new front end (SDL2 anyone?) then you just change the front end.

A better random number generator

A better random number generator

Binary numbers
Image by Gordon Johnson from Pixabay

How’s this for a minimal RNG implementation in C?

// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)

typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;

uint32_t pcg32_random_r(pcg32_random_t* rng)
{
    uint64_t oldstate = rng->state;
    // Advance internal state
    rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
    // Calculate output function (XSH RR), uses old state for max ILP
    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
    uint32_t rot = oldstate >> 59u;
    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}

https://www.pcg-random.org/

is a website dedicated to random numbers using their algorithms, The whole site is good but I particularly like the party tricks page where they show that one of their random number generators generates a sequence that contains interesting things like source of a C file, zip files and text from hamlet.

More thoughts on shuffledness

More thoughts on shuffledness

Shuffling
Image by Hucklebarry from Pixabay

Thinking about what I said, it can’t be just about how far a card moves when shuffled but how much disordering occurs as well. If you shuffled the deck and discovered 7 cards in a sequence like 2,3,4,5,6 of hearts deep into the deck, they would have moved from near the top of the deck (an “ordered deck” is A-K in Hearts, Clubs, Diamonds and Spades) then it probably wasn’t a very good shuffle.

One way to measure “disorder” is to subtract each card’s ordinal value from it’s successor and sum up the absolute value of them . Ordinal value is the value 0-51 where 0 = Ace Hearts, 1 = 2 Hearts and so on. In an ordered deck the sum of all these subtractions will be 51. In a well shuffled deck I would guess it might be something like 1352 (52 x 26). Absolute value is the abs(x) function of x which is always positive if x is negative.  abs(-8) = 8. abs(8) = 8.

So now for shuffledness we have two values. Displacement and disorder. If both are calculated as a value between 0 and 1 then multiplying them together might work as a measure of shuffledness.

Here’s a very simple example of calculating the value for disorder. So far the calculations have never got a total much above 900, and not near 1352. I’ll run a few experiments and see the range of values.

// shuffledness.c : This measures how shuffled a deck of cards is
// cards are held as values 0-51 in a 52 int array.

#include <time.h>
#include <stdio.h>
#include <stdlib.h>

int deck[52];
time_t t;

// Order the cards 0-51. 0 = Acew Hards,13 = Ace Clubs,26 = Ace of Diamonds and 51 = King of Spades
void InitDeck() {
	for (int i = 0; i < 52; i++) {
		deck[i] = i;
	}
}

// Works on glovbal array deck and calculates a value for how displayed each card is
float CalcDisorder() {
	int total=0;
	for (int i = 1; i < 52; i++) {
		total += abs(deck[i] - deck[i - 1]);
	}
	printf("Total = %d\n", total);
	return total / (52.0f * 26.0f);
}

// Shuffle a deck by swapping two random cards a specified number of times
void ShuffleDeck(int numtries) {
	int firstIndex, secondIndex;
	for (int i = 0; i < numtries; i++) {
		do {
			firstIndex = rand() % 52;
			secondIndex = rand() % 52;
		}
		while (firstIndex == secondIndex);
		int value = deck[firstIndex];
		deck[firstIndex] = deck[secondIndex];
		deck[secondIndex] = value;
	}
}

int main() {
	/* Intializes random number generator */
	srand((unsigned)time(&t));
	InitDeck();
	ShuffleDeck(1000);
	printf("CalcDisorder() == %f\n", CalcDisorder());
	return 0;
}

That’s about 50 lines long. I’ll work on it and add the displacement calculation and try and get a maximum figure the the disorder calculation.

Fascinating look at the BBC Micro game Elite

Fascinating look at the BBC Micro game Elite

BBC Micro EditeThis is somewhat off-topic and a little bit of self-indulgence because (a) it’s about a computer that existed over 36 years ago and (b) a game that was programmed in 6502 assembler. It’s also a game I played a lot back in 1984.

The reason for including it here is because a British Web Developer called Mark Moxon has created an excellent website about the game, looking at the algorithms, source code etc. of the BBC Micro version of Elite. Everything you wanted to know about how it works.

I’d sum up this website as the “Cliff’s Notes” to the BBC Micro version of Elite. Be sure to click the three bars at the top left as the Navigation Bar gives an idea of just how much there is in this website. There’s bit by bit breakdowns of variables for example, in generating System Data.

Government
  ----------
  The government is given by a 3-bit value, taken from bits 3-5 of w1_lo. This
  value determine the type of government as follows:
  
    0 = Anarchy
    1 = Feudal
    2 = Multi-government
    3 = Dictatorship
    4 = Communist
    5 = Confederacy
    6 = Democracy
    7 = Corporate State

This is a remarkable piece of work, I can’t imagine how many hours Mark has put into it. Possibly as many as it took to develop the game originally!

Quake II – still a favourite

Quake II – still a favourite

Quake II screenshotOh I do play much newer games such as Far Cry 5 which I’ve completed recently but Quake II was a favourite of mine back in 1997 when I bought it. I’m more of a Quake than a Doom person. Unfortunately for me, my then PC couldn’t run it. It was only two years old as well.  But I got a new PC in 1998 and that played it just fine. I’m not saying I’m a saddo but I can play it through on the hardest level without losing a life.

The reason I mention it because of an article I came across that described the different ID Tech Game engines and the games made with each engine. All have been open sourced (Up to ID Tech 4). Quake II was written using the ID Tech 2 engine itself written in C and assembler.

For some reason the link to Quake II source code is wrong in that article but you can find it on GitHub. In one of 18 of ID Tech’s 18 repositories there.

If you are interested in downloading and trying to understand the Quake II source code, I strongly recommend you read Fabien Sangard’s walkthough of the code.

Interesting C Program- What do you think it does?

Interesting C Program- What do you think it does?

Question mark
Image by Gordon Johnson from Pixabay

This is a past IOCCC winner. It needs a #include <stdio.h> to compile.

#define _ -F<00||--F-OO--;
int F=00,OO=00;main(){F_OO();printf("%1.3f\n",4.*-F/OO/OO);}F_OO()
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
        _-_-_-_-_-_-_-_
            _-_-_-_
}

When I compiled and ran it in Visual Studio it output 0.25 which is not the value it’s intended to output. That said it also messed up the formatting.

I can’t recommend this formatting BTW but then that’s the idea, to obfuscate i.e. disguise its purpose! So have you figured it out yet? I put the image on the right so as not to break up the program listing…

How to calculate how effective a Riffle is

How to calculate how effective a Riffle is

deck of cards
Image by Hebi B. from Pixabay

In my previous post I mentioned about writing a program to determine how effective a riffle shuffle was. So here’s the code.

How it works

I’m using an array of 52 chars to hold the deck. I’m only interested in the card’s position in the deck so each card is initialised with a value in the range 0-51. I’m using three other similar sized arrays.

  • tempCards are used purely for doing the riffle.
  • distances are used to calculate the maximum distance the card moved
  • startPos tracks the cards starting position 0-51 before doing lots of rounds of riffles.

The program starts by picking up ( as a parameter) how many rounds you want it to run. It defaults to 10 if no value is input.

It then clears distances and inits cards. In each round, it starts by storing card positions in startPos. It then does seven riffles and works out how far a card has moved. If it has moved more than before (in distances) it stores it in distances.

DoRiffle works by indexing through the two 1/2 deck piles taking a card from each and a 50:50 random chance determines which of the two cards goes into the shuffled deck first and then second.

Here’s the listing.

// riffle.c by D. Bolton (C) 2020 Learncgames.com - TYou are free to redistribute but please keep this line in

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// #defines
#define MAXROUNDS 10
#define NUMRIFFLES 7
#define NUMCARDS 52

// variables
int NumRounds;
char cards[NUMCARDS],tempCards[NUMCARDS],startPos[NUMCARDS];
int distances[NUMCARDS];
time_t t;

// functions

// Convert string to int calling strtol
int GetIntArg(char* str) {
	char* ptr;
	return strtol(str, &ptr, 10);
}

// Merges two cards a and b. 50:50 chance that a above b or other way
void DoRiffle() {
	// Copy cards into tempCards
	memcpy(tempCards, cards, sizeof(cards));
	// Merge each pair of cards tempCards[i] and TempCards[i+26]
	int cardIndex = 0;
	for (int i = 0; i < NUMCARDS / 2; i++) {
		if (rand() % 2) {
			cards[cardIndex++] = tempCards[i];
			cards[cardIndex++] = tempCards[i + 26];

		}
		else {
			cards[cardIndex++] = tempCards[i + 26];
			cards[cardIndex++] = tempCards[i];
		}
	}
}

// Works out how far cards have moved, added to distances
void CalculateDistances() {
	for (int i = 0; i < NUMCARDS; i++) {
		int moved = abs(cards[i] - startPos[i]);
		if (moved > distances[i])
			distances[i] = moved;
	}
}

void DoShuffles() {
	// Clear distances and init cards
	for (char i = 0; i < NUMCARDS; i++) {
		distances[i] = 0;		
		cards[i] = i;
	}
    // do Numrounds  rounds
	for (int round =0;round<NumRounds;round++){
		// Mark where the card starts
		for (char i = 0; i < NUMCARDS; i++) {
			startPos[i] = cards[i];
		}
		// Do seven riffles
		for (int i = 0; i < NUMRIFFLES; i++) {
			DoRiffle();
		}		
		CalculateDistances();
	}
	int furthest = 0;
	for (int i = 0; i < NUMCARDS; i++) {
		printf("Distance[%d]=%d\n", i, distances[i]);
		if (distances[i]> furthest) {
			furthest = distances[i];
		}
	}
	printf("furthest moved is %d\n", furthest);
}


int main(int argc, char* argv[]) {
	srand((unsigned)time(&t));
	if (argc ==1 || argc== 2) {
		NumRounds = MAXROUNDS;
		if (argc == 2) {
			NumRounds = GetIntArg(argv[1]);
			printf("Numrounds = %d\n", NumRounds);
		}
		DoShuffles();
	}
	else {
		printf("Please supply 0 or 1 arguments e.g. riffle 60\n");
	}
}

Even with ten rounds I’ve seen cards move 51 positions. With 5,000 rounds all cards but one moved by 51 and one by 50.

MonoGame – How to make a clickable button

MonoGame – How to make a clickable button

Clear Button with one card clickedI’m using this in Android games but the principle applies to any MonoGame game. Here clickable and touchable mean the same.

You need three things to make something clickable.

  1. The area. For simplicity sake this will always be rectangular.
  2. The Action. When you touch (or click it), you want it to run code.
  3. An id of sorts. If you have multiple buttons etc, you meed to distinguish them.

We’ll use an int for 3. Use const ints to give it a name rather than being a magic number.

 

When you click whatever, the Event should include the ide so let’s define the event Type first.

public class ButtonClickedEventArgs : EventArgs
{
    public int Id { get; set; }
}

Not rocket science is it!

Now lets define a ClickButton class.

public class ClickButton
{
    public int Id { get; set; }
    public Rectangle TouchArea { get; set; }
    public Action<object, ButtonClickedEventArgs> AnAction { get; set; } = null;

    public ClickButton(int id)
    {
        Id = id;
        TouchArea = new Rectangle(0, 0, 0, 0);
    }
}

Again nothing too complicated. There’s an int Id which which is set in the Constructor, a Rectangle TouchArea and an Action which is defined to include our ButtonClickedEventArgs.

Here;’s some example code. I’ve defined a graphic for a Clear button in my game and this is loaded as usual in the LoadContent().  I’ve also defined the button in Class declaration.

ClickButton ClearButton;

In LoadControl(), this is also initialised. Here’s it’s two line. It could be done in one, by altering the constuctor.

ClearButton = new ClickButton(1);  // 1 is the id
ClearButton.AnAction += ClearCards;

ClearCards is a method that does something when the button is cleared. This matches our Event handler as it has the usal two parameters for an Event except the args is our ButtonClickedEventArgs.

private void ClearCards(object sender, ButtonClickedEventArgs args)  {
   // all the code here, not shown
}

Where is the TouchArea defined?

So are we all setup ready to rock’n’roll? Well not quite. We haven’t said exactly where the TouchArea is. That of course depends on where we draw the button. In my game, the ClearButton moves across. It’s absent when all six cards are present but as soon as one has been touched and a back card touched to move it, the Clear Card appears. In the top image you can see it to the right of the five top cards. I had clicked the seven of clubs when it was in the top row then the first back on the top row of the three rows.

For my next move I clicked the ten of diamonds and the second back on that first row where the ten of diamonds no wit. It now looks like this and the Clear Button has moved over.  If I click the Clear button it will move the seven clubs and ten diamonds back to the top row and replace them in the first row with backs.

Second clickTo set the TouchArea of the ClearButton, I do it in the Draw method. It’s as simple as this:

if (hand.Count < 6) // Draw ClearButton on end
  {
    spriteBatch.Draw(clearButton, new Rectangle(x, y, cardWidth, cardHeight), 
        new Rectangle(0, 0, cardWidth, cardHeight), Color.White);
    ClearButton.TouchArea = new Rectangle(x, y, cardWidth, cardHeight);
  }

There’s actually a small bug visible. When you click a top row card, the game highlights it by reducing its opacity to 0.5. If you look at the ten of diamonds, you can see it still has that reduced opacity; it should have been restored to 1.0 when it was moved to the first row. The same is true in the top picture for the seven clubs! Easily overlooked but just a one-line fix.

Some Touchy Code

The very last bit is to fire touch detection and this is done in the Update() method. When you touch the screen, calling Touchpanel.GetState() returns a collection of touches. This is my code. It cycles through the touches collection, gets the X, Y position of each touch and adjusts it to match the virtual screen coordinates. (Drawing to a virtual screen means this looks the same on every Android irrespective of its physical screen sizes and resolution).

touchState = TouchPanel.GetState();
foreach (var touch in touchState)
{
   if (touch.State == TouchLocationState.Pressed)
    {
         var x = touch.Position.X / xRatio; // adjust for virtual screen
         var y = touch.Position.Y / yRatio;
         CheckClickedTop(x, y, hand);
         if (pickedCard == null) return; // no point checking further...
         for (var i = 0; i < 3; i++)
            CheckClickedBottom(x, y, commonCards[i], true);
            if (hand.Count == 6) continue; // All top cards so no ClearButton visible
            // Check if Clear button
            if (ClearButton.TouchArea.Contains(x, y))
              {
                  ClearButton.AnAction(ClearButton, new ButtonClickedEventArgs() { Id = ClearButton.Id }); 
              }
      }
}

The top cards are held in a class called hand and the bottom three rows are held in CommonCards[3] each of which is a hand. The CheckClicked.. methods cycle through the cards in the hand comparing coordinates to see which card if at all has been clicked. If it has it calls the AnAction Event for the one clicked. The very last if shows how this works to check if the ClearButton was clicked. I’ll simplify this code by moving it into a ClickButton method.

Using heap memory with malloc

Using heap memory with malloc

For some reason malloc seems to confuse new programmers but it’s very straightforward.  I didn’t use it or even talk about it in the ebook. Memory allocation is not something you want to be doing in a game loop, running 60 times a second. All the memory that was ever used in the asteroids game was for text strings, variables and arrays and you don’t have to explicitly allocate any memory for those.

When you have a program that needs to allocate and free memory, like say a compiler or text editor then you grab a block of RAM using malloc.  You have to specify how much RAM you need and you must type cast it, because malloc return a void *.

Here’s an example. The image shows the output in the Visual Studio debugger.


#include <stdio.h>
#include <stdlib.h>

char* ptr[10];
int main() {
	for (int i = 0; i < 10; i++) {
		ptr[i] = (char *)malloc(1000);			
		char* aptr = ptr[i];
		for (int j = 0; j < 1000; j++) {
			aptr[j] = i + 64;
		}
        }
	for (int i = 0; i < 10; i++) {
		free(ptr[i]);
	}
}

DEbugger showing array valuesThis is what the Visual Studio debugger shows just before the final loop that calls free.

It has allocated 1000 bytes of memory for each of the ten char * in ptr[] and then fills it with 1000 each of the ASCII values 64..73 @

Finally, it frees up the memory using free. For every malloc, there should be a corresponding free or else your program will develop a memory leak.

 

 

Do you use assert in your code?

Do you use assert in your code?

assertIt’s a macro that checks an expression, and if that expression isn’t true (.e. non-zero) it outputs a message and halts the program.

Here’s an example.

#include 
#include 

int main() {
	int x = 0;
	assert(x != 0);
	printf("It is the end");
}

Because x is 0, it triggers the assert and the program never reaches the printf statement. It’s a bit of a crude tool. In other programming languages like C++ or Delphi it raises an exception which can be handles but C of course does not have exceptions.

My own preference is to check the value for example making sure a pointer is not null and nthen displaying an error but other programmers prefer to use assert and have it kill the program if things go wrong.