Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

share|improve this question
add comment

4 Answers

up vote 4 down vote accepted

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

share|improve this answer
    
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*. –  Steve Blackwell Jul 3 '12 at 13:21
1  
@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. –  bummzack Jul 3 '12 at 13:36
add comment

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.

share|improve this answer
    
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. –  ver Jul 3 '12 at 6:32
    
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. –  ver Jul 3 '12 at 6:36
    
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. –  bummzack Jul 3 '12 at 6:42
    
@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. –  ver Jul 3 '12 at 7:08
2  
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"). –  bummzack Jul 3 '12 at 7:35
show 2 more comments

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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