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);
}
}
}
}