Normally you know where you start. For instance a respawn point holds the position x,y and the cell ID. Then you keep track of the cell each time you cross an opening.

But if for one reason or another you need a function
f(x,y) = cell ID, well it's just a typical path finding, with any cell chosen as a start. Now if you want to accelerate, I suppose you can cache the info to apply the search in real time to start closer to the searched cell. Just build a 2D (or) 3D array of sample points or a quadtree/octree. Then you get the closest cell to any point. However that should not be very practical. What's the point in applying f() if the request position is inside a wall. If for instance you want an object appear at a random position in your level, just roll the dice and select a celll rather than x,y coordinates.

[edited by - Charles B on March 23, 2004 4:30:06 AM]

If all your cells are convex, it should be easy, shouldn''t it? First an AABB around each cell, possibly in a tree; feed in your point to get a small group of cells (because doubtless they''ll overlap in places). Then take a line passing through your point and the center of a cell, and see how many times it collides with the cell polygons; if it''s an odd number of times (and for convex hulls, that number will always be one), then that''s the cell you''re in.

That does require that there be no leaks, though.