Searching for vertexes...

Sage
Posts: 1,482
Joined: 2002.09
Post: #16
Not quite, more like this:
Code:
int index = hashing_function(x, y);
LinkedListOrArrayOrWhatever *vertexes = hash_table[index%hash_table_length];

The hashing function takes the x and y cell coordinates and scrambles them together into a single number. The idea is to make a function that cells that are near each other in the grid won't be near each other in the hash table. I do this by multiplying the x and y coordinates by two different large prime numbers and then XORing the result. It works quite well.

Code:
static inline cpHashValue
hash_func(cpHashValue x, cpHashValue y, cpHashValue n)
{
        return (x*2185031351ul ^ y*4232417593ul) % n;
}

Spatial hashes are a bit more complicated though if you are dealing with objects that overlap more than one cell at a time. For just a list of vertexes that are effectively sizeless you don't really run into those issues though.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Member
Posts: 281
Joined: 2009.04
Post: #17
So, I should instead store my vertices as:

Code:
vertex[index] = hash(x_cell,y_cell);

So then I have a list of vertexes and their corresponding cells. But when it comes to my physics function (lacking a better name) ....?

Code:
player_hash_cell = hash(player_x_cell,player_y_cell);

while (vertexcount >= index)
{
if (vertex[index] == player_hash_cell)
closestdistance = // blahblahblah

// do the more intensive checks...

}

~ Bring a Pen ~
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #18
No no. I think you misunderstood. The hash function generates an index for a cell based on cell_x and cell_y, so that you can use a small 1D array to represent all cells everywhere instead of using a 2D or 3D array.

You don't store vertexes in that 1D array (or 2D or 3D array) but a list of vertexes.

Code:
typedef struct IntList {
  int *arr;
  int size;
} IntList;

IntList intListList[10] = {}; // fill with zeros

int size = 2;
intListList[0].arr = malloc(sizeof(int)*size);
intListList[0].size = size;
intListList[0].arr[0] = 1;
intListList[0].arr[2] = 2;

That code makes an array of 10 lists. The first list has two numbers in it, and the rest are empty. You might want to spend some time looking at basic data structures such as linked lists and such if this is proving tricky for you.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Member
Posts: 281
Joined: 2009.04
Post: #19
Ohhh, right, use structs...

I was going to use structs but I didn't see how to implement them. Just to vertify:

Code:
struct list_of_verts {
int vertexes[1]; // reallocate sizes later...
int size;
}
Code:
int

// physics.c

if () // how do I find which box the vertex is in? All I have is an index in the actual drawing array... And a nicely sorted hash indexed array!

~ Bring a Pen ~
Quote this message in a reply
Member
Posts: 281
Joined: 2009.04
Post: #20
Oops, sorry, didn't mean that. I've got it working now, so, thanks for all the help. I'll post a demo soon.

Thanks again

~ Bring a Pen ~
Quote this message in a reply
Member
Posts: 281
Joined: 2009.04
Post: #21
Sorry to bump an old thread, but just so you know I did get it working but it took two hours to load and got a <1 fps. Sad

~ Bring a Pen ~
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Finding the height of a point on a given list of vertexes? mikey 10 5,481 Jan 4, 2010 05:36 AM
Last Post: mikey
  Searching Headers &amp; Documentation OneSadCookie 0 2,226 May 1, 2006 11:31 PM
Last Post: OneSadCookie
  Searching Within .app For Files Nick 4 3,139 Jun 5, 2005 02:46 PM
Last Post: AnotherJake