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