Archived

This topic is now archived and is closed to further replies.

Choosing a suitable data-structure for A *

This topic is 5047 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

I''m working with pathfinding for my game, and am puzzled by a problem with datastructures for the closed and open sets. I want to use binary heap priorityqueues (implemented as arrays), but a problem arises when I update a node that''s in a heap. If I know the index it''s easy to update the heap in log(n) time - so I thought about backing it with a hashmap mapping keys to heap array indexes. Now my problem is: which hashfunction would be suitable for a pair of integers (map position)? My best bet so far is a bitwise XOR of x and y - but that only gives me sqrt(n) time lookup in the hashtable, constant time would be nicer *** For Java games and Java related resources, go to http://www.javaengines.dk ***

Share this post


Link to post
Share on other sites
It''s trivial when you think about it. Imagine your x and y coordinates are a 2D grid of positions. Now imagine you had to give each position a unique number. The first row would be 0 to p, the second row would be p+1 to 2p, the 3rd row would be 2p+1 to 3p, etc. So the formula would be

x + max_x * y

where max_x is the number of possible values of x. This will give you a zero collision rate in the hash table. If zero collisions is actually problem due to the implementation of the hash table, then reduce max_x.

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

Share this post


Link to post
Share on other sites