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 MoveCostTest01
{
///
/// This is the main type for your game
///
public class Game1 : Microsoft.Xna.Framework.Game
{
GraphicsDeviceManager graphics;
SpriteBatch spriteBatch;
private const int INF = 99;
private const int vMax = 6;
private const int goal = 0;
int n;
int[,] dist;
int[] cost;
bool[] used;
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.dist = new int[,]
{
{ 0, 1, 99, 2, 3, 99},
{ 1, 0, 4,99, 1, 99},
{99, 4, 0,99, 1, 3},
{ 2, 99, 99, 0, 2, 99},
{ 3, 1, 1, 2, 0, 3},
{99, 99, 3,99, 3, 0},
};
n = this.dist.GetLength(0);
this.cost = new int[n];
this.used = new bool[n];
// ダイクストラ法による最短経路探索
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)
{
// 初期化
int x, y, min;
for (x = 0; x < n; x++)
{
this.cost[x] = INF;
this.used[x] = false;
}
this.cost[goal] = 0;
// 最短ノード番号の初期化
int minNo = 0;
while (true)
{
// 未確定ノードの中から最短のノードを探す
min = INF;
for (x = 0; x < n; x++)
{
// 未使用かつコスト最小?
if (!this.used[x] && min > this.cost[x])
{
// 最短ノードを更新する
min = this.cost[x];
// 最短ノード番号を更新する
minNo = x;
}
}
// 未確定ノードが無くなれば終了
if (min == INF)
break;
// 使用済みフラグを立てる
this.used[minNo] = true;
// 接続先ノードの情報を更新する
for (y = 0; y < n; y++)
{
if (this.cost[y] == min)
{
for (x = 0; x < n; x++)
{
if (this.cost[x] > this.dist[x, y] + this.cost[y])
this.cost[x] = this.dist[x, y] + this.cost[y];
}
}
}
}
}
// コンソールに出力する
private void consoleOut()
{
for (int i = 0; i < this.used.Length; i++)
{
Console.WriteLine(
"i = " + i.ToString()
+ "\tused = " + this.used[i].ToString()
+ "\tcost = " + this.cost[i].ToString());
}
}
}
}