Fast Distance formula?

Member
Posts: 281
Joined: 2009.04
Post: #1
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.

~ Bring a Pen ~
Quote this message in a reply
Moderator
Posts: 1,560
Joined: 2003.10
Post: #2
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?
Quote this message in a reply
Member
Posts: 281
Joined: 2009.04
Post: #3
Well it's not working...

~ Bring a Pen ~
Quote this message in a reply
Member
Posts: 281
Joined: 2009.04
Post: #4
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);

~ Bring a Pen ~
Quote this message in a reply
Moderator
Posts: 1,560
Joined: 2003.10
Post: #5
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?
Quote this message in a reply
Member
Posts: 281
Joined: 2009.04
Post: #6
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

~ Bring a Pen ~
Quote this message in a reply
Moderator
Posts: 133
Joined: 2008.05
Post: #7
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.
Quote this message in a reply
Member
Posts: 281
Joined: 2009.04
Post: #8
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

~ Bring a Pen ~
Quote this message in a reply
Member
Posts: 144
Joined: 2009.11
Post: #9
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!

Everyone's favourite forum lurker!
https://github.com/NSError
Quote this message in a reply
Moderator
Posts: 3,570
Joined: 2003.06
Post: #10
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.
Quote this message in a reply
Member
Posts: 144
Joined: 2009.11
Post: #11
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!

Everyone's favourite forum lurker!
https://github.com/NSError
Quote this message in a reply
Member
Posts: 281
Joined: 2009.04
Post: #12
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.

~ Bring a Pen ~
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Formula for converting angle to vector? komirad 2 9,455 Jul 29, 2011 07:29 AM
Last Post: ThemsAllTook
  Direction formula? TimMcD 2 5,002 Nov 11, 2009 11:42 PM
Last Post: TimMcD
  calculating X and Y coordinates w/ an angle and distance ferum 13 14,446 Jun 25, 2008 10:53 PM
Last Post: rosenth
  Signed distance fields imikedaman 16 9,013 Jul 20, 2007 07:13 PM
Last Post: imikedaman
  Mathmatical formula for integer checking Jones 12 5,358 Jan 24, 2006 01:58 AM
Last Post: zKing