http://www.waitingfy.com/archives/951
贪吃蛇移动的特点
在计算机中我们可以简单的考虑贪吃蛇的移动，假设用一个数组来存储所有组成贪吃蛇的格子，那么移动一步，就是把将来的格子插入到这个数组的头部，然后再去掉这个数组的最后一个元素。我们只做两件事情，就完成了一整条蛇的移动！
怎样保证贪吃蛇永远不死？我们知道无论往那个方向前进一步，尾巴的格子都会空出来，那么追着贪吃蛇的尾巴移动，就能保证贪吃蛇永远不死！
寻路算法之A Star
A Star 需要特别注意两个问题：1.整个蛇的身体是不可接触的格子的，要排除掉。2.因为贪吃蛇移动是一个动态的过程，所以每走一步，要重新进行寻路，而不是一次寻路完，走完路线，因为尾巴的位置会不断的空出来。
4.单纯使用寻路算法遇到的问题
4.1会进入死胡同
4.2 找不到路线
4.3 一味的最短路线吃东西，留下太多洞
就是在最后一行空出来，留做逃生的路线，然后像弹簧一样无脑向右推进，吃完后，从底部绕回最左边，继续这样的策略，直到填满整个游戏区域。
6. 贪吃蛇AI实现
我们知道追着尾巴跑，蛇就不会死，所以我们以最短路线去吃苹果时，要给自己留条后路，策略1.如果吃完苹果还可以找到到自己尾巴路线的话，才去吃苹果。
http://www.robbiewolfe.ca/programming/snake/
The modified rules for the game were that there could be obstacles, and the snake wouldn't grow. For fun, I retained the original game's functionality of the snake growing when it ate food.
public Point snakeHead;
2
public LinkedList<eDirection> snakeOrientation;
3
public LinkedList<Point> foodLocations;
4
public LinkedList<Point> wallLocations;
5
public boolean isDeadState;
First is the location of the snake head. Next is the orientation of the snake. For example, the initial state of the snake is [LEFT, LEFT, LEFT, LEFT, LEFT]. It is the direction to the next body part of the snake, starting at the tail. It is also the direction to move that body part, if the snake moves forward. The tail can be inferred from the head/orientation, so it isn’t stored.
The game allows for multiple food locations and wall locations. Thus they are stored as lists.
A state is considered dead if the head is equal to any of the wall locations, the border of the game, or another part of the snake body itself. A state is considered a goal state if the head is equal to any of the food locations.
Two states are equal if any only if all of the above properties are equal. Thus, two states that have the same snakehead/foodLocations/wallLocations, but a different orientation, are considered different. This allows the snake to move on the same spot more than once, but in a different orientation. Although this makes solutions sometimes longer (in the case of DFS), it allows the snake to get “unstuck” if it is trapped within walls, but can reorient itself towards the goal.
1. Depth First Search
Finds an extremely long path to the food. However, it expands the least amount of nodes, so it is one of the quicker algorithms to execute.
2. Breadth First Search
Finds an optimal path, however it expands a very large amount of nodes and takes longer than DFS.
3. A* Search
Based on a heuristic, finds the optimal path. It expands a low amount of nodes but can take longer than the other algorithms. Three different heuristics (as well as the average of one with another) were used as an experiment to see which was better.
Heuristics
1. Euclidean Distance
Takes the snakehead and returns the minimum Euclidean distance to one of the food locations (square root of x^2+y^2). This heuristic is ensured to be less than the actual distance.
2. Manhattan Distance
Takes the snakehead and returns the minimum Manhattan distance to one of the food locations. This is involves going in a straight line horizontally and vertically (instead of diagonally). It was chosen because it is the simplest path the snake can take, and is always possible (unless there is a wall in the way)
3. Direction Rank
This involves determining if the direction this Node is moving is in the general direction of one of the food locations. If it’s going away from it, it returns a larger value. For example:
Moving down, and numbers represent where the food is and its rank
4 5 4
3 D 3
2 1 2
So if the food is UP and you are moving DOWN, return largest value. If it is DOWN and to the LEFT or RIGHT and you are moving DOWN, return the second smallest value, etc.
This heuristic was chosen because it logically makes sense. If you are headed in the direction of the food that is good, if you are headed in the opposite direction that is bad.
http://louisbourque.ca/AI-Snake-Game/
https://github.com/louisbourque/AI-Snake-Game
It's the heuristics! A* search allows us to know what direction the food is closest to, so we search in that direction instead of randmonly wandering around the board. Sort of like if the snake had a sense of smell.
http://dralias.github.io/SnakeBot-Game/
Code:
https://github.com/DrAlias/SnakeBot-Game/
https://github.com/EinBaum/Snake
https://github.com/brandonSc/AI-Snake/blob/master/Search.java
https://code.google.com/p/java-path-finding/source/browse/snake/src/main/java/ath/bakersoftware/Ai.java
http://blog.csdn.net/dog250/article/details/6787135
http://www.ncsa.illinois.edu/People/kindr/teaching/ece190_sp11/MPs/ece190_sp11_mp5.pdf
贪吃蛇移动的特点
在计算机中我们可以简单的考虑贪吃蛇的移动，假设用一个数组来存储所有组成贪吃蛇的格子，那么移动一步，就是把将来的格子插入到这个数组的头部，然后再去掉这个数组的最后一个元素。我们只做两件事情，就完成了一整条蛇的移动！
怎样保证贪吃蛇永远不死？我们知道无论往那个方向前进一步，尾巴的格子都会空出来，那么追着贪吃蛇的尾巴移动，就能保证贪吃蛇永远不死！
寻路算法之A Star
A Star 需要特别注意两个问题：1.整个蛇的身体是不可接触的格子的，要排除掉。2.因为贪吃蛇移动是一个动态的过程，所以每走一步，要重新进行寻路，而不是一次寻路完，走完路线，因为尾巴的位置会不断的空出来。
4.单纯使用寻路算法遇到的问题
4.1会进入死胡同
4.2 找不到路线
4.3 一味的最短路线吃东西，留下太多洞
我们看下这张图，红色的表示现在出现的苹果，橙色的表示吃完红色的苹果后，苹果可能出现的位置，如果我们简单的用最短路线去吃红色的，即无脑往左走，那么橙色的就在会出现在蛇的包围圈中，将来要吃这个就非常不利，要走很多步。
这个时候比较好的走法是下图：
尽可能的多绕，尽可能地把空白地方填完，而不是以最短路线去吃，要为将来打算
5. 贪吃蛇的最佳无脑模式就是在最后一行空出来，留做逃生的路线，然后像弹簧一样无脑向右推进，吃完后，从底部绕回最左边，继续这样的策略，直到填满整个游戏区域。
6. 贪吃蛇AI实现
我们知道追着尾巴跑，蛇就不会死，所以我们以最短路线去吃苹果时，要给自己留条后路，策略1.如果吃完苹果还可以找到到自己尾巴路线的话，才去吃苹果。
var canFindPath= false; //可以找到吃苹果的路线var canFindTail = false; //可以找到自己尾巴的路线canFindPath = startPathFinding(); //开始寻找路线 if(canFindPath){ //如果可以找到吃苹果的路线 moveSnake() //移动一条看不见的贪吃蛇去吃 canFindTail = startPathFinding(); //尝试找自己尾巴路线 if(canFindTail){ //如果可以找到自己尾巴路线 return safePathCell; //返回吃苹果路线的第一步 } } |
策略2.如果找不到吃苹果路线或者吃完苹果后，会发生找不到自己尾巴路线的话，那么就在头部的周围找一个格子，这个格子要满足两个条件，条件1，走完这个格子要能找到到尾巴的路线，条件2，这个格子到苹果的距离是最远的。
http://www.waitingfy.com/archives/846http://www.robbiewolfe.ca/programming/snake/
The modified rules for the game were that there could be obstacles, and the snake wouldn't grow. For fun, I retained the original game's functionality of the snake growing when it ate food.
public Point snakeHead;
2
public LinkedList<eDirection> snakeOrientation;
3
public LinkedList<Point> foodLocations;
4
public LinkedList<Point> wallLocations;
5
public boolean isDeadState;
First is the location of the snake head. Next is the orientation of the snake. For example, the initial state of the snake is [LEFT, LEFT, LEFT, LEFT, LEFT]. It is the direction to the next body part of the snake, starting at the tail. It is also the direction to move that body part, if the snake moves forward. The tail can be inferred from the head/orientation, so it isn’t stored.
The game allows for multiple food locations and wall locations. Thus they are stored as lists.
A state is considered dead if the head is equal to any of the wall locations, the border of the game, or another part of the snake body itself. A state is considered a goal state if the head is equal to any of the food locations.
Two states are equal if any only if all of the above properties are equal. Thus, two states that have the same snakehead/foodLocations/wallLocations, but a different orientation, are considered different. This allows the snake to move on the same spot more than once, but in a different orientation. Although this makes solutions sometimes longer (in the case of DFS), it allows the snake to get “unstuck” if it is trapped within walls, but can reorient itself towards the goal.
1. Depth First Search
Finds an extremely long path to the food. However, it expands the least amount of nodes, so it is one of the quicker algorithms to execute.
2. Breadth First Search
Finds an optimal path, however it expands a very large amount of nodes and takes longer than DFS.
3. A* Search
Based on a heuristic, finds the optimal path. It expands a low amount of nodes but can take longer than the other algorithms. Three different heuristics (as well as the average of one with another) were used as an experiment to see which was better.
Heuristics
1. Euclidean Distance
Takes the snakehead and returns the minimum Euclidean distance to one of the food locations (square root of x^2+y^2). This heuristic is ensured to be less than the actual distance.
2. Manhattan Distance
Takes the snakehead and returns the minimum Manhattan distance to one of the food locations. This is involves going in a straight line horizontally and vertically (instead of diagonally). It was chosen because it is the simplest path the snake can take, and is always possible (unless there is a wall in the way)
3. Direction Rank
This involves determining if the direction this Node is moving is in the general direction of one of the food locations. If it’s going away from it, it returns a larger value. For example:
Moving down, and numbers represent where the food is and its rank
4 5 4
3 D 3
2 1 2
So if the food is UP and you are moving DOWN, return largest value. If it is DOWN and to the LEFT or RIGHT and you are moving DOWN, return the second smallest value, etc.
This heuristic was chosen because it logically makes sense. If you are headed in the direction of the food that is good, if you are headed in the opposite direction that is bad.
http://louisbourque.ca/AI-Snake-Game/
https://github.com/louisbourque/AI-Snake-Game
It's the heuristics! A* search allows us to know what direction the food is closest to, so we search in that direction instead of randmonly wandering around the board. Sort of like if the snake had a sense of smell.
http://dralias.github.io/SnakeBot-Game/
Code:
https://github.com/DrAlias/SnakeBot-Game/
https://github.com/EinBaum/Snake
https://github.com/brandonSc/AI-Snake/blob/master/Search.java
https://code.google.com/p/java-path-finding/source/browse/snake/src/main/java/ath/bakersoftware/Ai.java
http://blog.csdn.net/dog250/article/details/6787135
http://www.ncsa.illinois.edu/People/kindr/teaching/ece190_sp11/MPs/ece190_sp11_mp5.pdf
