What data structure should I use for a snake game?

Question

I have some homework for my school and I have to make a snake game, like Nokia's, in Delphi. I wonder which solution is the best. I want my snake be a class and the body is an array of points (parent class) or a linked list of points. What's the best? An array or a linked list?

Answer 1

Here are some nice starting points for you...since i dont want to do your homework:

Pseudo Code for Snake Game to get an Idea

Thread with a german example...maybe this code helps you

If errors occur during your programming process feel free to open a new question.

Answer 2

A Linked list is better. (Each node can point to the previous and next node) It is easier to add nodes to the end of a linked list.

If you use an array you would either need to resize it or initialise it to the Maximum possible snake length to start with which can be wasteful on memory.

UPDATE This article talks about pointers in Delph and even suggests a simple Node definition delphi article

Answer 3

In Delphi, I'd use a TQueue, witch is defined in the Contnrs unit. You can "push" your new coordinate into it (snake head), and when your max snake size is reached you just have to call "pop" to free the snake tail.

lp := new(PPoint);
lp^.X := x;
lp^.X := y;

Body.Push(lp);    

if Body.count > iSnakeLength then
  Dispose(Body.Pop); // Free the last TCoord that is pop'ed.

Then, all you need to do is to draw what's in that TObjectQueue. To access the List of the TQueue, you have to expose the property List... To do that, simply define your snake body class like that;

  TSnakeBody = class(TObjectQueue)
  public
    property List;  //Expose the list
  end;

Answer 4

I have a very old turbopascal snake program. It uses an array for the body.

const MaxBodyLength = 100;
type
  TSnake = record
    Dir : (nord,sud,est,oest);
    Head : tpoint;
    BodyLength : integer;
    Body : array[1..MaxBodyLength] of tPoint;
    Tail : tpoint;
  end;    
var
  Snake : TSnake;
  Fruit : tPoint;

and the code that moves the snake around...

procedure Slither;
var i : integer;
    npos,lpos : tPoint;
    hasEaten:boolean;
begin
  npos:=Snake.Head;
  lpos:=Snake.Tail;
  case Snake.dir of
    East  : inc(npos.x);
    West  : dec(npos.x);
    South : inc(npos.y);
    North : dec(npos.y);
  end;
  hasEaten:=(npos.x=fruit.x) and (npos.y=fruit.y);
  if hasEaten then 
    inc(Snake.BodyLength)
  else
    Snake.Tail:=Snake.Body[Snake.BodyLength];

  for i:=Snake.BodyLength downto 2 do
    Snake.Body[i]:=Snake.Body[i-1];
  Snake.Body[1]:=Snake.Head; 

  if not hasEaten then
    Snake.Head:=npos;

  writeP(idHead,Snake.Head);  
  writeP(idBody,Snake.Body[1]); 

  if not hasEaten then 
   begin
    writeP(idTail,Snake.Tail); 
    writeP(idResidual,lPos); 
   end;
  if hasEaten then 
    NewFruit;
end;

Answer 5

A simple solution is to make an array[horizontal][vertical] of type, so that there is one item for each coordinate on the screen. Each type can be a snake-direction, food, poison, wall or empty. This means that you only need to remember the head and tail position of the snake, and the count of food and poisons, and the array describes how the screen looks like.

This removes the hassle of handling the snake's elements, and makes it easy to position new food or poison items on the screen, ensuring that you're not putting it into a place that is already occupied.

When you need to remove the tail element of the snake, get the direction of the tail using direction:=array[tailx,taily]; and then set array[tailx,taily]:=empty. Afterwards, update tailx and taily depending on the direction. That's it.