WPF Canvas and Collision Detection

Question

I'm trying to position multiple children canvasses randomly on a parent canvas. I don't want the sibling canvasses to overlap (or collide) so I am using some collision detection.

I'm obviously doing something wrong as there are collisions but can't put my finger on it.

My draw method (being called every second)

    private void draw(int args)
    {
        parent.Children.Clear();

        List<MyCanvas> children = fetchManyChildren(100);
        Random rand = new Random();

        foreach (MyCanvas child in children)
        {
            child.xPos = nextDouble(rand, 0, parent.ActualWidth - child.Width);
            child.yPos = nextDouble(rand, 0, parent.ActualHeight - child.Height);

            foreach (MyCanvas sibling in parent.Children)
            {
                while (child.collidesWith(sibling))
                {
                    child.xPos = nextDouble(rand, 0, parent.ActualWidth - child.Width);
                    child.yPos = nextDouble(rand, 0, parent.ActualHeight - child.Height);
                }
            }

            Canvas.SetLeft(child, child.xPos);
            Canvas.SetTop(child, child.yPos);

            parent.Children.Add(child);
        }
    }

A couple of helper methods:

    private List<MyCanvas> fetchManyChildren(int amount)
    {
        List<MyCanvas> children = new List<MyCanvas>(amount);

        Random rand = new Random();

        for (int i = 1; i <= amount; i++)
        {
            double size = nextDouble(rand, 1, MAX_SIZE);

            MyCanvas child = new MyCanvas(0, 0, size, size);

            child.Background = randomBrush(rand);

            children.Add(child);
        }

        return children;
    }

    private double nextDouble(Random rand, double min, double max)
    {
        return min + (rand.NextDouble() * (max - min));
    }

A class deriving from Canvas which allows me to give x/y position to a Canvas and check for collisions:

public class MyCanvas : Canvas
{
    public double xPos = 0;
    public double yPos = 0;

    public MyCanvas(double x, double y, double w, double h)
    {
        this.xPos = x;
        this.yPos = y;
        this.Width = w;
        this.Height = h;
    }

    public bool collidesWith(MyCanvas p)
    {
        double bottom = this.yPos + this.Height;
        double top = this.yPos;
        double left = this.xPos;
        double right = this.xPos + this.Width;

        return !((bottom < p.yPos) ||
                 (top > p.yPos + p.Height) ||
                 (left > p.xPos + p.Width) ||
                 (right < p.xPos));
    }
}

Answer 1

When you change the random position when a collision occurs you have forgotten to go back to checking against all the children again in the parent.Children .... if you don't then you might have a collision that's undetected because your iterator is already past that item.

You need something like the code below.

Note you need to be careful....

You should alter your/my code in some way to handle the case where it is impossible to place your child in an un-occuppied area i.e. there just isn't any free room left.

As you are relying on the "random" number generation to eventually find the "free" positions.....the amount of time and "luck" this takes to discover areas could put you in a situation where it takes an inordinate or infinite amount of time...a better algorithm that "finds" free areas would be desirable.

private void draw(int args)
    {
        parent.Children.Clear();

        List<MyCanvas> children = fetchManyChildren(100);
        Random rand = new Random();

        foreach (MyCanvas child in children)
        {
            while(true)
            {
                // Choose a random place on Canvas we would like to place child

                child.xPos = nextDouble(rand, 0, parent.ActualWidth - child.Width);
                child.yPos = nextDouble(rand, 0, parent.ActualHeight - child.Height);

                // Now see if it collides with ones already on Canvas

                bool bCollisionDetected = false;

                foreach (MyCanvas sibling in parent.Children)
                {
                    bCollisionDetected = child.collidesWith(sibling);

                    if (bCollisionDetected)
                        break;
                }

                if (!bCollisionDetected) // Was able to place child in free position
                    break;
            }

            Canvas.SetLeft(child, child.xPos);
            Canvas.SetTop(child, child.yPos);

            parent.Children.Add(child);
        }
    }