Jump to content
  • Advertisement
Sign in to follow this  
Monkan

Spatial Hashing C++

This topic is 2726 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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 - http://www.gamedev.n...l-hashing-r2697

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

#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);
};



HashTable.cpp


#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);
}

}


Many thanks.

Share this post


Link to post
Share on other sites
Advertisement
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

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


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

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.


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 hash_compare 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:

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;}

[font="arial, verdana, tahoma, sans-serif"]I'm confused as to what you mean, so I should make my own class which I use as the 3rd template parameter? [/font]
[font="arial, verdana, tahoma, sans-serif"]And should I use the () instead of < so where the current hash_compare has [/font]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[font="arial, verdana, tahoma, sans-serif"][/font][font="arial, verdana, tahoma, sans-serif"]template<class Key, class Traits = less<Key> >[/font]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[font="arial, verdana, tahoma, sans-serif"][/font][font="arial, verdana, tahoma, sans-serif"]Should I put something like:[/font]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[font="arial, verdana, tahoma, sans-serif"]template<class Key, class Traits = ()<Key> >[/font]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[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]
[font="arial, verdana, tahoma, sans-serif"][/font][font="arial, verdana, tahoma, sans-serif"]Can you explain a bit more please?[/font]
[font="arial, verdana, tahoma, sans-serif"][/font][font="arial, verdana, tahoma, sans-serif"]Thanks.[/font][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


#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);
};



HashTable.cpp


#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);
}
}



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


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



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...)

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

Recommendations
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:

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;
}

Share this post


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


[color="#1C2837"]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.)
[/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="#000000"]hash_map[color="#666600"]<[color="#660066"]Point[color="#666600"],[color="#000000"] std[color="#666600"]::[color="#000000"]list[color="#666600"]<[color="#660066"]BaseObject[color="#666600"]*>, [color="#660066"]MyHashCompare[color="#666600"]>[color="#000000"] table[color="#666600"];

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:


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



This is what I have:


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:
};



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:



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


and what its purpose is.

Thanks

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

[font="Arial"] [/font]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!