Jump to content
  • Advertisement

kiniport

Member
  • Content Count

    25
  • Joined

  • Last visited

Community Reputation

130 Neutral

About kiniport

  • Rank
    Member
  1. kiniport

    Caluclating a characters heading

    heading=normalize(velocity) or, heading=normalize(destination-current_position)
  2. kiniport

    ArtificialSort

    Release mode. Yeah, I was surprised too.
  3. kiniport

    ArtificialSort

    Promit, using: void ArtificialQuickSort(int *array, int nor); runs much faster than: void ArtificialQuickSort(vector<int> &array, int nor); with your example code. I assume the reason it's so much faster is the extra level of indirection of dereferencing a vector. Here are my times(best time for each): std::sort 1.885 Artificial Sort 1.449 Artificial Sort, strictly comparison based(meja=temp1) 1.469 Artificial Sort(taking vector&) 2.467 Radix Sort 0.333 With the following code: Sorts.h #ifndef SORTS_H_9d5940fd_e455_4702_b35a_6483f93e8b2e #define SORTS_H_9d5940fd_e455_4702_b35a_6483f93e8b2e #pragma once #include "SortData.h" #include <algorithm> template<int shift,int bucket_size> void RadixPass(int *src,int *dest,int size) { int counts[bucket_size]; int i; for(i=0;i<bucket_size;i++) counts=0; for(i=0;i<size;i++) counts[(src>>shift)&(bucket_size-1)]++; int prev=0; for(i=0;i<bucket_size;i++) { int next=prev+counts; counts=prev; prev=next; } for(i=0;i<size;i++) { int val=src; int *b=counts+((val>>shift)&(bucket_size-1)); dest[*b]=val; (*b)++; } } void RadixSort(int *array1,int size) { int *array2=new int[size]; RadixPass<0,256>(array1,array2,size); RadixPass<8,256>(array2,array1,size); RadixPass<16,256>(array1,array2,size); RadixPass<24,256>(array2,array1,size); delete[] array2; } //void ArtificialQuickSort(std::vector<int> &array, int nor) { void ArtificialQuickSort(int *array, int nor) { int levi[256]; int desni[256]; int index = 0; int i = 0; int j = 0; int left = 0; int right = 0; int meja = 0; int left1 = 0; int right1 = 0; int temp1 = 0; int temp2 = 0; int temp = 0; left = 0; right = nor-1; while (left < right){ if (array > array) { temp = array; array = array; array = temp; } left++; right--; } index = 0; levi[index] = 0; desni[index] = nor-1; while ( index >= 0 ) { left = levi[index]; right = desni[index]; temp = right - left; if ( temp > 15 ) { // Main section of ArtificialQuickSort ------------------------------------------- temp1 = array; for ( j = left+1; j <= right; j++) { temp2 = array[j]; if ( temp2 < temp1) { // meja=temp1; meja = ( temp1 + temp2 + 1 ) >> 1; if ( array[ (left + right) >> 1 ] > meja ) { meja = array[ (left + right) >> 1 ]; } left1 = left; right1 = right; for (;;) { while ( array[right1] >= meja ) right1--; while ( array[left1] < meja ) left1++; if (left1>right1) break; temp = array[right1]; array[right1--] = array[left1]; array[left1++] = temp; } desni[index] = --left1; levi[++index] = ++right1; desni[index] = right; goto labelcritticall5; } temp1=temp2; } // End of the main section of ArtificialQuickSort -------------------------------- } else { if ( temp != 0 ) { // InsertionSort ----------------------------------------------------------- temp1 = array; for ( i = left+1; i <= right; ++i ) { temp2 = array; if ( temp1 > temp2 ) { array = temp1; for ( j = i-1; j > left; ) { temp = array[j-1]; if ( temp > temp2 ) array[j--] = temp; else break; } array[j] = temp2; } else { temp1 = temp2; } } // End of InsertionSort ----------------------------------------------------- } } index--; labelcritticall5:; } } #endif SortTest.cpp #include "SortData.h" #include "Sorts.h" #define NOMINMAX #include <windows.h> #include <cstdio> #include <cassert> void RunTest() { ObjectList libValues = GenerateValues( 10000000, 1 << 30 ); ObjectList asValues = GenerateValues( 10000000, 1 << 30 ); ObjectList radValues = GenerateValues( 10000000, 1 << 30 ); DWORD libStart = timeGetTime(); std::sort( libValues.begin(), libValues.end() ); DWORD libEnd = timeGetTime(); DWORD asStart = timeGetTime(); // ArtificialQuickSort(&asValues[0],asValues.size()); ArtificialQuickSort(asValues,asValues.size()); DWORD asEnd = timeGetTime(); DWORD radStart = timeGetTime(); RadixSort(&radValues[0],radValues.size()); DWORD radEnd = timeGetTime(); if(!IsSorted(libValues)) printf( "Library FAILED.\n" ); if(!IsSorted(asValues)) printf( "Artifical FAILED.\n" ); if(!IsSorted(radValues)) printf( "Radix FAILED.\n" ); //output the results printf( "Library time: %.3f\n", (libEnd-libStart) / 1000.0f ); printf( "Artificial time: %.3f\n", (asEnd-asStart) / 1000.0f ); printf( "Radix time: %.3f\n", (radEnd-radStart) / 1000.0f ); printf( "\n" ); } int main() { for( int i = 0; i < 10; ++i ) { RunTest(); } return 0; }
  4. kiniport

    Problem with this timer code?

    Your formula is wrong. It should look like this: time_in_msec = ((HighResTimer.QuadPart*1000) / TimerFrequency.QuadPart);
  5. I think you want something like this: void cull(int xoff,int zoff,int size) { int view=isBoxInFrustum(x,0.0f,zoff,size,height,size); if(view==1 && size>1) { size/=2; cull(xoff,zoff,size); cull(xoff+size,zoff,size); cull(xoff,zoff+size,size); cull(xoff+size,zoff+size,size); } else { int x,z; for(z=zoff;z<zoff+size;z++) for(x=xoff;x<xoff+size;x++) sectorBuf[z][x]=view; } } Then just do cull(0,0,16); to start.
  6. kiniport

    Normal of a non-convex poly

    Thank you Wasting Time, Newell's method is exactly what I needed(and pretty close to what I had guessed). ;)
  7. kiniport

    Normal of a non-convex poly

    Since its a non-convex polygon, if I take the cross product of a pair of edges that are on a "concave" part of the polygon, the normal will be in the wrong direction. jpetrie: My polygons are planar. Proper triangulation of a non-convex polygon is pretty involved, and definately seems like overkill.
  8. I'm tryinbg to simply and reliably trying to find the normal on a non-convex polygon. Currently, I'm summing the cross product of all neighboring edges, which works for most cases, but not all. Any ideas?
  9. Try keybd_event() Edit: Nevermind, I guess that dosen't work anymore.
  10. I'm not sure, but I think you need to pass NULL for the window handle on GetMessage. Otherwise I think it filters out the WM_QUIT, because I don't think it's associated with the apps window. while (GetMessage(&msg, NULL, 0 , 0))
  11. kiniport

    Number of Edges In Connected Cubes

    This is what I get: (h+1)*w*(d+1) + (w+1)*h*(d+1) + (h+1)*(w+1)*d Simplified(sort of). 3*h*w*d + 2*w*d + 2*h*w + 2*h*d + h + w + d I'm not sure if it's right, but it works for your example.(w=h=2,d=1)
  12. kiniport

    Whats Wrong with this?

    Maybe stdin and cin don't work together?
  13. kiniport

    c++ memory issue

    You could just do this: Foo Foo::doSomething() { Foo result; // Do stuff to result. return result; }
  14. You could calculate the speed at a fixed time step(like 60hz) and interpolate. mult=ln(.9)/60 while(dt > 1/60th of a sec) { speed=speed*mult } speed_est=speed-speed*(1-mult)*dt*60 [Edited by - kiniport on December 16, 2005 2:53:44 AM]
  15. kiniport

    Experiment with a (real) ant.

    Quote: Given a finite number of queens, and an infinite probability for a mutation to be detrimental, what pops into your logic that's the logical result? I agree most mutations would probably kill the colony. Just like most mutations in a dog would kill the dog. But there are many more ant colonies than there are dogs, and I'm sure the life of a queen is alot shorter. So I imagine ant colonies could evolve alot faster than a large animal like a dog.
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!