Find nearest tile of type x

Question

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)?

Answer 1

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).

Answer 2

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.

Answer 3

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.

Answer 4

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.