1
0
forked from s425077/PotatoPlan
JoelForkTest/Game1/Sources/Pathing/A-Star/Astar.cs

159 lines
5.6 KiB
C#
Raw Permalink Normal View History

2020-05-03 13:05:05 +02:00
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Microsoft.Xna.Framework;
class Astar
{
private Vector2 tractorPos;
private Vector2 housePos;
private Crops[,] crops;
private Vector2 Size;
private PriorityQueue allPaths;
2020-05-03 16:35:46 +02:00
private Vector2 targetPos;
private int Rotation;
2020-05-03 13:05:05 +02:00
public void update(Crops[,] newCrops, Vector2 newSize, Vector2 newTractorPos, Vector2 newHousePos, Vector2 newtargetPos, int rotation)
2020-05-03 13:05:05 +02:00
{
tractorPos = new Vector2((int)newTractorPos.X, (int)newTractorPos.Y);
housePos = new Vector2((int)newHousePos.X, (int)newHousePos.Y);
2020-05-03 16:35:46 +02:00
targetPos = newtargetPos;
2020-05-03 13:05:05 +02:00
crops = newCrops;
Size = newSize;
Rotation = rotation;
2020-05-03 13:05:05 +02:00
}
2020-05-03 16:35:46 +02:00
public Nodes getOptimalPath()
2020-05-03 13:05:05 +02:00
{
2020-05-03 16:35:46 +02:00
return allPaths.Peek();
2020-05-03 13:05:05 +02:00
}
// Get all adjacent nodes
private List<Nodes> GetAdjacentNodes(Vector2 currentPos)
2020-05-03 13:05:05 +02:00
{
2020-05-03 16:35:46 +02:00
var adjacentNodes = new List<Nodes>()
{
2020-05-03 23:40:40 +02:00
new Nodes(new Vector2(currentPos.X, currentPos.Y+1), 0),
new Nodes(new Vector2(currentPos.X + 1, currentPos.Y), 1),
new Nodes(new Vector2(currentPos.X, currentPos.Y - 1), 2),
new Nodes(new Vector2(currentPos.X - 1, currentPos.Y), -1),
2020-05-03 16:35:46 +02:00
};
2020-05-03 23:40:40 +02:00
//check if out of range
for (int i = 3; i >= 0; i--)
2020-05-03 17:06:03 +02:00
{
if (adjacentNodes[i].getCords().X < 0 || adjacentNodes[i].getCords().Y < 0)
adjacentNodes.Remove(adjacentNodes[i]);
else
{
2020-05-03 19:30:41 +02:00
if (adjacentNodes[i].getCords().X > Size.X - 1 || adjacentNodes[i].getCords().Y > Size.Y - 1)
2020-05-03 17:06:03 +02:00
adjacentNodes.Remove(adjacentNodes[i]);
}
}
// return if not an obstacle
2020-05-03 16:35:46 +02:00
return adjacentNodes.Where(
2020-05-05 16:27:45 +02:00
item => (crops[(int)item.getCords().X, (int)item.getCords().Y].getStatus()) != 0).ToList();
2020-05-03 16:35:46 +02:00
}
2020-05-03 23:40:40 +02:00
// Heuristic function, Manhattan method.
2020-05-03 16:35:46 +02:00
public int ComputeHScore(Vector2 currentNode, Vector2 endNote)
{
return (int)(Math.Abs(endNote.X - currentNode.X) + Math.Abs(endNote.Y - currentNode.Y));
}
// Rotation Cost
2020-05-03 23:40:40 +02:00
public int CalculateRotationCost(int currDir, int newDir)
{
if (currDir == newDir)
return 0;
else if (Math.Abs(currDir - newDir) == 1 || Math.Abs(currDir - newDir) == 3)
return 2;
else if (Math.Abs(currDir - newDir) == 0 || Math.Abs(currDir - newDir) == 2)
return 9;
2020-05-03 23:40:40 +02:00
return 0;
}
// Convert rotation used by sprite, to get direction of first node in next path
public int ConvertRotation()
{
int rotation = 0;
if (Rotation == 180)
rotation = 0;
else if (Rotation == 270)
rotation = 1;
else if (Rotation == 0)
rotation = 2;
else if (Rotation == 90)
rotation = -1;
return rotation;
}
// Main function of A* algorithm
2020-05-03 16:35:46 +02:00
public Path FindPath()
{
int g = 0;
int direction = ConvertRotation();
2020-05-03 17:06:03 +02:00
Path path = new Path();
2020-05-03 22:28:52 +02:00
MinHeap openList = new MinHeap();
MinHeap closedList = new MinHeap();
2020-05-03 17:52:35 +02:00
Nodes target = new Nodes(targetPos);
Nodes startPos = new Nodes(tractorPos, direction);
2020-05-03 16:35:46 +02:00
Nodes current = null;
2020-05-03 22:28:52 +02:00
openList.Insert(startPos);
2020-05-03 16:35:46 +02:00
2020-05-03 22:28:52 +02:00
while (openList.GetSize() > 0)
2020-05-03 16:35:46 +02:00
{
2020-05-03 22:28:52 +02:00
current = openList.getMin();
closedList.Insert(current);
openList.removeMin();
2020-05-03 23:40:40 +02:00
direction = current.getDirection();
2020-05-03 16:35:46 +02:00
2020-05-03 22:28:52 +02:00
if (current.getCords() == target.getCords())
break;
2020-05-03 16:35:46 +02:00
var adjacentNodes = GetAdjacentNodes(current.getCords());
foreach (var adjacentNode in adjacentNodes)
2020-05-03 16:35:46 +02:00
{
if (closedList.Exists(adjacentNode.getCords())) // check if adjacent node is on closed list, if it is, skip it
2020-05-03 16:35:46 +02:00
continue;
g = current.getG() + crops[(int)adjacentNode.getCords().X, (int)adjacentNode.getCords().Y].getCostOnMovement() + CalculateRotationCost(direction, adjacentNode.getDirection()); // calculate g - cost from start point
if (!(openList.Exists(adjacentNode.getCords()))) // if adjacent node is not on open list, add it
2020-05-03 16:35:46 +02:00
{
2020-05-03 16:35:46 +02:00
adjacentNode.setG(g);
2020-05-03 17:52:35 +02:00
adjacentNode.setH(ComputeHScore(adjacentNode.getCords(), target.getCords()));
2020-05-03 16:35:46 +02:00
adjacentNode.calculateF();
adjacentNode.setParent(current);
2020-05-03 22:28:52 +02:00
openList.Insert(adjacentNode);
2020-05-03 16:35:46 +02:00
}
else
{
if (g + adjacentNode.getH() < adjacentNode.getF()) // check if adjacent node is a better path than the current one
2020-05-03 16:35:46 +02:00
{
adjacentNode.setG(g);
adjacentNode.calculateF();
adjacentNode.setParent(current);
}
}
2020-05-03 23:40:40 +02:00
2020-05-03 16:35:46 +02:00
}
}
// backtrack to create path
2020-05-03 17:52:35 +02:00
while (current != null)
2020-05-03 16:35:46 +02:00
{
path.AddNode(current);
current = current.getParent();
}
2020-05-03 19:30:41 +02:00
path = path.FlipArray();
2020-05-03 22:28:52 +02:00
openList.deleteHeap();
closedList.deleteHeap();
2020-05-03 16:35:46 +02:00
return path;
2020-05-03 13:05:05 +02:00
}
2020-05-03 16:35:46 +02:00
}