Собственно, это первая часть статьи о том, как можно попробовать решить эту задачку. Скажем так разминочная, перед основным боем.
С чего всё началось
Дабы быть полностью откровенным, началось все с просмотра видео чувака из Австрали именующего себя "Code Bullet"
Он в нем пытается решить с помощь различных алгоритмов AI простую игру в змейку.
У него толком ничего не получается, и вот почему… Текущие алгоритмы, которые предоставляет сейчас сообщество AI решают только две задачи либо Классификации, либо Регрессии (предсказания). А вот змейка ни туда ни туда не вписывается. Ибо идея о том, что съесть мышь – это хорошо, а врезаться — плохо. Разбивается об хвост, который постоянно растет и растет пока не займет всё поле. Так вот написать полноценный самообучающий AI для такой задачи – показалось прикольной идей, но для начала я решил размяться и написать просто алгоритм, который решал бы задачку в лоб, без обучения. Собственно, о таком алгоритме и пойдёт речь.
П.С. В статье не будет великих открытий, скорее «заимствованные» идеи у других и собственная реализация с рассказом, что и откуда взялось.
Пишем игру
Перед тем как, играть, напишем саму игру.
Все расчеты будем производить на сервере, отображать змейку в браузере, а инфой будем обмениваться через WebSocket (SignalR).
isLife: boolean, isWin: boolean, xSize: number, ySize: number, mouse: Vector2, piton: Vector2[]snake.ts
import { HubConnection, HubConnectionBuilder } from "@microsoft/signalr"; import { observable } from "mobx"; import { start } from "repl"; export enum Cell { None = "None", Mouse = "Mouse", Snake = "Snake" } export interface Vector2 { x: number, y: number } interface StateBoard { isLife: boolean, isWin: boolean, xSize: number, ySize: number, mouse: Vector2, piton: Vector2[] hamiltonPath: Vector2[] } class Snake { @observable public state?: StateBoard; private connection: HubConnection; constructor() { this.connection = new HubConnectionBuilder() .withUrl("http://localhost:5000/snake") .withAutomaticReconnect() .build(); this.start(); } private start = async () => { await this.connection.start(); this.connection.on("newState", (board: string) => { var state = JSON.parse(board) as StateBoard; if (state.isLife) { this.state = state; } else { this.state!.isLife = false; this.state!.isWin = state.isWin; if (this.state!.isWin) { this.state = state; } } }); } } export const snake = new Snake();И React компонент, который просто все это дело рисует.
App.tsx
import { snake } from './shores/snake'; import { useObserver } from 'mobx-react-lite'; import cs from 'classnames'; const App = (): JSX.Element => { const cellRender = (indexRow: number, indexColumn: number): JSX.Element => { const state = snake.state!; const isMouse = state.mouse.x == indexColumn && state.mouse.y == indexRow; if (isMouse) { return <div key={`${indexRow}_${indexColumn}`} className='cell mouse'></div>; } const indexCellSnake = state.piton.findIndex(p => p.x == indexColumn && p.y == indexRow); if (indexCellSnake == -1) { return <div key={`${indexRow}_${indexColumn}`} className='cell'></div>; } const prewIndexCellSnake = indexCellSnake - 1; const prewCellPiton = 0 <= prewIndexCellSnake ? state.piton[prewIndexCellSnake] : null; const cellPiton = state.piton[indexCellSnake]; const nextIndexCellSnake = indexCellSnake + 1; const nextCellPiton = nextIndexCellSnake < state.piton.length ? state.piton[nextIndexCellSnake] : null; let up = false, left = false, down = false, rigth = false; if (!!prewCellPiton) { if (prewCellPiton.x < cellPiton.x) { left = true; } if (prewCellPiton.y < cellPiton.y) { up = true; } if (cellPiton.x < prewCellPiton.x) { rigth = true; } if (cellPiton.y < prewCellPiton.y) { down = true; } } if (!!nextCellPiton) { if (cellPiton.x < nextCellPiton.x) { rigth = true; } if (cellPiton.y < nextCellPiton.y) { down = true; } if (nextCellPiton.x < cellPiton.x) { left = true; } if (nextCellPiton.y < cellPiton.y) { up = true; } } return <div key={`${indexRow}_${indexColumn}`} className='cell'> <table className='shake'> <tbody> <tr> <td width="10%" height="10%" /> <td height="10%" className={cs({ 'shake-segment': up })} /> <td width="10%" height="10%" /> </tr> <tr> <td width="10%" className={cs({ 'shake-segment': left })} /> <td className='shake-segment' /> <td width="10%" className={cs({ 'shake-segment': rigth })} /> </tr> <tr> <td width="10%" height="10%" /> <td height="10%" className={cs({ 'shake-segment': down })} /> <td width="10%" height="10%" /> </tr> </tbody> </table> </div>; } const rowRender = (indexRow: number): JSX.Element => { const state = snake.state!; const cells: JSX.Element[] = []; for (let j = 0; j < state.ySize; j++) { cells.push(cellRender(indexRow, j)); } return (<>{cells}</>); } const tableRender = (): JSX.Element => { const state = snake.state!; const rows: JSX.Element[] = []; for (let i = 0; i < state.ySize; i++) { rows.push( (<div key={i.toString()} className="row"> {rowRender(i)} </div>) ); } return (<>{rows}</>); } return useObserver(() => { console.log(snake.state); if (!snake.state) { return <div /> } let state: string = "идет игра"; if (snake.state.isLife == false) { state = snake.state.isWin ? "Победа" : "Поражение" } return (<> <span className="state">{state}</span> <div className="table"> {tableRender()} </div> </>); }); } export default App;С беком тоже мудрить не будем:
public class SnakeSender { class Vector2 { public int X { get; set; } public int Y { get; set; } public Vector2(int x, int y) { this.X = x; this.Y = y; } } class Vector2Comparer : IEqualityComparer<Vector2> { public bool Equals([AllowNull] Vector2 value1, [AllowNull] Vector2 value2) { return value1.X == value2.X && value1.Y == value2.Y; } public int GetHashCode([DisallowNull] Vector2 obj) { return 0; } } private readonly static Vector2Comparer vector2Comparer = new Vector2Comparer(); [JsonConverter(typeof(StringEnumConverter))] enum Cell { None, Mouse, Snake } enum Directions { Up, Left, Down, Rigth } class StateBoard { public bool IsLife { get; set; } public bool IsWin { get; set; } public int XSize { get; set; } public int YSize { get; set; } public Vector2 Mouse { get; set; } public List<Vector2> Piton { get; set; } public List<Vector2> HamiltonPath { get; set; } } const int xSize = 12, ySize = 12; ... private void CheckDead() { Vector2 head = this.Piton.Last(); if (head.X < 0 || head.Y < 0 || xSize <= head.X || ySize <= head.Y || this.Piton.SkipLast(1).Contains(head, vector2Comparer)) { this.IsLife = false; this.IsWin = false; return; } } private void Render() { var hubContext = (IHubContext<SnakeHub>)this.ServiceProvider.GetService(typeof(IHubContext<SnakeHub>)); var piton = this.Piton.ToList(); piton.Reverse(); hubContext.Clients?.All.SendAsync("newState", JsonConvert.SerializeObject(new StateBoard() { IsLife = this.IsLife, IsWin = this.IsWin, XSize = xSize, YSize = ySize, Mouse = this.Mouse, Piton = piton, HamiltonPath = HamiltonPath })); } private List<Vector2> GetEmptyCells() { List<Vector2> emptyCells = new List<Vector2>(xSize * ySize); for (int i = 0; i < ySize; i++) { for (int j = 0; j < xSize; j++) { if (!this.Piton.Contains(new Vector2(j, i), vector2Comparer)) { emptyCells.Add(new Vector2(j, i)); } } } return emptyCells; } }
В начале игры у нас есть одна красная мышь и одноклеточная змея.
А теперь нам, как-то надо начать играть.
Вообще играть в змейку очень просто – нужно просто проходить один раз по каждой клеточке в матрице. И всё задача решена – Happy End.
Если быть более точным, наше поле представляет собой «Связный граф». Т.е. каждая клеточка на доске – это вершина. Из каждой вершины идут ребра – это переход на соседнюю вершину.
Таких ребер либо от 2 до 4. Для крайней клеточки и для центральной соответственно.
Где-то 4 августа 1805 — 2 сентября 1865 в Ирландии жил некий Гамильтон Уильям Роуэн, исследовал задачу «кругосветного путешествия» по додекаэдру. В этой задаче вершины додекаэдра символизировали известные города, такие как Брюссель, Амстердам, Эдинбург, Пекин, Прага, Дели, Франкфурт и др., а рёбра — соединяющие их дороги. Путешествующий должен пройти «вокруг света», найдя путь, который проходит через все вершины ровно один раз. Чтобы сделать задачу более интересной, порядок прохождения городов устанавливался заранее. А чтобы было легче запомнить, какие города уже соединены, в каждую вершину додекаэдра был вбит гвоздь, и проложенный путь отмечался небольшой верёвкой, которая могла обматываться вокруг гвоздя. Однако такая конструкция оказалась слишком громоздкой, и Гамильтон предложил новый вариант игры, заменив додекаэдр плоским графом, изоморфным графу, построенному на рёбрах додекаэдра.
В общем есть такая шутка как «Гамильтоновый цикл». Гамильтоновый цикл» — это такой цикл (замкнутый путь), который проходит через каждую вершину данного графа ровно по одному разу; то есть простой цикл, в который входят все вершины графа. Также с гамильтоновым графом тесно связано понятие гамильтонова пути, который является простым путём (путём без петель), проходящим через каждую вершину графа ровно один раз. Гамильтонов путь отличается от цикла тем, что у пути начальные и конечные точки могут не совпадать, в отличие от цикла. Гамильтонов цикл является гамильтоновым путём.
Визуально это можно представить как
В нашем случае так.
Только вот нюанс… Если мы от балды попробуем построить такой вот цикл, мы получим перебор такого количества вариантов, что ждать можно будет до второго пришествия.
Суть в том, что общий подход к нахождению «Гамильтонов цикла» подразумевает полный перебор и ничего более оптимального вроде как нет. А у нас при матрице 12 на 12 только вершин 144 и для каждой нужно проверить от 2 до 4-х ребер. В общем, там где-то сложность n!..
Но т.к. мы решаем задачку для матрицы в которой каждая вершина связана со всеми соседями, можно сделать просто проход по часовой стрелке.
Тогда построить «Гамильтонов цикл» не составляет труда.
private void CreateHamiltonPath() { this.HamiltonPath.Clear(); this.HamiltonPath.Add(new Vector2(0, 0)); HamiltonStep(this.HamiltonPath.Last()); } private bool HamiltonStep(Vector2 current) { if (HamiltonPath.Count == HamiltonPath.Capacity) { var first = HamiltonPath.First(); return (first.X == current.X && first.Y == current.Y - 1) || (first.X == current.X && first.Y == current.Y + 1) || (first.X - 1 == current.X && first.Y == current.Y) || (first.X + 1 == current.X && first.Y == current.Y); } foreach (var direction in new[] { Directions.Down, Directions.Rigth, Directions.Up, Directions.Left }) { Vector2 newElement = null; switch (direction) { case Directions.Up: newElement = new Vector2(current.X, current.Y - 1); break; case Directions.Left: newElement = new Vector2(current.X - 1, current.Y); break; case Directions.Down: newElement = new Vector2(current.X, current.Y + 1); break; case Directions.Rigth: newElement = new Vector2(current.X + 1, current.Y); break; } if (0 <= newElement.X && newElement.X < xSize && 0 <= newElement.Y && newElement.Y < ySize && !HamiltonPath.Contains(newElement, vector2Comparer)) { HamiltonPath.Add(newElement); if (HamiltonStep(newElement)) { return true; } HamiltonPath.Remove(newElement); } } return false; }И да это идею я „заимствовал“ эту идею у „Code Bullet“, а он её еще у одного чувака в интеренте.
Короче, как сказал Пабло Пикассо:
Хорошие художники копируют, великие художники воруют
И так, мы получаем змейку которая ходит поэтому циклу до победы:
В целом задача решена! Но как же убого выглядит, когда одноклеточная змея ползет от точки в другую сторону. Хотя никаких препятствий взять её нет…
А с точки зрения математики мы получаем сложность в (O)n^n-1
Т.к. каждый раз… Каждый…. Нам нужно обходить всё по циклу…
Проще говоря — устанем ждать… Так, что решение хоть и хорошее, но есть проблема — времени требует много…
Оптимизация
Что мы знаем о змее. Её длина изменяется при поедании мыши. И идеальной траекторией движения для нее является Гамельтонов путь. А самое короткое расстояние между двумя точками – это прямая.
Начнем с вызова рекурсии:
private void CalculatePath() { this.StepsCountAfterCalculatePath = 0; int finalIndexPoint = this.HamiltonPath.FindIndex(p => p.X == this.Mouse.X && p.Y == this.Mouse.Y); List<Vector2> tempPath = new List<Vector2>(); List<Vector2> stepPiton = new List<Vector2>(this.Piton); Debug.WriteLine($"Piton length: {this.Piton.Count}"); int index = 0; var result = StepTempPath(ref index, GetInvert(stepPiton, this.Mouse), this.Piton.Last(), finalIndexPoint, stepPiton, tempPath); if (result.PathIsFound) { this.TempPath = new Queue<Vector2>(tempPath); this.InvertHamiltonPath = result.InvertHamiltonPath; } }А вот рекурсивную часть разберем по отдельности.
Основная часть — максимально простая.
Мы упорно приближаемся к цели:
if (current.X < finalPoint.X) { newElement = new Vector2(current.X + 1, current.Y); } else if (finalPoint.X < current.X) { newElement = new Vector2(current.X - 1, current.Y); } else if (current.Y < finalPoint.Y) { newElement = new Vector2(current.X, current.Y + 1); } else if (finalPoint.Y < current.Y) { newElement = new Vector2(current.X, current.Y - 1); }Змея не умеет ползать по диагонали, то сейчас мы сначала выравниваемся по вертикали, а потом уже идем к цели по горизонтали. И дальше можно заходить на новую итерацию для проверки.
Проверка финального состояния выглядит как-то так для начала.
if (current.X == finalPoint.X && current.Y == finalPoint.Y) { var tempPiton = stepPiton.TakeLast(this.Piton.Count).ToList(); for (int i = 1; i < this.Piton.Count; i++) { var hamiltonPoint = (finalIndexPoint + i < this.HamiltonPath.Count) ? this.HamiltonPath[finalIndexPoint + i] : this.HamiltonPath[finalIndexPoint + i - this.HamiltonPath.Count]; if (tempPiton.TakeLast(this.Piton.Count).Contains(hamiltonPoint, vector2Comparer)) { return false; } tempPiton.Add(hamiltonPoint); } return true; }Что мы тут собственно делаем.
Когда мы находим на виртуальному пути нашу мышь. Мы дополнительно, продолжаем строить путь, но уже по идеальному пути Гамильтона и если он не пересекается с телом нашей змеи, то мы точно знаем, что по такому пути до текущей мыши можно спокойно пустить змею т.к. после «съедения мыши», где бы не находилась следующая, мы сможем пройти по пути полного цикла и съесть следующую.
Пока мы одноклеточные — проблем вообще быть не может в принципе, но это продолжается не долго… Как только наша длина становится больше одного прямой путь к цели – порождает проблему. Цикл имеет определённую направленность, т.е. змея движется всегда по часовой стрелке, как мы собственно стоили сам путь.
И тут возникает проблема. Допустим мы подошли к следующей мыши сверху, а пусть Гамильтона в данной конкретном месте пути идет вверх. По змея будет двигаться против самой себя, что в принципе невозможно… Для решения этой проблемы, мы введем понятие инвертированного пути Гамильтона.
Т.е. змея может двигаться не только по часовой стрелке по которой строился путь, но и в обратном направлении по этому пути. Путь от этого не изменится, а вот направление движения – да.
Изменим проверку.
if (current.X == finalPoint.X && current.Y == finalPoint.Y) { if (this.Piton.Count == 1) { return new ResultAnlaizePath(true); } foreach (var d in new[] { false, true }) { var tempPiton = stepPiton.TakeLast(this.Piton.Count).ToList(); bool isFound = true; bool invertHamiltonPath = d; for (int j = 1; j < this.Piton.Count; j++) { Vector2 hamiltonPoint; if (invertHamiltonPath) { hamiltonPoint = (finalIndexPoint - j >= 0) ? this.HamiltonPath[finalIndexPoint - j] : this.HamiltonPath[this.HamiltonPath.Count - j]; } else { hamiltonPoint = (finalIndexPoint + j < this.HamiltonPath.Count) ? this.HamiltonPath[finalIndexPoint + j] : this.HamiltonPath[finalIndexPoint + j - this.HamiltonPath.Count]; } if (tempPiton.TakeLast(this.Piton.Count).Contains(hamiltonPoint, vector2Comparer)) { isFound = false; break; } tempPiton.Add(hamiltonPoint); } if (isFound) { return new ResultAnlaizePath(true, invertHamiltonPath); } } return new ResultAnlaizePath(false); }И кстати, упомянутый «Code Bullet» до этого финта ушами не додумался. Я про инвертирование, да он «срезал углы», по некому своему алгоритму, который остался в тайне покрытым мраком. Но точно могу сказать, что в его решения был косячок, из-за которого провалился его проход.
Ну в целом, что еще можно сказать. Понятное дело, что кроме противохода движению змеи, можно банально попасть в её хвост. Для обхода данной ситуации напишем простой поиск другого варианта пути.
if (!stepPiton.TakeLast(this.Piton.Count).Contains(newElement, vector2Comparer)) { tempPath.Add(newElement); stepPiton.Add(newElement); var retult = StepTempPath(ref index, !invert, newElement, finalIndexPoint, stepPiton, tempPath); if (retult.PathIsFound) { return retult; } if (this.HamiltonPath.Count < index) { return new ResultAnlaizePath(false); } tempPath.Remove(newElement); stepPiton.Remove(newElement); } Vector2 nextFinalPoint; if (this.InvertHamiltonPath) { nextFinalPoint = (finalIndexPoint - 1 < 0) ? this.HamiltonPath[this.HamiltonPath.Count - 1] : this.HamiltonPath[finalIndexPoint - 1]; } else { nextFinalPoint = (finalIndexPoint + 1 == this.HamiltonPath.Count) ? this.HamiltonPath[0] : this.HamiltonPath[finalIndexPoint + 1]; } List<Directions> directions = new List<Directions>(4); directions.Add(finalPoint.Y < nextFinalPoint.Y ? Directions.Up : Directions.Down); directions.Add(finalPoint.X < nextFinalPoint.X ? Directions.Left : Directions.Rigth); directions.Add(finalPoint.Y < nextFinalPoint.Y ? Directions.Down : Directions.Up); directions.Add(finalPoint.X < nextFinalPoint.X ? Directions.Rigth : Directions.Left); foreach (var direction in directions) { switch (direction) { case Directions.Up: newElement = new Vector2(current.X, current.Y - 1); break; case Directions.Left: newElement = new Vector2(current.X - 1, current.Y); break; case Directions.Down: newElement = new Vector2(current.X, current.Y + 1); break; case Directions.Rigth: newElement = new Vector2(current.X + 1, current.Y); break; } if (0 <= newElement.X && newElement.X < xSize && 0 <= newElement.Y && newElement.Y < ySize && !stepPiton.TakeLast(this.Piton.Count).Contains(newElement, vector2Comparer)) { tempPath.Add(newElement); stepPiton.Add(newElement); var retult = StepTempPath(ref index, GetInvert(stepPiton, finalPoint), newElement, finalIndexPoint, stepPiton, tempPath); if (retult.PathIsFound) { return retult; } if (this.HamiltonPath.Count < index) { return new ResultAnlaizePath(false); } tempPath.Remove(newElement); stepPiton.Remove(newElement); } } return new ResultAnlaizePath(false);В целом ничего сложного.
Можно остановиться только на этом.
Здесь я пытаюсь пусть поиск в противоход «прямому движению» к мыше описанному выше.
List<Directions> directions = new List<Directions>(4); directions.Add(finalPoint.Y < nextFinalPoint.Y ? Directions.Up : Directions.Down); directions.Add(finalPoint.X < nextFinalPoint.X ? Directions.Left : Directions.Rigth); directions.Add(finalPoint.Y < nextFinalPoint.Y ? Directions.Down : Directions.Up); directions.Add(finalPoint.X < nextFinalPoint.X ? Directions.Rigth : Directions.Left); Т.е. «сделать шаг в другую строну» дабы обойти препятствие которое было найдено на прямом пути.
Ниже полный код, да его можно было разбить на под файлики сделать красиво, но сейчас так наглядней для статьи.
using Microsoft.AspNetCore.SignalR; using Newtonsoft.Json; using Newtonsoft.Json.Converters; using System; using System.Collections; using System.Collections.Generic; using System.Diagnostics; using System.Diagnostics.CodeAnalysis; using System.Linq; using System.Runtime.ExceptionServices; using System.Threading.Tasks; using System.Timers; namespace SnakeApplication.WebApp.Hubs { public class SnakeHub : Hub { } public class SnakeSender { class Vector2 { public int X { get; set; } public int Y { get; set; } public Vector2(int x, int y) { this.X = x; this.Y = y; } } class Vector2Comparer : IEqualityComparer<Vector2> { public bool Equals([AllowNull] Vector2 value1, [AllowNull] Vector2 value2) { return value1.X == value2.X && value1.Y == value2.Y; } public int GetHashCode([DisallowNull] Vector2 obj) { return 0; } } private readonly static Vector2Comparer vector2Comparer = new Vector2Comparer(); [JsonConverter(typeof(StringEnumConverter))] enum Cell { None, Mouse, Snake } enum Directions { Up, Left, Down, Rigth } class StateBoard { public bool IsLife { get; set; } public bool IsWin { get; set; } public int XSize { get; set; } public int YSize { get; set; } public Vector2 Mouse { get; set; } public List<Vector2> Piton { get; set; } public List<Vector2> HamiltonPath { get; set; } } const int xSize = 12, ySize = 12; private Random Rand { get; } private IServiceProvider ServiceProvider { get; } private bool IsLife { get; set; } private bool IsWin { get; set; } Directions Direction { get; set; } private Vector2 Mouse { get; set; } private Queue<Vector2> Piton { get; set; } private bool InvertHamiltonPath { get; set; } private List<Vector2> HamiltonPath { get; } private Queue<Vector2> TempPath { get; set; } private int StepsCountAfterCalculatePath { get; set; } public SnakeSender(IServiceProvider serviceProvider) { this.Rand = new Random(); this.ServiceProvider = serviceProvider; this.TempPath = new Queue<Vector2>(); this.HamiltonPath = new List<Vector2>(xSize * ySize); this.CreateHamiltonPath(); this.CreateBoard(); } private void CreateHamiltonPath() { this.HamiltonPath.Clear(); this.HamiltonPath.Add(new Vector2(0, 0)); HamiltonStep(this.HamiltonPath.Last()); } private bool HamiltonStep(Vector2 current) { if (HamiltonPath.Count == HamiltonPath.Capacity) { var first = HamiltonPath.First(); return (first.X == current.X && first.Y == current.Y - 1) || (first.X == current.X && first.Y == current.Y + 1) || (first.X - 1 == current.X && first.Y == current.Y) || (first.X + 1 == current.X && first.Y == current.Y); } foreach (var direction in new[] { Directions.Down, Directions.Rigth, Directions.Up, Directions.Left }) { Vector2 newElement = null; switch (direction) { case Directions.Up: newElement = new Vector2(current.X, current.Y - 1); break; case Directions.Left: newElement = new Vector2(current.X - 1, current.Y); break; case Directions.Down: newElement = new Vector2(current.X, current.Y + 1); break; case Directions.Rigth: newElement = new Vector2(current.X + 1, current.Y); break; } if (0 <= newElement.X && newElement.X < xSize && 0 <= newElement.Y && newElement.Y < ySize && !HamiltonPath.Contains(newElement, vector2Comparer)) { HamiltonPath.Add(newElement); if (HamiltonStep(newElement)) { return true; } HamiltonPath.Remove(newElement); } } return false; } private void CreateBoard() { Task.Run(async () => { this.Piton = new Queue<Vector2>(); //for (int i = 0; i < 1; i++) //{ // this.Piton.Enqueue(new Vector2(ySize / 2, xSize / 2 - i)); //} this.Piton.Enqueue(new Vector2(0, 0)); this.IsLife = true; this.Direction = Directions.Up; this.CreateMouse(); while (this.IsLife) { this.LifeCycle(); await Task.Delay(100); } }); } private void LifeCycle() { this.SetDirection(); this.Step(); this.CheckDead(); this.Render(); } private void SetDirection() { Vector2 head = this.Piton.Last(); int currentIndnex = this.HamiltonPath.FindIndex(p => p.X == head.X && p.Y == head.Y); Vector2 currentElement = this.HamiltonPath[currentIndnex]; Vector2 nextElement = null; if (this.TempPath.Count > 0) { nextElement = this.TempPath.Dequeue(); } else { this.StepsCountAfterCalculatePath++; if (this.InvertHamiltonPath) { nextElement = (currentIndnex - 1 < 0) ? this.HamiltonPath[this.HamiltonPath.Count - 1] : this.HamiltonPath[currentIndnex - 1]; } else { nextElement = (currentIndnex + 1 == this.HamiltonPath.Count) ? this.HamiltonPath[0] : this.HamiltonPath[currentIndnex + 1]; } } if (currentElement.X == nextElement.X && currentElement.Y < nextElement.Y) { this.Direction = Directions.Down; return; } if (currentElement.X == nextElement.X && nextElement.Y < currentElement.Y) { this.Direction = Directions.Up; return; } if (currentElement.X < nextElement.X && currentElement.Y == nextElement.Y) { this.Direction = Directions.Rigth; return; } if (nextElement.X < currentElement.X && currentElement.Y == nextElement.Y) { this.Direction = Directions.Left; return; } throw new NotImplementedException(); } private void Step() { Vector2 head = this.Piton.Last(); switch (this.Direction) { case Directions.Up: this.Piton.Enqueue(new Vector2(head.X, head.Y - 1)); break; case Directions.Left: this.Piton.Enqueue(new Vector2(head.X - 1, head.Y)); break; case Directions.Down: this.Piton.Enqueue(new Vector2(head.X, head.Y + 1)); break; case Directions.Rigth: this.Piton.Enqueue(new Vector2(head.X + 1, head.Y)); break; } if (this.Piton.Contains(this.Mouse, vector2Comparer)) { CreateMouse(); } else { this.Piton.Dequeue(); } if (this.Piton.Count < this.StepsCountAfterCalculatePath) { this.CalculatePath(); } } private void CheckDead() { Vector2 head = this.Piton.Last(); if (head.X < 0 || head.Y < 0 || xSize <= head.X || ySize <= head.Y || this.Piton.SkipLast(1).Contains(head, vector2Comparer)) { this.IsLife = false; this.IsWin = false; return; } } private void Render() { var hubContext = (IHubContext<SnakeHub>)this.ServiceProvider.GetService(typeof(IHubContext<SnakeHub>)); var piton = this.Piton.ToList(); piton.Reverse(); hubContext.Clients?.All.SendAsync("newState", JsonConvert.SerializeObject(new StateBoard() { IsLife = this.IsLife, IsWin = this.IsWin, XSize = xSize, YSize = ySize, Mouse = this.Mouse, Piton = piton, HamiltonPath = HamiltonPath })); } private void CreateMouse() { List<Vector2> emptyCells = GetEmptyCells(); if (emptyCells.Count > 0) { this.Mouse = emptyCells[this.Rand.Next(emptyCells.Count)]; this.CalculatePath(); } else { this.IsLife = false; this.IsWin = true; } } private void CalculatePath() { this.StepsCountAfterCalculatePath = 0; int finalIndexPoint = this.HamiltonPath.FindIndex(p => p.X == this.Mouse.X && p.Y == this.Mouse.Y); List<Vector2> tempPath = new List<Vector2>(); List<Vector2> stepPiton = new List<Vector2>(this.Piton); Debug.WriteLine($"Piton length: {this.Piton.Count}"); int index = 0; var result = StepTempPath(ref index, GetInvert(stepPiton, this.Mouse), this.Piton.Last(), finalIndexPoint, stepPiton, tempPath); if (result.PathIsFound) { this.TempPath = new Queue<Vector2>(tempPath); this.InvertHamiltonPath = result.InvertHamiltonPath; } } private bool GetInvert(List<Vector2> stepPiton, Vector2 finalPoint) { if (this.Piton.Count > 1) { int pitonDirection = stepPiton.Last().Y - stepPiton[stepPiton.Count - 2].Y; int mouseDirection = stepPiton.Last().Y - finalPoint.Y; return (pitonDirection < 0 && mouseDirection < 0) || (pitonDirection > 0 && mouseDirection > 0); } return false; } class ResultAnlaizePath { public bool PathIsFound { get; set; } public bool InvertHamiltonPath { get; set; } public ResultAnlaizePath(bool pathIsFound, bool invertHamiltonPath = false) { PathIsFound = pathIsFound; InvertHamiltonPath = invertHamiltonPath; } } private ResultAnlaizePath StepTempPath(ref int index, bool invert, Vector2 current, int finalIndexPoint, List<Vector2> stepPiton, List<Vector2> tempPath) { index++; if (this.HamiltonPath.Count < index) { return new ResultAnlaizePath(false); } Debug.WriteLine($"index {index} {tempPath.Count}"); var finalPoint = this.HamiltonPath[finalIndexPoint]; if (current.X == finalPoint.X && current.Y == finalPoint.Y) { if (this.Piton.Count == 1) { return new ResultAnlaizePath(true); } foreach (var d in new[] { false, true }) { var tempPiton = stepPiton.TakeLast(this.Piton.Count).ToList(); bool isFound = true; bool invertHamiltonPath = d; for (int j = 1; j < this.Piton.Count; j++) { Vector2 hamiltonPoint; if (invertHamiltonPath) { hamiltonPoint = (finalIndexPoint - j >= 0) ? this.HamiltonPath[finalIndexPoint - j] : this.HamiltonPath[this.HamiltonPath.Count - j]; } else { hamiltonPoint = (finalIndexPoint + j < this.HamiltonPath.Count) ? this.HamiltonPath[finalIndexPoint + j] : this.HamiltonPath[finalIndexPoint + j - this.HamiltonPath.Count]; } if (tempPiton.TakeLast(this.Piton.Count).Contains(hamiltonPoint, vector2Comparer)) { isFound = false; break; } tempPiton.Add(hamiltonPoint); } if (isFound) { return new ResultAnlaizePath(true, invertHamiltonPath); } } return new ResultAnlaizePath(false); } if ((xSize + ySize * 2) <= tempPath.Count) { return new ResultAnlaizePath(false); } Vector2 newElement = null; if (invert) { if (current.X < finalPoint.X) { newElement = new Vector2(current.X + 1, current.Y); } else if (finalPoint.X < current.X) { newElement = new Vector2(current.X - 1, current.Y); } else if (current.Y < finalPoint.Y) { newElement = new Vector2(current.X, current.Y + 1); } else if (finalPoint.Y < current.Y) { newElement = new Vector2(current.X, current.Y - 1); } } else { if (current.Y < finalPoint.Y) { newElement = new Vector2(current.X, current.Y + 1); } else if (finalPoint.Y < current.Y) { newElement = new Vector2(current.X, current.Y - 1); } else if (current.X < finalPoint.X) { newElement = new Vector2(current.X + 1, current.Y); } else if (finalPoint.X < current.X) { newElement = new Vector2(current.X - 1, current.Y); } } if (!stepPiton.TakeLast(this.Piton.Count).Contains(newElement, vector2Comparer)) { tempPath.Add(newElement); stepPiton.Add(newElement); var retult = StepTempPath(ref index, !invert, newElement, finalIndexPoint, stepPiton, tempPath); if (retult.PathIsFound) { return retult; } if (this.HamiltonPath.Count < index) { return new ResultAnlaizePath(false); } tempPath.Remove(newElement); stepPiton.Remove(newElement); } Vector2 nextFinalPoint; if (this.InvertHamiltonPath) { nextFinalPoint = (finalIndexPoint - 1 < 0) ? this.HamiltonPath[this.HamiltonPath.Count - 1] : this.HamiltonPath[finalIndexPoint - 1]; } else { nextFinalPoint = (finalIndexPoint + 1 == this.HamiltonPath.Count) ? this.HamiltonPath[0] : this.HamiltonPath[finalIndexPoint + 1]; } List<Directions> directions = new List<Directions>(4); directions.Add(finalPoint.Y < nextFinalPoint.Y ? Directions.Up : Directions.Down); directions.Add(finalPoint.X < nextFinalPoint.X ? Directions.Left : Directions.Rigth); directions.Add(finalPoint.Y < nextFinalPoint.Y ? Directions.Down : Directions.Up); directions.Add(finalPoint.X < nextFinalPoint.X ? Directions.Rigth : Directions.Left); foreach (var direction in directions) { switch (direction) { case Directions.Up: newElement = new Vector2(current.X, current.Y - 1); break; case Directions.Left: newElement = new Vector2(current.X - 1, current.Y); break; case Directions.Down: newElement = new Vector2(current.X, current.Y + 1); break; case Directions.Rigth: newElement = new Vector2(current.X + 1, current.Y); break; } if (0 <= newElement.X && newElement.X < xSize && 0 <= newElement.Y && newElement.Y < ySize && !stepPiton.TakeLast(this.Piton.Count).Contains(newElement, vector2Comparer)) { tempPath.Add(newElement); stepPiton.Add(newElement); var retult = StepTempPath(ref index, GetInvert(stepPiton, finalPoint), newElement, finalIndexPoint, stepPiton, tempPath); if (retult.PathIsFound) { return retult; } if (this.HamiltonPath.Count < index) { return new ResultAnlaizePath(false); } tempPath.Remove(newElement); stepPiton.Remove(newElement); } } return new ResultAnlaizePath(false); } private List<Vector2> GetEmptyCells() { List<Vector2> emptyCells = new List<Vector2>(xSize * ySize); for (int i = 0; i < ySize; i++) { for (int j = 0; j < xSize; j++) { if (!this.Piton.Contains(new Vector2(j, i), vector2Comparer)) { emptyCells.Add(new Vector2(j, i)); } } } return emptyCells; } } }
Собственно как всё это ползает.
Всем спасибо за уделенное внимание.
Теперь осталось написать для нее нормальный AI.
ссылка на оригинал статьи https://habr.com/ru/post/544696/
Добавить комментарий