what is the conventional way to represent snake when coding snake game in C?

Herbal Tea 0
Viewed 64

A bit of context: I have some experience with other programing languages, but when it comes to C my knowledge is not that big. I'm also attempting to make the snake game without relying on dynamic memory allocation which is not the part of std, as it is intended to run on a microcontroller.

I previously coded snake game in python, rust, and java and my go to approach was to store pairs of x and y coordinates in some form of dynamic list or vector. Every iteration of the game loop I would append the element to the list/vector of pairs based on the current last element and and respective dx and dy, and if the snake was not growing deleted or poped the first element of the vector/list, making the snake "move".

I was particularly fond of this approach, since it meant I'm not required to store my entire game field in a 2d array. It also was a very clean implementation in my opinion. Now in C, I have to major problems - no dynamically sized lists and ability to delete first element of the array and shifting all the elements back without iterating through all of the array.

For the first problem, I've considered either using a fixed size array with some limit which would be above reasonable snake length while keeping track of snake length separately, or using a linked list of structs which would contain a nullable pointer to itself. Latter one seems to be unnecessarily complex, while the first one seems like a very dirty fix.

For the second problem, I've considered overriding array pointer with the pointer to its second element, but while that semi worked - I'm concerned with following issues:

  • do I have to free the previous array pointer (a.k.a. the previous first element)
  • when doing something like this, I assume that the pointer to the array would keep on growing, and sooner or later it would segfault as it does not reuse the memory it already slided away from.

So I thought I should ask more experienced coders on a cleaner and more conventional ways to implement snake in C. Thank you in advance,

c
1 Answers

There is an upper bound on the length of the snake -- the size of your 2d board. And this upper bound is very well achievable if your player is good at the game. Therefore you can preallocate an array of that size and use it as a pool for your linked-list nodes or a circular queue.

You can simplify further by using a 2d array for your board, and storing just the next/previous links within each cell where there's a snake. Then you don't need to store the x/y of each segment:

enum { TYPE_EMPTY, TYPE_FOOD, TYPE_SNAKE };
struct Cell { int type, next, prev; };
struct Cell board[width*height];
int head, tail;

This approach is easy to generalize to multiple players on the same board, multiple items or item types, etc.

There is nothing 'wrong' in storing an explicit 2d representation of your board. In fact it is a natural way to attack the problem. It allows fast checks for self-collisions, among other things. I bet your previous implementations resorted to a slow O(n) check to see if the snake self-intersects, which isn't pretty by itself.

Yakov Galka0
Related