Sebenarnya, ini adalah bagian pertama dari artikel tentang bagaimana Anda dapat mencoba menyelesaikan masalah ini. Anggap saja pemanasan, sebelum pertarungan utama.
Bagaimana semuanya dimulai
Sejujurnya, semuanya dimulai dengan menonton video seorang pria dari Australia yang menyebut dirinya " Code Bullet ".
Dia mencoba memecahkan permainan ular sederhana menggunakan berbagai algoritma AI.
Dia benar-benar tidak berhasil, dan itulah mengapa ... Algoritme saat ini yang disediakan komunitas AI sekarang hanya menyelesaikan dua masalah, baik Klasifikasi atau Regresi (prediksi). Tapi ular itu tidak muat di sana atau di sana. Untuk gagasan bahwa memakan tikus itu baik dan menabrak itu buruk. Itu patah di bagian ekor, yang terus tumbuh dan berkembang sampai menempati seluruh bidang. Jadi sepertinya ide yang keren untuk menulis AI belajar mandiri yang lengkap untuk tugas semacam itu, tetapi pertama-tama saya memutuskan untuk melakukan pemanasan dan menulis hanya algoritme yang akan menyelesaikan masalah secara langsung, tanpa pelatihan. Sebenarnya algoritma ini akan dibahas.
P.S. Artikel tersebut tidak akan berisi penemuan-penemuan besar, melainkan "meminjam" ide-ide dari orang lain dan implementasinya sendiri dengan cerita tentang apa yang datang dan dari mana.
Menulis game
Sebelum bermain, mari kita tulis game itu sendiri.
Semua perhitungan akan dilakukan di server, ular akan ditampilkan di browser, dan info akan dipertukarkan melalui WebSocket (SignalR).
Kode membosankan yang tanpanya tidak ada yang berhasil
. 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;
}
}
Di awal permainan, kita memiliki seekor tikus merah dan seekor ular bersel satu.
Dan sekarang kami harus mulai bermain.
Secara umum, bermain snake sangat sederhana - Anda hanya perlu melewati setiap sel di matriks satu kali. Dan seluruh masalah terpecahkan - Happy End.
Untuk lebih tepatnya, bidang kami adalah "Grafik Terhubung". Itu. setiap sel di papan tulis adalah puncak. Tepi pergi dari setiap simpul - ini adalah transisi ke simpul yang berdekatan.
Ada 2 sampai 4 sisi seperti itu. Untuk sel ekstrim dan sel tengah, masing-masing.
Suatu tempat pada tanggal 4 Agustus 1805 - 2 September 1865, seorang Hamilton William Rowan tinggal di Irlandia, menyelidiki masalah "berkeliling dunia" di sepanjang dodecahedron. Dalam soal ini, simpul-simpul dodecahedron melambangkan kota-kota terkenal seperti Brussel, Amsterdam, Edinburgh, Beijing, Praha, Delhi, Frankfurt, dll., Dan ujung-ujungnya melambangkan jalan yang menghubungkan mereka. Pelancong harus pergi "keliling dunia", menemukan jalan setapak yang melewati semua puncak tepat sekali. Untuk membuat tugas lebih menarik, urutan perjalanan kota ditetapkan sebelumnya. Dan agar lebih mudah mengingat kota mana yang sudah terhubung, sebuah paku ditancapkan ke setiap simpul dodecahedron, dan jalan beraspal itu ditandai dengan tali kecil yang bisa dililitkan di sekeliling paku. Namun, konstruksi ini ternyata terlalu rumit, dan Hamilton mengusulkan versi baru permainan, menggantikan dodecahedron dengan grafik datar,isomorfik ke grafik yang dibangun di tepi dodecahedron.
Secara umum, ada lelucon seperti "siklus Hamiltonian". Siklus Hamiltonian "adalah siklus (jalur tertutup) yang melewati setiap simpul dari graf tertentu tepat satu kali; yaitu, siklus sederhana yang mencakup semua simpul pada grafik. Yang juga terkait erat dengan graf Hamiltonian adalah pengertian lintasan Hamiltonian, yang merupakan lintasan sederhana (lintasan tanpa loop) yang melewati setiap simpul graf tepat satu kali. Jalur Hamiltonian berbeda dari sebuah siklus dimana titik awal dan akhir jalur mungkin tidak bertepatan, tidak seperti sebuah siklus. Siklus Hamiltonian adalah jalur Hamiltonian.
Secara visual, ini dapat direpresentasikan sebagai
Dalam kasus kami, jadi.
Hanya di sini nuansanya ... Jika kita mencoba membangun siklus seperti itu dari buldoser, kita akan mendapatkan penghitungan dari begitu banyak opsi sehingga dimungkinkan untuk menunggu sampai kedatangan yang kedua.
Intinya adalah bahwa pendekatan umum untuk menemukan "siklus Hamiltonian" melibatkan pencarian menyeluruh dan tampaknya tidak ada yang lebih optimal. Dan kami memiliki, dengan matriks 12 kali 12, hanya 144 simpul dan untuk masing-masing kita perlu memeriksa dari 2 hingga 4 sisi. Secara umum, ada suatu tempat kompleksitas n! ..
Tapi sejak kami memecahkan masalah untuk matriks di mana setiap simpul terhubung ke semua tetangga, Anda bisa membuat lintasan searah jarum jam.
Maka tidak sulit untuk membangun "siklus Hamiltonian".
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;
}
Dan ya, saya "meminjam" ide ini dari " Code Bullet ", dan dia mendapatkannya dari orang lain di Internet.
Singkatnya, seperti yang dikatakan Pablo Picasso:
Seniman yang baik meniru, seniman hebat mencuri
Jadi, kita mendapatkan seekor ular yang terus berputar sampai menang:
Secara umum, masalahnya sudah terpecahkan! Tapi betapa menyedihkannya ketika seekor ular bersel tunggal merangkak dari satu titik ke sisi lain. Meskipun tidak ada kendala untuk menerimanya ...
Dan dari sudut pandang matematika, kita mendapatkan kompleksitas dalam (O) n ^ 2. Di mana n adalah jumlah titik (dalam kasus kami n = 144).
Karena setiap waktu… setiap…. Kita perlu membahas semuanya dalam satu lingkaran ...
Sederhananya - kita akan bosan menunggu ... Jadi, meskipun solusinya bagus, ada masalah - itu membutuhkan banyak waktu ...
Optimasi
Apa yang kita ketahui tentang ular itu. Panjangnya berubah saat tikus dimakan. Dan jalur yang ideal untuknya adalah jalur Hamelton. Dan jarak terpendek antara dua titik adalah garis lurus.
Mari kita mulai dengan memanggil rekursi:
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;
}
}
Tapi mari kita analisis bagian rekursif secara terpisah.
Bagian utamanya sesederhana mungkin.
Kami dengan keras kepala mendekati tujuan:
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);
}
Ular tidak tahu cara merangkak secara diagonal, tetapi sekarang kita pertama-tama menyelaraskan secara vertikal, dan kemudian kita pergi ke tujuan secara horizontal. Dan kemudian Anda bisa pergi ke iterasi baru untuk diperiksa.
Pemeriksaan status terakhir terlihat seperti ini untuk memulai.
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;
}
Apa yang sebenarnya kami lakukan di sini.
Saat kami menemukan mouse kami di jalur virtual. Selain itu, kami terus membangun jalur, tetapi kali ini di sepanjang jalur ideal Hamilton, dan jika tidak bersinggungan dengan tubuh ular kami, maka kami tahu pasti bahwa di sepanjang jalur ini ke tikus saat ini, Anda dapat dengan aman. biarkan ular itu pergi, sejak itu setelah "memakan seekor tikus", di mana pun tikus berikutnya berada, kita dapat mengikuti jalur siklus penuh dan makan yang berikutnya.
Selama kita bersel tunggal, pada prinsipnya tidak akan ada masalah sama sekali, tetapi ini tidak berlangsung lama ... Begitu panjang kita menjadi lebih dari satu jalur langsung ke tujuan, itu menciptakan masalah. Siklus memiliki arah tertentu, yaitu ular selalu bergerak searah jarum jam, karena kita sebenarnya mengorbankan jalur itu sendiri.
Dan di sinilah masalahnya muncul. Katakanlah kita menuju mouse berikutnya dari atas, dan membiarkan Hamilton naik ke tempat khusus ini di jalan setapak. Ular akan bergerak melawan dirinya sendiri, yang pada prinsipnya tidak mungkin ... Untuk mengatasi masalah ini, kami akan memperkenalkan konsep jalur Hamilton terbalik.
Itu. ular dapat bergerak tidak hanya searah jarum jam di sepanjang jalur yang dibangun, tetapi juga ke arah yang berlawanan di sepanjang jalur ini. Jalannya tidak akan berubah dari ini, tetapi arah gerakan - ya.
Mari kita ubah ceknya.
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);
}
Dan omong-omong, "Code Bullet" yang disebutkan di atas tidak memikirkan tipuan ini dengan telinganya. Saya berbicara tentang pembalik, tetapi dia "mengambil jalan pintas", menurut beberapa algoritmanya, yang tetap menjadi rahasia yang tertutup dalam kegelapan. Tetapi saya dapat mengatakan dengan pasti bahwa ada kesepakatan dalam keputusannya, karena itu perjalanannya gagal.
Nah, secara umum, apa lagi yang bisa saya katakan. Jelas bahwa selain melawan pergerakan ular, Anda bisa langsung masuk ke ekornya. Untuk mengatasi situasi ini, kami akan menulis pencarian sederhana untuk opsi jalur lain.
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);
Secara umum, tidak ada yang rumit.
Kami hanya bisa memikirkan ini.
Di sini saya mencoba membiarkan pencarian berlawanan arah dengan "gerakan maju" ke mouse yang dijelaskan di atas.
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);
Itu. "Ambil langkah ke sisi lain" untuk menghindari rintangan yang ditemukan di jalan lurus.
Di bawah ini adalah kode lengkapnya, tetapi bisa saja dipecah menjadi beberapa file agar menjadi indah, tetapi sekarang lebih jelas untuk artikelnya.
Kode file logika lengkap
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;
}
}
}
Sebenarnya, bagaimana semua itu merinding.
Terima kasih atas perhatiannya.
Sekarang tinggal menulis AI normal untuk itu.