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.

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

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.

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]

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

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]