Algorithm for finding nearest object on 2D grid

Viewed 31298

Say you have a 2D grid with each spot on the grid having x number of objects (with x >=0). I am having trouble thinking of a clean algorithm so that when a user specifies a coordinate, the algorithm finds the closest coordinate (including the one specified) with an object on it.

For simplicity's sake, we'll assume that if 2 coordinates are the same distance away the first one will be returned (or if your algorithm doesn't work this way then the last one, doesn't matter).

Edit: A coordinate that is 1 away must be either 1 up, down, left or right. Coordinates that are away diagonally are 2.

As a side note, what is a great, free, online reference for algorithms?

5 Answers

A simple BFS from starting coordinate in 4 directions is sufficient to find the closest point on the grid with the object.

Related