current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 1 down vote favorite

Am using a while loop to find an index within a 1D array, is there an easier, less-time-consuming and/or mathmatical way to find the index?

Consider the next grid:

 4   o
     |\  
     | \ 
     |  \
 3   o---o
     |\  |\  
     | \ | \ 
     |  \|  \
 2   o---o---o
     |\  |\  |\  
     | \ | \ | \ 
     |  \|  \|  \
 1   o---o---o---o
     |\  |\  |\  |\  
     | \ | \ | \ | \ 
     |  \|  \|  \|  \
 0   o---o---o---o---o

     0   1   2   3   4

To find an index in the triangular grid within a 1D array I have the next function:

//int size = 5;
int getindex( int x, int y )
{

    int columnCount = size;
    while( y-- > 0 ) x += columnCount--;

    return x;

}

The array (The numbers within the parenthesis are the coordinates and to simplify your view, in reality the (x,y) is in its whole the data):

pointdata data[ 15 ] = {
    (0,0), (1,0), (2,0), (3,0), (4,0),
    (0,1), (1,1), (2,1), (3,1),
    (0,2), (1,2), (2,2),
    (0,3), (1,3),
    (0,4),
};
share|improve this question

1 Answer 1

up vote 0 down vote accepted

This is rather problem to sum numbers between n and m, which is pretty widely known: it is sum of numbers 1 to m minus sum of numbers 1 to n(n-1 infact, but it gets eliminated in the code) plus x, ofcourse. In your example, it is:

index = columnCount * ( columnCount + 1 ) / 2 - ( columnCount - y ) * ( columnCount - y + 1 ) / 2 ) + x;
plus, since column count is static (presumably), you can pre-cumpute the first part or even better just use total length of your array.

share|improve this answer
    
Column count is indeed static but what do you mean by pre-compute the first part. The first row? –  brainoverflow Jan 18 at 1:40
    
The point is the idea what you need - compute total count of members on previous rows. Code is irrelevant. You can also compute average of largest row and y-1 row and multiply it be y. –  wondra Jan 18 at 1:40
    
@brainoverflow sum from 1 to m is static. Sum from 1 to n is based on y. –  wondra Jan 18 at 1:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.