# Pathplanning A* Getting stuck in wall

I'm having a problem with my pathplanning.

I can plan a path and make my character follow it, that's not a problem. But when I plan a path around a wall, it takes the shortest way as A* suggests, which is normally good. But the player I'm moving is not 1 pixel by 1 pixel, so it overlaps with the wall. My question, should I check for that during the calculation of the path created by A* or should I do it somewhere later?

I thought it'd be wise to take the Player's width and height into account with the A* calculation. But I don't know how I'm going to do that.

I hope you guys can help me out.

Here's my A* search:

internal class SearchWithAStar
{
private SparseGraph _graph;
private int _source, _target;
private List<double> _costToThisNode;
private List<double> _mgCost;
private List<Edge> _shortestPathTree, _searchFrontier;

public SearchWithAStar(SparseGraph graph, int source, int target)
{
_graph = graph;
_source = source;
_target = target;
_shortestPathTree = new List<Edge>(_graph.NumNodes);
_searchFrontier = new List<Edge>(_graph.NumNodes);
_costToThisNode = new List<double>(_graph.NumNodes);
_mgCost = new List<double>(_graph.NumNodes);

for (int i = 0; i < _graph.NumNodes; ++i)
{
_shortestPathTree.Insert(i, null);
_searchFrontier.Insert(i, null);
_costToThisNode.Insert(i, 0);
_mgCost.Insert(i, 0);
}
Search();
}

private void Search()
{
//m_FCosts = _costToThisNode
//
IndexedPriorityQLow<double> pq = new IndexedPriorityQLow<double>(_costToThisNode, _graph.NumNodes);
pq.Insert(_source);
while (!pq.Empty)
{
//get lowest cost node from the queue
int NextClosestNode = pq.Pop();

//move this node from the frontier to the spanning tree
_shortestPathTree[NextClosestNode] = _searchFrontier[NextClosestNode];

//if the target has been found exit
if (NextClosestNode == _target) return;

List<Edge> nodeEdges = _graph.GetAllEdgesFromNode(NextClosestNode);

foreach (Edge edge in nodeEdges)
{
//calculate the heuristic cost from this node to the target (H)
double HCost = Heuristic.Calculate(_graph, _target, edge.To);

//calculate the 'real' cost to this node from the source (G)
double GCost = _costToThisNode[NextClosestNode] + edge.Cost;

//if the node has not been added to the frontier, add it and update
//the G and F costs
if (_searchFrontier[edge.To] == null)
{
_costToThisNode[edge.To] = GCost + HCost;
_mgCost[edge.To] = GCost;

pq.Insert(edge.To);

_searchFrontier[edge.To] = edge;
}

//if this node is already on the frontier but the cost to get here
//is cheaper than has been found previously, update the node
//costs and frontier accordingly.
else if ((GCost < _mgCost[edge.To]) && (_shortestPathTree[edge.To] == null))
{
_costToThisNode[edge.To] = GCost + HCost;
_mgCost[edge.To] = GCost;

pq.ChangePriority(edge.To);

_searchFrontier[edge.To] = edge;
}
}
}
}

public List<int> GetPathToTarget()
{
var path = new LinkedList<int>();

// if the target has not been set, then no path has
// been found
if (_target < 0)
return path.ToList();

// add the target node to the linked list
var node = _target;
path.AddFirst(node);

// then add each node on the shortest path tree
while ((node != _source) && (_shortestPathTree[node] != null))
{
node = _shortestPathTree[node].From;
path.AddFirst(node);
}

// return the completed path as a List<>
return path.ToList();
}


And a picture for more detail about this "error": the guy should walk around the wall, not through the wall.

## 2 Answers

One thing you can do is not let the character travel diagonally when the path crosses the corner of a wall. The character is free to travel diagonally out on the open, but not next to a wall. This is done in your a* algorithm.

Yes you should factor the size of the character into the A* calculation. There are basically two ways you can either make your character larger, which complicates the computation. Alternatively you can make the wall wider and pretend your character has 0 width.

• Could you help me with that? as i'm getting stuck when i pass the entity to the function.. D: Jun 26 '14 at 14:47