Snake AI

so, I have been working on something along the lines of a computer controlled version of snake.. and i have gotten most of it done, but i am having so many issues getting the artificial intelligence to work right.

so far, i have it set up so that the head of the snake constantly moves toward the dots it is trying to pick up.

And i also have it set up so that every frame it checks to see if there is another block in its path. the problem is, once it knows there is something in the way, it cant seem to figure out how to get around it.

in other words, i dont know what to tell it to do once it notices it is about to die.

does any body have any ideas? i can post the fla or a bit of code if it would help any body.

any help would be much appreciated

thanks so much,
-Neil

the fla or code would help a lot.

the computer controling is basicly only this code:

Code:

---

        Xdirection = 0;
        Ydirection = Math.abs(Apple._y-S0._y)/(Apple._y-S0._y);
        if (Math.abs(Ydirection) != 1) {
                Ydirection = 0;
                Xdirection = Math.abs(Apple._x-S0._x)/(Apple._x-S0._x);
        }
        Turn();

Turn = function () {
        for (j=0; j<=SnakeLength; j++) {
                if ((Math.abs(Apple._y-S0._y)>Math.abs(Apple._y-_root["S"+(j+1)]._y)) && ((Math.abs(Apple._y-S0._y)/(Apple._y-S0._y)) == (Math.abs(Apple._y-_root["S"+(j+1)]._y)/(Apple._y-_root["S"+(j+1)]._y))) && (_root["S"+(j+1)]._x == S0._x) && (Math.abs(Ydirection) == 1)) {
                        trace("Turn Y"+getTimer());
                }
                if ((Math.abs(Apple._x-S0._x)>Math.abs(Apple._x-_root["S"+(j+1)]._x)) && ((Math.abs(Apple._x-S0._x)/(Apple._x-S0._x)) == (Math.abs(Apple._x-_root["S"+(j+1)]._x)/(Apple._x-_root["S"+(j+1)]._x))) && (_root["S"+(j+1)]._y == S0._y) && (Math.abs(Xdirection) == 1)) {
                        trace("Turn X"+getTimer());
                }
        }
};

---

essentially, what this is telling it to do is to go up or down depending on where the dot it is trying to pick up is located, then once it arrives at the appropriate _y value, it goes left or right, depending on which direction is needed.

and it constantly runs a function called Turn() which checks to see if it has something in the way of its path...

i'll attach the .fla too, but please ignore my //notes i dislike deleting things when i am coding.

One thing to do that might help is instead of making it go Y and then X you can try making it go in the direction of the shortest distance first, and then the longest. In other words, the apple is 4 tiles away in the x direction, and 7 in the y direction, it would move in the x direction first.

As for the turning, that type of AI can be challenging sometimes. One thing I noticed is that you are doing all your calculations based on the position of the apple in relation to the snake. You should probably switch that and do them based on the position of the snake in relation to the apple.

One thing you might want to look into is AI pathfinding algorithms.

I reccomend A* (pronounced "A Star") which is a great algorithm that I have used many times in tile-based games, mostly for AI.

i'm not exactly sure what you mean by doing my calculations based on the position of the snake in relation to the apple.. or what advantage that would have.

could you explain for me?

also, i tried to do some research on A*, and after reading quite a few different sources, i realize that i AM going to need help with this. =/

is there any way you could help me figure out a path finding function for my snake?

in my project file, i have two arrays, one holding the _x position of each block on the screen, and one holding the _y positions of each block on the screen. but i cant seem to get the concepts i have read about (A*) to apply to my program.....

do you know where i could possibly start? =/

Okay, I'll try to explain A* a little better (I know lots of websites are very complex).

Let's start with the map. I know you aren't using individual tiles for your game, but you can create Objects to represent each tile.

Each tile has 4 variables:
cost (represented as "g")
score (represented as "f")
heuristic (represented as "h")
and parent


Luckily you don't have to deal with "movement costs" because all your tiles are the same terrain, so that simplifies the explanation of costs. The cost (which is different from the movement cost) is basically the number of tiles traveled to get from the start to the current tile. Each time you visit a new tile, the new tile's cost will be the previous tile's score plus 1.


The score is the sum of the tile's cost and heuristic (I'll explain heuristics later). Basically, each time A* explores another tile, that tile's score will be the previous tile's score plus the new tile's cost and heuristic. The goal of A* is to find the best path from start to finish. Therefore, it will choose the path with the lowest score (the higher the score, the longer it took to get there).


Now for heuristics. A tile's heuristic can be explained as an estimate of the shortest path from the current tile (not the starting tile) to the goal tile. Heuristics help A* decide which way would be best to look in first. Heuristics are more complicated, because there are a few different types. For your purposes, you can use the simplest one: The Manhattan Distance. Here is the formula for the Manhattan Distance:

Code:

---

h(n) = D * (abs(n.x-goal.x) + abs(n.y-goal.y))

---

Where n is the current tile, and D is the cost of movement.


Each tile (besides the starting tile) has a "parent" tile. The parent tile is basically the previous in the path from the start to the current tile. Each time a tile is expanded and all the neighboring tiles are checked, each new neighbor gets the current tile as its "parent" tile.



Now I will explain how the algorithm itself works.

The first thing the algorithm needs is two arrays: the "open" array, and the "closed" array. The closed array will contain all the tiles that have been visited and expanded, while the open array will contain an array of all tiles that have been visited, but not expanded yet. We always keep the open array sorted based on each tile's score. The closed array doesn't need to be sorted.

Here is a pseudocode version of the A* algorithm:
(remember, f is score, g is cost, and h is heuristic)

Code:

---

initialize the open list
 initialize the closed list
 put the starting tile in the open list

 while the open list is not empty
    sort the open list by f value
    pop the tile with the lowest f off the open list, call it "n"
    find n's 4 neighboring tiles and set their parents to n
    for each neighbor (m) of n
            if m is the goal, stop the search and backtrack to the start to generate the path
        if m is already in the open list,
                skip this tile
        m.g = n.g
        m.h = distance from m to the goal
        m.f = n.f + m.h
    push n into the closed list

---

I am sure you will have lots of questions about this, and I am happy to answer them. This is the basics of it, and I can easily give more detail if it is needed.

thank you so so so much for your help. you are absolutely incredible.

with a combination of your help and tonypa's tutorials, i think i have pretty much gotten the path finding figured out...

i am still struggling, however, with making it fast enough. i have written a code that ONLY uses its path finding ability when it is close enough to the object and can not get there any other way. which is good, because it means the game will only have to pause every now and again.

if you have any suggestions that could possibly help, they would be MUCH appreciated.

i will post my code if you would like. but it is really messy and long and scary. lol.

for now, here is the swf.... it may take a few min to see the bugs, but they are defiantly there.
http://img163.imageshack.us/img163/6057/snake2.swf

Yeah, I can see what you mean about the pausing...and it also tends to go through itself. Let me take a look at your code.

One thing to know is that you can sacrifice accuracy for speed (or the other way around) by modifying your heuristic calculations. The One thing you are probably going to want is a "tie breaker" in your heuristic. Try multiplying the heuristic by 1+1/(rows*columns). See if that makes it a little faster.

could you explain the scalar of the heuristic a bit more for me, what it is doing and that sort of thing. :]

here is the essentials of my code... its veryy long and scary. Do keep in mind that although i (think i) completely understand it, i did base much of it off of tonypa's example code.

Code:

---

_root.onEnterFrame = function() {
        if (PathControl == true) {
                DoPath();
        }
        if (PathControl != true) {
                Turn();
                if (Pathcontrol == true) {
                        break;
                }
                if (S0.hittest(Apple._x+4, Apple._Y+4)) {
                        SnakeLengthAnticipation += 5;
                        MakeApple();
                }
                Xdirection = 0;
                Ydirection = Math.abs(Apple._y-S0._y)/(Apple._y-S0._y);
                if (Math.abs(Ydirection) != 1) {
                        Ydirection = 0;
                        Xdirection = Math.abs(Apple._x-S0._x)/(Apple._x-S0._x);
                }
        } else {
                Xdirection = 0;
                Ydirection = 0;
        }
}
AddNode = function (ob, x, y, targetx, targety) {
        path.name = "node_"+y+"_"+x;
        walkAble = true;
        // is it walkable?
        for (k=1; k<=(SnakeLength); k++) {
                if ((x == Xpositions[k]) && (y == Ypositions[k])) {
                        walkAble = false;
                }
        }
        if (walkAble == true) {
                // find estimated cost to the target
                var cost = Math.abs(x-targetx)+Math.abs(y-targety);
                // and if its not visited yet
                if (path[path.name].cost>cost or path[path.name].cost == undefined) {
                        // make new node
                        path[path.name] = {x:x, y:y, visited:false, parentx:ob.x, parenty:ob.y, cost:cost};
                        // add to the array
                        for (var i = 0; i<path.Unchecked_Neighbours.length; i++) {
                                if (cost<path.Unchecked_Neighbours[i].cost) {
                                        path.Unchecked_Neighbours.splice(i, 0, path[path.name]);
                                        break;
                                }
                        }
                        // didnt add it yet, too much cost, add to the end
                        if (i>=path.Unchecked_Neighbours.length) {
                                path.Unchecked_Neighbours[path.Unchecked_Neighbours.length] = path[path.name];
                        }
                }
        }
};
function findPath(startx, starty, targetx, targety) {
        // make new path object
        path = {};
        path.Unchecked_Neighbours = [];
        path.done = false;
        path.name = "node_"+starty+"_"+startx;
        StepCount = 0;
        // create first node
        var cost = Math.abs(startx-targetx)+Math.abs(starty-targety);
        path[path.name] = {x:startx, y:starty, visited:true, parentx:null, parenty:null, cost:cost};
        // add node to array
        path.Unchecked_Neighbours[path.Unchecked_Neighbours.length] = path[path.name];
        while (path.Unchecked_Neighbours.length>0) {
                // get the next node
                var N = path.Unchecked_Neighbours.shift();
                if ((N.x == targetx and N.y == targety)) {
                        CreatePath(N);
                        path.done = true;
                        break;
                } else {
                        N.visited = true;
                        // right neighbour
                        addNode(N, N.x+9, N.y, targetx, targety);
                        // left neighbour
                        addNode(N, N.x-9, N.y, targetx, targety);
                        // up neighbour
                        addNode(N, N.x, N.y+9, targetx, targety);
                        // down neighbour
                        addNode(N, N.x, N.y-9, targetx, targety);
                }
        }
        // remove path object
        delete path;
        // check if path was found
        if (path.done) {
                // we reached the goal
                return true;
        } else {
                // we couldn't get there;
                return false;
        }
}
CreatePath = function (ob) {
        myPathX = [];
        myPathY = [];
        while (ob.parentx != null) {
                // add the x and y
                myPathX[myPathX.length] = ob.x;
                myPathY[myPathY.length] = ob.y;
                ob = path["node_"+ob.parenty+"_"+ob.parentx];
        }
};
Turn = function () {
        for (j=1; j<=SnakeLength; j++) {
                if ((Math.abs(Apple._y-S0._y)>Math.abs(Apple._y-_root["S"+(j+1)]._y)) && (Math.abs(S0._y-_root["S"+(j+1)]._y)<45) && ((Math.abs(Apple._y-S0._y)/(Apple._y-S0._y)) == (Math.abs(Apple._y-_root["S"+(j+1)]._y)/(Apple._y-_root["S"+(j+1)]._y))) && (_root["S"+(j+1)]._x == S0._x) && (Math.abs(Ydirection) == 1) && ((SnakeLength-j)>(Math.abs(S0._y-_root["S"+j]._y)/9))) {
                        PathControl = true;
                        trace("y")
                        findPath(S0._x, S0._y, Apple._x, Apple._y);
                        break;
                }
                if ((Math.abs(Apple._x-S0._x)>Math.abs(Apple._x-_root["S"+(j+1)]._x)) && (Math.abs(S0._x-_root["S"+(j+1)]._x)<45) && ((Math.abs(Apple._x-S0._x)/(Apple._x-S0._x)) == (Math.abs(Apple._x-_root["S"+(j+1)]._x)/(Apple._x-_root["S"+(j+1)]._x))) && (_root["S"+(j+1)]._y == S0._y) && (Math.abs(Xdirection) == 1) && ((SnakeLength-j)>(Math.abs(S0._x-_root["S"+j]._x)/9))) {
                        trace("x")
                        PathControl = true;
                        findPath(S0._x, S0._y, Apple._x, Apple._y);
                        break;
                }
        }
};
MakeApple = function () {
        for (j=0; j<=SnakeLength; j++) {
                newX = (random(60)*9)-1;
                newY = (random(45)*9)+1;
                if ((newX == Xpositions[i]) && (newY == Ypositions[i])) {
                        MakeApple();
                } else {
                        Apple._x = (random(60)*9)-1;
                        Apple._y = (random(45)*9)+1;
                }
        }
};
DoPath = function () {
        if ((myPathX.length == 0) && (myPathY.length == 0)) {
                SnakeLengthAnticipation += 5;
                if (S0.hittest(Apple._x+4, Apple._Y+4)) {
                        MakeApple();
                }
                turn()
                PathControl = false;
                // findPath(S0._x, S0._y, Apple._x, Apple._y);
        } else {
                S0._x = myPathX[myPathX.length-1];
                S0._y = myPathY[myPathY.length-1];
                myPathX.pop();
                myPathY.pop();
        }
};

---

the best way i can describe how i set it up is this...

move in the right direction until something is in your way,
check to see if it is going to get out of your way by the time you get there
if it is not, figure out another way around it, once you do find your way to the apple, repeat.



also.... if you have any idea at all why it is randomly extruding its self every time it calculates its path, that would be realllly amazing. :)

Hmm... one thing I can think of would be to spread out your path calculation over multiple frames. Basically, choose a point that the snake will reach in a few frames, and calculate only a portion of the path from that point to the end each time until the full path is complete. Once complete, when the snake hits the starting point of the path, have it start following.