[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: [pygame] quadtrees



Gerrit Holl <gerrit@nl.linux.org>:
>
[snip]
> 
> I am afraid I do not understand what you are saying, I do not have
> enough background knowledge:

Sorry -- I just tried to be brief and ended up being cryptic :/

> I have never heard of "Voronoi tesselation"
> or "Delaunay triangulations" and don't know what "NN-queries" are, but
> this does give me some more terms to Google for.

By NN-query I simply meant "nearest neighbor-queries", that is, given
a query point (e.g. the player position), finding the closest object
of some kind. (I seemed to recall that this was the topic in question
a while back, although in collision detection you'd rather want the
"closest pair" problem.)

If we just skip the Delaunay triangulations for now (they are sort of
an inverse of Voronoi tesseleations anyway), we're left with the
Voronoi stuff... A Voronoi tesselation (or diagram) is simply a
segmentation of the plane (or some other space) into regions (bounded
or unbounded polygons), each linked to one of the points of the
database (i.e. the objects in the game). The region consists of all
position that have the given objects as the closest one, so if a point
is found to be within a given region, you also know which object is
closest.

A Voronoi diagram can be calculated in O(n log n) time.

Based on the diagram/tesselation, you can create a point location
structure (a sort of an index for finding out in which polygon a point
is located), also in O(n log n) time, IIRC. Using this, you can locate
a point in a given polygon in O(log n) time.

Given these two structures, you can find out in which Voronoi cell a
point is located, and thereby which object is the closest one, in
O(log n) time. Updating the structure should (again, IIRC) take O(log
n) time.

But the algorithms aren't exactly simple, so this might be overkill...

Anyway... I still think partitioning the plane into rectangular cells
and doing a simple search of those (using hashing or rounding or
something) seems like the easiest solution...

By the way: If the problem is collision detection (that is, closest
pair and not nearest neighbor), there is an elegant algorithm which is
not based on indexing (and is meant to be used when you cannot do any
preprocessing). It's the divide-and-conquer closest pair algorithm.  A
description can be found here:
http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf (among other
places)

[snip]

-- 
Magnus Lie Hetland                "In this house we obey the laws of
http://hetland.org                 thermodynamics!"    Homer Simpson