Sign in to follow this  
Grantyt3

Snake

Recommended Posts

I'm going to make a snake game, and I wanted your guys' opinion. It's going to be a grid-based snake game. My plan for movement is to have a vector for the snake pieces. When the player's head is on the same grid point as a piece of food, it will add a new piece to the vector. For movement, each piece would move to the piece in front of it. I know I wasn't very specific, but is this a good way to do it, or how is it usually done?

Share this post


Link to post
Share on other sites
Personally, rather than 'move' each segment of the snake. Id save myself a lot of work and use a RingQueue of snake segments, with a running count of how long it is, and which slot contains the head.
Thus rather than 'move' (change tons of parameters for each segment); they individually remain static, with only the memory mapping order changing. As the snake moves forward, correspondingly the head position in the queue changes, and the length counter makes the tail end of the queue expire. Only one segment actually needed to be updated (head) the intermediate body segments remain as is, and the tail is basically ignored(you'll automatically deallocate it as the ringqueue wraps around in the future).

Share this post


Link to post
Share on other sites
It may have several different names depending on what school you went to.
I've known it as RingQueue
but Ring Buffer
Circular Buffer
Circular Queue
etc
may also be valid

wikipedia: http://en.wikipedia.org/wiki/Circular_buffer

basically you make a Big Array, big enough to hold the Max length of your snake.
and you have a pointer to the 'head'(insertion end) of the Queue (also the literal head of the snake) As your snake moves forward, rather than change the x,y coodinates of each body segment, you simply create a new head, and add it to the ringqueue. The old snakehead, stays in the ringqueue, and keeps its old x,y coords, but it gets treated as body segment #1 instead of a head. similarly, old body segment #1 is now treated as #2, and so on down to the end of the queue (and end of the snake).
None of the segments in the Array actually move, you simply draw them to screen in a different order (one slot higher each time)
after a while, the front of the array will be full of 'dead' body segments that are no longer used, and the 'head' will reach the end of the array. To handle this issue, you wrap the array into a 'ring'(hence RingQueue) and reset the 'head' to the front of the array ontop of the dead slots.
(the drawing order of body segments also needs to be able to travel off the end of the array and onto the other side)

The advantage of doing this, instead of a Vector or LinkedList approach, is that memory access is minimal for the snake segments. You are not constantly allocating and deallocating memory as segments are added and expired. And there is no modification to segments after creation.

Share this post


Link to post
Share on other sites
I'm 99% sure that the orginal Snake arcade game used a RingQueue, since on that old hardware performance was paramount.
On a modern computer however, Snake is a relatively simple task, and your Vector/LinkList approach should still work.
So if your goal is just to get a game running, Vector is fine.

It is good to know about various data structures though, and this project does sound like a good opportunity to learn RingQueue. So it depends what you want to focus on. If you still want to know, I can write some psuedocode for ringqueue/snake when I get home later...

Share this post


Link to post
Share on other sites
I'd like to use Ring Queue since this is just for learning purposes anyway, and I might as well learn as much as I can in the process. So yes, example would be great when you get home.

Share this post


Link to post
Share on other sites
Here is an ilistration of a circular array

http://lcm.csa.iisc.ernet.in/dsa/node24.html

This should also help in creating a circular array
http://www.cs.hmc.edu/claremont/keller/webBook/ch07/sec10.html

Hope this helps in creating the circular array datatype.

Share this post


Link to post
Share on other sites
You could use a deque and push the new piece on the front, then pop the last piece off the back.

Share this post


Link to post
Share on other sites
Read this pdf it's a snakes clone written in java and will give you all the info you need:
http://fivedots.coe.psu.ac.th/~ad/jg/ch02/ch2.pdf

Share this post


Link to post
Share on other sites
you will need to create a SnakeSegment Struct or Class, which represents a single segemnt of snake, and contains x and y position.

The RingQueue should then be filled up with SnakeSegments as the snake grows.

Every update, the snake head moves, so you create a new SnakeSegment for the new head position, and enqueue it into the RingQueue. At the same time, the very tip of the snake's tail should be removed (since the snake stay constant length unless it is eating an apple) to remove the tip of the tail, simply do a dequeue on the RingQueue to remove the last segment.

Also, very Important, the links you saw explained how a basic RingQueue works, but for Snake you will need to add an extra feature, to 'View' the queue in order without actually removing anything from it. This will be needed for drawing all the SnakeSegments, and in checking that the head of the snake is not biting its body.
View is easy to add, in additon to a Head(enqueue) and Tail(dequeue) index on the Ring, you should also have a View index, which can be moved forward, backwards, or reset to Tail via a few 'View' functions attached to the RingQueue class.

Share this post


Link to post
Share on other sites
Is Queue part of C++ or is it just a way of using an array?

Also, I don't see how it's position in the queue is related to it's position on screen.

Share this post


Link to post
Share on other sites
A queue is a data structure that can be created in pretty much any language, and it can be made using array's or like a linked-list where nodes have points to the next node on the queue.
Correct me if i'm wrong, but i think the other people are wanting you to store the positions of each part of the snake in the queue, it's just that the first item in the queue is the head.
Then, when the snake moves, instead of updating every piece of the snake, take the last item, and put it in the front and just change it's position.

Share this post


Link to post
Share on other sites
They say I should make a class for each snake "peice" which is what I was planning on doing.

So, when the snake moves, I should move the tail "piece" one place ahead of the head "piece"?

Share this post


Link to post
Share on other sites
A queue is a FIFO datastructure. FIFO means First In First Out which means the first element that is inserted in the queue is the first element that is 'popped off'/'dequeued'. I think STL has a class for this.

e.g.
[] - empty queue
[3] - added the element 3 to the queue
[3, 4] - added the element 4 to the queue
[4] - dequeued the queue so the 3 was removed as it was the first element that was inserted.

To relate it to your game, say you had a struct or class to represent the body segment that holds the X,Y position of itself, you would have a queue of this struct/class and to 'move', you create a new segment that holds the new position of the head of the snake and add it to the queue, you then dequeue the queue to remove the last piece of the tail to keep the snake the same length.

[a, b, c, d] - current queue
[a, b, c, d, e] - e represents the new head position, a is the last tail piece
[b, c, d, e] - a is dequeued to keep the length of the snake.

Why would this be better/faster? Say you have a huge snake, 20 odd pieces, using your current method with vectors, you would have to tranverse the entire vector array and update the X/Y positions of the segments and this would get worse performence wise the larger the snake gets. With a queue you just creating and adding a new segment and removing and deleting a tail segment no matter how large the snake gets. Using a ringqueue (which is a fixed size) you don't create or delete any segments, you just overwrite an existing element.

Share this post


Link to post
Share on other sites
Ohhhh, okay, I totally understand it now, thanks! Now for the code part. I would just create a single dimensional array that's the maximum size of the snake right? Then make the pointers to the front and the back, then when the snake eats, add a new one to the back?

Or I could just use the Queue class you mentioned right?

Share this post


Link to post
Share on other sites
If you use the 'pure' Queue method, then I would just go for the STL Queue class, if the RingQueue, I would create my own class and use a STL Vector to hold the elements and two 'pointers' or iterators to hold the front and rear of the queue in the RingQueue with checks if any of the 'pointers' or iterators reach the end of the vector list.

Share this post


Link to post
Share on other sites
One doesn't have an end, the other does.

So when you transverse through a Ring array, you can keep going indefinitely. A standard array you will hit either the beginning or the end.


Ring:
-->--
| |
--<--

Non-ring(?)
-->--

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this