贪吃蛇AI

贪吃蛇AI"/>

贪吃蛇AI

另一种实现思路

首先，将点阵转化成一个大环路，如下图：

为了美观，我们将它画成圆形，图中橙色为蛇的头，两次键头指向了食物，由于蛇头一般有三个方向（其中一个必是蛇的身体）可以移动，因此，它可以在（一定条件下）不按这个圆圈走，跳着走，便会体现一定的智能性，那么是在什么样的条件下呢？

蛇头和蛇尾之间的所有的点（其中一些并没有被蛇的身体占据）,归类为蛇头不可跳点。只要不是不可跳点，那么蛇都可以尽可能的抄近路跳着走来体现智能性。

使用方法Snake(int x,int y)控制长和宽，必须为偶数

Thread.Sleep(100)指制跑的速度；己注释，跑得老快，算法本身很快但打印跟不上。

using System;
using System.Collections;
using System.Threading;
using System.Collections.Generic;//特殊情况 头走尾，尾不删，不置false
//遇食物，尾不动
namespace snakeai
{class Program{static void Main(string[] args){Console.CursorVisible = false;Snake a = new Snake(16, 16);a.eatFood();}}class Snake {public struct Point {public int x;public int y;public Point(int xx, int yy) {x = xx; y = yy;}public static bool operator ==(Point a, Point b) {return a.x == b.x && a.y == b.y;}public static bool operator !=(Point a, Point b){return !(a == b);}}LinkedList<Point> body;Hashtable hash;Point[] pos;Point food;Random rd;int xlen;int ylen;bool[,] board;public Point generateNode() {Point p;int len = xlen * ylen - body.Count;if(len==0) return new Point(-1, -1);int t = rd.Next(0, len-1);int c = 0;for (int i = 0; i < xlen; i++) { for(int j = 0; j < ylen; j++){if (board[i, j] == false) {if (c == t) return new Point(i, j);c++;}}}Console.WriteLine("Error");return new Point(-1, -1);}public Snake(int x ,int y) {body = new LinkedList<Point>();hash = new Hashtable();rd = new Random();board = new bool[x, y];for (int i = 0; i < x; i++) for (int j = 0; j < y; j++) board[i, j] = false;xlen = x;ylen = y;int cnt = 0;pos = new Point[x * y];for (int i = 0; i < x; i++) {if (i % 2 == 1){for (int j = ylen - 1; j > 0; j--){if (hash.Contains(new Point(i, j)))hash.Remove(new Point(i, j));hash.Add(new Point(i, j), cnt);pos[cnt++] = new Point(i, j);}}else{for (int j = 1; j < ylen; j++){if (hash.Contains(new Point(i, j)))hash.Remove(new Point(i, j));hash.Add(new Point(i, j), cnt);pos[cnt++] = new Point(i, j);}}}for (int i = xlen - 1; i >= 0; i--) {if (hash.Contains(new Point(i, 0)))hash.Remove(new Point(i, 0));hash.Add(new Point(i, 0), cnt);pos[cnt++] = new Point(i, 0);}food = generateNode();GenerateBody(food);var s = generateNode();GenerateBody(s);body.AddFirst(s);}public Point generateNewHead() {var head = body.First.Value;var p = (int)hash[head];return pos[(p + 1)%(xlen*ylen)];}public void move(Point newHead) {//Thread.Sleep(100);body.AddFirst(newHead);board[newHead.x, newHead.y] = true;GenerateBody(newHead);if (newHead == food){food = generateNode();if(food.x!=-1)GenerateBody(food);}else{var last = body.Last.Value;body.RemoveLast();if (last != newHead){board[last.x, last.y] = false;EraseTail(last);}}}public void eatFood() {while (body.Count < xlen * ylen){int dx = (food.x > body.First.Value.x) ? 1 : -1;int dy = (food.y > body.First.Value.y) ? 1 : -1;if (food.x == body.First.Value.x) dx = 0;if (food.y == body.First.Value.y) dy = 0;var head = body.First.Value;Point[] tmp = new Point[4];tmp[0].x = head.x+1;tmp[0].y = head.y;tmp[1].x = head.x-1;tmp[1].y = head.y;tmp[2].x = head.x;tmp[2].y = head.y+1;tmp[3].x = head.x;tmp[3].y = head.y-1;Point init = generateNewHead();int len = Distance(init, food);for (int i = 0; i < 4; i++) {if (LegalPoint(tmp[i])&&board[tmp[i].x, tmp[i].y] == false&&inCircle(tmp[i])==false) {if (Distance(init, food) > Distance(tmp[i], food)) init = tmp[i];}}move(init);}while (true) ;}public bool LegalPoint(Point p){return p.x >= 0 && p.x < xlen && p.y >= 0 && p.y < ylen;}public int Distance(Point a, Point b) {int alen = (int)hash[a];int blen = (int)hash[b];if (alen > blen)return (xlen*ylen-(alen-blen));elsereturn blen - alen;}public bool inCircle (Point p){int start = (int)hash[body.First.Value];int end = (int)hash[body.Last.Value];int v =(int) hash[p];if (start >= end){return v <= start && v >= end;}else {return !(v <= start && v >= end);}}public static void GenerateBody(Point p){Console.SetCursorPosition(p.x, p.y);Console.Write("*");}public static void EraseTail(Point p){Console.SetCursorPosition(p.x, p.y);Console.Write(" ");}}}