// 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 Bucket;

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

class Bucket
{
    public:
    Bucket* north;
    Bucket* east;
    Bucket* south;
    Bucket* west;
    
    long top;
    long left;
    long bottom;
    long right;
    
    BotP bots;
};
typedef Bucket* BucketP;

void initialiseRandom(void);
long random(long range);
void tick(BucketP buckets, long width, long height, BotP bots, long number, long range);
void addBot(BucketP bucket, BotP bot);
void subBot(BucketP bucket, BotP bot);
BotP createBots(BucketP buckets, long width, long height, long number, long radius, long range);
BucketP createBuckets(long width, long height, long range);
void deleteBuckets(BucketP buckets, long width, long height);
long cycle(long number, long size, long time, long range, int width, int height);
void collisionBot(BucketP bucket, BotP bot);
void collision(BotP bots, long number);

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(BucketP buckets, long width, long height, BotP bots, long number, long range)
{
    BotP    p;
    long w = range / width;
    long h = range / height;
    
    for (p = bots + number - 1; p >= bots; p--)
        {
        p->x = (p->x + p->dx) & (range - 1);
        p->y = (p->y + p->dy) & (range - 1);
        BucketP home = &buckets[(p->y * width / range) * width + (p->x * width / range)];
        if (home != p->home)
            {
            subBot(p->home, p);
            p->home = home;
            addBot(p->home, p);
            }
        }
}

void collisionBot(BucketP bucket, BotP bot)
{
    BotP q = bucket->bots;
    
    for (BotP p = q->next; p != q; p = p->next)
        {
        long dx = (p->x - bot->x);
        long dy = (p->y - bot->y);
        long dr = (p->r + bot->r);
        
        if (dx * dx + dy * dy <= dr * dr)
            {
            p->collision = true;
            bot->collision = true;
            }
        }
}

void collision(BotP bots, long number)
{
    for (BotP p = bots + number - 1; p >= bots; p--)
        {
        BucketP home = p->home;
        subBot(home, p);
        collisionBot(home, p);
        if (home->north != null && home->top > p->y - p->r)
            collisionBot(home->north, p);
        if (home->west != null && home->left > p->x - p->r)
            collisionBot(home->west, p);
        if (home->south != null && home->bottom < p->y + p->r)
            collisionBot(home->south, p);
        if (home->east != null && home->right < p->x + p->r)
            collisionBot(home->east, p);
        addBot(home, p);
        }
}

void addBot(BucketP bucket, BotP bot)
{
    bot->next = bucket->bots->next;
    bot->prev = bucket->bots;
    bucket->bots->next->prev = bot;
    bucket->bots->next = bot;
}

void subBot(BucketP, BotP bot)
{
    bot->next->prev = bot->prev;
    bot->prev->next = bot->next;
}

BotP createBots(BucketP buckets, long width, long height, long number, long radius, long range)
{
    BotP bots = new Bot[number];
    
    for (BotP 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;
        p->home = &buckets[(p->y * width / range) * width + (p->x * width / range)];
        addBot(p->home, p);
        }
    return bots;
}

BucketP createBuckets(long width, long height, long range)
{
    BucketP buckets = new Bucket[width * height];
    
    for (int y = height - 1; y >= 0; y--)
        for (int x = width - 1; x >= 0; x--)
            {
            BucketP bucket = &buckets[y * width + x];
            
            BotP b = new Bot;
            b->next = b;
            b->prev = b;
            bucket->bots = b;
            
            // what neighbours
            bucket->north = (y > 0) ? &buckets[(y - 1) * width + x] : null;
            bucket->east = (x < width - 1) ? &buckets[y * width + (x + 1)] : null;
            bucket->south = (y < height - 1) ? &buckets[(y + 1) * width + x] : null;
            bucket->west = (x > 0) ? &buckets[y * width + (x - 1)] : null;
            
            // what range
            bucket->top = range * y / height;
            bucket->left = range * x / width;
            bucket->bottom = range * (y + 1) / height - 1;
            bucket->right = range * (x + 1) / width - 1;
            }
    return buckets;
}

void deleteBuckets(BucketP buckets, long width, long height)
{
    for (int y = height - 1; y >= 0; y--)
        for (int x = width - 1; x >= 0; x--)
            delete buckets[y * width + x].bots;
    delete buckets;
}

long cycle(long number, long size, long time, long range, int width, int height)
{
    initialiseRandom();
    
    BucketP buckets = createBuckets(width, height, range);
    BotP bots = createBots(buckets, width, height, 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(buckets, width, height, bots, number, range);
        count++;
        ticks = TickCount();
        }
    
    delete bots;
    deleteBuckets(buckets, width, height);
    
    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, 4, 4);
            cout << time << " seconds " << number << " objects of size " << size << " gives density of ";
            cout << 100 * (3.14 * size * size * number) / (range * range);
            cout << "% - " << count << " cycles." << "\r";
            }
}