What data structure should I use for a snake game?

I have some homework for my school and I have to make a开发者_StackOverflow 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?

---

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

---

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.

---

I used something different for my Snake implementation. The idea is that you store

1. the location of the snake's head
2. the length of the snake
3. the direction of the snake's head
4. an array of "bend" objects, where a bend consist of a direction (left or right) and an offset (e.g. (left, 3) when there's a left bend at the third position in the snake)

This is pretty efficient, not a dumb solution like a simple array and can easily used to draw "fancier" snakes, e.g. with rounded corners.

---

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.

---

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;

---

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;

---

You can use a circular buffer. To elaborate:

Get an array, sufficiently big to hold the maximum snake. Establish two pointers, one for the head, one for the tail.

At the beginning, the tail would be in cell #1, the head in cell #3. As the snake moves, move the head pointer to the right and write the new coordinate. Then, if there's no food eaten, move the tail pointer to the right as well. If either of the pointers tries to go beyond the rightmost end of the array, wrap them over to the beginning.