iDevGames Forums
Fast Distance formula? - Printable Version

+- iDevGames Forums (http://www.idevgames.com/forums)
+-- Forum: Development Zone (/forum-3.html)
+--- Forum: Game Programming Fundamentals (/forum-7.html)
+--- Thread: Fast Distance formula? (/thread-573.html)



Fast Distance formula? - mikey - Nov 22, 2009 07:23 AM

Well hello again everyone, my 3D game is working. WowSmile

I won't bother to go into the details but it is enough to say that I have to check the distance between two points in the physics function. I have been using Pythagoras' function, and this works, but very slowly.

Is there a fast distance alternative?
I have read about some very complicated alternatives, but they seem to be way above my skill level.


Fast Distance formula? - ThemsAllTook - Nov 22, 2009 10:03 AM

If you only need to compare two distances to determine if they're nearer/farther than a certain threshold, you can work with squared distances ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) + (z1 - z2) * (z1 - z2)) so you don't have to call sqrt(). Manhattan distance ((x1 - x2) + (y1 - y2) + (z1 - z2)) can give you an estimate that's within a factor of sqrt(2) of accuracy, if an approximation is good enough. However, if you need to accurately measure linear distance between two points, you're pretty much stuck with sqrt().

How many times per frame are you measuring distance that it's actually a bottleneck?


Fast Distance formula? - mikey - Nov 22, 2009 10:11 AM

Well it's not working...


Fast Distance formula? - mikey - Nov 22, 2009 10:32 AM

Thanks, but it is still too slow. Have a look at the source:

The way my game's physics work (just keeping the player on the floor at the moment) are like this:

• At load-time sort each map (level) vertex into a grid cell appropriate to it's position.

• When it's time to get the player's altitude, find the grid cell which the player occupies then search through all vertices in that cell.

• Then return the Y value of the vertex closest to the player in that cell.

Physics.c:

Code:
// The grid is made like this: grid_list[grid_cell].arr[vertex' index]


    cellx = (int) (x/2) ; //
    celly = (int) (y/2) ;  // ^^ get the player's grid cell,
    
    cellhash = hash_func(cellx,celly,100); // then hash it, so it fits in a 1D array.
    
    
    
    
    printf("grid_list[%i].size = %i\n",cellhash,grid_list[cellhash].size);
    counter = 0;
    

    
    while (grid_list[cellhash].size >= counter) // loop through the grid cell looking for verts...
    {
        
        

        if (grid_list[cellhash].size == 0) // empty cell, so return the player's current height
        {
            printf("No verts in cell...\n");
            return y;
        }

                        
                        printf ("No errors found...\n");
                        
        
        
        printf("counter = %i\n",counter
        );
        printf("cellhash = %i\n",cellhash);
        
    
    
        

        
        x1 = mesh->verts[grid_list[cellhash].arr[counter]];        //  )
        y1 = mesh->verts[(grid_list[cellhash].arr[counter])+1];  //   } These lines just get the vertex in the grid cell of the player according to counter
        z1 = mesh->verts[(grid_list[cellhash].arr[counter])+2];  // )
        
        
        printf("x1 = %f\n",x1);
        printf("y1 = %f\n",y1);
        printf("z1 = %f\n",z1);
          
        
        
            
        dist = ((x1-x)*(x1-x)) + ((y1-y)*(y1-y)) + ((z1-z)*(z1-z)); // not the actual distance!
        
        
        
            printf("distance = %f\n",dist);
            if (dist < closestdist)
            {
                bestmatchy = y1;
                closestdist = dist;
                
            }
            else
            {
                
            }
            
        counter++;
    }
    
    
    printf("returning %f\n",bestmatchy);
        return bestmatchy + 2; // add height
        

}

And the part in main.c:

Code:
yp = 0;
printf("yp is %f\n",yp);
    yp +=  getFloor(Lvl1 , xp, yp, zp) + 2;
    printf("yp is now %f\n",yp);
//printf("llamaII %i\n", (getFloor(Lvl1, ux, uy, uz)));
    
    
    glRotatef(pitch, 1.0f, 0.0f, 0.0f);
    glRotatef(heading, 0.0f, 1.0f, 0.0f);
    glTranslatef(-xp, -yp, -zp);



Fast Distance formula? - ThemsAllTook - Nov 22, 2009 11:13 AM

You say "it's still too slow". How are you measuring that? What's Shark telling you? What optimization flags are you using? Have you tried compiling without all the printfs in there?


Fast Distance formula? - mikey - Nov 22, 2009 12:35 PM

Ahah! I removed all the printfs, and it goes normal. I didn't realise printf was that consuming!

P.S It is working smoothly but wrong. Sometimes it flips to underneath the terrain Sad


Fast Distance formula? - longjumper - Nov 22, 2009 12:48 PM

If you are using the iPhone and building on the device, printing to the console is *always* very slow. You can't measure performance with NSLog or printf.

Instead of Shark, I'd suggest Instruments and the CPU sample tool. Build your application, then select Run->Start with Performance Tool->CPU Sampler.


Fast Distance formula? - mikey - Nov 22, 2009 01:05 PM

Ahah! I removed all the printfs, and it goes normal. I didn't realise printf was that consuming!

Thank you very much! SmileSmileSmile

P.S longjumper, I am building on the iMac in C.7


Fast Distance formula? - cmiller - Nov 22, 2009 02:27 PM

mikey Wrote:Ahah! I removed all the printfs, and it goes normal. I didn't realise printf was that consuming!

P.S It is working smoothly but wrong. Sometimes it flips to underneath the terrain Sad

There are two major kinds of output stream: buffered and serial. A buffered I/O stream will append your output to a buffer, only printing every once in a while, or when the stream is flushed. Serial I/O streams will block the thread until the output can be rendered to the terminal (TTY, be it a screen or an SSH session).

Both take time to process, though obviously the serial I/O streams place a significant drain on your performance.

As AnotherJake said, you really should use debugger breakpoints whenever possible. From there you can inspect the entire call stack, all active variables, etc. Familiarize yourself with Shark and Instruments! They're fantastic tools and can save you a lot of time!


Fast Distance formula? - AnotherJake - Nov 22, 2009 03:11 PM

cmiller Wrote:As AnotherJake said...

Hehe, you mean ThemsAllTook. What's really funny about it is that I actually did say that in a reply I was composing, and when I previewed it, I saw ThemsAllTook had already beaten me to it so I cancelled. That happened on both of his posts in this thread. Some kind of weird collective consciousness going on or something. Wacko ... must be a glitch in the matrix.


Fast Distance formula? - cmiller - Nov 23, 2009 01:30 AM

AnotherJake Wrote:Hehe, you mean ThemsAllTook. What's really funny about it is that I actually did say that in a reply I was composing, and when I previewed it, I saw ThemsAllTook had already beaten me to it so I cancelled. That happened on both of his posts in this thread. Some kind of weird collective consciousness going on or something. Wacko ... must be a glitch in the matrix.

Actually I wrote that on my iPod touch, so I couldn't really scroll up that easily to verify.

My bad!


Fast Distance formula? - mikey - Nov 23, 2009 10:43 AM

Quote:glitch in the matrix.

I love that film Smile

P.S The flipping underneath the terrain is caused by the map (The player jumps from closest vertex to closest vert) so it's not a fault in the code.