Clever Geek Handbook

ヘビ、マウス、ハミルトン

良い一日。コンピューターにヘビを遊ぶように教えましょう。



実際、これは、この問題を解決する方法に関する記事の最初の部分です。メインの戦いの前に、ウォームアップとだけ言いましょう。





すべての始まり



率直に言って、それはすべて、オーストラリアの男が自分自身を「コードブレット」と呼んでいるビデオを見ることから始まりました 。

彼はさまざまなAIアルゴリズムを使用してヘビの単純なゲームを解決しようとしています。

彼は本当に成功しません、そしてそれが理由です... AIコミュニティが提供する現在のアルゴリズムは現在、分類または回帰（予測）の2つの問題のみを解決します。しかし、ヘビはそこにもそこにも収まりません。マウスを食べることは良く、ぶつかることは悪いという考えのために。それは尾で壊れます、そしてそれはそれがフィールド全体を占めるまで絶えず成長していて成長しています。そのため、このようなタスクのために本格的な自己学習型AIを作成するのはクールなアイデアのように思えましたが、最初にウォームアップして、トレーニングなしで問題を正面から解決するアルゴリズムだけを作成することにしました。実際には、このアルゴリズムについて説明します。



P.S. この記事には、すばらしい発見ではなく、他の人から「借りた」アイデアと、何がどこから来たのかについてのストーリーを含む独自の実装が含まれます。



ゲームを書く



プレイする前に、ゲーム自体を書いてみましょう。



すべての計算はサーバー上で行われ、ヘビはブラウザーに表示され、情報はWebSocket（SignalR）を介して交換されます。



何も機能しない退屈なコード
. Store . 



    isLife: boolean,
    isWin: boolean,
    xSize: number,
    ySize: number,
    mouse: Vector2,
    piton: Vector2[]


snake.ts 



import { HubConnection, HubConnectionBuilder } from "@microsoft/signalr";
import { observable } from "mobx";
import { start } from "repl";

export enum Cell {
    None = "None",
    Mouse = "Mouse",
    Snake = "Snake"
}

export interface Vector2 {
    x: number,
    y: number
}

interface StateBoard {
    isLife: boolean,
    isWin: boolean,
    xSize: number,
    ySize: number,
    mouse: Vector2,
    piton: Vector2[]
    hamiltonPath: Vector2[]
}

class Snake {
    @observable
    public state?: StateBoard;

    private connection: HubConnection;

    constructor() {
        this.connection = new HubConnectionBuilder()
            .withUrl("http://localhost:5000/snake")
            .withAutomaticReconnect()
            .build();
        this.start();
    }

    private start = async () => {
        await this.connection.start();
        this.connection.on("newState", (board: string) => {
            var state = JSON.parse(board) as StateBoard;
            if (state.isLife) {
                this.state = state;
            } else {
                this.state!.isLife = false;
                this.state!.isWin = state.isWin;
                if (this.state!.isWin) {
                    this.state = state;
                }
            }
        });
    }
}
export const snake = new Snake();


React , .



App.tsx 



import { snake } from './shores/snake';
import { useObserver } from 'mobx-react-lite';
import cs from 'classnames';

const App = (): JSX.Element => {

  const cellRender = (indexRow: number, indexColumn: number): JSX.Element => {
    const state = snake.state!;
    const isMouse = state.mouse.x == indexColumn && state.mouse.y == indexRow;
    if (isMouse) {
      return <div key={`${indexRow}_${indexColumn}`} className='cell mouse'></div>;
    }
    const indexCellSnake = state.piton.findIndex(p => p.x == indexColumn && p.y == indexRow);
    if (indexCellSnake == -1) {
      return <div key={`${indexRow}_${indexColumn}`} className='cell'></div>;
    }
    const prewIndexCellSnake = indexCellSnake - 1;
    const prewCellPiton = 0 <= prewIndexCellSnake ? state.piton[prewIndexCellSnake] : null;
    const cellPiton = state.piton[indexCellSnake];
    const nextIndexCellSnake = indexCellSnake + 1;
    const nextCellPiton = nextIndexCellSnake < state.piton.length ? state.piton[nextIndexCellSnake] : null;
    let up = false, left = false, down = false, rigth = false;
    if (!!prewCellPiton) {
      if (prewCellPiton.x < cellPiton.x) {
        left = true;
      }
      if (prewCellPiton.y < cellPiton.y) {
        up = true;
      }
      if (cellPiton.x < prewCellPiton.x) {
        rigth = true;
      }
      if (cellPiton.y < prewCellPiton.y) {
        down = true;
      }
    }
    if (!!nextCellPiton) {
      if (cellPiton.x < nextCellPiton.x) {
        rigth = true;
      }
      if (cellPiton.y < nextCellPiton.y) {
        down = true;
      }
      if (nextCellPiton.x < cellPiton.x) {
        left = true;
      }
      if (nextCellPiton.y < cellPiton.y) {
        up = true;
      }
    }
    return <div key={`${indexRow}_${indexColumn}`} className='cell'>
      <table className='shake'>
        <tbody>
          <tr>
            <td width="10%" height="10%" />
            <td height="10%" className={cs({
              'shake-segment': up
            })} />
            <td width="10%" height="10%" />
          </tr>
          <tr>
            <td width="10%" className={cs({
              'shake-segment': left
            })} />
            <td className='shake-segment' />
            <td width="10%" className={cs({
              'shake-segment': rigth
            })} />
          </tr>
          <tr>
            <td width="10%" height="10%" />
            <td height="10%" className={cs({
              'shake-segment': down
            })} />
            <td width="10%" height="10%" />
          </tr>
        </tbody>
      </table>
    </div>;
  }

  const rowRender = (indexRow: number): JSX.Element => {
    const state = snake.state!;
    const cells: JSX.Element[] = [];
    for (let j = 0; j < state.ySize; j++) {
      cells.push(cellRender(indexRow, j));
    }
    return (<>{cells}</>);
  }

  const tableRender = (): JSX.Element => {
    const state = snake.state!;
    const rows: JSX.Element[] = [];
    for (let i = 0; i < state.ySize; i++) {
      rows.push(
        (<div key={i.toString()} className="row">
          {rowRender(i)}
        </div>)
      );
    }
    return (<>{rows}</>);
  }

  return useObserver(() => {
    console.log(snake.state);
    if (!snake.state) {
      return <div />
    }
    let state: string = " ";
    if (snake.state.isLife == false) {
      state = snake.state.isWin ? "" : ""
    }
    return (<>
      <span className="state">{state}</span>
      <div className="table">
        {tableRender()}
      </div>
    </>);
  });
}

export default App;


: 



    public class SnakeSender
    {
        class Vector2
        {
            public int X { get; set; }
            public int Y { get; set; }
            public Vector2(int x, int y)
            {
                this.X = x;
                this.Y = y;
            }
        }

        class Vector2Comparer : IEqualityComparer<Vector2>
        {
            public bool Equals([AllowNull] Vector2 value1, [AllowNull] Vector2 value2)
            {
                return value1.X == value2.X && value1.Y == value2.Y;
            }

            public int GetHashCode([DisallowNull] Vector2 obj)
            {
                return 0;
            }
        }

        private readonly static Vector2Comparer vector2Comparer = new Vector2Comparer();


        [JsonConverter(typeof(StringEnumConverter))]
        enum Cell
        {
            None,
            Mouse,
            Snake
        }

        enum Directions
        {
            Up,
            Left,
            Down,
            Rigth
        }

        class StateBoard
        {
            public bool IsLife { get; set; }
            public bool IsWin { get; set; }
            public int XSize { get; set; }
            public int YSize { get; set; }
            public Vector2 Mouse { get; set; }
            public List<Vector2> Piton { get; set; }
            public List<Vector2> HamiltonPath { get; set; }
        }

        const int xSize = 12, ySize = 12;
      
...
private void CheckDead()
        {
            Vector2 head = this.Piton.Last();
            if (head.X < 0
             || head.Y < 0
             || xSize <= head.X
             || ySize <= head.Y
             || this.Piton.SkipLast(1).Contains(head, vector2Comparer))
            {
                this.IsLife = false;
                this.IsWin = false;
                return;
            }
        }
 private void Render()
        {
            var hubContext = (IHubContext<SnakeHub>)this.ServiceProvider.GetService(typeof(IHubContext<SnakeHub>));
            var piton = this.Piton.ToList();
            piton.Reverse();
            hubContext.Clients?.All.SendAsync("newState", JsonConvert.SerializeObject(new StateBoard()
            {
                IsLife = this.IsLife,
                IsWin = this.IsWin,
                XSize = xSize,
                YSize = ySize,
                Mouse = this.Mouse,
                Piton = piton,
                HamiltonPath = HamiltonPath
            }));
        }
private List<Vector2> GetEmptyCells()
        {
            List<Vector2> emptyCells = new List<Vector2>(xSize * ySize);
            for (int i = 0; i < ySize; i++)
            {
                for (int j = 0; j < xSize; j++)
                {
                    if (!this.Piton.Contains(new Vector2(j, i), vector2Comparer))
                    {
                        emptyCells.Add(new Vector2(j, i));
                    }
                }
            }

            return emptyCells;
        }
}




ゲームの開始時に、1匹の赤いマウスと1つのセルのヘビがいます。



そして今、私たちはどういうわけか遊び始める必要があります。



一般に、ヘビのプレイは非常に簡単です。マトリックスの各セルを1回通過するだけです。そして、問題全体が解決されました-ハッピーエンド。



より正確には、私たちの分野は「連結グラフ」です。それら。ボード上のすべてのセルは頂点です。エッジは各頂点から移動します-これは隣接する頂点への遷移です。

このようなエッジは2〜4つあり、それぞれ極端なセルと中央のセルに使用されます。



1805年8月4日から1865年9月2日までのどこかで、あるハミルトンウィリアムローワンがアイルランドに住んでいて、十二面体に沿って「世界中を旅する」問題を調査しました。この問題では、十二面体の頂点はブリュッセル、アムステルダム、エジンバラ、北京、プラハ、デリー、フランクフルトなどの有名な都市を象徴し、エッジはそれらを結ぶ道路を象徴していました。旅行者は、すべての山頂を1回だけ通過する道を見つけて、「世界中を旅する」必要があります。タスクをより面白くするために、都市の通過順序が事前に確立されました。また、どの都市がすでに接続されているかを思い出しやすくするために、十二面体の各頂点に釘を打ち込み、舗装された小道に釘に巻き付けることができる小さなロープを付けました。しかし、この構造は面倒であることが判明し、ハミルトンはゲームの新しいバージョンを提案し、十二面体を平らなグラフに置き換えました。十二面体のエッジ上に作成されたグラフと同型です。



一般的に、「ハミルトン閉路」のような冗談があります。ハミルトン閉路は、特定のグラフの各頂点を1回だけ通過する閉路（閉路）です。つまり、グラフのすべての頂点を含む単純なサイクルです。また、ハミルトングラフと密接に関連しているのは、ハミルトンパスの概念です。これは、グラフの各頂点を1回だけ通過する単純なパス（ループのないパス）です。ハミルトンパスは、サイクルとは異なり、パスの開始点と終了点が一致しない場合があるという点でサイクルとは異なります。ハミルトン閉路はハミルトン経路です。



視覚的には、これは次のように表すことができます。





私たちの場合、そうです。





ここだけがニュアンスです...ブルドーザーからそのようなサイクルを構築しようとすると、再臨まで待つことができるほど多くのオプションの列挙が得られます。



結論として、「ハミルトン閉路」を見つけるための一般的なアプローチには徹底的な検索が含まれ、これ以上最適なものはないようです。そして、12 x 12のマトリックスでは、144の頂点しかなく、それぞれについて2から4のエッジをチェックする必要があります。一般的に、どこかにnの複雑さがあります！..



しかしそれ以来各頂点がすべての隣接頂点に接続されている行列の問題を解決します。時計回りにパスするだけです。



そうすれば、「ハミルトン閉路」を構築することは難しくありません。 



private void CreateHamiltonPath()
        {
            this.HamiltonPath.Clear();
            this.HamiltonPath.Add(new Vector2(0, 0));
            HamiltonStep(this.HamiltonPath.Last());
        }

        private bool HamiltonStep(Vector2 current)
        {
            if (HamiltonPath.Count == HamiltonPath.Capacity)
            {
                var first = HamiltonPath.First();
                return (first.X == current.X && first.Y == current.Y - 1)
                    || (first.X == current.X && first.Y == current.Y + 1)
                    || (first.X - 1 == current.X && first.Y == current.Y)
                    || (first.X + 1 == current.X && first.Y == current.Y);
            }
            foreach (var direction in new[] { Directions.Down, Directions.Rigth, Directions.Up, Directions.Left })
            {
                Vector2 newElement = null;
                switch (direction)
                {
                    case Directions.Up:
                        newElement = new Vector2(current.X, current.Y - 1);
                        break;
                    case Directions.Left:
                        newElement = new Vector2(current.X - 1, current.Y);
                        break;
                    case Directions.Down:
                        newElement = new Vector2(current.X, current.Y + 1);
                        break;
                    case Directions.Rigth:
                        newElement = new Vector2(current.X + 1, current.Y);
                        break;
                }
                if (0 <= newElement.X && newElement.X < xSize
                    && 0 <= newElement.Y && newElement.Y < ySize
                    && !HamiltonPath.Contains(newElement, vector2Comparer))
                {
                    HamiltonPath.Add(newElement);
                    if (HamiltonStep(newElement))
                    {
                        return true;
                    }
                    HamiltonPath.Remove(newElement);
                }
            }
            return false;
        }


はい、私はこのアイデアを「Code Bullet」から「借りて」、彼はインターネット上の別の人からそれを入手 しました。



要するに、パブロ・ピカソが言ったように：

優れたアーティストはコピーし、優れたアーティストは盗む






そして、私たちは勝利までのサイクルに行くヘビを手に入れます：





一般的に、問題は解決されました！しかし、単細胞のヘビが一点から反対側に這うとき、それはどれほど悲惨に見えるか。それを取るのに障害はありませんが...



そして数学の観点から、（O）n ^ 2の複雑さを取得します。ここで、nはポイントの数です（この場合、n = 144）。



なぜなら 毎回…毎回…。私たちはすべてをループで回る必要があります...



簡単に言えば-私たちは待つのに飽きます...したがって、解決策は良いですが、問題があります-それは多くの時間がかかります...



最適化



ヘビについて私たちは何を知っていますか。マウスを食べると長さが変わります。そして彼女にとって理想的な軌道はハメルトンの道です。そして、2点間の最短距離は直線です。



再帰を呼び出すことから始めましょう： 



private void CalculatePath()
        {
            this.StepsCountAfterCalculatePath = 0;
            int finalIndexPoint = this.HamiltonPath.FindIndex(p => p.X == this.Mouse.X && p.Y == this.Mouse.Y);
            List<Vector2> tempPath = new List<Vector2>();
            List<Vector2> stepPiton = new List<Vector2>(this.Piton);
            Debug.WriteLine($"Piton length: {this.Piton.Count}");
            int index = 0;
            var result = StepTempPath(ref index, GetInvert(stepPiton, this.Mouse), this.Piton.Last(), finalIndexPoint, stepPiton, tempPath);
            if (result.PathIsFound)
            {
                this.TempPath = new Queue<Vector2>(tempPath);
                this.InvertHamiltonPath = result.InvertHamiltonPath;
            }
        }


ただし、再帰部分を個別に分析してみましょう。



主要部分は可能な限りシンプルです。



私たちは頑固に目標に近づいています： 



if (current.X < finalPoint.X)
                {
                    newElement = new Vector2(current.X + 1, current.Y);
                }
                else if (finalPoint.X < current.X)
                {
                    newElement = new Vector2(current.X - 1, current.Y);
                }
                else if (current.Y < finalPoint.Y)
                {
                    newElement = new Vector2(current.X, current.Y + 1);
                }
                else if (finalPoint.Y < current.Y)
                {
                    newElement = new Vector2(current.X, current.Y - 1);
                }


ヘビは斜めに這う方法を知りませんが、今度は最初に垂直に整列し、次に水平にゴールに行きます。次に、新しいイテレーションに移動して確認できます。



最終的な状態チェックは、最初は次のようになります。 



if (current.X == finalPoint.X && current.Y == finalPoint.Y)
            {
                var tempPiton = stepPiton.TakeLast(this.Piton.Count).ToList();
                for (int i = 1; i < this.Piton.Count; i++)
                {
                    var hamiltonPoint = (finalIndexPoint + i < this.HamiltonPath.Count) ? this.HamiltonPath[finalIndexPoint + i] : this.HamiltonPath[finalIndexPoint + i - this.HamiltonPath.Count];
                    if (tempPiton.TakeLast(this.Piton.Count).Contains(hamiltonPoint, vector2Comparer))
                    {
                        return false;
                    }
                    tempPiton.Add(hamiltonPoint);
                }
                return true;
            }


ここで実際に何をしているのか。



仮想パス上にマウスを見つけたとき。さらに、私たちはパスを構築し続けますが、今回はハミルトンの理想的なパスに沿っており、それがヘビの体と交差しない場合は、現在のマウスへのこのパスに沿って安全にできることが確実にわかりますヘビを手放すので「ネズミを食べた」後は、次のネズミがどこにいても、フルサイクルの道を進んで次のネズミを食べることができます。



単細胞であれば、原理的には全く問題ありませんが、長続きしません…長さが目標への直接の道を複数回るとすぐに問題が発生します。サイクルには特定の方向があります。実際にパス自体にコストがかかるため、ヘビは常に時計回りに移動します。



そして、これが問題が発生する場所です。上から次のマウスに来て、ハミルトンをパスのこの特定の場所に上げたとしましょう。ヘビはそれ自体に逆らって動きますが、これは原則として不可能です...この問題を解決するために、逆ハミルトンパスの概念を紹介します。



それら。ヘビは、パスが作成された時計回りだけでなく、このパスに沿って反対方向にも移動できます。パスはこれから変更されませんが、移動の方向は変わりません-はい。



チェックを変更しましょう。 



if (current.X == finalPoint.X && current.Y == finalPoint.Y)
            {
                if (this.Piton.Count == 1)
                {
                    return new ResultAnlaizePath(true);
                }
                foreach (var d in new[] { false, true })
                {
                    var tempPiton = stepPiton.TakeLast(this.Piton.Count).ToList();
                    bool isFound = true;
                    bool invertHamiltonPath = d;
                    for (int j = 1; j < this.Piton.Count; j++)
                    {
                        Vector2 hamiltonPoint;
                        if (invertHamiltonPath)
                        {
                            hamiltonPoint = (finalIndexPoint - j >= 0) ? this.HamiltonPath[finalIndexPoint - j] : this.HamiltonPath[this.HamiltonPath.Count - j];
                        }
                        else
                        {
                            hamiltonPoint = (finalIndexPoint + j < this.HamiltonPath.Count) ? this.HamiltonPath[finalIndexPoint + j] : this.HamiltonPath[finalIndexPoint + j - this.HamiltonPath.Count];
                        }
                        if (tempPiton.TakeLast(this.Piton.Count).Contains(hamiltonPoint, vector2Comparer))
                        {
                            isFound = false;
                            break;
                        }
                        tempPiton.Add(hamiltonPoint);
                    }
                    if (isFound)
                    {
                        return new ResultAnlaizePath(true, invertHamiltonPath);
                    }
                }
                return new ResultAnlaizePath(false);
            }


ちなみに、前述の「Code Bullet」は、このフェイントを耳で考えていませんでした。私は反転について話しているが、彼のアルゴリズムのいくつかによれば、彼は「角を切り」、それは暗闇に覆われた秘密のままだった。しかし、彼の決定には共同体があったことは確かです。そのため、彼の通過は失敗しました。







さて、一般的に、私は他に何を言うことができますか。ヘビの動きに対抗することに加えて、あなたは単にその尻尾に入ることができることは明らかです。この状況を回避するために、別のパスオプションの簡単な検索を記述します。 



if (!stepPiton.TakeLast(this.Piton.Count).Contains(newElement, vector2Comparer))
            {
                tempPath.Add(newElement);
                stepPiton.Add(newElement);
                var retult = StepTempPath(ref index, !invert, newElement, finalIndexPoint, stepPiton, tempPath);
                if (retult.PathIsFound)
                {
                    return retult;
                }
                if (this.HamiltonPath.Count < index)
                {
                    return new ResultAnlaizePath(false);
                }
                tempPath.Remove(newElement);
                stepPiton.Remove(newElement);
            }

            Vector2 nextFinalPoint;
            if (this.InvertHamiltonPath)
            {
                nextFinalPoint = (finalIndexPoint - 1 < 0) ? this.HamiltonPath[this.HamiltonPath.Count - 1] : this.HamiltonPath[finalIndexPoint - 1];
            }
            else
            {
                nextFinalPoint = (finalIndexPoint + 1 == this.HamiltonPath.Count) ? this.HamiltonPath[0] : this.HamiltonPath[finalIndexPoint + 1];
            }
            List<Directions> directions = new List<Directions>(4);
            directions.Add(finalPoint.Y < nextFinalPoint.Y ? Directions.Up : Directions.Down);
            directions.Add(finalPoint.X < nextFinalPoint.X ? Directions.Left : Directions.Rigth);
            directions.Add(finalPoint.Y < nextFinalPoint.Y ? Directions.Down : Directions.Up);
            directions.Add(finalPoint.X < nextFinalPoint.X ? Directions.Rigth : Directions.Left);

            foreach (var direction in directions)
            {
                switch (direction)
                {
                    case Directions.Up:
                        newElement = new Vector2(current.X, current.Y - 1);
                        break;
                    case Directions.Left:
                        newElement = new Vector2(current.X - 1, current.Y);
                        break;
                    case Directions.Down:
                        newElement = new Vector2(current.X, current.Y + 1);
                        break;
                    case Directions.Rigth:
                        newElement = new Vector2(current.X + 1, current.Y);
                        break;
                }
                if (0 <= newElement.X && newElement.X < xSize
                 && 0 <= newElement.Y && newElement.Y < ySize
                 && !stepPiton.TakeLast(this.Piton.Count).Contains(newElement, vector2Comparer))
                {
                    tempPath.Add(newElement);
                    stepPiton.Add(newElement);
                    var retult = StepTempPath(ref index, GetInvert(stepPiton, finalPoint), newElement, finalIndexPoint, stepPiton, tempPath);
                    if (retult.PathIsFound)
                    {
                        return retult;
                    }
                    if (this.HamiltonPath.Count < index)
                    {
                        return new ResultAnlaizePath(false);
                    }
                    tempPath.Remove(newElement);
                    stepPiton.Remove(newElement);
                }
            }
            return new ResultAnlaizePath(false);


一般的に、複雑なことは何もありません。



私たちはこれにのみこだわることができます。



ここでは、上記のマウスの「前進」とは逆方向に検索させようとしています。 



            List<Directions> directions = new List<Directions>(4);
            directions.Add(finalPoint.Y < nextFinalPoint.Y ? Directions.Up : Directions.Down);
            directions.Add(finalPoint.X < nextFinalPoint.X ? Directions.Left : Directions.Rigth);
            directions.Add(finalPoint.Y < nextFinalPoint.Y ? Directions.Down : Directions.Up);
            directions.Add(finalPoint.X < nextFinalPoint.X ? Directions.Rigth : Directions.Left);


それら。まっすぐな道で見つかった障害物を回避するために、「反対側に一歩踏み出してください」。



以下は完全なコードですが、美しくするためにファイルに分割することもできましたが、今では記事が非常に明確になっています。



完全なロジックファイルコード 

using Microsoft.AspNetCore.SignalR;
using Newtonsoft.Json;
using Newtonsoft.Json.Converters;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Linq;
using System.Runtime.ExceptionServices;
using System.Threading.Tasks;
using System.Timers;

namespace SnakeApplication.WebApp.Hubs
{
    public class SnakeHub : Hub
    {
    }

    public class SnakeSender
    {
        class Vector2
        {
            public int X { get; set; }
            public int Y { get; set; }
            public Vector2(int x, int y)
            {
                this.X = x;
                this.Y = y;
            }
        }

        class Vector2Comparer : IEqualityComparer<Vector2>
        {
            public bool Equals([AllowNull] Vector2 value1, [AllowNull] Vector2 value2)
            {
                return value1.X == value2.X && value1.Y == value2.Y;
            }

            public int GetHashCode([DisallowNull] Vector2 obj)
            {
                return 0;
            }
        }

        private readonly static Vector2Comparer vector2Comparer = new Vector2Comparer();


        [JsonConverter(typeof(StringEnumConverter))]
        enum Cell
        {
            None,
            Mouse,
            Snake
        }

        enum Directions
        {
            Up,
            Left,
            Down,
            Rigth
        }

        class StateBoard
        {
            public bool IsLife { get; set; }
            public bool IsWin { get; set; }
            public int XSize { get; set; }
            public int YSize { get; set; }
            public Vector2 Mouse { get; set; }
            public List<Vector2> Piton { get; set; }
            public List<Vector2> HamiltonPath { get; set; }
        }

        const int xSize = 12, ySize = 12;
        private Random Rand { get; }
        private IServiceProvider ServiceProvider { get; }
        private bool IsLife { get; set; }
        private bool IsWin { get; set; }
        Directions Direction { get; set; }
        private Vector2 Mouse { get; set; }
        private Queue<Vector2> Piton { get; set; }
        private bool InvertHamiltonPath { get; set; }
        private List<Vector2> HamiltonPath { get; }
        private Queue<Vector2> TempPath { get; set; }
        private int StepsCountAfterCalculatePath { get; set; }

    public SnakeSender(IServiceProvider serviceProvider)
        {
            this.Rand = new Random();
            this.ServiceProvider = serviceProvider;
            this.TempPath = new Queue<Vector2>();
            this.HamiltonPath = new List<Vector2>(xSize * ySize);
            this.CreateHamiltonPath();
            this.CreateBoard();
        }

        private void CreateHamiltonPath()
        {
            this.HamiltonPath.Clear();
            this.HamiltonPath.Add(new Vector2(0, 0));
            HamiltonStep(this.HamiltonPath.Last());
        }

        private bool HamiltonStep(Vector2 current)
        {
            if (HamiltonPath.Count == HamiltonPath.Capacity)
            {
                var first = HamiltonPath.First();
                return (first.X == current.X && first.Y == current.Y - 1)
                    || (first.X == current.X && first.Y == current.Y + 1)
                    || (first.X - 1 == current.X && first.Y == current.Y)
                    || (first.X + 1 == current.X && first.Y == current.Y);
            }
            foreach (var direction in new[] { Directions.Down, Directions.Rigth, Directions.Up, Directions.Left })
            {
                Vector2 newElement = null;
                switch (direction)
                {
                    case Directions.Up:
                        newElement = new Vector2(current.X, current.Y - 1);
                        break;
                    case Directions.Left:
                        newElement = new Vector2(current.X - 1, current.Y);
                        break;
                    case Directions.Down:
                        newElement = new Vector2(current.X, current.Y + 1);
                        break;
                    case Directions.Rigth:
                        newElement = new Vector2(current.X + 1, current.Y);
                        break;
                }
                if (0 <= newElement.X && newElement.X < xSize
                    && 0 <= newElement.Y && newElement.Y < ySize
                    && !HamiltonPath.Contains(newElement, vector2Comparer))
                {
                    HamiltonPath.Add(newElement);
                    if (HamiltonStep(newElement))
                    {
                        return true;
                    }
                    HamiltonPath.Remove(newElement);
                }
            }
            return false;
        }

        private void CreateBoard()
        {
            Task.Run(async () =>
            {
                this.Piton = new Queue<Vector2>();
                //for (int i = 0; i < 1; i++)
                //{
                //    this.Piton.Enqueue(new Vector2(ySize / 2, xSize / 2 - i));
                //}
                this.Piton.Enqueue(new Vector2(0, 0));
                this.IsLife = true;
                this.Direction = Directions.Up;
                this.CreateMouse();
                while (this.IsLife)
                {
                    this.LifeCycle();
                    await Task.Delay(100);
                }
            });
        }

        private void LifeCycle()
        {
            this.SetDirection();
            this.Step();
            this.CheckDead();
            this.Render();
        }

        private void SetDirection()
        {
            Vector2 head = this.Piton.Last();
            int currentIndnex = this.HamiltonPath.FindIndex(p => p.X == head.X && p.Y == head.Y);
            Vector2 currentElement = this.HamiltonPath[currentIndnex];
            Vector2 nextElement = null;
            if (this.TempPath.Count > 0)
            {
                nextElement = this.TempPath.Dequeue();
            }
            else
            {
                this.StepsCountAfterCalculatePath++;
                if (this.InvertHamiltonPath)
                {
                    nextElement = (currentIndnex - 1 < 0) ? this.HamiltonPath[this.HamiltonPath.Count - 1] : this.HamiltonPath[currentIndnex - 1];
                }
                else
                {
                    nextElement = (currentIndnex + 1 == this.HamiltonPath.Count) ? this.HamiltonPath[0] : this.HamiltonPath[currentIndnex + 1];
                }
            }

            if (currentElement.X == nextElement.X && currentElement.Y < nextElement.Y)
            {
                this.Direction = Directions.Down;
                return;
            }

            if (currentElement.X == nextElement.X && nextElement.Y < currentElement.Y)
            {
                this.Direction = Directions.Up;
                return;
            }

            if (currentElement.X < nextElement.X && currentElement.Y == nextElement.Y)
            {
                this.Direction = Directions.Rigth;
                return;
            }

            if (nextElement.X < currentElement.X && currentElement.Y == nextElement.Y)
            {
                this.Direction = Directions.Left;
                return;
            }

            throw new NotImplementedException();
        }

        private void Step()
        {
            Vector2 head = this.Piton.Last();
            switch (this.Direction)
            {
                case Directions.Up:
                    this.Piton.Enqueue(new Vector2(head.X, head.Y - 1));
                    break;
                case Directions.Left:
                    this.Piton.Enqueue(new Vector2(head.X - 1, head.Y));
                    break;
                case Directions.Down:
                    this.Piton.Enqueue(new Vector2(head.X, head.Y + 1));
                    break;
                case Directions.Rigth:
                    this.Piton.Enqueue(new Vector2(head.X + 1, head.Y));
                    break;
            }
            if (this.Piton.Contains(this.Mouse, vector2Comparer))
            {
                CreateMouse(); 
            }
            else
            {
                this.Piton.Dequeue();
            }
            if (this.Piton.Count < this.StepsCountAfterCalculatePath) {
                this.CalculatePath();
            }
        }

        private void CheckDead()
        {
            Vector2 head = this.Piton.Last();
            if (head.X < 0
             || head.Y < 0
             || xSize <= head.X
             || ySize <= head.Y
             || this.Piton.SkipLast(1).Contains(head, vector2Comparer))
            {
                this.IsLife = false;
                this.IsWin = false;
                return;
            }
        }

        private void Render()
        {
            var hubContext = (IHubContext<SnakeHub>)this.ServiceProvider.GetService(typeof(IHubContext<SnakeHub>));
            var piton = this.Piton.ToList();
            piton.Reverse();
            hubContext.Clients?.All.SendAsync("newState", JsonConvert.SerializeObject(new StateBoard()
            {
                IsLife = this.IsLife,
                IsWin = this.IsWin,
                XSize = xSize,
                YSize = ySize,
                Mouse = this.Mouse,
                Piton = piton,
                HamiltonPath = HamiltonPath
            }));
        }

        private void CreateMouse()
        {
            List<Vector2> emptyCells = GetEmptyCells();
            if (emptyCells.Count > 0)
            {
                this.Mouse = emptyCells[this.Rand.Next(emptyCells.Count)];
                this.CalculatePath();
            }
            else
            {
                this.IsLife = false;
                this.IsWin = true;
            }
        }

        private void CalculatePath()
        {
            this.StepsCountAfterCalculatePath = 0;
            int finalIndexPoint = this.HamiltonPath.FindIndex(p => p.X == this.Mouse.X && p.Y == this.Mouse.Y);
            List<Vector2> tempPath = new List<Vector2>();
            List<Vector2> stepPiton = new List<Vector2>(this.Piton);
            Debug.WriteLine($"Piton length: {this.Piton.Count}");
            int index = 0;
            var result = StepTempPath(ref index, GetInvert(stepPiton, this.Mouse), this.Piton.Last(), finalIndexPoint, stepPiton, tempPath);
            if (result.PathIsFound)
            {
                this.TempPath = new Queue<Vector2>(tempPath);
                this.InvertHamiltonPath = result.InvertHamiltonPath;
            }
        }

        private bool GetInvert(List<Vector2> stepPiton, Vector2 finalPoint)
        {
            if (this.Piton.Count > 1)
            {
                int pitonDirection = stepPiton.Last().Y - stepPiton[stepPiton.Count - 2].Y;
                int mouseDirection = stepPiton.Last().Y - finalPoint.Y;
                return (pitonDirection < 0 && mouseDirection < 0) || (pitonDirection > 0 && mouseDirection > 0);
            }
            return false;
        }

        class ResultAnlaizePath
        {
            public bool PathIsFound { get; set; }
            public bool InvertHamiltonPath { get; set; }
            public ResultAnlaizePath(bool pathIsFound, bool invertHamiltonPath = false)
            {
                PathIsFound = pathIsFound;
                InvertHamiltonPath = invertHamiltonPath;
            }
        }

        private ResultAnlaizePath StepTempPath(ref int index, bool invert, Vector2 current, int finalIndexPoint, List<Vector2> stepPiton, List<Vector2> tempPath)
        {
            index++;
            if (this.HamiltonPath.Count < index)
            {
                return new ResultAnlaizePath(false);
            }
            Debug.WriteLine($"index {index} {tempPath.Count}");
            var finalPoint = this.HamiltonPath[finalIndexPoint];
            if (current.X == finalPoint.X && current.Y == finalPoint.Y)
            {
                if (this.Piton.Count == 1)
                {
                    return new ResultAnlaizePath(true);
                }
                foreach (var d in new[] { false, true })
                {
                    var tempPiton = stepPiton.TakeLast(this.Piton.Count).ToList();
                    bool isFound = true;
                    bool invertHamiltonPath = d;
                    for (int j = 1; j < this.Piton.Count; j++)
                    {
                        Vector2 hamiltonPoint;
                        if (invertHamiltonPath)
                        {
                            hamiltonPoint = (finalIndexPoint - j >= 0) ? this.HamiltonPath[finalIndexPoint - j] : this.HamiltonPath[this.HamiltonPath.Count - j];
                        }
                        else
                        {
                            hamiltonPoint = (finalIndexPoint + j < this.HamiltonPath.Count) ? this.HamiltonPath[finalIndexPoint + j] : this.HamiltonPath[finalIndexPoint + j - this.HamiltonPath.Count];
                        }
                        if (tempPiton.TakeLast(this.Piton.Count).Contains(hamiltonPoint, vector2Comparer))
                        {
                            isFound = false;
                            break;
                        }
                        tempPiton.Add(hamiltonPoint);
                    }
                    if (isFound)
                    {
                        return new ResultAnlaizePath(true, invertHamiltonPath);
                    }
                }
                return new ResultAnlaizePath(false);
            }
            if ((xSize + ySize * 2) <= tempPath.Count)
            {
                return new ResultAnlaizePath(false);
            }
            Vector2 newElement = null;

            if (invert)
            {
                if (current.X < finalPoint.X)
                {
                    newElement = new Vector2(current.X + 1, current.Y);
                }
                else if (finalPoint.X < current.X)
                {
                    newElement = new Vector2(current.X - 1, current.Y);
                }
                else if (current.Y < finalPoint.Y)
                {
                    newElement = new Vector2(current.X, current.Y + 1);
                }
                else if (finalPoint.Y < current.Y)
                {
                    newElement = new Vector2(current.X, current.Y - 1);
                }
            }
            else
            {
                if (current.Y < finalPoint.Y)
                {
                    newElement = new Vector2(current.X, current.Y + 1);
                }
                else if (finalPoint.Y < current.Y)
                {
                    newElement = new Vector2(current.X, current.Y - 1);
                }
                else if (current.X < finalPoint.X)
                {
                    newElement = new Vector2(current.X + 1, current.Y);
                }
                else if (finalPoint.X < current.X)
                {
                    newElement = new Vector2(current.X - 1, current.Y);
                }
            }

            if (!stepPiton.TakeLast(this.Piton.Count).Contains(newElement, vector2Comparer))
            {
                tempPath.Add(newElement);
                stepPiton.Add(newElement);
                var retult = StepTempPath(ref index, !invert, newElement, finalIndexPoint, stepPiton, tempPath);
                if (retult.PathIsFound)
                {
                    return retult;
                }
                if (this.HamiltonPath.Count < index)
                {
                    return new ResultAnlaizePath(false);
                }
                tempPath.Remove(newElement);
                stepPiton.Remove(newElement);
            }

            Vector2 nextFinalPoint;
            if (this.InvertHamiltonPath)
            {
                nextFinalPoint = (finalIndexPoint - 1 < 0) ? this.HamiltonPath[this.HamiltonPath.Count - 1] : this.HamiltonPath[finalIndexPoint - 1];
            }
            else
            {
                nextFinalPoint = (finalIndexPoint + 1 == this.HamiltonPath.Count) ? this.HamiltonPath[0] : this.HamiltonPath[finalIndexPoint + 1];
            }
            List<Directions> directions = new List<Directions>(4);
            directions.Add(finalPoint.Y < nextFinalPoint.Y ? Directions.Up : Directions.Down);
            directions.Add(finalPoint.X < nextFinalPoint.X ? Directions.Left : Directions.Rigth);
            directions.Add(finalPoint.Y < nextFinalPoint.Y ? Directions.Down : Directions.Up);
            directions.Add(finalPoint.X < nextFinalPoint.X ? Directions.Rigth : Directions.Left);

            foreach (var direction in directions)
            {
                switch (direction)
                {
                    case Directions.Up:
                        newElement = new Vector2(current.X, current.Y - 1);
                        break;
                    case Directions.Left:
                        newElement = new Vector2(current.X - 1, current.Y);
                        break;
                    case Directions.Down:
                        newElement = new Vector2(current.X, current.Y + 1);
                        break;
                    case Directions.Rigth:
                        newElement = new Vector2(current.X + 1, current.Y);
                        break;
                }
                if (0 <= newElement.X && newElement.X < xSize
                 && 0 <= newElement.Y && newElement.Y < ySize
                 && !stepPiton.TakeLast(this.Piton.Count).Contains(newElement, vector2Comparer))
                {
                    tempPath.Add(newElement);
                    stepPiton.Add(newElement);
                    var retult = StepTempPath(ref index, GetInvert(stepPiton, finalPoint), newElement, finalIndexPoint, stepPiton, tempPath);
                    if (retult.PathIsFound)
                    {
                        return retult;
                    }
                    if (this.HamiltonPath.Count < index)
                    {
                        return new ResultAnlaizePath(false);
                    }
                    tempPath.Remove(newElement);
                    stepPiton.Remove(newElement);
                }
            }
            return new ResultAnlaizePath(false);
        }

        private List<Vector2> GetEmptyCells()
        {
            List<Vector2> emptyCells = new List<Vector2>(xSize * ySize);
            for (int i = 0; i < ySize; i++)
            {
                for (int j = 0; j < xSize; j++)
                {
                    if (!this.Piton.Contains(new Vector2(j, i), vector2Comparer))
                    {
                        emptyCells.Add(new Vector2(j, i));
                    }
                }
            }

            return emptyCells;
        }
    }
}




実際、それがどのように忍び寄るのか。





ご清聴ありがとうございました。



今では、通常のAIを作成する必要があります。


More articles:


All Articles