Hello
I'm still working on AI for my game, however I'm getting close. After 2 completely failed attempts and 1 semi-decent attempt I finally wrote that works as intended which I am happy with. However, there are 2 problems I'm currently trying to solve:
- AI is still blind for map changes until it recalculates the path
- Enemies cannot avoid each other if they need to pass through same node
I'm using 15*15 square grid with no diagonal movement, single region.
I've come up with several possible solutions which are (or at least should be) fairly easy to implement, however I'm not pleased with either of them. I've also checked multiple sources on internet about A* but either there wasn't much useful stuff or I'm still too stupid (or "inexperienced") to figure out proper solution from material I found.
While I'm trying to figure out proper solution, I'd like an opinion of more experienced people on solutions listed below and code provided, or maybe some other ideas I could try.
1) Perform only several steps with each update while taking other enemies into account
This solution looks nice, however I cannot figure out how would I be able to detect if there is no path, since A* (at least the form I know) detects it from having an empty list of open nodes at the start of new loop.
2) Update path when collision with other unit is detected
This "feels" more like a band aid rather than valid solution. It helps resolving stucked enemies but does not fix the problems. Impossible if there are 2 parts of the map connected only with one 1 tile wide path.
3) Recalculate path each Update when possible
I tried it... just now. Enemies started dancing between 2 nodes - I assume there is the path of equivalent cost from both those nodes.
4) Recalculate path when 2 enemies are going to step on same node
Sounds nice, however also suffers with "choke" problem.
AI code:
[spoiler]
if (FindAIPath.Count > 0)
AI[FindAIPath.Dequeue()].UpdateAI();
foreach (var item in AI)
{
item.Pathfollow();
if (!item.PathFound) FindAIPath.Enqueue(AI.IndexOf(item));
}
[/spoiler]
Pathfinding code:
[spoiler]
void Pathfinding()
{
Square currentSquare = new Square(Tanks[Index].Position, TileSize, null);
OpenList.Clear();
ClosedList.Clear();
Path.Clear();
pathFound = false;
OpenList.Add(currentSquare);
do
{
// Take the square with lowest F number from open list and put it in closed list
currentSquare = OpenList[0];
OpenList.Remove(currentSquare);
ClosedList.Add(currentSquare);
// For each adjacent square...
List<Vector2> adj = new List<Vector2>();
adj.Add(new Vector2(currentSquare.Position.X - TileSize, currentSquare.Position.Y));
adj.Add(new Vector2(currentSquare.Position.X + TileSize, currentSquare.Position.Y));
adj.Add(new Vector2(currentSquare.Position.X, currentSquare.Position.Y - TileSize));
adj.Add(new Vector2(currentSquare.Position.X, currentSquare.Position.Y + TileSize));
foreach (var a in adj)
{
Square sq = new Square(a, TileSize, currentSquare);
// If it is unwalkable, ignore it
if (UnwalkableTest(sq.Tile)) continue;
// If it is destination, stop with algorithm
if (sq.Tile == Target.Tile)
{
ClosedList.Add(currentSquare);
currentSquare = sq;
pathFound = true;
break;
}
// If it is in closed list, ignore it
if (ClosedList.Exists(x => sq.Position == x.Position))
continue;
sq.AssignValues(Target.Position, step[0]);
// if is in open list, check if old path is better
int i = OpenList.FindIndex(x => x.Tile == sq.Tile);
if (i > -1)
{
if (sq.G < OpenList.G)
{
OpenList.Parent = currentSquare;
OpenList.G = sq.G;
OpenList.F = OpenList.G + OpenList.H;
}
continue;
}
// Add to open list
i = OpenList.FindIndex(x => x.F > sq.F);
if (i > -1) OpenList.Insert(i, sq);
else OpenList.Add(sq);
}
} while (OpenList.Count > 0);
if (pathFound)
{
while (currentSquare.Parent != null)
{
Path.Push(currentSquare.Position);
currentSquare = currentSquare.Parent;
}
}
else
{
if (ClosedList.Count > 1) Path.Push(ClosedList[1].Position);
pathFound = true;
}
}
[/spoiler]
Maybe I could work on art a little until I figure out proper solution... XD
Thanks in advance