Оптимизация
Что мы знаем о змее. Её длина изменяется при поедании мыши. И идеальной траекторией движения для нее является Гамильтонов путь. А самое короткое расстояние между двумя точками – это прямая.
Начнем с вызова рекурсии:
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.
Пишем игру
Перед тем как, играть, напишем саму игру.
Все расчеты будем производить на сервере, отображать змейку в браузере, а инфой будем обмениваться через WebSocket (SignalR).
Скучный код без которого ничего не работает
Отображение максимально простое. У нас есть Store который получает информацию об положении змеи и размере поля и состоянии игры.
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;
}
И да это идею я „заимствовал“ эту идею у „
“, а он её еще у одного чувака в интеренте.
Короче, как сказал Пабло Пикассо:
Хорошие художники копируют, великие художники воруют
И так, мы получаем змейку которая ходит поэтому циклу до победы:
В целом задача решена! Но как же убого выглядит, когда одноклеточная змея ползет от точки в другую сторону. Хотя никаких препятствий взять её нет…
А с точки зрения математики мы получаем сложность в (O)n^2. Где n — количество точек (в нашем случае n = 144).
Т.к. каждый раз… Каждый…. Нам нужно обходить всё по циклу…
Проще говоря — устанем ждать… Так, что решение хоть и хорошее, но есть проблема — времени требует много…
Пишем скрипт
1. Зададим все переменные, которые нам понадобятся.
// Поле, на котором всё будет происходить, — тоже как бы переменная
var canvas = document.getElementById('game');
// Классическая змейка — двухмерная, сделаем такую же
var context = canvas.getContext('2d');
// Размер одной клеточки на поле — 16 пикселей
var grid = 16;
// Служебная переменная, которая отвечает за скорость змейки
var count = 0;
// А вот и сама змейка
var snake = {
// Начальные координаты
x: 160,
y: 160,
// Скорость змейки — в каждом новом кадре змейка смещается по оси Х или У. На старте будет двигаться горизонтально, поэтому скорость по игреку равна нулю.
dx: grid,
dy: 0,
// Тащим за собой хвост, который пока пустой
cells: [],
// Стартовая длина змейки — 4 клеточки
maxCells: 4
};
// А это — еда. Представим, что это красные яблоки.
var apple = {
// Начальные координаты яблока
x: 320,
y: 320
};2. Сделаем генератор случайных чисел. Он нам понадобится, чтобы размещать еду на поле случайным образом.
// Делаем генератор случайных чисел в заданном диапазоне
function getRandomInt(min, max) {
return Math.floor(Math.random() * (max - min)) min;
3. Напишем основной игровой цикл, который будет работать бесконечно.
// Игровой цикл — основной процесс, внутри которого будет всё происходить
function loop() {
// Дальше будет хитрая функция, которая замедляет скорость игры с 60 кадров в секунду до 15. Для этого она пропускает три кадра из четырёх, то есть срабатывает каждый четвёртый кадр игры. Было 60 кадров в секунду, станет 15.
requestAnimationFrame(loop);
// Игровой код выполнится только один раз из четырёх, в этом и суть замедления кадров, а пока переменная count меньше четырёх, код выполняться не будет.
if ( count < 4) {
return;
}
// Обнуляем переменную скорости
count = 0;
// Очищаем игровое поле
context.clearRect(0, 0, canvas.width, canvas.height);
// Двигаем змейку с нужной скоростью
snake.x = snake.dx;
snake.y = snake.dy;
// Если змейка достигла края поля по горизонтали — продолжаем её движение с противоположной стороны
if (snake.x < 0) {
snake.x = canvas.width - grid;
}
else if (snake.x >= canvas.width) {
snake.x = 0;
}
// Делаем то же самое для движения по вертикали
if (snake.y < 0) {
snake.y = canvas.height - grid;
}
else if (snake.y >= canvas.height) {
snake.y = 0;
}
// Продолжаем двигаться в выбранном направлении. Голова всегда впереди, поэтому добавляем её координаты в начало массива, который отвечает за всю змейку.
snake.cells.unshift({ x: snake.x, y: snake.y });
// Сразу после этого удаляем последний элемент из массива змейки, потому что она движется и постоянно особождает клетки после себя
if (snake.cells.length > snake.maxCells) {
snake.cells.pop();
}
// Рисуем еду — красное яблоко
context.fillStyle = 'red';
context.fillRect(apple.x, apple.y, grid - 1, grid - 1);
// Одно движение змейки — один новый нарисованный квадратик
context.fillStyle = 'green';
// Обрабатываем каждый элемент змейки
snake.cells.forEach(function (cell, index) {
// Чтобы создать эффект клеточек, делаем зелёные квадратики меньше на один пиксель, чтобы вокруг них образовалась чёрная граница
context.fillRect(cell.x, cell.y, grid - 1, grid - 1);
// Если змейка добралась до яблока...
if (cell.x === apple.x && cell.y === apple.y) {
// увеличиваем длину змейки
snake.maxCells ;
// Рисуем новое яблочко
// Помним, что размер холста у нас 400x400, при этом он разбит на ячейки — 25 в каждую сторону
apple.x = getRandomInt(0, 25) * grid;
apple.y = getRandomInt(0, 25) * grid;
}
// Проверяем, не столкнулась ли змея сама с собой
// Для этого перебираем весь массив и смотрим, есть ли у нас в массиве змейки две клетки с одинаковыми координатами
for (var i = index 1; i < snake.cells.length; i ) {
// Если такие клетки есть — начинаем игру заново
if (cell.x === snake.cells[i].x && cell.y === snake.cells[i].y) {
// Задаём стартовые параметры основным переменным
snake.x = 160;
snake.y = 160;
snake.cells = [];
snake.maxCells = 4;
snake.dx = grid;
snake.dy = 0;
// Ставим яблочко в случайное место
apple.x = getRandomInt(0, 25) * grid;
apple.y = getRandomInt(0, 25) * grid;
}
}
});
}4. Сделаем управление стрелочками на клавиатуре.
// Смотрим, какие нажимаются клавиши, и реагируем на них нужным образом
document.addEventListener('keydown', function (e) {
// Дополнительно проверяем такой момент: если змейка движется, например, влево, то ещё одно нажатие влево или вправо ничего не поменяет — змейка продолжит двигаться в ту же сторону, что и раньше. Это сделано для того, чтобы не разворачивать весь массив со змейкой на лету и не усложнять код игры.
// Стрелка влево
// Если нажата стрелка влево, и при этом змейка никуда не движется по горизонтали…
if (e.which === 37 && snake.dx === 0) {
// то даём ей движение по горизонтали, влево, а вертикальное — останавливаем
// Та же самая логика будет и в остальных кнопках
snake.dx = -grid;
snake.dy = 0;
}
// Стрелка вверх
else if (e.which === 38 && snake.dy === 0) {
snake.dy = -grid;
snake.dx = 0;
}
// Стрелка вправо
else if (e.which === 39 && snake.dx === 0) {
snake.dx = grid;
snake.dy = 0;
}
// Стрелка вниз
else if (e.which === 40 && snake.dy === 0) {
snake.dy = grid;
snake.dx = 0;
}
});5. Запускаем игру. Для этого достаточно запустить предыдущий бесконечный цикл, поэтому пишем:
requestAnimationFrame(loop);
6. Наслаждаемся результатом:
Чтобы у вас тоже получилось такое, просто скопируйте готовый код, сохраните его как HTML-файл и откройте в браузере.
<!DOCTYPE html>
<html>
<head>
<title>Змейка</title>
<style>
html,
body {
height: 100%;
margin: 0;
}
/*Задаём глобальные параметры*/
body {
background: black;
display: flex;
align-items: center;
justify-content: center;
}
/*Делаем границу вокруг игрового поля*/
canvas {
border: 1px solid white;
}
</style>
</head>
<body>
<!-- Рисуем игровое поле -->
<canvas width="400" height="400" id="game"></canvas>
<!-- Сам скрипт с игрой -->
<script>
// Поле, на котором всё будет происходить, — тоже как бы переменная
var canvas = document.getElementById('game');
// Классическая змейка — двухмерная, сделаем такую же
var context = canvas.getContext('2d');
// Размер одной клеточки на поле — 16 пикселей
var grid = 16;
// Служебная переменная, которая отвечает за скорость змейки
var count = 0;
// А вот и сама змейка
var snake = {
// Начальные координаты
x: 160,
y: 160,
// Скорость змейки — в каждом новом кадре змейка смещается по оси Х или У. На старте будет двигаться горизонтально, поэтому скорость по игреку равна нулю.
dx: grid,
dy: 0,
// Тащим за собой хвост, который пока пустой
cells: [],
// Стартовая длина змейки — 4 клеточки
maxCells: 4
};
// А это — еда. Представим, что это красные яблоки.
var apple = {
// Начальные координаты яблока
x: 320,
y: 320
};
// Делаем генератор случайных чисел в заданном диапазоне
function getRandomInt(min, max) {
return Math.floor(Math.random() * (max - min)) min;
}
// Игровой цикл — основной процесс, внутри которого будет всё происходить
function loop() {
// Хитрая функция, которая замедляет скорость игры с 60 кадров в секунду до 15 (60/15 = 4)
requestAnimationFrame(loop);
// Игровой код выполнится только один раз из четырёх, в этом и суть замедления кадров, а пока переменная count меньше четырёх, код выполняться не будет
if ( count < 4) {
return;
}
// Обнуляем переменную скорости
count = 0;
// Очищаем игровое поле
context.clearRect(0, 0, canvas.width, canvas.height);
// Двигаем змейку с нужной скоростью
snake.x = snake.dx;
snake.y = snake.dy;
// Если змейка достигла края поля по горизонтали — продолжаем её движение с противоположной строны
if (snake.x < 0) {
snake.x = canvas.width - grid;
}
else if (snake.x >= canvas.width) {
snake.x = 0;
}
// Делаем то же самое для движения по вертикали
if (snake.y < 0) {
snake.y = canvas.height - grid;
}
else if (snake.y >= canvas.height) {
snake.y = 0;
}
// Продолжаем двигаться в выбранном направлении. Голова всегда впереди, поэтому добавляем её координаты в начало массива, который отвечает за всю змейку
snake.cells.unshift({ x: snake.x, y: snake.y });
// Сразу после этого удаляем последний элемент из массива змейки, потому что она движется и постоянно освобождает клетки после себя
if (snake.cells.length > snake.maxCells) {
snake.cells.pop();
}
// Рисуем еду — красное яблоко
context.fillStyle = 'red';
context.fillRect(apple.x, apple.y, grid - 1, grid - 1);
// Одно движение змейки — один новый нарисованный квадратик
context.fillStyle = 'green';
// Обрабатываем каждый элемент змейки
snake.cells.forEach(function (cell, index) {
// Чтобы создать эффект клеточек, делаем зелёные квадратики меньше на один пиксель, чтобы вокруг них образовалась чёрная граница
context.fillRect(cell.x, cell.y, grid - 1, grid - 1);
// Если змейка добралась до яблока...
if (cell.x === apple.x && cell.y === apple.y) {
// увеличиваем длину змейки
snake.maxCells ;
// Рисуем новое яблочко
// Помним, что размер холста у нас 400x400, при этом он разбит на ячейки — 25 в каждую сторону
apple.x = getRandomInt(0, 25) * grid;
apple.y = getRandomInt(0, 25) * grid;
}
// Проверяем, не столкнулась ли змея сама с собой
// Для этого перебираем весь массив и смотрим, есть ли у нас в массиве змейки две клетки с одинаковыми координатами
for (var i = index 1; i < snake.cells.length; i ) {
// Если такие клетки есть — начинаем игру заново
if (cell.x === snake.cells[i].x && cell.y === snake.cells[i].y) {
// Задаём стартовые параметры основным переменным
snake.x = 160;
snake.y = 160;
snake.cells = [];
snake.maxCells = 4;
snake.dx = grid;
snake.dy = 0;
// Ставим яблочко в случайное место
apple.x = getRandomInt(0, 25) * grid;
apple.y = getRandomInt(0, 25) * grid;
}
}
});
}
// Смотрим, какие нажимаются клавиши, и реагируем на них нужным образом
document.addEventListener('keydown', function (e) {
// Дополнительно проверяем такой момент: если змейка движется, например, влево, то ещё одно нажатие влево или вправо ничего не поменяет — змейка продолжит двигаться в ту же сторону, что и раньше. Это сделано для того, чтобы не разворачивать весь массив со змейкой на лету и не усложнять код игры.
// Стрелка влево
// Если нажата стрелка влево, и при этом змейка никуда не движется по горизонтали…
if (e.which === 37 && snake.dx === 0) {
// то даём ей движение по горизонтали, влево, а вертикальное — останавливаем
// Та же самая логика будет и в остальных кнопках
snake.dx = -grid;
snake.dy = 0;
}
// Стрелка вверх
else if (e.which === 38 && snake.dy === 0) {
snake.dy = -grid;
snake.dx = 0;
}
// Стрелка вправо
else if (e.which === 39 && snake.dx === 0) {
snake.dx = grid;
snake.dy = 0;
}
// Стрелка вниз
else if (e.which === 40 && snake.dy === 0) {
snake.dy = grid;
snake.dx = 0;
}
});
// Запускаем игру
requestAnimationFrame(loop);
</script>
</body>
</html>
