// Collision Detection Tests
//
// What is best -
//   ordinary quadratic collision detection
//   quadratic collision detection with buckets
//   n.logn collision detection
//   n.logn collision detection with buckets
//
// Author  Matthew Caryl
// Created 11.5.97

#include <iostream.h>

#define null 0L

class Bot
{
    public:
    
    long x;
    long y;
    long r;
    
    long dx;
    long dy;
    
    bool collision;
};
typedef Bot* BotP;

void initialiseRandom(void);
long random(long range);
void tick(BotP bots, long number, long range);
BotP createBots(long number, long radius, long range);
void collision(BotP bots, long number);
long cycle(long number, long size, long time, long range);

unsigned long seed;

void initialiseRandom(void)
{
    seed = 0;
}

long random(long range)
{
    seed = seed * 1103515245 + 12345;
    return (unsigned long) ((seed / 65536) & (range - 1));
}

void tick(BotP bots, long number, long range)
{
    BotP    p;
    
    for (p = bots + number - 1; p >= bots; p--)
        {
        p->x = (p->x + p->dx) & (range - 1);
        p->y = (p->y + p->dy) & (range - 1);
        }
}

BotP createBots(long number, long radius, long range)
{
    BotP bots = new Bot[number];
    
    BotP p;
    
    for (p = bots + number - 1; p >= bots; p--)
        {
        p->x = random(range);
        p->y = random(range);
        p->r = radius;
        p->dx = random(15) - 7;
        p->dy = random(15) - 7;
        }
    return bots;
}

void collision(BotP bots, long number)
{
    for (BotP p = bots + number - 1; p >= bots; p--)
        for (BotP q = p - 1; q > bots; q--)
            {
            long dx = (p->x - q->x);
            long dy = (p->y - q->y);
            long dr = (p->r + q->r);
            
            if (dx * dx + dy * dy <= dr * dr)
                {
                p->collision = true;
                q->collision = true;
                }
            }
}

long cycle(long number, long size, long time, long range)
{
    initialiseRandom();
    
    BotP bots = createBots(number, size, range);
    long count;
    long start, finish, ticks;
        
    count = 0;
    start = ticks = TickCount();
    finish = TickCount() + time * 60;
    
    while (ticks < finish)
        {
        collision(bots, number);
        tick(bots, number, range);
        count++;
        ticks = TickCount();
        }
    
    delete bots;
    
    return count;
}

void main(void)
{
    long time = 1;
    long count;
    long base_range = 128;
    
    for (long number = 2; number <= 512; number *= 4, base_range *= 2)
        for (long size = 4, range = base_range; size <= 32; size *= 2, range *= 2)
            {
            count = cycle(number, size, time, range);
            cout << time << " seconds " << number << " objects of size " << size << " gives density of ";
            cout << 100 * (3.14 * size * size * number) / (range * range);
            cout << "% - " << count << " cycles." << "\r";
            }
}