A question about the logic of making a "Snake" game

[Jamin2112]

I've started to make a "Snake" game (example: http://www.kongregate.com/games/uchiha/classic-snake-game) and reached a dead end. I'm not sure the programmatically best way of figuring out where the snake's "food" should next appear. It should of course appear anywhere on the screen that doesn't collide with the snake. I therefore think there are 2 procedures:

• (1) Pick a random location on the screen. If this location lies somewhere on the snake, then pick another random location. Do this until you find a proper location.
• (2) Use the positions of the links that compose the snake to figure out a proper next random location for the food.

The first one is inefficient, especially when the snake is long. The second one, I don't know how to write. Any ideas for how I can write the second one?

By the way, here's what I have so far:

The snakegame class is: jaminweb.com/Snakegame.html

        $(document).keydown(function(e)
        {
            switch(e.which)
            {
                case 37: // left arrow key
                  s.redirect(3);
                  break;

                case 38: // up arrow key
                  s.redirect(4);
                  break;

                case 39: // right arrow key
                   s.redirect(1)
                   break;

                case 40: // down arrow key
                   s.redirect(2);
                   break;

                default: return; // exit this handler for other keys
            }
            e.preventDefault(); // prevent the default action (scroll / move caret)
         });

        function snakegame(C, C_h, C_w)
        {
                /* NOTE TO SELF: C is a Raphel object. Can't find a method to return the height
                   and width of a Raphael object in the documentation: 
                   [PLAIN]http://raphaeljs.com/reference.html#Raphael.[/PLAIN] 
                   Using C_h and C_w for now, but should probably change it later.
                */
                
                this.linkSize = 30; // size of a snake unit, in pixels
                
                this.food = C.rect(10, 30, this.linkSize, this.linkSize);
                this.food.attr("fill","#39275b")
                this.food.glow();
                
                /* On instantiation, the snake direction is down and has 1 link */
                this.dy = this.linkSize;
                this.dx = 0;
                this.link = C.rect(C_h/2, C_w/2, this.linkSize, this.linkSize);
                this.link.attr("fill", "#d7a900");
                this.body = [this.link];
                
                /* Event listener for changing the direction of the
                   snake with arroy keys on the keyboard
                */
                this.redirect = function(dirnum)
                {
                    switch (dirnum)
                    {
                        /*
                            dirnum corresponds to
                            1 ---> right
                            2 ---> down
                            3 ---> left
                            4 ---> up
                        */
                        case 1: 
                            this.dx = this.linkSize;
                            this.dy = 0;
                            break;
                        
                        case 2:
                            this.dx = 0;
                            this.dy = this.linkSize;
                            break;
                        
                        case 3:
                            this.dx = -this.linkSize;
                            this.dy = 0;
                            break;
                        
                        case 4:
                            this.dx = 0;
                            this.dy = -this.linkSize;
                            break;
                        
                        default: // never happens
                            break;
                    }
                            
                }
                this.move = function()
                {
                    /*
                        ...
                    */
                    var temp = this.body[0];
                    var BBhead = temp.getBBox();
                    if (BBhead.x < 0 || BBhead.x2 > C_w || BBhead.y < 0 || BBhead.y2 > C_h)
                    {
                        clearInterval(mover); 
                        return;
                    }
                    var BBfood = this.food.getBBox();
                    if (this.boxCollision(BBhead, BBfood))
                    {
                        this.moveFood();
                        this.addLink();
                    }
                    this.body[0].translate(this.dx, this.dy);
                    for (var i = 1, j = this.body.length; i < j; ++i)
                    {
                        this.body[i] = temp;
                        temp = this.body[i];
                    }
                }
                
                var mover = setInterval(this.move.bind(this), 300);   
                
                this.addLink = function()
                {
                    alert("you hit it!"); 
                }
                
                this.moveFood = function()
                {
                    
                }
                this.boxCollision = function(A, B)
                {
                    return A.x > B.x && A.x < B.x2 && A.y > B.y && A.y < B.y2;
                }

        }

It's messy, but hopefully you can see my intent and give me some ideas for how to build off what I have now.

 

[interhacker]

The first method should be fine, really. I've made a similar snake game in html5 with method 1. Works perfectly.

Modern PCs don't lag much when computing a single random number.

 

[DavidSnider]

Instead of doing it purely random you should pick a random point in the array and forward-seek until you find a free space. This way the upper bound is N rather than unknown. That and you don't waste cycles generating random numbers.

 

[Jamin2112]

Instead of doing it purely random you should pick a random point in the array and forward-seek until you find a free space. This way the upper bound is N rather than unknown. That and you don't waste cycles generating random numbers.

Then the piece of food will always be right near the snake. He'll be stuck in one area of the screen because the piece of food will always appear next to one of his units.

 

[DavidSnider]

Then the piece of food will always be right near the snake. He'll be stuck in one area of the screen because the piece of food will always appear next to one of his units.

The vast majority of the time the initial space chosen will be empty, when the screen is mostly filled it's always going to be near the snake anyway. You could add a random jitter factor that says "pick the nth open spot you find" where n is a random number. You can also pick a random seek direction for less predictability.

 

[AlephZero]

Then the piece of food will always be right near the snake

You could forward-seek in steps of p locations, where p is relatively prime to the size of the playing area.

That will step through all the board locations in sequence, but in pseudo-random order.

For "more randomness", look up the "quadratic probing" technique for dealing with collisions in hash tables.