I have thought of a certain approach to the shortest path problem for Grid structures(Well suited for RTS''s, RPG''s and especially MMORPGs), and I was wondering if anyone has seen references to something similar before. The idea is to create a hash formula for any grid layout for grids of a given size. Then we precalculate the first move for the layouts and store them in chunks inside a vector. This way we can simply hash the layout surrounding the player at runtime and find the best move with a quick binary search. This method deals well with moving obstructions (Other mobiles) and is very fast, and I think it offers some optimization opportunities. On the other hand it does consume some memory. I just finished a test that filled out the first million permutations of a 7*7 grid in 10,000 table entries (there are around 10**13 possible permutations). This was a big drop from 250,000 entries, which I achieved through changing the hashing formula. Maybe changing it more could result in more compact results(I already have some ideas) Is the picture clear or should I go a bit more in depth? Do you know of similar approaches? Is it even worth the trouble? Peace Out!

This is just a different way of storing an optimal policy for a given grid. Indeed, you are likely to find that hash functions have previously been used for storing policy information. That shouldn''t stop you from investigating your method further though.

Timkin