distance lookup

[hunguptodry]

Hi,

1) I'm storing the distances between 100 points in an array. this is used in path finding.

2) I put them in an array for lookup so as to achieve something like ...
distance(i,j) == _distance[i*100+j];

3) now obviously distance(i,j) == distance(j,i) and distance(i,i) == 0.

4) so I'm wasting more than half the array.

5) is there a better way to do this.

6) perhaps using row strips with some index manipulations.

7) is this really worthwhile or should i simply waste the memory.

thanks

[Sol_HSA]

With such a low number of indexes, assuming you're writing form modern PC:s, such "waste" is probably worth the hassle.

But if you want to save some space, sort the parameters before indexing =)

_distance[MIN(i,j)*100+MAX(i,j)]

The saving will still be minimal, and you get bunch of branches per index; it might even be cheaper to just calculate the distance every time..

[hunguptodry]

1) yeah, 100 is kind of small. i suppose the number of nodes could grow up to 1000. so 1000x1000 = a million floats. is that significant enough to care in todays hardware?

2) distance is not euclidean. it is a path finding heuristic.

[Sol_HSA]

I guess you could create a hash table for the values, where (i,j) and (j,i) return the same value.. and before lookup, check that if i==j, just return zero.

[Nils Pipenbrinck]

The requirement is just a special case of symetric matrix compression. You can do this with triangle number sequences: http://www.research.att.com/%7Enjas/sequences/A000217 Also a google search on symetric matrix storage gives good hits. The main difference to the symetric matrix compression is that you don't need the diagonal where i == j.

I came up with a index calculation function that takes any i,j pair and turns it into an array-index. <i,j> will return the same index as <j,i>. The special case of i==j is handled by returning zero as an index (so put a zero in there, or whatever cost you like for pathfinding).

The tricky part was to write code that evaluates min (i,j) and max (i,j) fast and in a way that hints the compiler to transform it into a branchless version. The code below does just that. It still contains two compares but the compilers I've tested with generate branchless code with a good deal of parallelism.

That should execute very fast on all superscalar CPU's


int GetTriangularIndex (int i, int j)
{
int tmp = ((i - j) & -(i < j));
int min = j + tmp;
int max = i - tmp;
int id = ((max * max - max)>>1) + min + 1;
return (i==j) ? 0 : id;
}

Calculating the storage requirements of a matrix of size N*N is (N*N - N + 2)/2. Or you can just invoke the code with: GetTriangularIndex (N-1, N-2).

[.oisyn]

That's a nice min/max trick, gotta remember that :).

[hunguptodry]

1) thanks to Sol, Nils.

2) actually, my googling led me to sparse matrices. interesting read.

3) the triangle thing looks promising. i'll try that.