Searching for vertexes...
Post: #16
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.
Post: #17
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 ~
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.
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.
Post: #19
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 ~
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
Thanks again
~ 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 | 4,397 |
Jan 4, 2010 05:36 AM Last Post: mikey |
|
| Searching Headers & Documentation | OneSadCookie | 0 | 1,949 |
May 1, 2006 11:31 PM Last Post: OneSadCookie |
|
| Searching Within .app For Files | Nick | 4 | 2,820 |
Jun 5, 2005 02:46 PM Last Post: AnotherJake |
|