2

I am currently trying to make a snake pathfinding algorithm. I tried to make something, but a problem came up that I find hard. The problem is that I am implementing the algorithm in a recursive way which does not find one path, but searches for all the available paths which causes stack overflow exception because of the large console window size.

The "Grid" is a two dimensional boolean array which is as big as the console and a value is true if there is something like a part of the snake on the console.

Direction is an enumeration with Up, Down, Left, Right values. Position is a struct with two integers called X and Y.

ScheduledDirections is a list with directions which will be used in the future for the snake's drawing on the console.

What I want to do is to add one available path to that list fast. I know about pathfinding algorithms like A*, but I find it too complex and hard to implement.

This is the method that I am using to find an available path:

private static void FindAvailablePath(Position currentPosition, Direction currentDirection)
{
    // break if the snake's path search has ended or it went out of the console
    if (currentPosition.X < 0 || currentPosition.X >= Console.WindowWidth ||
        currentPosition.Y < 0 || currentPosition.Y >= Console.WindowHeight ||
        AIController.isReady)
    {
        return;
    }

    // break if there is something that is blocking the snake's path
    if (Snake.Grid[currentPosition.X, currentPosition.Y])
    {
        return;
    }

    // break if the snake has reached its destination
    if (currentPosition.Equals(AIController.Destination))
    {
        AIController.isReady = true;
        return;
    }

    // if the current path is available, adds it to the collection and checks for the next one
    if (!Snake.Grid[currentPosition.X, currentPosition.Y])
    {
        AIController.scheduledDirections.Add(currentDirection);

        FindAvailablePath(new Position(currentPosition.X + 1, currentPosition.Y), Direction.Right); // right
        FindAvailablePath(new Position(currentPosition.X, currentPosition.Y - 1), Direction.Up);    // up
        FindAvailablePath(new Position(currentPosition.X - 1, currentPosition.Y), Direction.Left);  // left
        FindAvailablePath(new Position(currentPosition.X, currentPosition.Y + 1), Direction.Down);  // down
    }
}

If someone has some better ideas I will be pleased to hear them. Thanks!

Improve this question
5
  • 3
    Without looking closely at the code, the fact that you are getting a stack overflow suggests that you don't consider the scenario where your path goes into a loop. Commented Apr 28, 2014 at 14:39
  • I do believe @500-InternalServerError is right. You must add a break condition for when the snake is in a position it has already explored. Commented Apr 28, 2014 at 14:44
  • 1
    Yes it does compile. And look at the first if condition. There is a static boolean variable isReady, which is set to true when the snake has reached its destination. It still doesnt work. Any suggestions? Commented Apr 28, 2014 at 14:49
  • Ignore my comment. I thought it was C++. Commented Apr 28, 2014 at 14:50
  • Again, it throws stack overflow before any case reaches the destination because all the available ways are too much. Commented Apr 28, 2014 at 14:51

1 Answer 1

Reset to default
1

You have to make sure the snake doesn't go back into a position it has already "visited" or else your code will have to explore an infinite number of possibilities (circle in the same four squares once, twice, three times, ... , four billions times, etc.).

This means you must keep a record of positions visited and check against that list.

This should do the trick:

private static void FindAvailablePath(Position currentPosition, Stack<Position> previousPositions, Direction currentDirection, Stack<Drection> previousDirections)
{
    // break if the snake's path search has ended or it went out of the console
    if (currentPosition.X < 0 || currentPosition.X >= Console.WindowWidth ||
        currentPosition.Y < 0 || currentPosition.Y >= Console.WindowHeight)
    {
        return;
    }

    // break if there is something that is blocking the snake's path
    if (Snake.Grid[currentPosition.X, currentPosition.Y])
    {
        return;
    }

    // break if the snake has reached its destination
    if (currentPosition.Equals(AIController.Destination))
    {
        if(AIController.scheduledDirections == null || AIController.scheduledDirections.Count > previousDirections.Count + 1)
        {
            AIController.scheduledDirections = previousDirections.ToList();
            AIController.scheduledDirections.Add(currentDirection);
        }
        return;
    }

    // Break if previously visited
    if(previousPositions.Contains(currentPosition))
    {
        return;
    }


    // if the current path is available, adds it to the collection and checks for the next one
    previousPositions.Push(currentPosition);
    previousDirections.Push(currentDirection);

    FindAvailablePath(new Position(currentPosition.X + 1, currentPosition.Y), previousPositions, Direction.Right, previousDirections); // right
    FindAvailablePath(new Position(currentPosition.X, currentPosition.Y - 1), previousPositions, Direction.Up, previousDirections);    // up
    FindAvailablePath(new Position(currentPosition.X - 1, currentPosition.Y), previousPositions, Direction.Left, previousDirections);  // left
    FindAvailablePath(new Position(currentPosition.X, currentPosition.Y + 1), previousPositions, Direction.Down, previousDirections);  // down

    previousPositions.Pop();
    previousDirections.Pop();
}

Also, pro tip: Add a "Left", "Right", "Top", "Down" methods to your position struct which return a new position in the right direction. This makes your code more readable.

Improve this answer
Sign up to request clarification or add additional context in comments.

13 Comments

I see, and yeah I think you are right, the method does not throw any kind of exceptions but now the problem is that the snake is only going to the right. Any suggestions? Maybe i'm doing something wrong?
What should I pass as a parameter when I call the method at the stack? Im passing new stack.
Just pass a new Stack. Found your other problem: you added the current position to your AI's path, even if it didn't end up in the final path. Changed the code to the answer so that when the destination is found, the previous and current positions are given to the AI.
Oops! Just noticed your AI used directions, not positions. I'll let you figure that one out. cough cough create a stack for the directions and push and pop them like with the positions
Well, something is wrong because is still hitting itself in the wall.Here is the code: pastebin.com/Kq9LvVGX
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.