I have decided to upload the entire source code of my Vault Engine on GitHub. The engine is still missing some features but you can still use it.
Enjoy ðŸ™‚
I have decided to upload the entire source code of my Vault Engine on GitHub. The engine is still missing some features but you can still use it.
Enjoy ðŸ™‚
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 ðŸ™‚
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.
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.
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.
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.
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.
Copyright © 2017, Vault 16 Software. Proudly powered by WordPress. Blackoot design by Iceable Themes.