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\$
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 '14 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.