Path-finding noob help! C# / XNA

Author
110
March 28, 2010 03:58 AM
Hey, so I am trying to develop path-finding for a turret defense game I am making, but I am having some major troubles with it. I told someone I thought there were some flaws with A* path finding, because when its given diagonal obsticals like in my video, it seems to make the path turn in on itself. They said that A* is flawless and it must be me that's doing something wrong :P Example of the program running:
Here's my code:
[SOURCE lang = "C#"]
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 Pathfinding_5
{
    public class Game1 : Microsoft.Xna.Framework.Game
    {
        #region /// ----------------------------- Variables ----------------------------- ///
        GraphicsDeviceManager graphics;
        SpriteBatch spriteBatch;
        Texture2D Background;
        Texture2D MouseTile;
        Vector2 MouseTilePos;
        Texture2D TestSprite;
        Vector2 TestPos = new Vector2(30, 204);
        Color TestColor = Color.White;
        Vector2 uTile;

        Random RandomColor = new Random();

        MouseState mouseState, preMouseState;
        #endregion

        int TileWidth = 20;
        int TileHeight = 20;
        Vector2 sTile = new Vector2(0, 5);
        Vector2 eTile = new Vector2(19, 5);
        int[,] Map = {
                         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0},
                         {0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0},
                         {0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0},
                         {0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0},
                         {0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
                         {0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},
                         {1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0},
                         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                     };

        List<Vector2> OpenList = new List<Vector2>();
        List<Vector2> ClosedList = new List<Vector2>();
        List<Vector2> ForkedList = new List<Vector2>();
        List<Texture2D> TileTexture = new List<Texture2D>();

        public Game1()
        {
            graphics = new GraphicsDeviceManager(this);
            Content.RootDirectory = "Content";
        }
        
        protected override void Initialize()
        {
            graphics.PreferredBackBufferWidth = 401;
            graphics.PreferredBackBufferHeight = 200;
            graphics.ApplyChanges();
            this.IsMouseVisible = true;

            OpenList.Add(sTile);
            uTile = sTile;

            base.Initialize();
        }

        protected override void LoadContent()
        {
            TileTexture.Add(Content.Load<Texture2D>("placeHolder"));
            TileTexture.Add(Content.Load<Texture2D>("blackTile"));
            TileTexture.Add(Content.Load<Texture2D>("ghostTile"));
            TileTexture.Add(Content.Load<Texture2D>("greyTile"));
            TileTexture.Add(Content.Load<Texture2D>("orange"));
            TileTexture.Add(Content.Load<Texture2D>("blueTile"));

            TestSprite = Content.Load<Texture2D>("hero");
            Background = Content.Load<Texture2D>("Realistic/background");
            MouseTile = Content.Load<Texture2D>("mouseTIle");

            spriteBatch = new SpriteBatch(GraphicsDevice);
        }

        protected override void UnloadContent()
        {
        }
        
        public Vector2 FindEnd(Vector2 uTile)
        {
            int CurrentCost, LastCost = 500;
            int x = (int)uTile.X, y = (int)uTile.Y;
            Vector2[] Tile = new Vector2[8];
            Vector2 returnTile = sTile, CurrentTile;
            bool ClearGrid = false, InListBool, TileExistsBool;

            #region
            ClearGrid = IsGridClear(new Vector2(x, y), true);
            if (ClearGrid)
            {
                Tile = new Vector2[8];
                Tile[0] = new Vector2(x - 1, y - 1);
                Tile[1] = new Vector2(x - 0, y - 1);
                Tile[2] = new Vector2(x + 1, y - 1);
                Tile[3] = new Vector2(x - 1, y - 0);
                Tile[4] = new Vector2(x + 1, y - 0);
                Tile[5] = new Vector2(x - 1, y + 1);
                Tile[6] = new Vector2(x - 0, y + 1);
                Tile[7] = new Vector2(x + 1, y + 1);
            }
            if (!ClearGrid)
            {
                Tile = new Vector2[4];
                Tile[0] = new Vector2(x - 0, y - 1);
                Tile[1] = new Vector2(x - 1, y - 0);
                Tile[2] = new Vector2(x + 1, y - 0);
                Tile[3] = new Vector2(x - 0, y + 1);
            }
            #endregion

            for (int i = 0; i < Tile.GetLength(0); i++)
            {
                CurrentTile = Tile;
                TileExistsBool = TileExists(Tile);
                InListBool = CheckOpenList(Tile);
                if (TileExistsBool && InListBool)
                {
                    CurrentCost = CalculateCost(Tile);
                    if (/*Map[(int)Tile.X, (int)Tile.Y] != 1 &&*/ (CurrentCost <= LastCost))
                    {
                        returnTile = Tile;
                        LastCost = CurrentCost;
                    }
                }
            }
            return returnTile;
        }
        
        public bool NextTile(Vector2 uTile)
        {
            Vector2 returnTile = sTile;
            bool sucsessful = true, isTileUsable;
            int lastCost = 500, currentCost, diagnalCost;

            List<Vector2> usableTiles = new List<Vector2>();

            Vector2[] Tile = new Vector2[8];
            Tile[0] = new Vector2(uTile.X - 1, uTile.Y - 1);
            Tile[1] = new Vector2(uTile.X, uTile.Y - 1);
            Tile[2] = new Vector2(uTile.X + 1, uTile.Y - 1);
            Tile[3] = new Vector2(uTile.X - 1, uTile.Y);
            Tile[4] = new Vector2(uTile.X + 1, uTile.Y);
            Tile[5] = new Vector2(uTile.X - 1, uTile.Y + 1);
            Tile[6] = new Vector2(uTile.X, uTile.Y + 1);
            Tile[7] = new Vector2(uTile.X + 1, uTile.Y + 1);

            for (int i = 0; i < Tile.GetLength(0); i++)
            {
                returnTile = Tile;
                if (TileExists(new Vector2(Tile.Y, Tile.X)))
                {
                    if (CheckOpenList(Tile))
                    {
                        if (Map[(int)Tile.Y, (int)Tile.X] != 1)
                        {
                            isTileUsable = true;

                            Vector2[] eGrid = new Vector2[4];               //Now if the tile is usable, check it to see if it shares horizontal or vertical adjacent tiles with the uTile, so we know wether there are any tiles that would obstruct it from moving to that position.
                            eGrid[0] = new Vector2(Tile.X, Tile.Y - 1);
                            eGrid[1] = new Vector2(Tile.X - 1, Tile.Y);
                            eGrid[2] = new Vector2(Tile.X + 1, Tile.Y);
                            eGrid[3] = new Vector2(Tile.X, Tile.Y + 1);

                            Vector2[] uGrid = new Vector2[4];
                            uGrid[0] = new Vector2(uTile.X, uTile.Y - 1);
                            uGrid[1] = new Vector2(uTile.X - 1, uTile.Y);
                            uGrid[2] = new Vector2(uTile.X + 1, uTile.Y);
                            uGrid[3] = new Vector2(uTile.X, uTile.Y + 1);

                            for (int l = 0; l < eGrid.GetLength(0); l++)
                            {
                                for (int k = 0; k < uGrid.GetLength(0); k++)
                                {
                                    if (eGrid[l] == uGrid[k])
                                    {
                                        if (TileExists(new Vector2(eGrid[l].Y, eGrid[l].X)))
                                        {
                                            if (Map[(int)eGrid[l].Y, (int)eGrid[l].X] == 1)
                                            {
                                                isTileUsable = false;
                                                break;
                                            }
                                        }
                                    }
                                }
                            }
                            if (isTileUsable)
                            {
                                usableTiles.Add(Tile);
                            }
                        }
                    }
                }
            }

            if (usableTiles.Count == 0) { sucsessful = false; }

            for (int j = 0; j < usableTiles.Count; j++)
            {
                currentCost = CalculateCost(usableTiles[j]) + AddDiagnalCost(uTile, usableTiles[j]);
                if (currentCost < lastCost)
                {
                    returnTile = usableTiles[j];
                    lastCost = currentCost;
                }
                else if (currentCost == lastCost)
                {
                    ForkedList.Add(uTile);
                    //returnTile = usableTiles[j];
                }
            }

            if (sucsessful) { OpenList.Add(returnTile); }
            return sucsessful;
        }

        public bool FindPath(Vector2 uTile)
        {
            Vector2 returnTile = sTile;
            bool sucsessful = true, isTileUsable;
            int lastCost = 1000, currentCost;

            List<Vector2> usableTiles = new List<Vector2>();

            Vector2[] Tile = new Vector2[8];
            Tile[0] = new Vector2(uTile.X - 1, uTile.Y - 1);
            Tile[1] = new Vector2(uTile.X, uTile.Y - 1);
            Tile[2] = new Vector2(uTile.X + 1, uTile.Y - 1);
            Tile[3] = new Vector2(uTile.X - 1, uTile.Y);
            Tile[4] = new Vector2(uTile.X + 1, uTile.Y);
            Tile[5] = new Vector2(uTile.X - 1, uTile.Y + 1);
            Tile[6] = new Vector2(uTile.X, uTile.Y + 1);
            Tile[7] = new Vector2(uTile.X + 1, uTile.Y + 1);

            for (int i = 0; i < Tile.GetLength(0); i++)
            {
                if (TileExists(new Vector2(Tile.Y, Tile.X)))
                {
                    if (!CheckOpenList(Tile) && CheckClosedList(Tile))//If the tile is in the openlist, but not in the closedlist
                    {
                        isTileUsable = true;

                        Vector2[] eGrid = new Vector2[4];               //Now if the tile is usable, check it to see if it shares horizontal or vertical adjacent tiles with the uTile, so we know wether there are any tiles that would obstruct it from moving to that position.
                        eGrid[0] = new Vector2(Tile.X, Tile.Y - 1);
                        eGrid[1] = new Vector2(Tile.X - 1, Tile.Y);
                        eGrid[2] = new Vector2(Tile.X + 1, Tile.Y);
                        eGrid[3] = new Vector2(Tile.X, Tile.Y + 1);

                        Vector2[] uGrid = new Vector2[4];
                        uGrid[0] = new Vector2(uTile.X, uTile.Y - 1);
                        uGrid[1] = new Vector2(uTile.X - 1, uTile.Y);
                        uGrid[2] = new Vector2(uTile.X + 1, uTile.Y);
                        uGrid[3] = new Vector2(uTile.X, uTile.Y + 1);

                        for (int l = 0; l < eGrid.GetLength(0); l++)
                        {
                            for (int k = 0; k < uGrid.GetLength(0); k++)
                            {
                                if (eGrid[l] == uGrid[k])
                                {
                                    if (TileExists(new Vector2(eGrid[l].Y, eGrid[l].X)))
                                    {
                                        if (Map[(int)eGrid[l].Y, (int)eGrid[l].X] == 1)
                                        {
                                            isTileUsable = false;
                                            break;
                                        }
                                    }
                                }
                            }
                        }
                        if (isTileUsable)
                        {
                            usableTiles.Add(Tile);
                        }
                    }
                }
            }

            if (usableTiles.Count == 0) { sucsessful = false; }

            for (int j = 0; j < usableTiles.Count; j++)
            {
                currentCost = (int)(Math.Abs(usableTiles[j].X - sTile.X) + Math.Abs(usableTiles[j].Y - sTile.Y)) + AddDiagnalCost(uTile, usableTiles[j]);
                if (currentCost <= lastCost)
                {
                    returnTile = usableTiles[j];
                    lastCost = currentCost;
                }
            }

            if (sucsessful) { ClosedList.Add(returnTile); }
            return sucsessful;
        }

        float timer, releaseInterval = 50;
        bool brokenPath = false, makingPath = false;
        Vector2 pathTile;

        protected override void Update(GameTime gameTime)
        {
            if (brokenPath)
            {
                TestColor = Color.Red;
            }
            else TestColor = Color.White;

            KeyboardState keyState = Keyboard.GetState();
            if (keyState.IsKeyDown(Keys.Space))
            {
                /*
                brokenPath = false;
                uTile = sTile;
                pathTile = eTile;
                ResetValues();
                ResetLists();
                OpenList.Add(sTile);
                ClosedList.Add(eTile);
                 */
                releaseInterval = 100;
                //makingPath = false;
            }

            timer += (float)gameTime.ElapsedGameTime.TotalMilliseconds;
            UpdateMouse();

            if (timer >= releaseInterval)
            {
                if (uTile != eTile && !makingPath)
                {
                    if (!NextTile(uTile))
                    {
                        if (ForkedList.Count > 0)
                        {
                            uTile = ReturnLastFork();
                        }
                        else if (!FindNewPath()) { brokenPath = true; }
                    }
                    else { uTile = OpenList[OpenList.Count - 1]; }
                }
                else
                {
                    makingPath = true;
                    if (pathTile != sTile)
                    {
                        if (FindPath(pathTile)) { pathTile = ClosedList[ClosedList.Count - 1]; }
                        else { brokenPath = true; }
                    }
                }
                timer = 0;
            }
            
            Map[(int)sTile.Y, (int)sTile.X] = 4;
            Map[(int)eTile.Y, (int)eTile.X] = 4;
            base.Update(gameTime);
        }

        protected override void Draw(GameTime gameTime)
        {
            GraphicsDevice.Clear(Color.CornflowerBlue);
            spriteBatch.Begin();

            spriteBatch.Draw(Background, new Vector2(0, 0), Color.White);

            //Draw Lists
            /*
            for (int j = 0; j < ForkedList.Count; j++)
            {
                spriteBatch.Draw(TileTexture[2], new Rectangle((int)ForkedList[j].X * TileWidth, (int)ForkedList[j].Y * TileHeight, TileWidth, TileHeight), Color.White);
            }
            */
            for (int j = 0; j < OpenList.Count; j++)
            {
                spriteBatch.Draw(TileTexture[3], new Rectangle((int)OpenList[j].X * TileWidth + 5, (int)OpenList[j].Y * TileHeight + 5, TileWidth - 10, TileHeight - 10), Color.White);
            }
            
            for (int j = 0; j < ClosedList.Count; j++)
            {
                spriteBatch.Draw(TileTexture[2], new Rectangle((int)ClosedList[j].X * TileWidth, (int)ClosedList[j].Y * TileHeight, TileWidth, TileHeight), Color.White);
            }

            for (int y = 0; y < Map.GetLength(0); y++)
            {
                for (int x = 0; x < Map.GetLength(1); x++)
                {
                    if(Map[y, x] == 1)
                    spriteBatch.Draw(TileTexture[Map[y, x]], new Rectangle(x * TileWidth, y * TileHeight, TileWidth, TileHeight), Color.White);
                }
            }

            spriteBatch.Draw(TestSprite, TestPos, TestColor);
            spriteBatch.Draw(MouseTile, new Rectangle((int)MouseTilePos.X, (int)MouseTilePos.Y, 21, 21), Color.White);

            spriteBatch.End();
            base.Draw(gameTime);
        }
        #region /*------------------------------------------------Debugging Functions-------------------------------------------------*/
        public void UpdateMouse()
        {
            int x, y;
            mouseState = Mouse.GetState();
            MouseTilePos = new Vector2(mouseState.X / TileWidth * TileWidth, mouseState.Y / TileHeight * TileHeight);
            y = (int)(MouseTilePos.X / TileWidth);
            x = (int)(MouseTilePos.Y / TileHeight);
            
            if (mouseState.LeftButton == ButtonState.Pressed && preMouseState.LeftButton == ButtonState.Released)
            {
                if (TileExists(new Vector2(x, y)))
                {

                    brokenPath = false;
                    uTile = sTile;
                    pathTile = eTile;
                    ResetValues();
                    ResetLists();
                    OpenList.Add(sTile);
                    ClosedList.Add(eTile);
                    releaseInterval = 0;
                    makingPath = false;

                    if (Map[x, y] == 1)
                        Map[x, y] = 0;
                    else
                        Map[x, y] = 1;
                }
            }
            preMouseState = mouseState;// To check for clicking
        }
        public void ResetValues()
        {
            for (int y = 0; y < Map.GetLength(0); y++)
            {
                for (int x = 0; x < Map.GetLength(1); x++)
                {
                    if (Map[y, x] != 1)
                    {
                        Map[y, x] = 0;
                    }
                }
            }
        }
        public void ResetLists()
        {
            OpenList = new List<Vector2>();
            ClosedList = new List<Vector2>();
            ForkedList = new List<Vector2>();
        }
        public bool TileExists(Vector2 uTile)
        {
            bool returnValue = false;
            if (uTile.X >= 0 && uTile.Y >= 0 && uTile.X < Map.GetLength(0) && uTile.Y < Map.GetLength(1))
            {
                returnValue = true;
            }
            return returnValue;
        }
        public int CalculateCost(Vector2 uTile)
        {
            int returnValue = 0;
            returnValue = (int)(Math.Abs(uTile.X - eTile.X) + Math.Abs(uTile.Y - eTile.Y));
            return returnValue;
        }
        public bool IsGridClear(Vector2 uTile, bool CheckFullGrid)
        {
            Vector2[] Tile = new Vector2[4];
            float x = uTile.X, y = uTile.Y;
            bool returnValue = true;
            if (CheckFullGrid)
            {
                Tile = new Vector2[8];
                Tile[0] = new Vector2(x - 1, y - 1);
                Tile[1] = new Vector2(x - 0, y - 1);
                Tile[2] = new Vector2(x + 1, y - 1);
                Tile[3] = new Vector2(x - 1, y - 0);
                Tile[4] = new Vector2(x + 1, y - 0);
                Tile[5] = new Vector2(x - 1, y + 1);
                Tile[6] = new Vector2(x - 0, y + 1);
                Tile[7] = new Vector2(x + 1, y + 1);
            }
            if (!CheckFullGrid)
            {
                Tile = new Vector2[4];
                Tile[0] = new Vector2(x - 0, y - 1);
                Tile[1] = new Vector2(x - 1, y - 0);
                Tile[2] = new Vector2(x + 1, y - 0);
                Tile[3] = new Vector2(x - 0, y + 1);
            }

            for (int i = 0; i < Tile.GetLength(0); i++)
            {
                if (TileExists(Tile))
                {
                    if (Map[(int)Tile.X, (int)Tile.Y] == 1)
                    {
                        returnValue = false;
                    }
                }
            }

            return returnValue;
        }
        public Vector2 ReturnLastFork()
        {
            Vector2 returnValue = sTile;//if there are no other forks, go back to sTile.
            if (ForkedList.Count > 0)
            {
                returnValue = ForkedList[ForkedList.Count - 1];
                ForkedList.RemoveAt(ForkedList.Count - 1);
            }
            return returnValue;
        }

        public bool FindNewPath()
        {
            bool returnValue = false;
            for (int i = 0; i < OpenList.Count; i++)
            {
                if (NextTile(OpenList)) { returnValue = true; break; }
            }

            return returnValue;
        }

        public bool CheckOpenList(Vector2 uTile)
        {
            bool returnValue = true;
            for(int i = 0; i < OpenList.Count - 1; i++)
            {
                if(OpenList == uTile)
                {
                    returnValue = false;
                    break;
                }
            }
            return returnValue;
        }
        public bool CheckClosedList(Vector2 uTile)
        {
            bool returnValue = true;
            for (int i = 0; i < ClosedList.Count - 1; i++)
            {
                if (ClosedList == uTile)
                {
                    returnValue = false;
                    break;
                }
            }
            return returnValue;
        }
        #endregion

        public int AddDiagnalCost(Vector2 uTile, Vector2 adjTile)
        {
            int returnValue = 0;
            Vector2[] Tile = new Vector2[4];
            Tile[0] = new Vector2(uTile.X - 1, uTile.Y - 1);
            Tile[0] = new Vector2(uTile.X + 1, uTile.Y - 1);
            Tile[0] = new Vector2(uTile.X - 1, uTile.Y + 1);
            Tile[0] = new Vector2(uTile.X + 1, uTile.Y + 1);

            for (int i = 0; i < Tile.GetLength(0); i++)
            {
                if (Tile == adjTile) { returnValue = 4; break; }
            }
            return returnValue;
        }
    }
}
I've read all the pathfinding tutorials I can find, and none seem to explain what to do when a path has to navigate around an obstical with a strange shape that would make it turn in on itself and make blotches of tiles in the path. Edit: So sorry about putting the code in a quote box, I couldn't figure out how to make a code box.. =/ Edit2: I have found this video on youtube,
This is a much different thing than what I did, at first it looked much more efficient than my method for finding the end tile, but then realized that it would most likely have the same problems as mine. and more so it dosn't give an actual path, it just finds the end which is kinda useless.. or is it? [Edited by - Dagz on March 28, 2010 12:30:58 PM]
Path-finding noob help! C# / XNA

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Path-finding noob help! C# / XNA

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines
