AI Tetris-like game

Question

I was thinking to rewrite my Python code to C++ since it contains quite a lot of simple loops. I was stunned to find out that this critical part of code (the code below) is about 5 times slower than the Python code, and I'm hoping you could help me figure out why.

The context is some kind of game similar to Tetris, where I'm recursing** through the board and visiting each tile (and then its neighbours if not yet visited) during a traverse.

C++

void Board::traverse (Tile *t, Neighbours neighbours)
  {
    t->visited = true;
    COO coo = make_pair(t->i, t->j);
    Buddies buddies = neighbours[coo];
    if (t->color != '0' && t->color != '.')
      {
        for (uint i = 0; i < buddies.size(); i++)
          {
            Tile *buddy = &this->field[buddies[i]];
            if (buddy->visited && buddy->color == t->color)
              {
                if (buddy->chainId == -1)
                  {
                    buddy->chainId = this->chains.size();
                    this->chains[buddy->chainId].push_back(*buddy);
                  }
                t->chainId = buddy->chainId;
                this->chains[t->chainId].push_back(*t);
                break;
              }
          }
        if (t->chainId == -1)
          {
            t->chainId = this->chains.size();
            this->chains[t->chainId].push_back(*t);
          }
      }

    for (uint i = 0; i < buddies.size(); i++)
      {
        if (!this->field[buddies[i]].visited)
          {
            this->traverse(&this->field[buddies[i]], neighbours);
          }
      }
  }

Python

class Board():

    def __init__(self, s):
        self.field = []
        self.chains = {}
        self.heights = None
        self.score = 0
        self.step = 1

    def traverse(self, t=None):
        t.visited = True
        buddies = neighbours[(t.i, t.j)]
        if t.color != '0' and t.color != '.':
            for i, j in buddies:
                if self.field[i][j].visited and self.field[i][j].color == t.color:
                    if self.field[i][j].chain_id is None:
                        self.field[i][j].chain_id = len(self.chains)
                        self.chains[self.field[i][j].chain_id] = [self.field[i][j]]
                    t.chain_id = self.field[i][j].chain_id
                    self.chains[t.chain_id].append(t)
                    break
            if t.chain_id is None:
                t.chain_id = len(self.chains)
                self.chains[t.chain_id] = [t]

        for i, j in buddies:
            if not self.field[i][j].visited:
                self.traverse(self.field[i][j])

---

** The reason for this recursing is that we are not looking for simple line clear but a "line" could be seen as 4 or more blocks adjacent; making recursion through connected nodes more logical. A chain in this context is a group of connected nodes of the same color.

Answer 1

First Pass:

void Board::traverse (Tile *t, Neighbours neighbours)
                          ^^^^ Pointers are bad idea.
                               They make resource management hard to 
                               reason about as pointers have no
                               ownership semantics. Prefer a reference
                               if it can not be nullptr.

void Board::traverse (Tile *t, Neighbours neighbours)
                               ^^^^^^^^^^^^^^^^^^^^^ 
                              Here you are passing neighbours by value.
                              This means you are making a copy of the
                              object. Prefer const reference.

    // What is the type of COO
    // is there a better way to create it?
    COO coo = make_pair(t->i, t->j);


    // Here you are copy the content of `neighbours[coo]`
    // into buddies. Do you need a copy or can we just
    // use a reference to the original value.
    Buddies buddies = neighbours[coo];


            // Prefer a reference to a pointer.
            Tile *buddy = &this->field[buddies[i]];



                    // Here you are making a copy of buddy.
                    // Do you really need another copy?
                    this->chains[buddy->chainId].push_back(*buddy);


                // Again you are copy the value of tile into chains.
                this->chains[t->chainId].push_back(*t);

            // Another copy of tiles is being put here.
            this->chains[t->chainId].push_back(*t);


            // And you are copying neighbours into the
            // recursive call here.
            this->traverse(&this->field[buddies[i]], neighbours);

Use of this

Your use of this is not idiomatic.

this->chains[t->chainId].push_back(*t);

Its much easier to write:

chains[t->chainId].push_back(*t);

The only reason to use this is to disambiguate the use of shadowed variables. But shadowed variables is an error waiting to happen. So it is best to avoid shadowed variables entirely (even turn on your errors to make sure they don't happen)

-Wall -Wextra -Wshadow -Werror