En fait, c'est la première partie d'un article sur la façon dont vous pouvez essayer de résoudre ce problème. Disons juste l'échauffement, avant le combat principal.
Comment tout a commencé
Pour être tout à fait franc, tout a commencé en regardant une vidéo d'un mec australien se faisant appeler " Code Bullet ".
Il essaie de résoudre un simple jeu de serpent en utilisant divers algorithmes d'IA.
Il n'y parvient vraiment pas, et c'est pourquoi ... Les algorithmes actuels que propose la communauté IA ne résolvent plus que deux problèmes, soit la classification, soit la régression (prédiction). Mais le serpent ne rentre ni là ni là-bas. Pour l'idée que manger une souris est bon et se cogner est mauvais. Il se brise sur la queue, qui ne cesse de croître et de grandir jusqu'à ce qu'elle occupe tout le champ. Cela me semblait donc être une bonne idée d'écrire une IA autodidacte à part entière pour une telle tâche, mais j'ai d'abord décidé de m'échauffer et d'écrire juste un algorithme qui résoudrait le problème de front, sans formation. En fait, cet algorithme sera discuté.
P.S. L'article ne contiendra pas de grandes découvertes, plutôt des idées «empruntées» à d'autres et leur propre mise en œuvre avec une histoire sur ce qui est venu et d'où.
Ecrire un jeu
Avant de jouer, écrivons le jeu lui-même.
Tous les calculs seront effectués sur le serveur, le serpent sera affiché dans le navigateur et les informations seront échangées via WebSocket (SignalR).
Code ennuyeux sans lequel rien ne fonctionne
. 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;
}
}
Au début du jeu, nous avons une souris rouge et un serpent unicellulaire.
Et maintenant, nous devons en quelque sorte commencer à jouer.
En général, jouer au serpent est très simple - il vous suffit de parcourir une fois chaque cellule de la matrice. Et tout le problème est résolu - Happy End.
Pour être plus précis, notre champ est un "graphe connecté". Celles. chaque cellule du plateau est un sommet. Les arêtes partent de chaque sommet - il s'agit d'une transition vers un sommet adjacent.
Il y a soit 2 à 4 de ces arêtes, respectivement pour la cellule extrême et pour la cellule centrale.
Quelque part du 4 août 1805 au 2 septembre 1865, un certain Hamilton William Rowan a vécu en Irlande, a enquêté sur le problème du «voyage autour du monde» le long du dodécaèdre. Dans ce problème, les sommets du dodécaèdre symbolisaient des villes célèbres telles que Bruxelles, Amsterdam, Édimbourg, Pékin, Prague, Delhi, Francfort, etc., et les bords symbolisaient les routes les reliant. Le voyageur doit faire le «tour du monde», trouver un chemin qui traverse tous les sommets une seule fois. Pour rendre la tâche plus intéressante, l'ordre de passage des villes a été établi à l'avance. Et pour se rappeler plus facilement quelles villes étaient déjà connectées, un clou a été enfoncé dans chaque sommet du dodécaèdre et le chemin pavé a été marqué avec une petite corde qui pouvait être enroulée autour du clou. Cependant, cette construction s'est avérée trop lourde et Hamilton a proposé une nouvelle version du jeu, remplaçant le dodécaèdre par un graphique plat,isomorphe au graphe construit sur les bords du dodécaèdre.
En général, il y a une blague comme "cycle hamiltonien". Un cycle hamiltonien "est un cycle (chemin fermé) qui traverse chaque sommet d'un graphe donné exactement une fois; c'est-à-dire un cycle simple qui inclut tous les sommets du graphe. Également étroitement liée à un graphe hamiltonien est la notion de chemin hamiltonien, qui est un chemin simple (chemin sans boucles) passant par chaque sommet du graphe exactement une fois. Un chemin hamiltonien diffère d'un cycle en ce que les points de départ et d'arrivée du chemin peuvent ne pas coïncider, contrairement à un cycle. Le cycle hamiltonien est le chemin hamiltonien.
Visuellement, cela peut être représenté comme
Dans notre cas, oui.
Seulement voici une nuance ... Si nous essayons de construire un tel cycle à partir du bulldozer, nous obtiendrons une énumération de tant d'options qu'il sera possible d'attendre la seconde venue.
L'essentiel est que l'approche générale pour trouver le «cycle hamiltonien» implique une recherche exhaustive et il ne semble y avoir rien de plus optimal. Et nous avons, avec une matrice 12 par 12, seulement 144 sommets et pour chacun, nous devons vérifier de 2 à 4 arêtes. En général, il y a quelque part la complexité de n! ..
Mais depuis nous résolvons un problème pour une matrice dans laquelle chaque sommet est connecté à tous les voisins, vous pouvez simplement faire un passage dans le sens des aiguilles d'une montre.
Ensuite, il n'est pas difficile de construire un «cycle hamiltonien».
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;
}
Et oui, j'ai "emprunté" cette idée à " Code Bullet ", et il l'a obtenue d'un autre gars sur Internet.
Bref, comme le disait Pablo Picasso:
Les bons artistes copient les grands artistes volent
Et donc, nous obtenons un serpent qui va pour un cycle jusqu'à la victoire:
En général, le problème est résolu! Mais comme ça a l'air misérable quand un serpent unicellulaire rampe d'un point à l'autre. Bien qu'il n'y ait pas d'obstacles pour le prendre ...
Et du point de vue des mathématiques, on obtient la complexité en (O) n ^ 2. Où n est le nombre de points (dans notre cas n = 144).
Parce que à chaque fois… tous les…. Nous devons tout faire le tour en boucle ...
En termes simples - nous en aurons assez d'attendre ... Donc, même si la solution est bonne, il y a un problème - cela prend beaucoup de temps ...
Optimisation
Que savons-nous du serpent. Sa longueur change lorsque la souris est mangée. Et la trajectoire idéale pour elle est le chemin Hamelton. Et la distance la plus courte entre deux points est une ligne droite.
Commençons par appeler la récursivité:
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;
}
}
Mais analysons la partie récursive séparément.
La partie principale est aussi simple que possible.
Nous approchons obstinément de l'objectif:
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);
}
Le serpent ne sait pas ramper en diagonale, mais maintenant nous nous alignons d'abord verticalement, puis nous allons au but horizontalement. Et puis vous pouvez passer à une nouvelle itération pour vérifier.
La vérification de l'état final ressemble à ceci pour commencer.
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;
}
Que faisons-nous réellement ici.
Lorsque nous trouvons notre souris sur le chemin virtuel. De plus, nous continuons à construire un chemin, mais cette fois sur le chemin idéal de Hamilton, et s'il ne croise pas le corps de notre serpent, nous savons avec certitude que le long de ce chemin vers la souris actuelle, vous pouvez en toute sécurité laisse le serpent partir, puisque après avoir "mangé une souris", où que se trouve la suivante, nous pouvons suivre le chemin d'un cycle complet et manger le suivant.
Tant que nous sommes unicellulaires, il ne peut y avoir aucun problème, en principe, mais cela ne dure pas longtemps ... Dès que notre longueur devient plus qu'un chemin direct vers le but, cela crée un problème. Le cycle a une certaine direction, c'est-à-dire le serpent se déplace toujours dans le sens des aiguilles d'une montre, car nous coûtons en fait le chemin lui-même.
Et c'est là que le problème se pose. Disons que nous arrivons à la souris suivante du haut et laissons Hamilton monter à cet endroit particulier sur le chemin. Le serpent se déplacera contre lui-même, ce qui est en principe impossible ... Pour résoudre ce problème, nous introduirons le concept d'un chemin Hamilton inversé.
Celles. le serpent peut se déplacer non seulement dans le sens des aiguilles d'une montre le long duquel le chemin a été construit, mais également dans le sens opposé le long de ce chemin. Le chemin ne changera pas à partir de cela, mais la direction du mouvement - oui.
Changeons le chèque.
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);
}
Et au fait, le "Code Bullet" susmentionné n'a pas pensé à cette feinte avec ses oreilles. Je parle d'inversion, mais il a "coupé les coins", selon certains de ses algorithmes, qui restaient un secret couvert de ténèbres. Mais je peux dire avec certitude qu'il y avait un joint dans sa décision, à cause de laquelle son passage a échoué.
Eh bien, en général, que puis-je dire d'autre. Il est clair qu'en plus de s'opposer au mouvement du serpent, on peut simplement se mettre dans sa queue. Pour contourner cette situation, nous allons écrire une simple recherche d'une autre option de chemin.
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);
En général, rien de compliqué.
Nous ne pouvons que nous attarder là-dessus.
Ici, je suis en train de laisser la recherche dans la direction opposée au "mouvement vers l'avant" à la souris décrit ci-dessus.
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);
Celles. «Faites un pas de l'autre côté» pour contourner l'obstacle qui a été trouvé sur le chemin rectiligne.
Vous trouverez ci-dessous le code complet, mais il aurait pu être divisé en fichiers pour le rendre magnifiquement, mais maintenant c'est tellement plus clair pour l'article.
Code de fichier logique complet
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;
}
}
}
En fait, comment tout cela rampe.
Merci à tous pour votre attention.
Il reste maintenant à écrire une IA normale pour cela.