Suggestions for Efficiency

David_Johanson · 2019-02-23 23:32:08 UTC

This will be a long intro post because I figure more info is better than less. I am new to arduboy but not new to arduino and have just made my first game. (Mostly, there isn’t a winning screen or anything, but you can meet the goal of the game and “beat it”). It is a re-creation of one of my favorite puzzles from one of my favorite games “Lufia II: Rise of the Sinistrals”. The puzzle is simple. Similar to those sliding square puzzles, you have to slide the blocks around until the big 2x2 block at the top comes to the bottom. Here is a picture from the original game:

Original Puzzle Game

I surprised myself by starting this project this morning and finally finishing it just now (mostly). Here is a screen shot from my arduboy version:

It needs some polish but is completely functional.

My main concern is that I programmed everything totally inefficiently. Video game programming is a new world to me and I want to learn more “tools of the trade”. With that said, can anyone here offer suggestions for how I could have made anything (especially the collision and boundary checks) much simpler? Here is my code:

#include <Arduboy2.h>  // Arduboy Library
Arduboy2 ab;           // Arduboy object

int lineWidth = 1;     // Width of white line aroun boxes
int bufferWidth = 2;   // Used to calculate width and height of black boxes
int screenWidth = 128; // Arduboy screen width and height
int screenHeight = 64;
int gameWidth = 32;    // Width of the game playing area
int halfGameWidth = gameWidth/2;

int currentPiece = 0; // Start with selecting piece zero (top left corner)
int frameRate = 45;
int gameState = 0;   // Start with game title page
bool collision = false; // Start with nothing is colliding
bool inBoundary = true; // Start with all boxes in boundary (32 by 40 pixle invisible playing area)

#define TITLE 0    // Game States
#define SELECT 1
#define MOVE 2

#define oneByTwo 0  // Block/Piece Types
#define twoByTwo 1
#define twoByOne 2
#define oneByOne 3

int pieceType[] = {
  0,               // piece 1 1x2
  1,               // piece 2 2x2 (Goal Block)
  0,               // piece 3 1x2
  0,               // piece 4 1x2
  2,               // piece 5 2x1
  0,               // piece 6 1x2
  3,               // piece 7 1x1
  3,               // piece 8 1x1
  3,               // piece 9 1x1
  3,               // piece 10 1x1 
};


int xPos[] = { // x starting positions of the pieces of the puzzle
  0,
  8,
  24,
  0,
  8,
  24,
  8,
  16,
  0,
  24,
};

int yPos[] = { // y starting positions of the pieces of the puzzle
  0,
  0,
  0,
  16,
  16,
  16,
  24,
  24,
  32,
  32,
};

int widths[] = { // widths of the pieces of the puzzle
  8,               // piece 1 1x2
  16,              // piece 2 2x2 (Goal Block)
  8,               // piece 3 1x2
  8,               // piece 4 1x2
  16,              // piece 5 2x1
  8,               // piece 6 1x2
  8,               // piece 7 1x1
  8,               // piece 8 1x1
  8,               // piece 9 1x1
  8,               // piece 10 1x1  
};

int heights[] = { // heights of the pieces of the puzzle
  16,              // piece 1 1x2
  16,              // piece 2 2x2 (Goal Block)
  16,              // piece 3 1x2
  16,              // piece 4 1x2
  8,               // piece 5 2x1
  16,              // piece 6 1x2
  8,               // piece 7 1x1
  8,               // piece 8 1x1
  8,               // piece 9 1x1
  8,               // piece 10 1x1  
};

void setup() {
  ab.begin();
  ab.clear();
  ab.setFrameRate(frameRate);
  ab.display();
}

void drawPuzzle() { // Used to draw the entire game board for any change the player makes
  // drawRect(x, y, w, h, COLOR);

  for (int selectedPiece = 0; selectedPiece < 10;  selectedPiece++) {
    
    // create the base of all 10 pieces of the game (white rectangle)
    ab.fillRect(xPos[selectedPiece] + ((screenWidth/2)-halfGameWidth), yPos[selectedPiece], widths[selectedPiece], heights[selectedPiece], WHITE);

    // if the game is in selecting mode, make the selected piece pure white.
    if (currentPiece == selectedPiece && gameState == 1) {
      ab.fillRect(xPos[selectedPiece] + ((screenWidth/2)-halfGameWidth) + lineWidth, yPos[selectedPiece] + lineWidth, widths[selectedPiece] - bufferWidth, heights[selectedPiece] - bufferWidth, WHITE);
    }

    // if the game is in moving mode, put a dot on the selected piece to track movement.
    else if (currentPiece == selectedPiece && gameState == 2) {
      ab.fillRect(xPos[selectedPiece] + ((screenWidth/2)-halfGameWidth) + lineWidth, yPos[selectedPiece] + lineWidth, widths[selectedPiece] - bufferWidth, heights[selectedPiece] - bufferWidth, WHITE);
      ab.fillCircle((xPos[selectedPiece] + ((screenWidth/2)-halfGameWidth) + lineWidth) + (widths[selectedPiece]/2), (yPos[selectedPiece] + lineWidth) + (heights[selectedPiece]/2), 1, BLACK);
    }
    else {
      // fill all other pieces in with black.
      ab.fillRect(xPos[selectedPiece] + ((screenWidth/2)-halfGameWidth) + lineWidth, yPos[selectedPiece] + lineWidth, widths[selectedPiece] - bufferWidth, heights[selectedPiece] - bufferWidth, BLACK);
    }
  }
  
  return;
}

void titleScreen() {
  ab.print("The Wolrd's Hardest\nPuzzle"); // display title
  ab.pollButtons();
  if (ab.justReleased(A_BUTTON)) {
    gameState++; // move on to selecting mode when A button is pressed.
  }
  return;
}

void selectPiece() { // Allows player to scroll through the pieces to select one to move
  ab.pollButtons();
  ab.clear();
  if (ab.justReleased(UP_BUTTON)) { // move forward a piece
    currentPiece = (currentPiece + 1) % 10;
  }
  if (ab.justReleased(RIGHT_BUTTON)) { // move forward a piece
    currentPiece = (currentPiece + 1) % 10;
  }
  if (ab.justReleased(DOWN_BUTTON)) { // move back a piece
    currentPiece = (currentPiece - 1) % 10;
    if (currentPiece < 0) {
      currentPiece = 9; // account for negative values, loop to the end
    }
  }
  if (ab.justReleased(LEFT_BUTTON)) { // move back a piece
    currentPiece = (currentPiece - 1) % 10;
    if (currentPiece < 0) {
      currentPiece = 9; // account for negative values, loop to the end
    }
  }
  if (ab.justReleased(A_BUTTON)) {
    gameState++; // put game in movement mode when pressing A button to select a piece
  }
  drawPuzzle();

  ab.display();
  return;
}

void movePiece() {
  ab.pollButtons();
  ab.clear();

  if (ab.justReleased(UP_BUTTON)) {                   // move piece up one block width (8 pixles)
    yPos[currentPiece] = yPos[currentPiece] - 8;
    checkCollision();                                 // check for collisions
    checkBoundary();                                  // check if block is in boundaries
    if (collision == true || inBoundary == false) {
      yPos[currentPiece] = yPos[currentPiece] + 8;    // if there is collision or boundary break, move block back to previous space.
    }
    collision = false;
    inBoundary = true;
  }
  if (ab.justReleased(DOWN_BUTTON)) {                 // Pattern for all movement is the same as stated in comments above.
    yPos[currentPiece] = yPos[currentPiece] + 8;      // Step 1: move, Step 2: check for collisions with other blocks, Step 3: check for boundaries, Step 4: Undo movement if there are problems.
    checkCollision();
    checkBoundary();
    if (collision == true || inBoundary == false) {
      yPos[currentPiece] = yPos[currentPiece] - 8;
    }
    collision = false;
    inBoundary = true;
  }
  if (ab.justReleased(LEFT_BUTTON)) {
    xPos[currentPiece] = xPos[currentPiece] - 8;
    checkCollision();
    checkBoundary();
    if (collision == true || inBoundary == false) {
      xPos[currentPiece] = xPos[currentPiece] + 8;
    }
    collision = false;
    inBoundary = true;
  }
  if (ab.justReleased(RIGHT_BUTTON)) {
    xPos[currentPiece] = xPos[currentPiece] + 8;
    checkCollision();
    checkBoundary();
    if (collision == true || inBoundary == false) {
      xPos[currentPiece] = xPos[currentPiece] - 8;
    }
    collision = false;
    inBoundary = true;
  }
  if (ab.justReleased(B_BUTTON)) {  // Press either button to move back to selecting a new piece to move.
    gameState = 1;
  }
  if (ab.justReleased(A_BUTTON)) {
    gameState = 1;
  }
  
  drawPuzzle();
  ab.display();
  return;
}

/******************************************************************************
 * Collision checking happens in two steps (probably can be done much simpler)
 * 
 * Step 1: loop through every piece in the game on a case by case basis.
 *  - Cases are determined by the dimensions of the block a 1x2, 2x2, 2x1, or 1x1
 *  
 *  - In each case, check to see if the top left corner of the block being moved
 *    is the same as the top left corner of any other block being moved.
 *    
 *  - Also check to see if the top left corner of the block being moved is the 
 *    same as any other block segment that is being filled by any blocks that
 *    take up more than one 8x8 pixle space.
 * 
 * Step 2: Find the dimensions of the piece being moved (i.e. 1x1, 1x2, ...)
 *  - Use those dimensions to determine if any other block has a top left corner
 *    that intersects with the area that the block being moved takes up.
 *    
 * If any of those statements are true, then there is a collision.
 ********************************************************************************/
void checkCollision() {
  for (int i = 0; i < 10; i++) {
    if (i == currentPiece) {
      collision = false;
    }
    else {
      switch (pieceType[i]) { 
        case oneByTwo:
          if (xPos[i] == xPos[currentPiece] && yPos[i] == yPos[currentPiece]) {
            collision = true;
            i = 10;
            return;
          }
          if (xPos[i] == xPos[currentPiece] && (yPos[i]+8) == yPos[currentPiece]) {
            collision = true;
            i = 10;
            return;
          }
          break;
        case twoByTwo:
          if (xPos[i] == xPos[currentPiece] && yPos[i] == yPos[currentPiece]) {
            collision = true;
            i = 10;
            return;
          }
          if (xPos[i] == xPos[currentPiece] && (yPos[i]+8) == yPos[currentPiece]) {
            collision = true;
            i = 10;
            return;
          }
          if ((xPos[i]+8) == xPos[currentPiece] && (yPos[i]+8) == yPos[currentPiece]) {
            collision = true;
            i = 10;
            return;
          }
          if ((xPos[i]+8) == xPos[currentPiece] && yPos[i] == yPos[currentPiece]) {
            collision = true;
            i = 10;
            return;
          }
          break;
        case twoByOne:
          if (xPos[i] == xPos[currentPiece] && yPos[i] == yPos[currentPiece]) {
            collision = true;
            i = 10;
            return;
          }
          if ((xPos[i]+8) == xPos[currentPiece] && yPos[i] == yPos[currentPiece]) {
            collision = true;
            i = 10;
            return;
          }
          break;
        case oneByOne:
          if (xPos[i] == xPos[currentPiece] && yPos[i] == yPos[currentPiece]) {
            collision = true;
            i = 10;
            return;
          }
          break;
        default:
          collision = false;
      }
      switch (pieceType[currentPiece]) {
        case oneByTwo:
          if (xPos[i] == xPos[currentPiece] && yPos[i] == yPos[currentPiece]) {
            collision = true;
            i = 10;
            return;
          }
          if (xPos[i] == xPos[currentPiece] && yPos[i] == (yPos[currentPiece]+8)) {
            collision = true;
            i = 10;
            return;
          }
          break;
        case twoByTwo:
          if (xPos[i] == xPos[currentPiece] && yPos[i] == yPos[currentPiece]) {
            collision = true;
            i = 10;
            return;
          }
          if (xPos[i] == xPos[currentPiece] && yPos[i] == (yPos[currentPiece]+8)) {
            collision = true;
            i = 10;
            return;
          }
          if (xPos[i] == (8+xPos[currentPiece]) && yPos[i] == (8+yPos[currentPiece])) {
            collision = true;
            i = 10;
            return;
          }
          if (xPos[i] == (8+xPos[currentPiece]) && yPos[i] == yPos[currentPiece]) {
            collision = true;
            i = 10;
            return;
          }
          break;
        case twoByOne:
          if (xPos[i] == xPos[currentPiece] && yPos[i] == yPos[currentPiece]) {
            collision = true;
            i = 10;
            return;
          }
          if (xPos[i] == (8+xPos[currentPiece]) && yPos[i] == yPos[currentPiece]) {
            collision = true;
            i = 10;
            return;
          }
          break;
        case oneByOne:
          if (xPos[i] == xPos[currentPiece] && yPos[i] == yPos[currentPiece]) {
            collision = true;
            i = 10;
            return;
          }
          break;
        default:
          collision = false;
      }
    }
  }

  return;
}


/**************************************************************************************************************************
 * Boundary Checking is similary to collision checking and can probably be simpler
 * 
 *  - The boundary is a 32 by 40 rectangle (hence the numbers 32 and 40 are hard coded into the if statements
 *    32 pixles is the width and 40 pixles is the height
 * 
 *  - The space marked at 0,0 is defined to be the top left corner of the game board (not the arduino screen).
 *    It is 48 pixles to the right of the arduino screen origin.
 *    
 *  - The piece demensions are determined and if the top left corner exits the boundary, it is reported as out of bounds
 *  
 *  - The exceptions are pieces that are large than 1x1. The top left corner of the section that can go out of bounds
 *    is used when necessary (hence some if statments have a +8 in them, telling the program to look at another section
 *    of the block for boundary checks).
 **************************************************************************************************************************/
void checkBoundary() {
  // make sure the blocks stay in the boundary
  switch (pieceType[currentPiece]) {
    case oneByTwo:
      if (xPos[currentPiece] >= 32 || xPos[currentPiece] < 0 || (yPos[currentPiece]+8) >= 40 || yPos[currentPiece] < 0) {
        inBoundary = false;
        return;
      }
      break;
    case twoByTwo:
      if ((xPos[currentPiece]+8) >= 32 || xPos[currentPiece] < 0 || (yPos[currentPiece]+8) >= 40 || yPos[currentPiece] < 0) {
        inBoundary = false;
        return;
      }
      break;
    case twoByOne:
      if ((xPos[currentPiece]+8) >= 32 || xPos[currentPiece] < 0 || yPos[currentPiece] >= 40 || yPos[currentPiece] < 0) {
        inBoundary = false;
        return;
      }
      break;
    case oneByOne:
      if (xPos[currentPiece] >= 32 || xPos[currentPiece] < 0 || yPos[currentPiece] >= 40 || yPos[currentPiece] < 0) {
        inBoundary = false;
        return;
      }
      break;
    default:
      inBoundary = true;
  }
  return;
}

void loop() { // The main loop
  if(!ab.nextFrame()) {
    return;
  }
  
  ab.clear();

  switch (gameState) {
    case TITLE:
      titleScreen();
      break;
    case SELECT:
      selectPiece();
      break;
    case MOVE:
      movePiece();
      break;
  }
  
  ab.display();
}

Pharap · 2019-02-24 00:34:58 UTC

I apologise in advance if this seems long or overcritical.
Programming is a deep topic and it’s hard to judge how much advice to give.

If any of your int variables won’t exceed 255 and don’t need negative numbers,
change them from int to uint8_t.
E.g. for(uint8_t selectedPiece = 0; selectedPiece < 10; ++selectedPiece)
The same applies to your arrays.

Any variables that should never change (i.e. they are ‘constant’) should be marked constexpr.
E.g. constexpr uint8_t lineWidth = 1;

On the Arduboy, any string literals that you’re giving straight to a print function should be wrapped in the F macro.
It does some magic to put the string in ‘progmem’ (read-only memory) and allow the print function to still print it properly.
E.g. arduboy.print(F("The Wolrd's Hardest\nPuzzle"));

You should move ab.pollButtons into loop rather than squashing it into titleScreen, selectPiece etc.

Instead of signalling your collisions and boundary checks with global variables, you should return a bool from checkCollision and checkBoundary.
E.g.

if (ab.justReleased(RIGHT_BUTTON)) {
	xPos[currentPiece] = xPos[currentPiece] + 8;
	bool collision = checkCollision();
	bool inBoundary = checkBoundary();
	if (collision == true || inBoundary == false) {
		xPos[currentPiece] = xPos[currentPiece] - 8;
	}
}

This would also allow you to exit early from your collision checking function.
E.g.

void checkCollision() {
  for (int i = 0; i < 10; i++) {
    if (i == currentPiece) {
      return false;
    }
    else {
      switch (pieceType[i]) { 
        case oneByTwo:
          if (xPos[i] == xPos[currentPiece] && yPos[i] == yPos[currentPiece]) {
            return true;
          }
          if (xPos[i] == xPos[currentPiece] && (yPos[i]+8) == yPos[currentPiece]) {
            return true;
          }
          break;
        case twoByTwo:
          if (xPos[i] == xPos[currentPiece] && yPos[i] == yPos[currentPiece]) {
            return true;
          }
          if (xPos[i] == xPos[currentPiece] && (yPos[i]+8) == yPos[currentPiece]) {
            return true;
          }
          if ((xPos[i]+8) == xPos[currentPiece] && (yPos[i]+8) == yPos[currentPiece]) {
            return true;
          }
          if ((xPos[i]+8) == xPos[currentPiece] && yPos[i] == yPos[currentPiece]) {
            return true;
          }
          break;
        case twoByOne:
          if (xPos[i] == xPos[currentPiece] && yPos[i] == yPos[currentPiece]) {
            return true;
          }
          if ((xPos[i]+8) == xPos[currentPiece] && yPos[i] == yPos[currentPiece]) {
            return true;
          }
          break;
        case oneByOne:
          if (xPos[i] == xPos[currentPiece] && yPos[i] == yPos[currentPiece]) {
            return true;
          }
          break;
      }
      switch (pieceType[currentPiece]) {
        case oneByTwo:
          if (xPos[i] == xPos[currentPiece] && yPos[i] == yPos[currentPiece]) {
            return true;
          }
          if (xPos[i] == xPos[currentPiece] && yPos[i] == (yPos[currentPiece]+8)) {
            return true;
          }
          break;
        case twoByTwo:
          if (xPos[i] == xPos[currentPiece] && yPos[i] == yPos[currentPiece]) {
            return true;
          }
          if (xPos[i] == xPos[currentPiece] && yPos[i] == (yPos[currentPiece]+8)) {
            return true;
          }
          if (xPos[i] == (8+xPos[currentPiece]) && yPos[i] == (8+yPos[currentPiece])) {
            return true;
          }
          if (xPos[i] == (8+xPos[currentPiece]) && yPos[i] == yPos[currentPiece]) {
            return true;
          }
          break;
        case twoByOne:
          if (xPos[i] == xPos[currentPiece] && yPos[i] == yPos[currentPiece]) {
            return true;
          }
          if (xPos[i] == (8+xPos[currentPiece]) && yPos[i] == yPos[currentPiece]) {
            return true;
          }
          break;
        case oneByOne:
          if (xPos[i] == xPos[currentPiece] && yPos[i] == yPos[currentPiece]) {
            return true;
          }
          break;
      }
    }
  }
  return false;
}

Now because the function exits early you could get rid of the else before the switch if you wanted.
The compiler would do this anyway, but I think removing the extra level of indenting makes the code clearer.
Also I’d like to point out that you didn’t need the lines that were setting i to 10 because you were following them all with a return, and return exits the function immediately, it doesn’t even skip to the end of the function - it just leaves straightaway.

This function could probably be split up into a few smaller functions to make matters easier.

(Those suggestions apply to chekBoundary too of course.)

Really your game states should be using things called scoped enumerations (enum class).

I’d recommend looking into them, they’re relatively simple to learn/understand and can greatly improve your code by offering type safety.
(I recommend reading this and then this if you’re interested. This is also useful.)

Here’s what an example of the game loop would look like using an enum class instead of the #define approach:

#include <Arduboy2.h>

Arduboy2 arduboy;

enum class GameState : uint8_t
{
	TitleScreen,
	Select,
};

GameState gameState;

void setup()
{
	arduboy.begin();
}

void loop()
{
	if (!arduboy.nextFrame())
		return;

	arduboy.clear();

	switch(gameState)
	{
		case GameState::TitleScreen:
			updateTitleScreen();
			break;
		case GameState::Select:
			updateSelect();
			break;
	}

	arduboy.display();
}

void updateTitleScreen()
{
	// etc
}

void updateSelect()
{
	// etc
}

I had a number of stylistic issues that I wanted to discuss,
but I decided to cut them out for now because you only asked for efficieny problems.
If you want to know about issues of clarity or style,
let me know and I’ll discuss those too.

If you have any questions about anything I’ve said, don’t hesitate to ask.

David_Johanson · 2019-02-24 04:05:55 UTC

Thank you for your in depth reply! Your examples and explanation make things clearer. Don’t worry about giving me as much information and suggestions as you are willing to.

My end goal is to make better and bigger games, so the sooner I can implement proper coding technique the better. I would love to hear the suggestions you have for style and clarity.

Pharap · 2019-02-25 00:25:34 UTC

I only just noticed your reply.

Small tip about using the forum:
People get notifications either when you directly reply to them (i.e. pressing the ‘Reply’ button at the bottom of their comment rather than the ‘Reply’ at the top or bottom of the thread) or when you @-mention them.

E.g. If I type @David_Johanson you should get a notification with an ‘@’ symbol next to it in your notification list.

The style suggestions I came up with yesterday:

Ideally ab should be renamed to arduboy,
partly for reasons of clarity, and partly because that’s the most common convention.

There’s no need for a return; at the end of a void function, it’s superfluous.

It shouldn’t affect the code size because the compiler should optimise it out and/or fuse it with the return that gets auto-inserted at the end of a function anyway, hence this is more of a style thing than an optimisation thing.

Setting the game state specifically is better than using ++ or -- for two reasons:

Firstly it makes the intent clearer, and secondly you don’t have to worry about what the actual numbers are.
Also, there’s no point in making the defines if you’re just going to do gameState = 1; instead of gameState = SELECT;.

Using == or != with true and/or false is very unusual.
Instead of if (collision == true || inBoundary == false) you should do if (collision || !inBoundary) (! means, and is pronounced as, ‘not’).

There’s two reasons for this.
Firstly you can then pronounce the code as “if collision or not in boundary”.
Secondly because it’s redundant:
If collision is true then collision == true gets evaluated to true,
and if collision is false then collision == true gets evaluated to false,
hence simply using collision gives you the same result without the unnecessary extra step.
(The compiler should filter out the unnecessary extra step anyway to be fair, but it’s still an extra mental step when reading the code.)

Some I’ve thought of just now…

A macro (i.e. a symbol defined by #define) should use ‘macro case’, which means all-caps and underscores.
So oneByTwo ought to have been ONE_BY_TWO.
There are many different code styles, but pretty much all C++ conventions advise doing this for macros.
(Really oneByTwo etc shouldn’t be macros anyway, that’s another thing that makes more sense as an enum class.)

Some extra efficiency things:

You don’t need to call arduboy.clear() or arduboy.display() in setup, arduboy.begin() already does both.

If the data in your arrays never changes then you’ll want to start looking into how progmem works on the Arduboy.
E.g.

// x starting positions of the pieces of the puzzle
uint8_t xPos[] =
{
	0,
	8,
	24,
	0,
	8,
	24,
	8,
	16,
	0,
	24,
};

uint8_t getXPos(uint8_t index)
{
	return pgm_read_byte(&xPos[index]);
}

If you do make piece type an enum class, you could do:

enum class PieceType : uint8_t
{
	OneByTwo, TwoByTwo, TwoByOne, OneByOne,
};

PieceType pieceTypes[] PROGMEM =
{
	// piece 1 1x2
	PieceType::OneByTwo,
	// piece 2 2x2 (Goal Block)
	PieceType::TwoByTwo,
	// piece 3 1x2
	PieceType::OneByTwo,
	// piece 4 1x2
	PieceType::OneByTwo,
	// piece 5 2x1
	PieceType::TwoByOne,
	// piece 6 1x2
	PieceType::OneByTwo,
	// piece 7 1x1
	PieceType::OneByOne,
	// piece 8 1x1
	PieceType::OneByOne,
	// piece 9 1x1
	PieceType::OneByOne,
	// piece 10 1x1 
	PieceType::OneByOne,
};

PieceType getPieceType(uint8_t index)
{
	return static_cast<PieceType>(pgm_read_byte(&pieceTypes[index]));
}