0
\$\begingroup\$

A naive Snake game implementation works by using a queue data structure to store the position of every single square that the snake is a part of.

You can reduce the amount of memory by only storing the location and direction of the head, the location of the tail, and an array of locations where the snake bends.

In a 100 x 100 grid, there's 10,000 squares. A queue of points (stored as pairs of bytes) would require 10,000 * 2 bytes = 19.5KiB of memory in the worst case scenario, where every square is filled up. (This would be accomplished by the snake starting on a corner, and the dots always appearing right in front of him in an S-shaped pattern.)

Assuming you can store the location of the head, direction of the head, and location of the tail in bytes (total of 2 bytes + 2 bytes + 1 byte for location), what is the maximum amount of bends that could exist in a 100x100 grid, and how much space would you save with this method in the worst case? In the average case?

\$\endgroup\$
2
  • 3
    \$\begingroup\$ This question appears to be off-topic because it is about hypothetical performance differences between two implementations of a simple game. \$\endgroup\$ Nov 29, 2014 at 7:56
  • \$\begingroup\$ Why does this actually matter? What problem are you trying to solve? \$\endgroup\$
    – user1430
    Dec 3, 2014 at 16:50

2 Answers 2

0
\$\begingroup\$

You can store the direction with 2 bits: 1 for axis and 1 for pos/neg. As such, storage-wise it will be more efficient regardless of the number of bends -- about ~2.5 KB for 10,000 tiles. Store it as a bitmask as well (1.25 KB for 10K tiles) and then you have fast collision checks ("is snake on tile"). The slowest operation would be "Access nth body part" which would require you to iterate over all snake tiles, from the head, but if you don't need that operation that often, you should be fine.

\$\endgroup\$
0
\$\begingroup\$

In the worst case it looks to me like you're going to use more memory this way. Picture a snake that goes something like this: ‾|_|‾|_|‾ as much as possible. There are a few spots at the edge of the screen where it must go straight for a few squares but those aren't enough to overcome the higher memory storage per location unless the world is small.

While the average memory is lower what difference does that make? I would say the "naive" approach is the best one.

\$\endgroup\$
4
  • \$\begingroup\$ The location of a bend is just a pair of bytes, similar to the naive approach of just listing the pairs of all occupied squares. In the worst case scenario, every square is a bend, which in the end would only be storing the same amount of pairs as the other method. However, not every square CAN be a bend; I think in the worst case you still save memory. It's just a question of how much. \$\endgroup\$ Nov 23, 2014 at 17:37
  • 1
    \$\begingroup\$ @MichaelCelani You are giving 4 bytes/block for the naive approach, 5 bytes/bend for yours. Your approach only wins in the worst case if it's not possible to have a snake of at least 80% bends--and a snake that squirms like I drew will be well at least 99% bends given your board size. \$\endgroup\$ Nov 23, 2014 at 17:42
  • \$\begingroup\$ In the naive approach, you store 2 bytes/block - the X and Y coordinates, each one represented by a byte. In my approach, you store 5 bytes (X and Y of the head, X and Y of the tail, one byte to show the direction the snake is going) plus 2 bytes/bend. In my understanding, you save memory as long as there are at least three blocks that aren't bends. \$\endgroup\$ Nov 23, 2014 at 18:56
  • 1
    \$\begingroup\$ @MichaelCelani Those aren't the numbers I understood from your initial post. I do agree yours is slightly more efficient. I can't imagine there's an overall savings counting the complexity of the code, though. \$\endgroup\$ Nov 23, 2014 at 19:07

Not the answer you're looking for? Browse other questions tagged .