• Advertisement

kiniport

Member
  • Content count

    25
  • Joined

  • Last visited

Community Reputation

130 Neutral

About kiniport

  • Rank
    Member
  1. Caluclating a characters heading

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

    Release mode. Yeah, I was surprised too.
  3. 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[i]=0; for(i=0;i<size;i++) counts[(src[i]>>shift)&(bucket_size-1)]++; int prev=0; for(i=0;i<bucket_size;i++) { int next=prev+counts[i]; counts[i]=prev; prev=next; } for(i=0;i<size;i++) { int val=src[i]; 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[left] > array[right]) { temp = array[left]; array[left] = array[right]; array[right] = 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[left]; 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[left]; for ( i = left+1; i <= right; ++i ) { temp2 = array[i]; if ( temp1 > temp2 ) { array[i] = 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. 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. 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. 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. 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. Whats Wrong with this?

    Maybe stdin and cin don't work together?
  13. 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. 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