Searching for vertexes...
Not quite, more like this:
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.
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.
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.
So, I should instead store my vertices as:
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:
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 ~
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.
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.
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.
Ohhh, right, use structs...
I was going to use structs but I didn't see how to implement them. Just to vertify:
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 ~
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
Thanks again
~ Bring a Pen ~
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.
~ Bring a Pen ~
Possibly Related Threads...
Thread:  Author  Replies:  Views:  Last Post  
Finding the height of a point on a given list of vertexes?  mikey  10  8,734 
Jan 4, 2010 05:36 AM Last Post: mikey 

Searching Headers & Documentation  OneSadCookie  0  3,001 
May 1, 2006 11:31 PM Last Post: OneSadCookie 

Searching Within .app For Files  Nick  4  4,255 
Jun 5, 2005 02:46 PM Last Post: AnotherJake 