# Make A* pathing accept diagonal movement [HELP]

I implemented the algorithm A* Pathing to my enemies movement and it´s working fine. In order to step up the quality of my game I want to make my enemies also move diagonal so that their movement is more natural. I´ve made an attemp (will be possible to see in the code I will leave below) by adding to the crossable paths the tiles that are in the diagonal of the current tile with a cost that is half of the cost of a horizontal/vertical move. The problem is that when making diagonals the enemies can trespass my obstacles while with just top,down,left, right movement they avoid them. What would be a good aproach to find a solution?

``````
public List<Vector2> GetPathPositions(Vector2 _start,Vector2 _end)
{
List<Vector2> positions = new List<Vector2>();
List<PathUnit> path = GetPath(_start, _end);
for(int i = 0; i < path.Count; i++)
{
int x = path[i].GetTileY();
int y = path[i].GetTileX();
int positionX = (tiles.GetTilesWidht() - 1) + tiles.GetTilesWidht() * (x - 1) + tiles.GetTilesWidht() / 2;
int positionY= (tiles.GetTilesHeight() - 1) + tiles.GetTilesHeight() * (y - 1) + tiles.GetTilesHeight() / 2;

}

return positions;
}

public List<PathUnit> GetPath(Vector2 _start, Vector2 _end)           //must convert the positions to the tile they correspond
{
List<PathUnit> path = new List<PathUnit>();

PathUnit start = new PathUnit( (int)(_start.Y/GetTiles().GetTilesHeight()), (int)(_start.X / GetTiles().GetTilesWidht()), null,0);

PathUnit finish = new PathUnit((int)(_end.Y / GetTiles().GetTilesHeight()), (int) (_end.X / GetTiles().GetTilesWidht()) , null, 0);

start.SetDistance(finish.GetTileX(), finish.GetTileY());

var activeTiles = new List<PathUnit>();
var visitedTiles = new List<PathUnit>();

while (activeTiles.Any())
{
var checkTile = activeTiles.OrderBy(x => x.GetCostDistance()).First();

if (checkTile.GetTileX() == finish.GetTileX() && checkTile.GetTileY() == finish.GetTileY())     //if it´s the destiny point
{

PathUnit tile = checkTile;
while (tile!=null)
{
tile = tile.GetParent();
}

path.Reverse() ;
return path;
}

activeTiles.Remove(checkTile);

var walkableTiles = GetCrossableTiles( checkTile, finish);

foreach (var walkableTile in walkableTiles)
{
//We have already visited this tile so we don't need to do so again!
if (visitedTiles.Any(x => x.GetTileX() == walkableTile.GetTileX() && x.GetTileY() == walkableTile.GetTileY()))
continue;

//It's already in the active list, but that's OK, maybe this new tile has a better value (e.g. We might zigzag earlier but this is now straighter).
if (activeTiles.Any(x => x.GetTileX() == walkableTile.GetTileX() && x.GetTileY() == walkableTile.GetTileY()))
{
var existingTile = activeTiles.First(x => x.GetTileX() == walkableTile.GetTileX() && x.GetTileY() == walkableTile.GetTileY());
if (existingTile.GetCostDistance() > checkTile.GetCostDistance())
{
activeTiles.Remove(existingTile);
}
}
else
{
//We've never seen this tile before so add it to the list.
}
}
}

return path;
}

private List<PathUnit> GetCrossableTiles(PathUnit _currentPathUnit, PathUnit _targetPathUnit)
{
List<PathUnit> crossableTiles = new List<PathUnit>();

crossableTiles.Add(new PathUnit(_currentPathUnit.GetTileX(), _currentPathUnit.GetTileY() - 1, _currentPathUnit, _currentPathUnit.GetCost() + 1));
crossableTiles.Add(new PathUnit(_currentPathUnit.GetTileX(), _currentPathUnit.GetTileY() +1, _currentPathUnit, _currentPathUnit.GetCost() + 1));
crossableTiles.Add(new PathUnit(_currentPathUnit.GetTileX()-1, _currentPathUnit.GetTileY() , _currentPathUnit, _currentPathUnit.GetCost() + 1));
crossableTiles.Add(new PathUnit(_currentPathUnit.GetTileX()+1, _currentPathUnit.GetTileY() , _currentPathUnit, _currentPathUnit.GetCost() + 1));

for(int i = 0; i < crossableTiles.Count; i++)
{
crossableTiles[i].SetDistance(_targetPathUnit.GetTileX(), _targetPathUnit.GetTileY());
}

for (int i = 0; i < crossableTiles.Count; i++)
{

if (crossableTiles[i].GetTileX() < 0 || crossableTiles[i].GetTileX() > mapHeight - 1
|| crossableTiles[i].GetTileY() < 0 || crossableTiles[i].GetTileY() > mapWidth - 1
||!tiles.GetTile(map[crossableTiles[i].GetTileX(), crossableTiles[i].GetTileY()]).UnitCross() )
{
crossableTiles.RemoveAt(i);
}
}

return crossableTiles;
}
``````
``````
public class Enemy : Unit
{
protected int scoreAwarded;
protected Vector2 moveTo;
protected List<Vector2> path;
protected _Timer timer;
protected bool pathing;

public Enemy(string _path, Vector2 _position, Vector2 _dimensions, int _id) : base(_path, _position, _dimensions,_id)
{
moveTo = new Vector2(position.X,position.Y);
path = new List<Vector2>();
timer = new _Timer(3000);
pathing = false;
}

public int GetScoreAwarded()
{
return scoreAwarded;
}

public virtual void Update(Vector2 _offset, Character _character, List<Projectile> _projectiles,MapManager _map)
{
ArtificialIntelligence(_character, _projectiles,_map);

}

public void FindPath(MapManager _map,Vector2 _start,Vector2 _end,Character _character){
path.Clear();
path = _map.GetPathPositions(_start, _end);
List<Vector2> tempPath = new List<Vector2>();
for (int i = 1; i < path.Count - 1; i++)
{
}
//path.RemoveAt(0);
//path.Insert(0, position);
// path.RemoveAt(path.Count - 1);

path = tempPath;

}

public void MoveUnit()
{

if(position.X != moveTo.X || position.Y != moveTo.Y)
{
rotation = RotateTowards(position, moveTo);
}
else if (path.Count > 0)
{
moveTo = path[0];
path.RemoveAt(0);
}

}

public virtual void ArtificialIntelligence(Character _character, List<Projectile> _projectiles,MapManager _map)
{
// SetPosition(GetPosition() + RadialMovement(_character.GetPosition(), this.GetPosition(), this.speed));
// SetRotation(RotateTowards(this.GetPosition(), _character.GetPosition()));
timer.UpdateTimer();
if (path == null || (path.Count == 0 && position.X == moveTo.X && position.Y == moveTo.Y) || timer.Test())
{
if (!pathing)
{
{
pathing = true;
FindPath(_map, position, _character.GetPosition(),_character);
moveTo = path[0];
path.RemoveAt(0);
timer.ResetToZero();
pathing = false;
});

}

}

else
{
MoveUnit();

if (Vector2.Distance(this.GetPosition(), _character.GetPosition()) < this.GetAttackArea())
{
if (_character.HasShield())
{
_character.SetShieldStatus(false);
Debug.WriteLine("Perdeu o escudo");
}
else
{
_character.GetHit(GetDamage());
isDead = true;      //replace by character resistant to damage  for x seconds
}

}
}

}

public Vector2 RadialMovement(Vector2 focus, Vector2 position, float speed)       //focus is the destination point
{
float distance = Vector2.Distance(position, focus);

if (distance <= speed)
{
return focus - position;
}

else
{
return (focus - position) * speed / distance;
}

}
public override void Draw(Vector2 _offset)
{
base.Draw(_offset);
}
}

``````

I amended your title, as is looked like a solution thread and not a question thread title

the diagonal of the current tile with a cost that is half of the cost of a horizontal/vertical move

hmm, are these distances equivalent? sounds like a pretty rough heuristic to me.

your getting into fairly complex territory here. not knowing much about your game il give you a rundown of how i would handle path finding.

first depending on the game id pick an algorithm, id often use BFS for grid based pathing, A* for most any other case.

now i know the algorithm, i will pick a graph representation. in case of a grid this is easy, 2d array of course. for A* however, while a 2d array will work, its not really what A* is meant for. this is where stuff gets more tricky.

how will we represent our graph? and how will we create this graph?

for representation you will find lots of resources online about graph theory (in code its probably going to look like a vertex class, with a list of connected vertices).

for making it, depends. the more complex method would be to generate a “nav mesh” automatically for your map. or if you only have one small map it might be easier to just write a simple in game editor that allows you to place nodes and choose which nodes connect.

it’s one of those things that seems simple but isn’t trivial once you think on it.

1 Like

How about a simple check off, don’t include an obstacle if there is a blocked tile in one of the adjacent cardinal directions

For example, when checking if a tile in your pathfinding to the top right, if there is a blocked tile to the top, or a blocked tile to the right, then count the top right tile as blocked.

I am removing the obstacle ones before returning them

I do not understand where it is you think you’ve added diagonal movement.

In GetCrossableTiles, you generate a move list as the four cardinals here:

``````        crossableTiles.Add(new PathUnit(_currentPathUnit.GetTileX(), _currentPathUnit.GetTileY() - 1, _currentPathUnit, _currentPathUnit.GetCost() + 1));
crossableTiles.Add(new PathUnit(_currentPathUnit.GetTileX(), _currentPathUnit.GetTileY() +1, _currentPathUnit, _currentPathUnit.GetCost() + 1));
crossableTiles.Add(new PathUnit(_currentPathUnit.GetTileX()-1, _currentPathUnit.GetTileY() , _currentPathUnit, _currentPathUnit.GetCost() + 1));
crossableTiles.Add(new PathUnit(_currentPathUnit.GetTileX()+1, _currentPathUnit.GetTileY() , _currentPathUnit, _currentPathUnit.GetCost() + 1));
``````

You need to add the four corner positions to that result list as well.

Something like

``````      crossableTiles.Add(new PathUnit(_currentPathUnit.GetTileX()+1, _currentPathUnit.GetTileY()-1 , _currentPathUnit, _currentPathUnit.GetCost() + Math.Sqrt(2)));
``````

You need to cull fairly cleverly if you want to include neighboring obstacles. The way I’d write it might be a bit complex to discuss here. You can’t do this simplistic iterative approach anymore.

Secondary thing:

``````visitedTiles.Any(x => x.GetTileX() == walkableTile.GetTileX() && x.GetTileY() == walkableTile.GetTileY())
``````

That any invocation gets expensive as your map gets large and path long. If you start to see unacceptable performance dip, consider giving each tile an ID and using a dictionary for visited. Or if your map size is less than a couple million squares, us a 2d array for tracking visited. O(1M) is much better than O(NM)

I did have the four corners but deleted the comments.

`````` crossableTiles.Add(new PathUnit(_currentPathUnit.GetTileX()+1, _currentPathUnit.GetTileY() - 1, _currentPathUnit, _currentPathUnit.GetCost() + 0.5));
crossableTiles.Add(new PathUnit(_currentPathUnit.GetTileX()+1, _currentPathUnit.GetTileY() +1, _currentPathUnit, _currentPathUnit.GetCost() + 0.5));
crossableTiles.Add(new PathUnit(_currentPathUnit.GetTileX()-1, _currentPathUnit.GetTileY() - 1, _currentPathUnit, _currentPathUnit.GetCost() + 0.5));
crossableTiles.Add(new PathUnit(_currentPathUnit.GetTileX()-1, _currentPathUnit.GetTileY() + 1, _currentPathUnit, _currentPathUnit.GetCost() + 0.5));

``````

but with this four lines the monsters went trought obstacles

There are some things I would change with your code, but for the sake of getting it working I wrote an example within the context of your code:

``````    private List<PathUnit> GetCrossableTiles(PathUnit _currentPathUnit, PathUnit _targetPathUnit)
{
List<PathUnit> crossableTiles = new List<PathUnit>();

// don't add to list yet
// just create your main directions first
PathUnit leftTile = new PathUnit(_currentPathUnit.GetTileX() - 1, _currentPathUnit.GetTileY(), _currentPathUnit, _currentPathUnit.GetCost() + 1);
PathUnit rightTile = ...
PathUnit bottomTile = ...
PathUnit topTile = ...

... SetDistance...

// then check if the normal paths are valid
leftTile = CheckValidPath(leftTile);
rightTile = CheckValidPath(rightTile);
bottomTile = CheckValidPath(bottomTile);
topTile = CheckValidPath(topTile);

// create empty PathUnits for the diagonals
PathUnit bottomLeftTile, bottomRightTile, topLeftTile, topRightTile;

// check if the 4 normal paths are valid.
// if not, then the diagonal won't be valid
if (bottomTile != null)
{
if (leftTile != null)
{
bottomLeftTile = new PathUnit(_currentPathUnit.GetTileX() - 1, _currentPathUnit.GetTileY() - 1, _currentPathUnit, _currentPathUnit.GetCost() + 0.5);
}
if (rightTile != null) { bottomRightTile = ... }
}
if (topTile != null)
{
if (leftTile != null) { topLeftTile = ... }
if (rightTile != null) { topRightTile = ... }
}

// then check if the diagonal paths are valid
bottomLeftTile = CheckValidPath(bottomLeftTile);
bottomRightTile = CheckValidPath(bottomRightTile);
topLeftTile = CheckValidPath(topLeftTile);
topRightTile = CheckValidPath(topRightTile);

// add 4 normal paths to crossableTiles
if (leftTile != null) { crossableableTile.Add(leftTile); }
... rightTile...
... bottomTile...
... topTile...

// add 4 diagonal paths to crossableTiles
if (bottomLeftTile != null) { crossableableTile.Add(bottomLeftTile); }
... bottomRightTile...
... topLeftTile...
... topRightTile...
}

private PathUnit CheckValidPath(PathUnit crossableTile)
{
//  failsafe for the diagonals
if (crossableTile == null) { return null; }

if (crossableTile.GetTileX() < 0) { return null; }
if (crossableTile.GetTileX() > mapHeight - 1) { return null; }
if (crossableTile.GetTileY() < 0) { return null; }
if (crossableTile.GetTileY() > mapWidth - 1) { return null; }
if (!tiles.GetTile(map[crossableTile.GetTileX(), crossableTile.GetTileY()]).UnitCross())
{
// is this the code for checking obstacles?
return null;
}

return crossableTile;
}
``````

Btw, this was assuming your PathUnit is a class and not a struct. If it is a struct, instead of returning null, just return a false flag instead.

``````In GetCrossableTiles():            leftTile.valid = CheckValidTile(leftTile);
Then in CheckValidPath():          return false;
Then when checking tile != null:   if (!tile.valid)
``````

I would also note that you shouldn’t be calling new List<>() during runtime so much. I would create a corresponding List in your class and reuse it (also set a default capacity of 8: new List<>(8) for your 8 directions.

My problem is that with the diagonals my monsters cross lakes,etc, if I don´t add the diagonals they have the expected behavior

Without seeing a screenshot, I’m a bit confused. So for the above image as an example: assume enemy is green and water is blue. You’re saying that the enemy won’t cross onto the top or right water tiles, but it will cross onto the diagonal water tile?

What I am trying to say is that, if I don´t add the tiles in the diagonal, the enemy goes around the water, but if I do add them, he goes through the top right blue

This is the code for checking if a tile is a valid path right?

``````    // check if the 4 normal paths are valid.
// if not, then the diagonal won't be valid
if (bottomTile != null)
{
if (leftTile != null)
{
bottomLeftTile = new PathUnit(_currentPathUnit.GetTileX() - 1, _currentPathUnit.GetTileY() - 1, _currentPathUnit, _currentPathUnit.GetCost() + 0.5);
}
if (rightTile != null) { bottomRightTile = ... }
}
if (topTile != null)
{
if (leftTile != null) { topLeftTile = ... }
if (rightTile != null) { topRightTile = ... }
}
``````

If there are adjacent invalid tiles, then the diagonal tile is never given a PathUnit. Therefor it never even gets to the CheckValidPath code, so it isn’t able to be added to the crossableTiles list at the end of the method.

I may not be understanding correctly. In order to troubleshoot this: I would set up your map like my above screenshot and iterate just once through GetCrossableTiles and put a breakpoint at the end and look at your crossableTiles list to see which tiles are being added (by looking at their position). If you implemented my code, you shouldn’t get those diagonal tiles in the list. There may be something in your GetPath method that is not properly using the walkableTiles (the code in that method is confusing to look at so idk).