2
\$\begingroup\$

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.

Error, the guy should walk around the walls not through

\$\endgroup\$

2 Answers 2

4
\$\begingroup\$

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.

enter image description here

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Could you help me with that? as i'm getting stuck when i pass the entity to the function.. D: \$\endgroup\$
    – Baklap4
    Jun 26, 2014 at 14:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .