0
\$\begingroup\$

The setting is a game in a 2D gridlike labyrinth/maze. I'm looking at pathfinding algorithms such as A* and Dijkstra. I can't figure out how to have my game characters find the nearest resources. All the info I found regarding pathfinding deal with reaching a goal node. However, there are many potential goals so how do I find the path to the nearest resource? At first I thought running pathfinding for each potential goal, but that seems too time consuming (for 4-5 characters with 50 resource nodes). The characters are all competing for the resources so getting there fast is priority.

I understand that Dijkstra solves the distances to all nodes in the grid- so I think the solution lies there, but still the examples I found still require a goal node. So I'm confused how to distill paths from the node calculation.

Can someone explain how to handle pathfinding where finding the nearest goalnode is part of the problem?


Edit:

The solution I ended up using is this: As mentioned by ali ahmadi in the comments below, it proved quick enough to do a distance search on the potential goals and then do a A* pathfinding to that goal.

It does not answer the question exactly, but the AI players mimic the human player behaviour close enough which is fine for my game. I might get back to this when I need the AI to be more brutal...

\$\endgroup\$
  • 1
    \$\begingroup\$ Do you want to find precisely nearest resource or find fast near enough resource? This is the most important question and you should include answer to it in your post. \$\endgroup\$ – wondra Aug 20 '15 at 16:16
  • \$\begingroup\$ @wondra The area is a maze/labyrinth, the characters are competing for the resources so getting there fastest is priority over accuracy. \$\endgroup\$ – Felsir Aug 20 '15 at 16:31
  • \$\begingroup\$ You have missed a key concept - Dijkstra terminates when the goal condition is met. In your case, the goal condition is that a pellet has been reached. Run Dijkstra and terminate once a pellet has been reached. Check each clock pulse that no other agent has picked up the currently targeted pellet. \$\endgroup\$ – Pieter Geerkens Aug 20 '15 at 20:45
  • \$\begingroup\$ I was under the impression that Dijkstra evaluated the entire graph, where Astar terminates as the goal was reached? \$\endgroup\$ – Felsir Aug 21 '15 at 6:46
  • \$\begingroup\$ @Felsir: Dijkstra terminates when you tell it to terminate; that is often the whole graph, but not if you set an alternate termination condition. \$\endgroup\$ – Pieter Geerkens Aug 21 '15 at 8:27
1
\$\begingroup\$

modify a* considering goal as a set of points instead of a single point. If the euristic function is the distance, the each step of a* chose the path that minimize the closest point distance. Check also this

\$\endgroup\$
  • \$\begingroup\$ So if I understand correctly, the endpoint condition could be a set, so when one point is reached in that set, it is automatically the nearest point? \$\endgroup\$ – Felsir Aug 20 '15 at 14:46
  • 1
    \$\begingroup\$ If a* grants always shortest path, yes \$\endgroup\$ – dnk drone.vs.drones Aug 20 '15 at 19:53
1
\$\begingroup\$

here you go, here is a implantation of the A* in Action script 3, i wrote this a few years ago, there are a few things such as grid, grid view and node classes that i'm using which really don't have anything to do with the A* algorithm itself, and are all used for the graphic and visual side of the work, still if you are interested i can put them here so you can use them,
please read the codes very carefully, this class, finds the nearest and shortest path inside a grid! exactly what you need, so spend sometime reading it and if you still have problem understanding it, ask and i will help you.

package 
{

    public class AStar 
    {
        private var _open: Array;
        private var _closed: Array;
        private var _startNode: Node;
        private var _endNode: Node;
        private var _grid: Grid;
        private var _path: Array;
        //private var _heuristic: Function = manhattan;
        //private var _heuristic: Function = euclidian;
        private var _heuristic: Function = diagonal;
        private var _straightCost: Number = 1.0;
        private var _diagCost: Number = Math.SQRT2;

        public function AStar() 
        {

        }

        public function findPath(grid: Grid):Boolean
        {
            _grid = grid;
            _open = new Array();
            _closed = new Array();
            _startNode = _grid.startNode;
            _endNode = _grid.endNode;

            _startNode.g = 0;
            _startNode.h = _heuristic(_startNode);
            _startNode.f = _startNode.g + _startNode.h;

            return search();
        }

        public function search():Boolean
        {
            var node: Node = _startNode;
            while (node != _endNode)
            {
                var startX: int = Math.max(0, node.x - 1);
                var endX: int = Math.min(_grid.numCols - 1, node.x + 1);
                var startY: int = Math.max(0, node.y - 1);
                var endY: int = Math.min(_grid.numRows - 1, node.y + 1);

                for (var i: int = startX; i <= endX; i++)
                {
                    for (var j: int = startY; j <= endY; j++)
                    {
                        var test: Node = _grid.getNode(i, j);
                        if (test == node || !test.walkable || !_grid.getNode(node.x, test.y).walkable || !_grid.getNode(test.x, node.y).walkable) continue;

                        var cost: Number = _straightCost;
                        if (!(test.x == node.x) || (test.y == node.y))
                        {
                            cost = _diagCost
                        }

                        var g: Number = node.g + cost;
                        var h: Number = _heuristic(test);
                        var f: Number = g + h;
                        if ((isOpen(test) || isClosed(test)))
                        {
                            if (test.f > f)
                            {
                                test.f = f;
                                test.g = g;
                                test.h = h;
                                test.parent = node;
                            }
                        }
                        else
                        {
                            test.f = f;
                            test.g = g;
                            test.h = h;
                            test.parent = node;
                            _open.push(test);
                        }
                    }
                }

                _closed.push(node);
                if (_open.length == 0)
                {
                    trace("No Path Found");
                    return false;
                }

                _open.sortOn("f", Array.NUMERIC);
                node = _open.shift() as Node; // takeing the first element of array(which is the lowest cost!)
            }

            buildPath();
            return true;
        }

        private function buildPath():void
        {
            _path = new Array();
            var node: Node = _endNode;
            _path.push(node);

            while (node != _startNode)
            {
                node = node.parent;
                _path.unshift(node); // add to the begining of array
            }
        }

        public function get path():Array
        {
            return _path;
        }

        private function isOpen(node: Node):Boolean
        {
            for (var i: int = 0; i < _open.length; i++)
            {
                if (node == _open[i])
                    return true;
            }

            return false;
        }

        private function isClosed(node: Node):Boolean
        {
            for (var i: int = 0; i < _closed.length; i++)
            {
                if (node == _closed[i])
                    return true;
            }

            return false;
        }

        private function manhattan(node: Node):Number
        {
            return  Math.abs(node.x - _endNode.x) * _straightCost + 
                    Math.abs(node.y + _endNode.y) * _straightCost;
        }

        private function euclidian(node: Node):Number
        {
            var dx: Number = node.x - _endNode.x;
            var dy: Number = node.y - _endNode.y;
            return Math.sqrt(dx * dx + dy * dy) * _straightCost;
        }

        private function diagonal(node: Node):Number
        {
            var dx: Number = Math.abs(node.x - _endNode.x);
            var dy: Number = Math.abs(node.y - _endNode.y);
            var diag: Number = Math.min(dx, dy);
            var straight: Number = dx + dy;
            return _diagCost * diag + _straightCost * (straight - 2 * diag);    
        }

        public function get visited():Array
        {
            return _closed.concat(_open);
        }
    }
}

i think i should explain this, inside the codes, in class declaration
you see

//private var _heuristic: Function = manhattan;
//private var _heuristic: Function = euclidian;
 private var _heuristic: Function = diagonal;    

these are cost functions! each uses a different method, for example one uses,
if its left or right or top or bottom cell, it will cost 1 and if its topLeft, topRight, bottomLeft, bottomRight Cells it will cost 1.5 point, and it will uses these point to find the nearest path!
there is also custom costing as well ! why ? , for example every where is ground and some parts are water cells, you can say ground cells worth 1 point and water cells worth 3 point, meaning if you pass 3 ground cells it equals passing one water cell, and all these also will be considered in your nearest path Algorithm ,
and using it, you can easily make a game with different fields and paths
there is also

if (test == node || !test.walkable || !_grid.getNode(node.x, test.y).walkable || !_grid.getNode(test.x, node.y).walkable) continue;  

this part which has walkable variable for each node, if its true, the node can be used as a path! and if its false that node IS NOT WALKABLE this way you can even build walls and impossible to walk objects in some cells

here is a link to my Final project that uses this class (it's swf file which is uploaded online, so you can simply watch the output as long as you have flash player)
Make sure you watch this :
http://www.fastswf.com/HIa1W9M
hopefully what i said helps you.
Good luck.

\$\endgroup\$
  • \$\begingroup\$ Not sure if I read it correctly, but this code finds the path to a predefined goal? The thing is, I don't know the end node at the start of the algorithm. \$\endgroup\$ – Felsir Aug 20 '15 at 14:31
  • \$\begingroup\$ @Felsir, what do you mean by that ?, at some point you should know where your goal is ! or if you don't know your final goal , you still must have some sub goals to go , right ?, in that case you can simply find the path to the first goal and then after reaching it, you switch to the next one , or if none of them is what you need, please explain with more detail, maybe i can help. \$\endgroup\$ – ali ahmadi Aug 20 '15 at 15:15
  • \$\begingroup\$ By not knowing the goal I mean this: Consider a maze much like pacman. The player wants to go to the nearest pellet. There are no subgoals, the algorithm should find the path to the nearest pellet. Thus at the start the only 'known' is the player location and the pellets in the maze. \$\endgroup\$ – Felsir Aug 20 '15 at 15:46
  • 1
    \$\begingroup\$ @Felsir, ok i think i got it, first do a simple distance based search on all the goals! , use a simple for loop, it does not cost a lot! then after you find the nearest goal, find the closest path with A*, Note: this should work easily for 100 goal or even more! but if your goals are a lot , i mean like 1k or more, do a grid base search or quad tree search , that way you can reduce it to nothing easily. \$\endgroup\$ – ali ahmadi Aug 21 '15 at 7:50
  • \$\begingroup\$ This is what I ended up doing. A simple distance check on the goals works nicely to mimic the behaviour I'm looking for. \$\endgroup\$ – Felsir Aug 28 '15 at 12:00
0
\$\begingroup\$

The easiest solution is to use any flood-type algorithm, for example as you mentioned Dijkstra's algorithm. The only difference is the stopping condition:

if(Resources.Any(r => r == node)) { ...}

instead of

if(resource == node) { ...}

you can improve its performance by excluding resources that cannot be possibly reached yet from the check (=found distance is smaller than direct distance) and of course by simplifying the underlying data to graph of nodes and weighted edges.
Personally, I would not suggest A* as it is harder to implement and there can be many special cases in labyrinth leading to flood-type complexity anyway but if you need the little extra performance and/or if you expect the path to be often straightforward I dont see any problem with it.
However, for the fastest solution you can pre-compute all vs all distances in graph using Floyd–Warshall algorithm in n^3 and resolve nearest resource in linear time, more precisely O(1) for each resource. This solution has also the upside of not-having to implement anything as you can use any existing implementation without any modifications.
For finding optimal (or near optimal) solution to find shortest path between many(not just single closest) resources you can also check this question.

\$\endgroup\$

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.