## Fast Distance formula?

Member
Posts: 281
Joined: 2009.04
Post: #1
Well hello again everyone, my 3D game is working.

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 ~
Moderator
Posts: 1,563
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?
Member
Posts: 281
Joined: 2009.04
Post: #3
Well it's not working...

~ Bring a Pen ~
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 ~
Moderator
Posts: 1,563
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?
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

~ Bring a Pen ~
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.

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!

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

~ Bring a Pen ~
Member
Posts: 146
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

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/mysteriouspants
Moderator
Posts: 3,587
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. ... must be a glitch in the matrix.
Member
Posts: 146
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. ... 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.

Everyone's favourite forum lurker!
https://github.com/mysteriouspants
Member
Posts: 281
Joined: 2009.04
Post: #12
Quote:glitch in the matrix.

I love that film

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 ~