Actually, this is the first part of an article on how you can try to solve this problem. Let's just say warm-up, before the main fight.
How it all started
To be completely frank, it all started with watching a video of a dude from Australia calling himself " Code Bullet "
He is trying to solve a simple game of snake using various AI algorithms.
He really does not succeed, and that's why ... The current algorithms that the AI community provides now solve only two problems, either Classification or Regression (prediction). But the snake does not fit in either there or there. For the idea that eating a mouse is good and bumping is bad. It breaks on the tail, which is constantly growing and growing until it occupies the entire field. So it seemed like a cool idea to write a full-fledged self-teaching AI for such a task, but first I decided to warm up and write just an algorithm that would solve the problem head-on, without training. Actually, this algorithm will be discussed.
P.S. The article will not contain great discoveries, rather "borrowed" ideas from others and their own implementation with a story about what came from and where.
Writing a game
Before playing, let's write the game itself.
All calculations will be made on the server, the snake will be displayed in the browser, and the info will be exchanged via WebSocket (SignalR).
Boring code without which nothing works
. Store .
snake.ts
React , .
App.tsx
:
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;
}
}
At the beginning of the game, we have one red mouse and a one-celled snake.
And now we somehow need to start playing.
In general, playing snake is very simple - you just need to go through each cell in the matrix once. And the whole problem is solved - Happy End.
To be more precise, our field is a "Connected Graph". Those. every cell on the board is a vertex. Edges go from each vertex - this is a transition to an adjacent vertex.
There are either 2 to 4 of such edges. For the extreme cell and for the central one, respectively.
Somewhere August 4, 1805 - September 2, 1865, a certain Hamilton William Rowan lived in Ireland, investigated the problem of "traveling around the world" along the dodecahedron. In this problem, the vertices of the dodecahedron symbolized famous cities such as Brussels, Amsterdam, Edinburgh, Beijing, Prague, Delhi, Frankfurt, etc., and the edges symbolized the roads connecting them. The traveler must go “around the world”, finding a path that passes through all the peaks exactly once. To make the task more interesting, the order of passage of cities was established in advance. And to make it easier to remember which cities were already connected, a nail was driven into each top of the dodecahedron, and the paved path was marked with a small rope that could be wrapped around the nail. However, this construction turned out to be too cumbersome, and Hamilton proposed a new version of the game, replacing the dodecahedron with a flat graph,isomorphic to the graph constructed on the edges of the dodecahedron.
In general, there is such a joke as "Hamiltonian cycle". A Hamiltonian cycle "is a cycle (closed path) that passes through each vertex of a given graph exactly once; that is, a simple cycle that includes all the vertices of the graph. Also closely related to a Hamiltonian graph is the notion of a Hamiltonian path, which is a simple path (path without loops) passing through each vertex of the graph exactly once. A Hamiltonian path differs from a cycle in that the start and end points of a path may not coincide, unlike a cycle. The Hamiltonian cycle is the Hamiltonian path.
Visually, this can be represented as
In our case, so.
Only here is a nuance ... If we try to build such a cycle from the bulldozer, we will get an enumeration of so many options that it will be possible to wait until the second coming.
The bottom line is that the general approach to finding the "Hamiltonian cycle" involves exhaustive search and there seems to be nothing more optimal. And we have, with a 12 by 12 matrix, only 144 vertices, and for each we need to check from 2 to 4 edges. In general, there is somewhere the complexity of n! ..
But since we solve a problem for a matrix in which each vertex is connected to all neighbors, you can just make a clockwise pass.
Then it is not difficult to construct a "Hamiltonian cycle".
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;
}
And yes, I "borrowed" this idea from " Code Bullet ", and he got it from another guy on the Internet.
In short, as Pablo Picasso said:
Good artists copy, great artists steal
And so, we get a snake that goes for a cycle until victory:
In general, the problem is solved! But how wretched it looks when a single-celled snake crawls from a point to the other side. Although there are no obstacles to take it ...
And from the point of view of mathematics, we get the complexity in (O) n ^ 2. Where n is the number of points (in our case n = 144).
Because every time… every…. We need to go around everything in a loop ...
Simply put - we will get tired of waiting ... So, although the solution is good, there is a problem - it takes a lot of time ...
Optimization
What do we know about the snake. Its length changes when the mouse is eaten. And the ideal trajectory for her is the Hameltonian path. And the shortest distance between two points is a straight line.
Let's start by calling recursion:
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;
}
}
But let's analyze the recursive part separately.
The main part is as simple as possible.
We stubbornly approach the goal:
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);
}
The snake does not know how to crawl diagonally, but now we first align vertically, and then we go to the goal horizontally. And then you can go to a new iteration to check.
The final state check looks something like this to start with.
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;
}
What are we actually doing here.
When we find our mouse on the virtual path. In addition, we continue to build a path, but already along the ideal path of Hamilton, and if it does not intersect with the body of our snake, then we know for sure that along this path to the current mouse, you can safely let the snake go, since after "eating a mouse", wherever the next one is, we can go along the path of a full cycle and eat the next one.
As long as we are single-celled, there can be no problems at all, in principle, but this does not last long ... As soon as our length becomes more than one direct path to the goal, it creates a problem. The cycle has a certain direction, i.e. the snake always moves clockwise, as we actually cost the path itself.
And this is where the problem arises. Let's say we come to the next mouse from the top, and let Hamilton go up at this particular place on the path. The snake will move against itself, which is impossible in principle ... To solve this problem, we will introduce the concept of an inverted Hamilton path.
Those. the snake can move not only clockwise along which the path was built, but also in the opposite direction along this path. The path will not change from this, but the direction of movement - yes.
Let's change the check.
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);
}
And by the way, the aforementioned "Code Bullet" did not think of this feint with his ears. I'm talking about inverting, but he "cut corners", according to some of his algorithm, which remained a secret covered in darkness. But I can say for sure that there was a joint in his decision, because of which his passage failed.
Well, in general, what else can I say. It is clear that in addition to opposing the movement of the snake, you can corny get into its tail. To work around this situation, we will write a simple search for another path option.
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);
In general, nothing complicated.
We can only dwell on this.
Here I am trying to let the search in the opposite direction to the "forward movement" to the mouse described above.
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);
Those. "Take a step to the other side" in order to get around the obstacle that was found on the straight path.
Below is the complete code, but it could have been split into files to make it beautifully, but now it is so clearer for the article.
Complete logic file code
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;
}
}
}
Actually, how it all creeps.
Thank you all for your attention.
Now it remains to write a normal AI for it.