6
\$\begingroup\$

I currently have an array of tiles which makes up the tilemap (stored as an int array) and I want an NPC to be able to move itself to the nearest tile of type X (ie find the nearest tree and chop it down). What's the best algorithm to use to find the nearest tile of a certain type given a location (x,y)?

\$\endgroup\$

4 Answers 4

5
\$\begingroup\$

Problems like this can easily be solved by using Dijkstra's algorithm. See this answer for an explanation of how it works.

The others suggested a flood-fill, but that won't work (or at least won't be optimal) if there are obstacles (not trees) somewhere along the path. If there are only a few items to find, you could also use A* with an appropriate heuristic (eg. min. straight-line distance to items).

Update: If you don't want to implement Djikstra's algorithm yourself but have an A* implementation in your path-finding library, you could also set the A* heuristic to a constant value (eg. that it always returns 0). That way, A* will behave the same as Djikstra's.

Also note that in the examples I linked to, there's usually one goal-node to find. But it works just as well when searching for a "type" of node (just end the search whenever you find a tile of your desired type).

\$\endgroup\$
2
  • \$\begingroup\$ Dijkstra's is the right way to go for simple pathfinding. It works even better if the tiles have different travel speeds, like moving over a paved path is faster than moving over grassland. If, on the other hand, you have a huge tileset and Dijkstra's is taking too long, then use A*. \$\endgroup\$ Jul 3, 2012 at 13:21
  • 1
    \$\begingroup\$ @stevehb It's not really about the size of the tileset (amount of nodes) or "simple" vs. "complex" pathfinding. A* is using a heuristic to predict the best direction to go, thus potentially speeding up the search drastically. If you're searching for any tile of type X, then applying a good heuristic might be less efficient or even impossible compared to an uninformed search such as Djikstra's. \$\endgroup\$
    – bummzack
    Jul 3, 2012 at 13:36
4
\$\begingroup\$

If you know absolutely nothing about where such a tile could be I would suggest a sort of breadth first style floodfill:

PathNode start;
PathNodeType query; // the type we are looking for
Queue<PathNode> queue; // gives us a breadth first style search
HashSet<PathNode> visited; // tiles we already visited
queue.Push(start)

while(queue.Count > 0){
    PathNode current = queue.Pop();
    foreach(PathNode neighbour in current.Neighbours)
    {
        if(!visited.Contains(neighbour))
        {
            visited.Add(neighbour);
            if(neighbour.Type == query)
            {
                return neighbour;
            }
            else if(neighbour.IsWalkable)
            {
                queue.Push(neighbour);
            }
        }

    }
}

This algorithm first searches the tiles closest to start and then starts circling wider and wider over the walkable tiles until a tile of the given tile is found. By first checking if a neighbour tile is of the given type and only then checking if it is walkable we can also found tiles that are next to walkable tiles but arent walkable itself.

\$\endgroup\$
7
  • \$\begingroup\$ My words exactly. I'll just add a nice way of visualizing the algorithm: it behaves as if you started pouring water on your starting tile, which then flows into adjacent (accessible) tiles in all directions. (Hence, 'floodfill'.) The first tile of the sought type to be flooded is your nearest match. \$\endgroup\$
    – ver
    Jul 3, 2012 at 6:32
  • \$\begingroup\$ You should keep in mind, though, the special case here - when there are multiple equidistant tiles of the target type. (I.e. they are the same distance from your starting tile.) The algorithm provided by @RoyT just returns whichever one is first chosen by the PathNode.Neighbours implementation. \$\endgroup\$
    – ver
    Jul 3, 2012 at 6:36
  • \$\begingroup\$ You need some sort of "visited" flag, otherwise your code will loop endlessly. Also this approach will fall short (won't find the optimal path) if there are obstacles to consider. \$\endgroup\$
    – bummzack
    Jul 3, 2012 at 6:42
  • \$\begingroup\$ @bummzack yes, it may not find the optimal path, but that's irrelevant. The asker wanted an algorithm for finding the nearest tile that specifies the given condition; not a pathfinding one. \$\endgroup\$
    – ver
    Jul 3, 2012 at 7:08
  • 2
    \$\begingroup\$ In a tile-based environment, this flood-fill is basically an implementation of Djikstra's anyway. It just needs to keep track of costs to also get the path to the found tile (to satisfy the requirement of the OP: "I want an NPC to be able to move itself to the nearest tile of type X"). \$\endgroup\$
    – bummzack
    Jul 3, 2012 at 7:35
0
\$\begingroup\$

One approach is a simple breadth first search. If you've heard of A*, this is sort of the basis for that algorithm. Except you don't have a known goal location, so you can't direct the search in any one direction So you search all directions at once! There's some implementation details and nice little examples for tile based games here.

\$\endgroup\$
0
\$\begingroup\$

Could you add some more details like what language you are in? I mean I guess there could be a general algorithm.

If you have these different tiles in classes per se, you could add a move function in your NPC class or method. It would have to "see" the tile, so you could give it a tile radius and say if anything within X amount of squares of the NPC is this ID type of tile, then move to its x and y location.

An example in an OO language like Java:

    public Tile Tree;

    Tree.cutTree(NPC.getX, NPC,getY, Tree.getX, Tree.getY)

    public void cutTree(int NPCX, int NPCY, int treeX, int treeY)
    {
      if(treeX >= NPCX >= 5)
      {
         if(treeX >= NPCX >= 5)
         {
            NPC.move(treeX - 1, treeY - 1);
         }
      }
    }

Again I don't know EXACTLY what numbers to add and whether you have a move() function, but basically I would use the x and y position of the two tiles (if you can access each tree tile in the array).

The if statements are where I would use like the edge of the frame or screen but you have to remember if the map of tiles is big enough you could be accessing a tree tile across the map.

\$\endgroup\$

You must log in to answer this question.

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