using System; using System.Collections.Generic; using System.Linq; using Microsoft.Xna.Framework; using Microsoft.Xna.Framework.Audio; using Microsoft.Xna.Framework.Content; using Microsoft.Xna.Framework.GamerServices; using Microsoft.Xna.Framework.Graphics; using Microsoft.Xna.Framework.Input; using Microsoft.Xna.Framework.Media; using Microsoft.Xna.Framework.Net; using Microsoft.Xna.Framework.Storage; namespace MoveCostTest03 { /// /// This is the main type for your game /// public class Game1 : Microsoft.Xna.Framework.Game { GraphicsDeviceManager graphics; SpriteBatch spriteBatch; // ゴールのノード番号 private const int goal = 0; // コストの上限値 private const int costMax = 1000000000; // エッジクラス class Edge { // 接続先のノード番号 public int To; // コスト public int Cost; // コンストラクタ public Edge(int to, int cost) { this.To = to; this.Cost = cost; } } // ノードクラス class Node { // このノードから伸びるエッジの情報 public Edge[] Edges; // ダイクストラ法のためのデータ public bool Done; // 確定ノードか否か public int Cost; // このノードへの現時点で判明している最小コスト public int No; // このノード番号(最短経路確認用) public int Next; // 次のノード番号(最短経路確認用) public string Name; // ノード名称(最短経路確認用) // コンストラクタ public Node(int no, string name, Edge[] edges) { this.No = no; this.Name = name; this.Edges = edges; this.Done = false; this.Cost = costMax; this.Next = -1; } } // ノードの宣言 private Node[] nodes; public Game1() { graphics = new GraphicsDeviceManager(this); Content.RootDirectory = "Content"; } /// /// Allows the game to perform any initialization it needs to before starting to run. /// This is where it can query for any required services and load any non-graphic /// related content. Calling base.Initialize will enumerate through any components /// and initialize them as well. /// protected override void Initialize() { // TODO: Add your initialization logic here base.Initialize(); } /// /// LoadContent will be called once per game and is the place to load /// all of your content. /// protected override void LoadContent() { // Create a new SpriteBatch, which can be used to draw textures. spriteBatch = new SpriteBatch(GraphicsDevice); // TODO: use this.Content to load your game content here // コストの初期設定 this.nodes = new Node[] { new Node(0, "A", new Edge[] { new Edge(1, 1), new Edge(3, 2), new Edge(4, 3) }), new Node(1, "B", new Edge[] { new Edge(0, 1), new Edge(2, 4), new Edge(4, 1) }), new Node(2, "C",new Edge[] { new Edge(1, 4), new Edge(4, 1), new Edge(5, 3) }), new Node(3, "D",new Edge[] { new Edge(0, 2), new Edge(4, 2) }), new Node(4, "E",new Edge[] { new Edge(0, 3), new Edge(1, 1), new Edge(2, 1), new Edge(3, 2), new Edge(5, 3) }), new Node(5, "F",new Edge[] { new Edge(2, 3), new Edge(4, 3) }), }; // ダイクストラ法による最短経路探索 this.dijkstra(goal); // コンソールに出力する this.consoleOut(); } /// /// UnloadContent will be called once per game and is the place to unload /// all content. /// protected override void UnloadContent() { // TODO: Unload any non ContentManager content here } /// /// Allows the game to run logic such as updating the world, /// checking for collisions, gathering input, and playing audio. /// /// Provides a snapshot of timing values. protected override void Update(GameTime gameTime) { // Allows the game to exit if (GamePad.GetState(PlayerIndex.One).Buttons.Back == ButtonState.Pressed) this.Exit(); // TODO: Add your update logic here base.Update(gameTime); } /// /// This is called when the game should draw itself. /// /// Provides a snapshot of timing values. protected override void Draw(GameTime gameTime) { GraphicsDevice.Clear(Color.CornflowerBlue); // TODO: Add your drawing code here base.Draw(gameTime); } // ダイクストラ法による最短経路探索 private void dijkstra(int goal) { // 初期化 for (int i = 0; i < this.nodes.Length; i++) { this.nodes[i].Done = false; this.nodes[i].Cost = costMax; } // ゴールノードのコストは0 this.nodes[goal].Cost = 0; // ゴールノードの「次のノード番号」を設定(最短経路確認用) this.nodes[goal].Next = goal; // 最小値の宣言 int min; // 確定ノードの宣言 Node doneNode; // 直前ノード番号の宣言(最短経路確認用) int lastNode = goal; // ループ開始 while (true) { // 確定ノードの初期化 doneNode = null; // 最小値の初期化 min = costMax; // 未確定ノードの中から最短のノードを探す for (int i = 0; i < this.nodes.Length; i++) { // 未使用かつコスト最小? if (this.nodes[i].Done == false && min > this.nodes[i].Cost) { // 最小値を更新する min = this.nodes[i].Cost; // 確定ノードを設定する doneNode = this.nodes[i]; } } // 未確定ノードが無くなれば終了 if (doneNode == null) break; // 確定フラグを更新する doneNode.Done = true; // 接続先ノードの情報を更新する for (int i = 0; i < doneNode.Edges.Length; i++) { int to = doneNode.Edges[i].To; int cost = doneNode.Cost + doneNode.Edges[i].Cost; if (this.nodes[to].Cost > cost) { this.nodes[to].Cost = cost; // 次のノード番号を記録する this.nodes[to].Next = doneNode.No; } } } } // コンソールに出力する private void consoleOut() { for (int i = 0; i < this.nodes.Length; i++) { // 最短経路を連結する int last = i; string root = this.nodes[last].Name; while (true) { last = this.nodes[last].Next; root = root + " → " + this.nodes[last].Name; // ゴールであればループ終了 if (last == goal) break; } // コンソールに出力する Console.WriteLine( "i = " + i.ToString() + "\tused = " + this.nodes[i].Done.ToString() + "\tcost = " + this.nodes[i].Cost.ToString() + "\tfrom = " + this.nodes[i].Next.ToString() + "\t最短経路:" + root); } } } }