Tatsächlich ist dies der erste Teil eines Artikels darüber, wie Sie versuchen können, dieses Problem zu lösen. Sagen wir einfach Aufwärmen vor dem Hauptkampf.
Wie alles begann
Um ganz ehrlich zu sein, begann alles mit dem Anschauen eines Videos eines Typen aus Australien, der sich " Code Bullet " nennt.
Er versucht, ein einfaches Schlangenspiel mit verschiedenen KI-Algorithmen zu lösen.
Es gelingt ihm wirklich nicht, und deshalb ... Die aktuellen Algorithmen, die die KI-Community bereitstellt, lösen jetzt nur zwei Probleme, entweder Klassifizierung oder Regression (Vorhersage). Aber die Schlange passt weder dort noch dort hinein. Für die Idee, dass das Essen einer Maus gut und das Anstoßen schlecht ist. Es bricht am Schwanz, der ständig wächst und wächst, bis er das gesamte Feld einnimmt. Es schien also eine coole Idee zu sein, eine vollwertige autodidaktische KI für eine solche Aufgabe zu schreiben, aber zuerst entschied ich mich, mich aufzuwärmen und nur einen Algorithmus zu schreiben, der das Problem ohne Training direkt lösen würde. Tatsächlich wird dieser Algorithmus diskutiert.
P.S. Der Artikel wird keine großartigen Entdeckungen enthalten, sondern "geliehene" Ideen von anderen und deren eigene Umsetzung mit einer Geschichte darüber, was von wo kam.
Ein Spiel schreiben
Lassen Sie uns vor dem Spielen das Spiel selbst schreiben.
Alle Berechnungen werden auf dem Server durchgeführt, die Schlange wird im Browser angezeigt und die Informationen werden über WebSocket (SignalR) ausgetauscht.
Langweiliger Code, ohne den nichts funktioniert
. 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;
}
}
Zu Beginn des Spiels haben wir eine rote Maus und eine einzellige Schlange.
Und jetzt müssen wir irgendwie anfangen zu spielen.
Im Allgemeinen ist das Spielen von Schlangen sehr einfach - Sie müssen nur einmal durch jede Zelle in der Matrix gehen. Und das ganze Problem ist gelöst - Happy End.
Genauer gesagt ist unser Feld ein "Connected Graph". Jene. Jede Zelle auf dem Brett ist ein Scheitelpunkt. Kanten gehen von jedem Scheitelpunkt aus - dies ist ein Übergang zu einem benachbarten Scheitelpunkt.
Es gibt entweder 2 bis 4 solcher Kanten. Für die extreme Zelle bzw. für die zentrale.
Irgendwann vom 4. August 1805 bis 2. September 1865 lebte ein gewisser Hamilton William Rowan in Irland und untersuchte das Problem des "Reisens um die Welt" entlang des Dodekaeders. In diesem Problem symbolisierten die Eckpunkte des Dodekaeders berühmte Städte wie Brüssel, Amsterdam, Edinburgh, Peking, Prag, Delhi, Frankfurt usw., und die Kanten symbolisierten die Straßen, die sie verbanden. Der Reisende muss „um die Welt“ gehen und einen Weg finden, der genau einmal durch alle Gipfel führt. Um die Aufgabe interessanter zu gestalten, wurde im Voraus die Reihenfolge der Durchreise von Städten festgelegt. Um sich leichter daran zu erinnern, welche Städte bereits miteinander verbunden waren, wurde ein Nagel in jeden Scheitelpunkt des Dodekaeders getrieben und der gepflasterte Weg mit einem kleinen Seil markiert, das um den Nagel gewickelt werden konnte. Diese Konstruktion erwies sich jedoch als zu umständlich, und Hamilton schlug eine neue Version des Spiels vor, bei der das Dodekaeder durch ein flaches Diagramm ersetzt wurde.isomorph zu dem Graphen, der an den Rändern des Dodekaeders aufgebaut ist.
Im Allgemeinen gibt es einen Witz wie "Hamilton-Zyklus". Ein Hamilton-Zyklus "ist ein Zyklus (geschlossener Pfad), der genau einmal durch jeden Scheitelpunkt eines bestimmten Graphen verläuft. Dies ist ein einfacher Zyklus, der alle Eckpunkte des Diagramms enthält. Ebenfalls eng mit einem Hamilton-Graphen verwandt ist der Begriff eines Hamilton-Pfades, bei dem es sich um einen einfachen Pfad (Pfad ohne Schleifen) handelt, der genau einmal durch jeden Scheitelpunkt des Graphen verläuft. Ein Hamilton-Pfad unterscheidet sich von einem Zyklus darin, dass der Start- und Endpunkt des Pfads im Gegensatz zu einem Zyklus möglicherweise nicht zusammenfallen. Der Hamilton-Zyklus ist der Hamilton-Pfad.
Optisch kann dies als dargestellt werden
In unserem Fall also.
Nur hier ist eine Nuance ... Wenn wir versuchen, einen solchen Zyklus aus dem Bulldozer zu erstellen, erhalten wir eine Aufzählung von so vielen Optionen, dass wir bis zum zweiten Mal warten können.
Das Fazit ist, dass der allgemeine Ansatz zum Finden des "Hamilton-Zyklus" eine erschöpfende Suche beinhaltet und es nichts Optimaleres zu geben scheint. Und wir haben mit einer 12 x 12-Matrix nur 144 Eckpunkte und für jeden müssen wir 2 bis 4 Kanten überprüfen. Im Allgemeinen gibt es irgendwo die Komplexität von n! ..
Aber seitdem Wir lösen ein Problem für eine Matrix, in der jeder Scheitelpunkt mit allen Nachbarn verbunden ist. Sie können einfach einen Durchgang im Uhrzeigersinn machen.
Dann ist es nicht schwierig, einen "Hamilton-Zyklus" zu konstruieren.
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;
}
Und ja, ich habe diese Idee von " Code Bullet " "ausgeliehen" und er hat sie von einem anderen Mann im Internet bekommen.
Kurz gesagt, wie Pablo Picasso sagte:
Gute Künstler kopieren, große Künstler stehlen
Und so bekommen wir eine Schlange, die einen Zyklus bis zum Sieg durchläuft:
Im Allgemeinen ist das Problem gelöst! Aber wie elend sieht es aus, wenn eine einzellige Schlange von einem Punkt auf die andere Seite kriecht. Obwohl es keine Hindernisse gibt ...
Und aus mathematischer Sicht erhalten wir die Komplexität in (O) n ^ 2. Wobei n die Anzahl der Punkte ist (in unserem Fall n = 144).
weil jedes Mal ... jedes ... Wir müssen alles in einer Schleife
umgehen ... Einfach ausgedrückt - wir werden es leid zu warten ... Obwohl die Lösung gut ist, gibt es ein Problem - es dauert viel Zeit ...
Optimierung
Was wissen wir über die Schlange? Seine Länge ändert sich, wenn die Maus gefressen wird. Und die ideale Flugbahn für sie ist der Hamelton-Pfad. Und der kürzeste Abstand zwischen zwei Punkten ist eine gerade Linie.
Beginnen wir mit dem Aufruf der Rekursion:
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;
}
}
Aber lassen Sie uns den rekursiven Teil separat analysieren.
Der Hauptteil ist so einfach wie möglich.
Wir nähern uns hartnäckig dem Ziel:
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);
}
Die Schlange weiß nicht, wie man diagonal kriecht, aber jetzt richten wir uns zuerst vertikal aus und gehen dann horizontal zum Ziel. Und dann können Sie zu einer neuen Iteration gehen, um zu überprüfen.
Die endgültige Zustandsüberprüfung sieht zunächst ungefähr so aus.
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;
}
Was machen wir eigentlich hier?
Wenn wir unsere Maus auf dem virtuellen Pfad finden. Darüber hinaus bauen wir weiterhin einen Pfad, diesmal jedoch entlang des idealen Pfades von Hamilton. Wenn er sich nicht mit dem Körper unserer Schlange schneidet, wissen wir mit Sicherheit, dass Sie auf diesem Pfad zur aktuellen Maus sicher sind lass die Schlange los, da Nach dem "Essen einer Maus" können wir, wo immer die nächste ist, den Weg eines vollständigen Zyklus gehen und die nächste essen.
Solange wir einzellig sind, kann es im Prinzip überhaupt keine Probleme geben, aber dies dauert nicht lange ... Sobald unsere Länge mehr als ein direkter Weg zum Ziel ist, entsteht ein Problem. Der Zyklus hat eine bestimmte Richtung, d.h. Die Schlange bewegt sich immer im Uhrzeigersinn, da wir den Weg selbst kosten.
Und hier tritt das Problem auf. Nehmen wir an, wir kommen von oben zur nächsten Maus und lassen Hamilton an dieser bestimmten Stelle auf dem Weg nach oben gehen. Die Schlange wird sich gegen sich selbst bewegen, was im Prinzip unmöglich ist ... Um dieses Problem zu lösen, werden wir das Konzept eines umgekehrten Hamilton-Pfades einführen.
Jene. Die Schlange kann sich nicht nur im Uhrzeigersinn bewegen, entlang dem der Pfad gebaut wurde, sondern auch in die entgegengesetzte Richtung entlang dieses Pfades. Daraus ändert sich nicht der Weg, sondern die Bewegungsrichtung - ja.
Lassen Sie uns den Scheck ändern.
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);
}
Übrigens hat der oben erwähnte "Code Bullet" nicht mit den Ohren an diese Finte gedacht. Ich spreche von Invertieren, aber er "schneidet Ecken ab", gemäß einigen seiner Algorithmen, die ein Geheimnis blieben, das in der Dunkelheit verborgen war. Aber ich kann mit Sicherheit sagen, dass seine Entscheidung einen gemeinsamen Punkt hatte, aufgrund dessen seine Passage fehlschlug.
Nun, im Allgemeinen, was kann ich noch sagen. Es ist klar, dass Sie nicht nur der Bewegung der Schlange entgegenwirken, sondern auch einfach in ihren Schwanz gelangen können. Um diese Situation zu umgehen, schreiben wir eine einfache Suche nach einer anderen Pfadoption.
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);
Im Allgemeinen nichts kompliziertes.
Wir können nur darauf eingehen.
Hier versuche ich die Suche in die entgegengesetzte Richtung zur "Vorwärtsbewegung" zur oben beschriebenen Maus zu lassen.
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);
Jene. "Machen Sie einen Schritt auf die andere Seite", um das Hindernis zu umgehen, das auf dem geraden Weg gefunden wurde.
Unten ist der vollständige Code, aber er hätte in Dateien aufgeteilt werden können, um ihn schön zu machen, aber jetzt ist er für den Artikel so klarer.
Vollständiger Code der Logikdatei
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;
}
}
}
Eigentlich, wie alles kriecht.
Vielen Dank für Ihre Aufmerksamkeit.
Jetzt bleibt es, eine normale KI dafür zu schreiben.