austisticscreeching.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
using System.Text;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Audio;
using System.IO;
namespace Pathfinder
{
    class Dijkstra
    {
        public Dijkstra()
        {
            closed = new bool[40, 40];
            cost = new double[40, 40];
        }

        //find which grid locations are closed
        //Find a cost value for each node
        //A link for each node - find the best way to get there
        //Which nodes form the final path


        public bool[,] closed; //whether or not location is closed
        public double[,] cost; //cost value for each location
        public Coord2[,] link; //link for each location = coords of a neighbouring location
        public bool[,] inPath; //whether or not a location is in the final path

        public void Build(Level level, AiBotBase bot, Player plr)
        {
            //Set all costs to 1,000,000
            //Set all nodes to open
            for (int i = 0; i < 40; i++)
            {
                for (int n = 0; n < 40; n++)
                {
                    cost[i, n] = 1000000.0;
                    closed[i, n] = false;
                    inPath[i, n] = false;
                    link[i, n] = new Coord2(-1, -1);

                }
            }

            //bot's node = open
            closed[bot.GridPosition.X, bot.GridPosition.Y] = false;

            //bot's node cost = 0
            cost[bot.GridPosition.X, bot.GridPosition.Y] = 0;

            //Starts at bots' location
            //Bot assigns next 4 nodes to 1 - now the lowest value, closes own node
            //Moves to one of the lowest nodes and continues

            //Set initial surrounding node values
            cost[bot.GridPosition.X + 1, bot.GridPosition.Y] = 1;
            cost[bot.GridPosition.X - 1, bot.GridPosition.Y] = 1;
            cost[bot.GridPosition.X, bot.GridPosition.Y + 1] = 1;
            cost[bot.GridPosition.X, bot.GridPosition.Y - 1] = 1;

            cost[bot.GridPosition.X + 1, bot.GridPosition.Y + 1] = 1.4;
            cost[bot.GridPosition.X + 1, bot.GridPosition.Y - 1] = 1.4;
            cost[bot.GridPosition.X - 1, bot.GridPosition.Y + 1] = 1.4;
            cost[bot.GridPosition.X - 1, bot.GridPosition.Y - 1] = 1.4;


            //While the player's position is open
            while (closed[plr.GridPosition.X, plr.GridPosition.Y] == false)
            {
                //Increment X by 1
                for (int y = 0; y < 40; y++)
                {
                    //Lowest cost value
                    var minCost = System.Linq.Enumerable.Range(0, 4).Select(i => cost[i, 1]).Min();

                    //Increment Y by 1
                    for (int n = 0; n < 40; n++)
                    {
                        //If lowest cost and open
                        if (cost[y, n] == minCost && closed[y, n] == false)
                        {

                            //Mark current position as closed
                            closed[y, n] = true;

                            //If neighours' new cost is lower - and not blocked on the grid
                            //N, +/
                            if ((cost[y + 1, n] = (cost[y, n] + 1)) < (cost[y + 1, n]) && level.ValidPosition(true))
                            {
                                cost[y + 1, n] = (cost[y, n] + 1);
                                link[y + 1, n] = (y, n);
                            }

                            //S, -/
                            if ((cost[y - 1, n] = (cost[y, n] + 1)) < (cost[y - 1, n]) && (level.ValidPosition == true))
                            {
                                cost[y - 1, n] = (cost[y, n] + 1);
                                link[y - 1, n] = (y, n);
                            }

                            //E, /+
                            if ((cost[y, n + 1] = (cost[y, n] + 1)) < (cost[y, n + 1]) && (level.ValidPosition == true))
                            {
                                cost[y, n + 1] = (cost[y, n] + 1);
                                link[y, n + 1] = (y, n);
                            }

                            //W /-
                            if ((cost[y, n - 1] = (cost[y, n] + 1)) < (cost[y, n - 1]) && (level.ValidPosition == true))
                            {
                                cost[y, n - 1] = (cost[y, n] + 1);
                                link[y, n - 1] = (y, n);
                            }


                            //NE, +/+
                            if ((cost[y + 1, n + 1] = (cost[y, n] + 1.4)) < (cost[y + 1, n + 1]) && (level.ValidPosition == true))
                            {
                                cost[y + 1, n + 1] = (cost[y, n] + 1.4);
                                link[y + 1, n + 1] = (y, n);
                            }

                            //NW, +/-
                            if ((cost[y + 1, n - 1] = (cost[y, n] + 1.4)) < (cost[i + 1, n - 1]) && (level.ValidPosition == true))
                            {
                                cost[y + 1, n - 1] = (cost[y, n] + 1.4);
                                link[y + 1, n - 1] = (y, n);
                            }

                            //SE, -/+
                            if ((cost[y - 1, n + 1] = (cost[y, n] + 1.4)) < (cost[y - 1, n + 1]) && (level.ValidPosition == true))
                            {
                                cost[y - 1, n + 1] = (cost[y, n] + 1.4);
                                link[y - 1, n + 1] = (y, n);
                            }

                            //SW, -/-
                            if ((cost[y - 1, n - 1] = (cost[y, n] + 1.4)) < (cost[y - 1, n - 1]) && (level.ValidPosition == true))
                            {
                                cost[y - 1, n - 1] = (cost[y, n] + 1.4);
                                link[y - 1, n - 1] = (y, n);
                            }
                        }
                    }
                }
            }

            bool done = false; //set to true when we are back at the bot position
            Coord2 nextClosed = plr.GridPosition; //start of path
            while (!done)
            {
                inPath[nextClose.X, nextClose.Y] = true;
                nextClose = link[nextClose.X, nextClose.Y];
                if (nextClose == bot.GridPosition) done = true;
            }

        }

    }
}