Sign in to follow this  
Monkan

Spatial Hashing C++

Recommended Posts

Hi,

I've implemented spatial hashing before in XNA but now I would like to get some nice reusable code I can use in C++.

I was following this tutorial - [url="http://www.gamedev.net/page/resources/_//fsweet-snippet/spatial-hashing-r2697"]http://www.gamedev.n...l-hashing-r2697[/url]

and I have read up about the std::hash_map so I thought this might give me some benefits.
The problem I have run into is that the tutorial suggests using a point as the key so the spatial hashing can be 'sparse' instead of having a pre-defined grid structure.
But when I try to query the std::hash_map to see if a certain key already exists it gives me lots of errors along the lines of:


>c:\program files\microsoft visual studio 10.0\vc\include\xfunctional(125): error C2784: 'bool std::operator <(const std::_Tree<_Traits> &,const std::_Tree<_Traits> &)' : could not deduce template argument for 'const std::_Tree<_Traits> &' from 'const Point'
1> c:\program files\microsoft visual studio 10.0\vc\include\xtree(1885) : see declaration of 'std::operator <'
1> c:\program files\microsoft visual studio 10.0\vc\include\xfunctional(124) : while compiling class template member function 'bool std::less<_Ty>::operator ()(const _Ty &,const _Ty &) const'
1> with
1> [
1> _Ty=Point
1> ]

I presume this is because Point is my own structure so it cannot perform its checks in the map. Can anyone please suggest a way around this as if I want the spatial hashing to be 'sparse' then I really need to store a point as the index and not just a single value i.e. int.

Here is my code so far if it helps, the error is coming in the InsertObjectPoint function:

HashTable.h
[code]
#pragma once
#include <hash_map>
#include <map>
#include <list>
#include "Maths\Vector2.h"
#include "Maths\Vector3.h"
#include "BaseObject.h"

struct Point
{
int x, y;
};
class HashTable
{
public:
HashTable(int argCellSize);
HashTable(int argCellSize, int argWidth, int argHeight);
~HashTable(void);

private:
int cellSize;
bool sparse;
std::hash_map<Point, std::list<BaseObject*>> table;

int width, height;

// Methods
Point Hash(const Vector3f& position);
void InsertObjectPoint(BaseObject* object);
//void InsertObjectBox(BaseObject* object);
};
[/code]


HashTable.cpp
[code]

#include "HashTable.h"


HashTable::HashTable(int argCellSize)
{
cellSize = argCellSize;
sparse = true;
}
HashTable::HashTable(int argCellSize, int argWidth, int argHeight)
{
cellSize = argCellSize;
width = argWidth;
height = argHeight;
sparse = false;
}


HashTable::~HashTable(void)
{
}

Point HashTable::Hash(const Vector3f& position)
{
Point returnPoint;
returnPoint.x = (int)(position.x / cellSize);
returnPoint.y = (int)(position.y / cellSize);
return returnPoint;
}
//
void HashTable::InsertObjectPoint(BaseObject* object)
{
Point key = Hash(object->GetPosition());
if(table.find(key) != table.end())
{
table[key].push_back(object);
}
else
{
std::list<BaseObject*> newList;
table[key] = newList;
table[key].push_back(object);
}

}
[/code]

Many thanks.

Share this post


Link to post
Share on other sites
Ok I just got it to compile by making the key a pointer to a Point, is this wise or will it cause me numerous errors down the line somewhere???

EDIT:: Sorry, that doesnt work, the comparison does not return if the key is present because Im creating a new one so the address in memory isnt the same, me being stupid, sorry.

Thanks

Share this post


Link to post
Share on other sites
[quote name='Monkan' timestamp='1298385858' post='4777529']
Ok I just got it to compile by making the key a pointer to a Point, is this wise or will it cause me numerous errors down the line somewhere???

EDIT:: Sorry, that doesnt work, the comparison does not return if the key is present because Im creating a new one so the address in memory isnt the same, me being stupid, sorry.

Thanks
[/quote]

I'm guessing it is related to the fact that you have no methods to compare points to each other, so ==, <, >, whatever else is probably undefined.

edit: the pointer didn't work because it tests if they are in the same memory location then, not if they are actually equal.

Share this post


Link to post
Share on other sites
Yeah, that sounds about right.

I've tried it with my own Vector2 class which has overloaded operators for == and != and it still doesn't work.

I'm not sure how I would do a < or > check on a 2 point vector though as there are 2 separate values to check.

Can you suggest another way I might implement that tutorial in C++?? Should I just get rid of the std::hash_map and try making my own?

Thanks for the reply.

Share this post


Link to post
Share on other sites
[quote name='Monkan' timestamp='1298386687' post='4777533']
Yeah, that sounds about right.

I've tried it with my own Vector2 class which has overloaded operators for == and != and it still doesn't work.

I'm not sure how I would do a < or > check on a 2 point vector though as there are 2 separate values to check.

Can you suggest another way I might implement that tutorial in C++?? Should I just get rid of the std::hash_map and try making my own?

Thanks for the reply.
[/quote]

Did you get the same error with the vector2 class?

Share this post


Link to post
Share on other sites
If you want to use a class with stdext::hash_map, you need to provide an appropriate traits class for the key type as the third template parameter. It should implement the same interface as the [url=http://msdn.microsoft.com/en-us/library/1s1byw77(v=VS.100).aspx]hash_compare[/url] class. For a point type you generally implement operator()(const Point &, const Point &) as a lexicographic comparison.

Share this post


Link to post
Share on other sites
Sorry for the late reply, I've been a bit busy the past few days.

So SiCrane do you mean I have to create my own 'hash_compare' class which uses the Traits class? I'm a bit confused as to how to do this.
The MSDN gives the hash_compare as:
[code]
template<class Key, class Traits = less<Key> >
class hash_compare
{
Traits comp;
public:
const size_t bucket_size = 4;
const size_t min_buckets = 8;
hash_compare( );
hash_compare( Traits pred );
size_t operator( )( const Key& _Key ) const;
bool operator( )(
const Key& _Key1,
const Key& _Key2
) const;}
[/code]
[font="arial, verdana, tahoma, sans-serif"][size="2"]I'm confused as to what you mean, so I should make my own class which I use as the 3rd template parameter? [/size][/font]
[font="arial, verdana, tahoma, sans-serif"][size="2"]And should I use the () instead of < so where the current hash_compare has [/size][/font]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[size="2"][font="arial, verdana, tahoma, sans-serif"][/font][font="arial, verdana, tahoma, sans-serif"]template<class Key, class Traits = less<Key> >[/font][/size]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[size="2"][font="arial, verdana, tahoma, sans-serif"][/font][font="arial, verdana, tahoma, sans-serif"]Should I put something like:[/font][/size]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[font="arial, verdana, tahoma, sans-serif"][size="2"]template<class Key, class Traits = ()<Key> >[/size][/font]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[size="2"][font="arial, verdana, tahoma, sans-serif"][/font][font="arial, verdana, tahoma, sans-serif"]And then make sure in point class it has a () operator which compares the two points?[/font][/size]
[size="2"][font="arial, verdana, tahoma, sans-serif"][/font][font="arial, verdana, tahoma, sans-serif"]Can you explain a bit more please?[/font][/size]
[size="2"][font="arial, verdana, tahoma, sans-serif"][/font][font="arial, verdana, tahoma, sans-serif"]Thanks.[/font][/size][font="arial, verdana, tahoma, sans-serif"] [/font][font="arial, verdana, tahoma, sans-serif"] [/font][font="arial, verdana, tahoma, sans-serif"] [/font]

Share this post


Link to post
Share on other sites
OK, still a bit confused but have a look at what I've got so far and if someone could tell me if I'm on the right tracks that would be very nice.

HashTable.h
[code]

#pragma once
#include <hash_map>
#include <list>
#include "Maths\Vector2.h"
#include "Maths\Vector3.h"
#include "BaseObject.h"

class Point
{
public:
// Constructors
Point(void) : x(0), y(0), z(0) { }; // Set all values to zero as default
int x, y, z;

// Bool == Operator
bool operator == (const Point& argPoint)
{
if(x == argPoint.x &&
y == argPoint.y &&
z == argPoint.z)
{
return true;
}
return false;
}
private:
};

class MyHashCompare : public stdext::hash_compare <Point>
{
public:
MyHashCompare();
size_t operator( )( const Point& Key ) const; // This is a hash function
bool operator () (const Point& Key1, const Point& Key2) const
{
if(Key1.x == Key2.x &&
Key1.y == Key2.y)
{
return true;
}
return false;
}

private:
};

class HashTable
{
public:
HashTable(int argCellSize);
HashTable(int argCellSize, int argWidth, int argHeight);
~HashTable(void);

void InsertObjectPoint(BaseObject* object);

private:
int cellSize;
bool sparse;
std::hash_map<Point, std::list<BaseObject*>, MyHashCompare> table;

int width, height;

// Methods
Point Hash(const Vector3f& position);
};
[/code]


HashTable.cpp
[code]

#include "HashTable.h"

HashTable::HashTable(int argCellSize)
{
cellSize = argCellSize;
sparse = true;
}
HashTable::HashTable(int argCellSize, int argWidth, int argHeight)
{
cellSize = argCellSize;
width = argWidth;
height = argHeight;
}

HashTable::~HashTable(void)
{
}

Point HashTable::Hash(const Vector3f& position)
{
Point returnPoint;
returnPoint.x = (int)(position.x / cellSize);
returnPoint.y = (int)(position.y / cellSize);
return returnPoint;
//return Vector2i((int)(position.x / cellSize), (int)(position.y / cellSize));
}
void HashTable::InsertObjectPoint(BaseObject* object)
{
Point key = Hash(object->GetPosition());
if(table.count(key) > 0)
{
table[key].push_back(object);
}
else
{
std::list<BaseObject*> newList;
table[key] = newList;
table[key].push_back(object);
}
}
[/code]


It's still not compiling and giving me the errors:
[code]

1> LINK : C:\Users\Monkey\Desktop\FinalProject\Debug\FinalProject.exe not found or not built by the last incremental link; performing full link
1>HashTable.obj : error LNK2019: unresolved external symbol "public: __thiscall MyHashCompare::MyHashCompare(void)" (??0MyHashCompare@@QAE@XZ) referenced in function "public: __thiscall stdext::hash_map<class Point,class std::list<class BaseObject *,class std::allocator<class BaseObject *> >,class MyHashCompare,class std::allocator<struct std::pair<class Point const ,class std::list<class BaseObject *,class std::allocator<class BaseObject *> > > > >::hash_map<class Point,class std::list<class BaseObject *,class std::allocator<class BaseObject *> >,class MyHashCompare,class std::allocator<struct std::pair<class Point const ,class std::list<class BaseObject *,class std::allocator<class BaseObject *> > > > >(void)" (??0?$hash_map@VPoint@@V?$list@PAVBaseObject@@V?$allocator@PAVBaseObject@@@std@@@std@@VMyHashCompare@@V?$allocator@U?$pair@$$CBVPoint@@V?$list@PAVBaseObject@@V?$allocator@PAVBaseObject@@@std@@@std@@@std@@@3@@stdext@@QAE@XZ)
1>HashTable.obj : error LNK2019: unresolved external symbol "public: unsigned int __thiscall MyHashCompare::operator()(class Point const &)const " (??RMyHashCompare@@QBEIABVPoint@@@Z) referenced in function "protected: unsigned int __thiscall std::_Hash<class std::_Hmap_traits<class Point,class std::list<class BaseObject *,class std::allocator<class BaseObject *> >,class MyHashCompare,class std::allocator<struct std::pair<class Point const ,class std::list<class BaseObject *,class std::allocator<class BaseObject *> > > >,0> >::_Hashval(class Point const &)const " (?_Hashval@?$_Hash@V?$_Hmap_traits@VPoint@@V?$list@PAVBaseObject@@V?$allocator@PAVBaseObject@@@std@@@std@@VMyHashCompare@@V?$allocator@U?$pair@$$CBVPoint@@V?$list@PAVBaseObject@@V?$allocator@PAVBaseObject@@@std@@@std@@@std@@@3@$0A@@std@@@std@@IBEIABVPoint@@@Z)
1>C:\Users\Monkey\Desktop\FinalProject\Debug\FinalProject.exe : fatal error LNK1120: 2 unresolved externals
[/code]


Not too sure what I need to do. Any help is much appreciated.

Thanks

Share this post


Link to post
Share on other sites
Did you add HashTable.cpp to your project? :)
(I've missed that step a few times myself...)

[b]Important![/b]
The hash comparison function needs to return "less than", not "equals".

[b]Recommendations[/b]
Save yourself some trouble by using hash_multimap, which allows you to insert multiple elements into a key without having to maintain per-key object containers. At the very least use a hash_map of lists instead of a hash_map of pointers to lists. (Right now you have a memory leak.)

Implement Point::operator< instead of a custom hash_compare:

[code]Point::operator<(const Point &rhs)
{
if (x < rhs.x)
return true;
else if (x > rhs.x)
return false;
if (y < rhs.y)
return true;
else if (y > rhs.y)
return false;
if (z < rhs.y)
return true;
return false;
}
[/code]

Share this post


Link to post
Share on other sites
Thanks for the reply.

[quote]
[color="#1C2837"][size="2"]At the very least use a hash_map of lists instead of a hash_map of pointers to lists. (Right now you have a memory leak.)[/size][/color]
[/quote]


Am I not keeping a hash_map of lists of pointers to BaseObjects? And not a hash_map of pointers to lists?

[color="#666600"][color="#000000"]std[/color]::[/color][color="#000000"]hash_map[/color][color="#666600"]<[/color][color="#660066"]Point[/color][color="#666600"],[/color][color="#000000"] std[/color][color="#666600"]::[/color][color="#000000"]list[/color][color="#666600"]<[/color][color="#660066"]BaseObject[/color][color="#666600"]*>,[/color] [color="#660066"]MyHashCompare[/color][color="#666600"]>[/color][color="#000000"] table[/color][color="#666600"];[/color]

I've got it to compile but it doesn't work correctly because I'm not too sure what I need to put in this function:
[code]

size_t operator( )( const Point& Key ) const // This is a hash function
{
return 0;
}
[/code]


This is what I have:
[code]

class Point
{
public:
// Constructors
Point(void) : x(0), y(0), z(0) { }; // Set all values to zero as default
int x, y, z;

// Bool == Operator
bool operator == (const Point& argPoint) const
{
if(x == argPoint.x &&
y == argPoint.y &&
z == argPoint.z)
{
return true;
}
return false;
}
bool operator < (const Point &rhs) const
{
if (x < rhs.x)
return true;
else if (x > rhs.x)
return false;
if (y < rhs.y)
return true;
else if (y > rhs.y)
return false;
if (z < rhs.y)
return true;
return false;
}

private:
};

class MyHashCompare : public stdext::hash_compare <Point>
{
public:
MyHashCompare() {}
size_t operator( )( const Point& Key ) const // This is a hash function
{
return 0;
}
bool operator () (const Point& Key1, const Point& Key2) const
{
if(Key1 < Key2)
{
return true;
}
return false;
}

private:
};
[/code]


Sorry if I'm being a bit dumb, I'm finding some of this stuff quite hard to grasp.
Thanks for the patience and help.

EDIT: Sorry I was being stupid, it does seem to work now with the < instead of the == but I'm still not sure what I need to put in the function:

[code]

size_t operator( )( const Point& Key ) const // This is a hash function
{
return 0;
}
[/code]

and what its purpose is.

Thanks

[font="Courier New"] [/font]

[font="Arial"][size="2"] [/size][/font]

Share this post


Link to post
Share on other sites
[quote name='Monkan' timestamp='1298570456' post='4778527']
Am I not keeping a hash_map of lists of pointers to BaseObjects? And not a hash_map of pointers to lists?

[color="#666600"][color="#000000"]std[/color]::[/color][color="#000000"]hash_map[/color][color="#666600"]<[/color][color="#660066"]Point[/color][color="#666600"],[/color][color="#000000"] std[/color][color="#666600"]::[/color][color="#000000"]list[/color][color="#666600"]<[/color][color="#660066"]BaseObject[/color][color="#666600"]*>,[/color] [color="#660066"]MyHashCompare[/color][color="#666600"]>[/color][color="#000000"] table[/color][color="#666600"];
[/color][/quote]

Indeed you are! :lol:

(Reading comprehension fail... )

...

Now that you have operator< in your Point class, the default hash_compare may be sufficient. Try removing the MyHashCompare class and see what happens.

...

By the way, hash_map will create a list instance for you the first time you reference a given key with [], so you don't have to do that yourself.

Using std::hash_multimap may still a good idea since all the list management gets furled into the container. The interface is a bit different, though, and what you have now does work.

Share this post


Link to post
Share on other sites
way2lazy2care:

Thanks for the link, I think I get it all now.

kdmiller3:

[quote]
[color=#1C2837][size=2](Reading comprehension fail... )[/size][/color]
[color=#1C2837][size=2][/size][/color][/quote]

No problems, happens to me all the time. I've had a look at [color=#1C2837][size=2]hash_multimap and it seems like a good way but I've got this working now so I'm going to have a cup of tea and leave it as it is.[/size][/color]
[color=#1C2837][size=2]
[/size][/color]
[color=#1C2837][size=2]Thanks all for your help, you learn something new every day eh?? (or at least you should)[/size][/color]
[color=#1C2837][size=2]
[/size][/color]
[color=#1C2837][size=2]Cheers[/size][/color]

Share this post


Link to post
Share on other sites
Sorry to post again but this really isnt working.

So I get what everything does now (I think) and I've got to specify a hash function.

When I said before it was working, it wasn't really because I was just returning 0 from my hash function:

[code]

size_t operator( )( const Point& key ) const // This is a hash function
{
return 0;
}
[/code]


But really what I need to do is turn a 3 dimensional point into a single unique returnable value.
Any ideas???
I had a google about and nothing seems that helpful.

Thanks.

Share this post


Link to post
Share on other sites
Ohhh, right. FNV-1a is a decent choice since it doesn't need lookup tables like CRC32:

[code]
unsigned int HashFNV1a(void *data, size_t size, unsigned int hash = 2166136261)
{
for (unsigned char *p = (unsigned char *)data; p < (unsigned char *)data + size; ++p)
{
hash ^= *p
hash *= 16777619;
}
return hash;
}
[/code]

So:

[code]
size_t operator()(const Point& key) const
{
return HashFNV1a(&key, sizeof(key));
}
[/code]

Share this post


Link to post
Share on other sites
Wow, thanks,

I'd never seen ^= used before, XOR is it?
Very interesting method, the code doesn't like me though.
It says "type const Point * is incompatible with type void *"

and


error C2662: 'MyHashCompare::HashFNV1a' : cannot convert 'this' pointer from 'const MyHashCompare' to 'MyHashCompare &'
1> Conversion loses qualifiers

Not too sure what this second one could mean as the class itself is MyHashCompare so the function shouldn't be complaining about that. Unless I've done something stupid again??

Here's my HashCompare class again if it helps:
[code]

class MyHashCompare : public stdext::hash_compare <Point>
{
public:
MyHashCompare() { }
enum
{ // parameters for hash table
bucket_size = 4, // 0 < bucket_size
min_buckets = 512 // min_buckets = 2 ^^ N, 0 < N
};
unsigned int HashFNV1a(void *data, size_t size, unsigned int hash = 2166136261)
{
for (unsigned char *p = (unsigned char *)data; p < (unsigned char *)data + size; ++p)
{
hash ^= *p;
hash *= 16777619;
}
return hash;
}

size_t operator()(const Point& key) const
{
return HashFNV1a(&key, sizeof(key));
}

inline bool operator () (const Point& Key1, const Point& Key2) const
{
return Key1 < Key2;
}
//static int nextHashValue;
private:

};
[/code]


Thanks

Share this post


Link to post
Share on other sites
HashFNV1a doesn't need to be a member of MyHashCompare; it can be a free function since it's a general utility that can hash any data (hence the void*). If you want to keep it as a member, though, you should make it const:

[code]
unsigned int HashFNV1a(void *data, size_t size, unsigned int hash = 2166136261) const
[/code]

Share this post


Link to post
Share on other sites
The [url="http://isthe.com/chongo/tech/comp/fnv/"]FNV page[/url] suggests "XOR folding" the hash value when you need fewer bits of it, but hash_compare doesn't have access to the hash table size so it doesn't know how many bits to use. I doubt it will matter much in practice, though. It might cause a few more hash collisions behind the scenes and degrade lookup performance slightly, but [url="http://www.strchr.com/hash_functions"]a fast hash can more than make up for that[/url].

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this