Category: Game Development

A* Clearance-based Pathfinding algorithm

This is an improvement on my existing A* pathfinding algorithm.

What this addition to my A* pathfinding algorithm does, is take the size of the object into consideration while finding the shortest path between two points. This is very useful when you want larage objects to take one path and the smaller objects to take another.

This implementation is based on my reading of this article.

Here is a video of my implementation. Enjoy ūüôā


“The Exiled” Update 1


My GUI demo made using MonoGame/C#


A* Pathfinding and unit movement system C#/MonoGame

So you might ask, How is this done? How am I doing the movement system and the formation of the units.

Well lets start with the A* pathfinding. When you select the units you want to move, you click on the map and the A* algorithm will find the shortest path between the current unit position and the destination position which we selected by clicking on the map, and it will return a list of vector2 coordinates. After that is done, we actually have to move the units to that location. That’s a job for the waypoint system. The waypoint system will take the list of vector2 coordinates that was generated by the A* algorithm and it will move the units point by point until the unit reaches it destination.

public class WayPoint
{
    public int WayPointIndex;
    public bool ReachedDestination;

    public void MoveTo(GameTime gameTime, Vector2 UnitPosition, float UnitSpeed, List<Vector2> DestinationWaypoints)
    {
        //If the Waypoint list is not empty
        if (DestinationWaypoints.Count > 0)
        {
            //Did we reach the last waypoint in the list (our destination)?
            if (!ReachedDestination)
            {
                //Calculate the distance between the current unit position to the current waypoint in the list.
                float Distance = Vector2.Distance(UnitPosition, DestinationWaypoints[WayPointIndex]);

                //Calculate the direction vector for the unit to travel to from it current position to the waypoint in the list.
                Vector2 Direction = DestinationWaypoints[WayPointIndex] - UnitPosition;

                //If the distance > the length of the direction vector then that means we still 
                //didn't reach the waypoint position. So we normalize the vector 
                //and keep moving the unit in the waypoint direction.
                Direction.Normalize();

                if (Distance > Direction.Length())
                    unit.Position += Direction * (float)(Speed * gameTime.ElapsedGameTime.TotalMilliseconds);
                else
                {
                    //If we reached the last waypoint then we reached our
                    //destination. else we didn't reach our destination.
                    if (WayPointIndex >= DestinationWaypoints.Count - 1)
                    {
                        UnitPosition += Direction;
                        ReachedDestination = true;
                    }
                    else
                        //increment the index of waypoints in the list.
                        WayPointIndex++;
                }
            }
        }
    }
}

Now if you have a single unit and you want to find the shortest path from its current position to the target position and move it there, then that would not be a problem. The unit will find the shortest path using A* and the waypoint system will move that unit point by point until it reaches it’s destination. However what if you have more than one unit that wants to go to that same point on the map? Well if you have no collision detection between each unit then they will all move to the target position and they will stack on top of each other. Like so.

 

 

avoidance system 1

So how do we solve this problem. Well we need to implement some kind of avoidance system where if unit A collides with unit B then unit A will move few steps in the opposite direction of unit B.

avoidance system 2

 

So how do we do this? Well first we need to find which unit collided with the other unit first. Did unit A collide with unit B? or did unit B collide with unit A? Well from this figure you would look at the direction vector and see that both unit A and B are moving in that direction. and you can see that Unit A is behind unit B. So it would make sense that Unit A collided with unit B since they are both moving in the same direction. So we know that Unit A collided with Unit B, but how does the computer know?

Well the method I used to figure this out is by calculating the distance from unit A position to the destination point and then calculate the distance from Unit B to the destination point. And which ever distance is the longest means that, that unit is behind the other.

So by this calculation we can see that Unit A has the longest distance from its current position to the destination position, which means Unit A is behind Unit B. Which means Unit A collided with unit B.

 

avoidance system 3

 

So now since we know this information we can decide which unit should move few pixels backwards from the other unit. So what we do now is calculate the direction vector from unit A to unit B and we move unit A in the opposite direction of that vector until unit A is no longer collided with unit B.

 

avoidance system 4

And that is reall it. Here is the avoidance function that’s inside the unit class.

void Avoidance(GameTime gameTime, List<Unit> Units)
{
    //Loop through all the units
    for (int i = 0; i < Units.Count; i++)
    {
        //If unit A collides with another unit
        if (Units[i].Rectangle.Intersects(Rectangle))
        {
            //Calculate the distance from unit A position to the destination position.
            float DistanceA_To_Destination = Vector2.Distance(Position, WayPointsList[WayPointsList.Count - 1]);

            //Calculate the distance from unit B position to the destination position.
            float DistanceB_To_Destination = Vector2.Distance(Units[i].Position, WayPointsList[WayPointsList.Count - 1]);

            //If Distance from unit A to destination is longer than
            //Distance from unit B to the destination, unit A is behind unit B.
            if (DistanceA_To_Destination > DistanceB_To_Destination )
            {
                //Calculate the direction vector from unit A to unit B
                //and then flip it in the opposite direction.
                Vector2 OppositeDirection = -(Units[i].Position - Position);
                
                //Normalize the vector
                OppositeDirection.Normalize();

                //Move unit A in the opposite direction of unit B.
                Position += OppositeDirection * (float)(Speed * gameTime.ElapsedGameTime.TotalMilliseconds);
            }
        }
    }
}

Hope I explained that well. If you have any questions please feel free to leave a comment and I will do my best to respond to you.

 

[Update]
On the request of many people, here is the full source code built in C# and MonoGame.
A* pathfinding demo on Github

 

Enjoy.


This is how my procedurally generated dungeon rooms are generated


My HLSL lighting system in MonoGame.

And god said “Let there be light”


Calculating Light ray

So far the past few days I have been working on calculating light rays and the collision detection between light rays and polygons to produce real time shadows. In this video you can see how the light rays are colliding with the polygons. There are 50 light rays and I’m calculating for each light ray whether or whether not it collided with a polygon. Soon enough I can take this calculation and put it inside a shader to produce real time shadows.

Enjoy the video ^_^


My implementation of Procedural Dungeon Generation Algorithm V2.0


My implementation of Procedural Dungeon Generation Algorithm


All my textures disappear when I minimize my game window !!

So today I have found a bug in my game where if I minimized the game window, all the of my textures that use RenderTarget2D disappear. So naturally I went and googled the problem and I found this very interesting post on Stackoverflow that talks about this issue. If your an XNA/MonoGame game developer I encourage you to read it.

 

So why was I using RenderTarget2D and how did i fix this issue?

 

Well right now I have a 100×100 tile map that get drawn every single frame. That is 10,000 tiles or textures that should be drawn every single frame. Even with my 3930K clocked at 4.5Ghz and my AMD 7970 I was¬†barely¬†getting 60FPS !! Now if you have read my post about¬†How to overcome the performance issues in a tile based engine?¬†you would know that drawing more than 200-400 objects (Textures – 3D object etc…) is very bad thing to do. Both AMD and Nvidia recommends¬†to not have more than 600 draw calls. Imagine 10,000 draw calls !! So I found a¬†solution¬†to draw all 10,000 tiles and get more than 1600FPS !! How? using RenderTarget2D.

So basically what I did was, I have drawn all 10,000 tiles once to a RenderTarget2D and then I saved the RenderTarget2D to a Texture2D. This way instead of drawing 10,000 tiles I could just draw one big texture. Here is a snippet of my code.

 

void ConvertMapToTexture2D(SpriteBatch spriteBatch, Vector2 MapOffset)
{
renderTarget = new RenderTarget2D(Graphics.GraphicsDevice, (int)MaxTextureSize, (int)MaxTextureSize);

Graphics.GraphicsDevice.SetRenderTarget(renderTarget);

Graphics.GraphicsDevice.Clear(Color.White * 0f);

DrawTiles(spriteBatch, MapOffset);

Graphics.GraphicsDevice.SetRenderTarget(null);

MapTexture = renderTarget;
}

 

Now if you went and read the post at¬†Stackoverflow¬†you would know that when using RenderTarget2D¬†all the textures get saved on the GPU Vram and when you minimize your XNA game window you will¬†receive¬†a “Device Lost” error. This means all the data on the GPU Vram will be lost. That includes the RenderTarget2D and Texture2D. However when you load a texture from the Content Pipeline or by using Texture2D.FromStream(), the CPU will have a copy of that texture in the RAM just¬†in-case¬†all the data on the GPU Vram get erased.

So How to solve this issue? Well in the post at Stackoverflow there were few solution. One of them said to use Texture2D.Setdata() and Texture2D.GetData(). and this was a great solution. Because this way even if you minimize the game window and all your data in the GPU Vram get lost, you will still have a copy of that texture and you can then redraw it again.

 

void ConvertMapToTexture2D(SpriteBatch spriteBatch, Vector2 MapOffset)
{
renderTarget = new RenderTarget2D(Graphics.GraphicsDevice, (int)MaxTextureSize, (int)MaxTextureSize);

Graphics.GraphicsDevice.SetRenderTarget(renderTarget);

Graphics.GraphicsDevice.Clear(Color.White * 0f);

DrawTiles(spriteBatch, MapOffset);

Graphics.GraphicsDevice.SetRenderTarget(null);

Color[] data = new Color[renderTarget.Width * renderTarget.Height];

renderTarget.GetData<Color>(data);

MapTexture = new Texture2D(Graphics.GraphicsDevice, (int)MaxTextureSize, (int)MaxTextureSize);

MapTexture.SetData<Color>(data);
}

 

I hope that helped ūüôā