initial commit

[applet-bots.git] / src / appletbots / World.java

/*
 * Copyright (c) 2002 Erik Rasmussen - All Rights Reserved
 */
package appletbots;

import appletbots.geometry.Point;
import appletbots.geometry.Vector;

import javax.swing.*;
import java.awt.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

/**
 * This class represents a world in which multiple agents can exist and
 * interact with each other or with objects in the world.  The positions and
 * velocities of objects and agents are kept internally.  The positions cannot
 * be accessed by the agents or the objects themselves.  This keeps all agent
 * algorithms completely vector-based and, therefore, scalable.
 *
 * @author Erik Rasmussen
 */
public class World extends JPanel
{
        /**
         * The maximum number of attempts (1000) that should be made trying to add
         * an object randomly to the world.  This is to prevent infinite loops if
         * there is no space for the object.
         */
        protected static final int MAX_ADD_OBJECT_ATTEMPTS = 1000;
        /**
         * A hashtable mapping each object to its location and velocity datum
         */
        protected Map objectsTable = new HashMap();
        /**
         * The number of milliseconds to sleep in between time cycles
         */
        protected int delay = 500;
        /**
         * The thread driving the world
         */
        protected WorldThread thread;
        /**
         * The number of time cycles that have passed
         */
        protected long time = 0;
        /**
         * Registered listeners
         */
        protected List listeners = new ArrayList();
        /**
         * The object that is currently selected
         */
        protected WorldObject selectedObject;
        /**
         * The color to paint the object that is selected
         */
        protected Color selectedObjectColor = Color.yellow;
        /**
         * The color in which to paint the "sight circle" of the selected object
         */
        protected Color selectedSight;

        /**
         * Constructs a new world with the given dimensions
         *
         * @param width  The width of the world in pixels
         * @param height The height of the world in pixels
         */
        public World(final int width, final int height)
        {
                setMinimumSize(new Dimension(width, height));
                setMaximumSize(new Dimension(width, height));
                setBackground(Color.black);
        }

        /**
         * Paints the world (invoked by Swing)
         *
         * @param g The graphics object on which to paint the world
         */
        public void paint(final Graphics g)
        {
                super.paint(g);
                paintObjects(g);
        }

        /**
         * Paints the objects in the world
         *
         * @param g The graphics object on which to paint the objects
         */
        protected void paintObjects(final Graphics g)
        {
                if (selectedSight != null && selectedObject instanceof Agent)
                {
                        g.setColor(selectedSight);
                        final int sight = ((Agent) selectedObject).getSight();
                        final WorldObjectData selectedObjectData = getData(selectedObject);
                        g.drawOval((int) Math.round(selectedObjectData.getLocation().x) - selectedObject.getSize() - sight,
                                   (int) Math.round(selectedObjectData.getLocation().y) - selectedObject.getSize() - sight,
                                   2 * (selectedObject.getSize() + sight),
                                   2 * (selectedObject.getSize() + sight));
                }
                synchronized (objectsTable)
                {
                        for (Iterator iterator = objectsTable.keySet().iterator(); iterator.hasNext();)
                        {
                                final WorldObject object = (WorldObject) iterator.next();
                                // don't paint carried objects
                                if (!(object instanceof CarriableObject && ((CarriableObject) object).getCarriedBy() != null))
                                        paintObject(object, g);
                        }
                }
        }

        /**
         * Paints an individual object in the world
         *
         * @param object The object to paint
         * @param g      The graphics object on which to paint the object
         */
        protected void paintObject(final WorldObject object, final Graphics g)
        {
                final WorldObjectData data = getData(object);
                if (object.equals(selectedObject))
                        g.setColor(selectedObjectColor);
                else
                        g.setColor(object.getColor());

                // paint object
                g.fillOval((int) Math.round(data.getLocation().x) - object.getSize(),
                           (int) Math.round(data.getLocation().y) - object.getSize(),
                           object.getSize() * 2,
                           object.getSize() * 2);

                // paint any objects the current object is carrying
                if (object instanceof CarrierAgent)
                {
                        final CarriableObject[] carriedItems = ((CarrierAgent) object).getInventory();
                        for (int i = 0; i < carriedItems.length; i++)
                                paintObject(carriedItems[i], g);
                }

                if (object instanceof Agent)
                {
                        final Agent agent = (Agent) object;
                        final VectorToDraw[] vectorsToDraw = agent.getVectorsToDraw();
                        for (int i = 0; i < vectorsToDraw.length; i++)
                        {
                                g.setColor(vectorsToDraw[i].color);
                                final Point endPoint = data.getLocation().add(vectorsToDraw[i].vector);
                                g.drawLine((int) Math.round(data.getLocation().x),
                                           (int) Math.round(data.getLocation().y),
                                           (int) Math.round(endPoint.x),
                                           (int) Math.round(endPoint.y));
                        }
                }
        }

        /**
         * Adds an object to a random position in the world.  The object will have
         * an initial speed of 0.
         *
         * @param object The object to add
         * @throws CollisionException Thrown if the object cannot be added randomly
         *                            to the world in MAX_ADD_OBJECT_ATTEMPTS
         */
        public void addObject(final WorldObject object) throws CollisionException
        {
                addObject(object, new Vector(0, 0));
        }

        /**
         * Adds an object to a random position in the world with the given initial
         * velocity
         *
         * @param object   The object to add
         * @param velocity The initial velocity
         * @throws CollisionException Thrown if the object cannot be added randomly
         *                            to the world in MAX_ADD_OBJECT_ATTEMPTS
         */
        public void addObject(final WorldObject object, final Vector velocity) throws CollisionException
        {
                for (int i = 0; i < MAX_ADD_OBJECT_ATTEMPTS; i++)
                {
                        try
                        {
                                addObject(object, getRandomPoint(object.getSize()), velocity);
                                return;
                        }
                        catch (CollisionException e)
                        {
                        }
                        catch (OutOfThisWorldException e)
                        {
                        }
                }
                throw new CollisionException("Tried " + MAX_ADD_OBJECT_ATTEMPTS + " times to add an object randomly and failed.");
        }

        /**
         * Adds an object to the world at the given position with the given initial
         * velocity
         *
         * @param object   The object to add
         * @param location The location to add the object
         * @param velocity The initial velocity
         * @throws CollisionException      Thrown if the location given is at least
         *                                 partially occupied by another object
         * @throws OutOfThisWorldException Thrown if the location given will place
         *                                 at least part of the object outside the
         *                                 boundaries of the world
         */
        public void addObject(final WorldObject object, final Point location, final Vector velocity) throws CollisionException, OutOfThisWorldException
        {
                if (objectsTable.containsKey(object))
                        return; // already have this object
                if (!inWorld(location, object.getSize()))
                        throw new OutOfThisWorldException();
                final WorldObjectData data = new WorldObjectData(location, velocity, object);
                synchronized (objectsTable)
                {
                        for (Iterator iterator = objectsTable.keySet().iterator(); iterator.hasNext();)
                        {
                                final WorldObject otherObject = (WorldObject) iterator.next();
                                final WorldObjectData otherObjectData = getData(otherObject);
                                final double distance = location.distance(otherObjectData.getLocation());
                                if (distance < object.getSize() + otherObject.getSize())
                                        throw new CollisionException(object, otherObject);
                        }
                        objectsTable.put(object, data);
                        if (object instanceof Agent)
                                ((Agent) object).setWorld(this);
                }
        }

        /**
         * Returns a random point in the world
         *
         * @return A random point in the world
         */
        protected Point getRandomPoint()
        {
                return getRandomPoint(0);
        }

        /**
         * Returns a random point in the world within a given distance from the
         * boundaries
         *
         * @param distance The minimum distance from the boundaries that the point
         *                 can be
         * @return A random point in the world within a given distance from the
         *         boundaries
         */
        protected Point getRandomPoint(final int distance)
        {
                return new Point(Math.random() * (getWorldWidth() - distance - distance) + distance,
                                 Math.random() * (getWorldHeight() - distance - distance) + distance);
        }

        /**
         * Removes an object from the world
         *
         * @param object The object to remove
         */
        public void removeObject(final WorldObject object)
        {
                synchronized (objectsTable)
                {
                        objectsTable.remove(object);
                }
        }

        /**
         * Returns the location and velocity data for the given object
         *
         * @param object The object to get the data for
         * @return The location and velocity data for the given object
         */
        protected WorldObjectData getData(final WorldObject object)
        {
                if (object instanceof CarriableObject && ((CarriableObject) object).getCarriedBy() != null)
                        return getData(((CarriableObject) object).getCarriedBy());
                else
                        return (WorldObjectData) objectsTable.get(object);
        }

        /**
         * Returns the velocity for the given object
         *
         * @param object The object to get the velocity of
         * @return The velocity for the given object
         */
        public Vector getVelocity(final WorldObject object)
        {
                return getData(object).getVelocity();
        }

        /**
         * Moves an object
         *
         * @param object The object to move
         */
        private void moveObject(final WorldObject object)
        {
                final WorldObjectData data = getData(object);

                // don't move carried objects
                if (object instanceof CarriableObject && ((CarriableObject) object).getCarriedBy() != null)
                        return;

                if (object instanceof Agent)
                {
                        final Agent agent = (Agent) object;
                        data.setVelocity(data.getVelocity().add(agent.getAcceleration()));
                }
                if (data.getVelocity().getLength() == 0)
                        return;
                final Point newLocation = data.getLocation().add(data.getVelocity());
                // check that new location is in the world
                if (!inWorld(newLocation, object.getSize()))
                {
                        bounceOffWall(object);
                        return;
                }
                else
                {
                        // check for collisions
                        boolean collision = false;
                        final WorldObject aObject = object;
                        final WorldObjectData a = data;
                        for (Iterator iterator = objectsTable.keySet().iterator(); iterator.hasNext();)
                        {
                                final WorldObject bObject = (WorldObject) iterator.next();
                                final WorldObjectData b = getData(bObject);
                                // Define C as the vector from the center of A to the center of B
                                final Vector c = new Vector(a.getLocation(), b.getLocation());
                                final double lengthOfC = c.getLength();

                                //  Make sure A is going to travel far enough to hit B
                                final double aVelocityLength = a.getVelocity().getLength();
                                final double radiiSum = aObject.getSize() + bObject.getSize();
                                if (aVelocityLength < lengthOfC - radiiSum)
                                        continue;
                                // Make sure A is going towards B
                                if (a.getVelocity().dotProduct(c) <= 0)
                                        continue;
                                // Normalize A's velocity vector and call it N
                                final Vector n = a.getVelocity();
                                n.normalize();
                                // Get dot product of N and C.  This is the point along A's path
                                // where it will be closest to B.  We'll call it D.
                                final double d = n.dotProduct(c);
                                // Use the pythagorean theorem to get the value for the square
                                // of the closest distance on V to B, and call it F.
                                // (ie. the shortest distance from V to B is sqrt(F)
                                final double f = lengthOfC * lengthOfC - d * d;
                                // Define T such that "the longest distance A can travel without
                                // hitting B" = D - sqrt(T).  Again by the pythagorean theorem
                                final double radiiSumSquared = radiiSum * radiiSum;
                                final double t = radiiSumSquared - f;
                                // Check if closest point is within the two radii of B.  To save
                                // time, rather than taking the sqrt of F, we'll just square the
                                // other side of the equation
                                if (t < 0)
                                        continue;
                                // if A won't travel far enough to collide with B, there's no
                                // collision
                                final double distanceToCollision = d - Math.sqrt(t);
                                if (aVelocityLength < distanceToCollision)
                                        continue;
                                collision = true;
                                collide(aObject, bObject);
                        }
                        if (!collision)
                                data.setLocation(newLocation);
                }
        }

        /**
         * Called by the WorldThread.  This method does three things: it allows all
         * the agents to observe the world, moves all the objects, and repaints the
         * world.
         */
        public void incrementTime()
        {
                time++;
                for (Iterator iterator = objectsTable.keySet().iterator(); iterator.hasNext();)
                {
                        final WorldObject object = (WorldObject) iterator.next();
                        if (object instanceof Agent)
                                ((Agent) object).observeWorld();
                        moveObject(object);
                        // notify listeners
                        for (int i = 0; i < listeners.size(); i++)
                                ((WorldListener) listeners.get(i)).timeIncremented(time);
                }
                repaint();
        }

        /**
         * Returns the number of milliseconds to wait between time cycles
         *
         * @return The number of milliseconds to wait between time cycles
         */
        public int getDelay()
        {
                return delay;
        }

        /**
         * Sets the number of milliseconds to wait between time cycles
         *
         * @param delay The number of milliseconds to wait between time cycles
         */
        public void setDelay(final int delay)
        {
                this.delay = delay;
        }

        /**
         * Starts the world thread
         */
        public void startThread()
        {
                if (thread == null)
                {
                        thread = new WorldThread(this);
                        thread.start();
                        // notify listeners
                        for (int i = 0; i < listeners.size(); i++)
                                ((WorldListener) listeners.get(i)).threadStarted();
                }
        }

        /**
         * Stops the world thread
         */
        public void stopThread()
        {
                if (thread != null)
                {
                        thread.setRunning(false);
                        thread = null;
                        // notify listeners
                        for (int i = 0; i < listeners.size(); i++)
                                ((WorldListener) listeners.get(i)).threadStopped();
                }
        }

        /**
         * Returns whether or not the world thread is running
         *
         * @return Whether or not the world thread is running
         */
        public boolean isRunning()
        {
                return thread != null && thread.getRunning();
        }

        /**
         * Returns all the objects that can be seen by the given agent, normally
         * called by the given agent himself.
         * <br><br>
         * THIS METHOD WILL NOT RETURN OTHER AGENTS!  To get seen agents, use
         * getNeighbors().
         *
         * @param agent The agent for which to get the seen objects
         * @return All the objects the given agent can see
         */
        public List getSeenObjects(final Agent agent)
        {
                final List seenObjects = new ArrayList();
                for (Iterator iterator = objectsTable.keySet().iterator(); iterator.hasNext();)
                {
                        final WorldObject object = (WorldObject) iterator.next();
                        if (!(object instanceof Agent) && getDistanceBetweenObjects(agent, object) <= agent.getSight())
                                seenObjects.add(object);
                }
                return seenObjects;
        }

        /**
         * Returns all the other agents that can be seen by the given agent,
         * normally called by the given agent himself.
         *
         * @param agent The agent for which to return the seen neighbors
         * @return All the agents that the given agent can see
         */
        public List getNeighbors(final Agent agent)
        {
                final List neighbors = new ArrayList();
                for (Iterator iterator = objectsTable.keySet().iterator(); iterator.hasNext();)
                {
                        final WorldObject object = (WorldObject) iterator.next();
                        if (object instanceof Agent && !object.equals(agent) && getDistanceBetweenObjects(agent, object) <= agent.getSight())
                                neighbors.add(object);
                }
                return neighbors;
        }

        /**
         * Returns a vector from the first object to the second object.  This is
         * useful when an agent wants to move towards an object.  The returned
         * vector is the direction in which the agent should move.
         * <br><br>
         * Note:  The vector returned is not from the center of the first object to the
         * center of the second object!  The vector returned is the vector that, if added
         * to the first object's location, would place the object so that it was touching
         * the second object.  In other words, it's the vector from the center of the first
         * object to the center of the object <b>minus</b> the radii of the both objects.
         *
         * @param a The first object
         * @param b The second object
         * @return A vector from the first object to the second object
         */
        public Vector getVectorToObject(final WorldObject a, final WorldObject b)
        {
                Vector v = new Vector(getData(a).getLocation(), getData(b).getLocation());
                v = v.setLength(v.getLength() - a.getSize() - b.getSize());
                return v;
        }

        /**
         * Returns the distance between the two objects
         *
         * @param a An object
         * @param b Another object
         * @return The distance between the two objects
         */
        protected double getDistanceBetweenObjects(final WorldObject a, final WorldObject b)
        {
                return getVectorToObject(a, b).getLength();
        }

        /**
         * Returns the width (in pixels) of the world
         *
         * @return The width (in pixels) of the world
         */
        public int getWorldWidth()
        {
                return getMinimumSize().width;
        }

        /**
         * Returns the height (in pixels) of the world
         *
         * @return The height (in pixels) of the world
         */
        public int getWorldHeight()
        {
                return getMinimumSize().height;
        }

        /**
         * Returns the number of elapsed time cycles
         *
         * @return The number of elapsed time cycles
         */
        public long getTime()
        {
                return time;
        }

        /**
         * Imports all the objects from another world into this one
         *
         * @param world The world to import the objects from
         */
        public void importObjects(final World world)
        {
                objectsTable = world.objectsTable;
                delay = world.delay;
                selectedObject = null;
                selectedObjectColor = null;
                thread = null;
                time = 0;
        }

        /**
         * Returns whether or not an object with the given size at the given
         * location would be complete inside the boundaries of the world
         *
         * @param location The location of the hypothetical object
         * @param size     The size of the hypothetical object
         * @return Whether or not an object with the given size at the given
         *         location would be complete inside the boundaries of the world
         */
        protected boolean inWorld(final Point location, final int size)
        {
                return location.x >= size &&
                       location.x < getWorldWidth() - size &&
                       location.y >= size &&
                       location.y < getWorldHeight() - size;
        }

        /**
         * Collides two objects.  Using the objects' masses, locations, and
         * velocities it calculates the objects' velocities after a perfectly
         * elastic collision (i.e. no momentum or kinetic energy is lost).
         *
         * @param a An object
         * @param b Another object
         */
        private void collide(final WorldObject a, final WorldObject b)
        {
                final WorldObjectData aData = getData(a);
                final WorldObjectData bData = getData(b);

                // First, find the normalized vector n from the center of
                // A to the center of B
                final Vector n = new Vector(aData.getLocation(), bData.getLocation());
                n.normalize();

                // Find the length of the component of each of the velocities along n.
                // a1 = v1 . n
                // a2 = v2 . n
                final double a1 = aData.getVelocity().dotProduct(n);
                final double a2 = bData.getVelocity().dotProduct(n);

                // Using the optimized version,
                // optimizedP = Ê2(a1 - a2)
                // ÊÊÊÊÊÊÊÊÊÊÊÊÊ-----------
                // ÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊm1 + m2
                final double optimizedP = (2.0 * (a1 - a2)) / (a.getMass() + b.getMass());

                // Calculate final velocity for A
                // va' = va - optimizedP * mb * n
                aData.setVelocity(aData.getVelocity().subtract(n.multiply(optimizedP * b.getMass())));

                // Calculate final velocity for B
                // vb' = vb + optimizedP * ma * n
                bData.setVelocity(bData.getVelocity().add(n.multiply(optimizedP * a.getMass())));

                // Notify objects of collision
                a.collidedWith(b);
        }

        /**
         * Bounces the object off the wall.  Performs a calculation based on the
         * object's location and velocity and modifies the object's velocity
         * appropriately.  The collision is perfectly elastic (i.e. no momentum or
         * kinetic energy is lost)
         *
         * @param object The object to bounce
         */
        private void bounceOffWall(final WorldObject object)
        {
                final WorldObjectData data = getData(object);
                final Point newLocation = data.getLocation().add(data.getVelocity());

                // change velocity depending on which wall we've hit
                if (newLocation.x < object.getSize() || newLocation.x > getWorldWidth() - object.getSize())
                {
                        final Vector velocity = data.getVelocity();
                        velocity.x *= -1;
                        data.setVelocity(velocity);
                }
                if (newLocation.y < object.getSize() || newLocation.y > getWorldHeight() - object.getSize())
                {
                        final Vector velocity = data.getVelocity();
                        velocity.y *= -1;
                        data.setVelocity(velocity);
                }
        }

        /**
         * Returns the object at the given x and y coordinates.  Used for user
         * interaction and mouse-clicks.
         *
         * @param x The x coordinate
         * @param y The y coordinate
         * @return The object at the given location
         */
        protected WorldObject getObjectAt(final int x, final int y)
        {
                final Point point = new Point(x, y);
                for (Iterator iterator = objectsTable.keySet().iterator(); iterator.hasNext();)
                {
                        final WorldObject object = (WorldObject) iterator.next();
                        final WorldObjectData data = getData(object);
                        if (data.getLocation().distance(point) <= object.getSize())
                                return object;
                }
                return null;
        }

        /**
         * Selects the object at the given location
         *
         * @param x The x coordinate
         * @param y The y coordinate
         */
        public void selectObjectAt(final int x, final int y)
        {
                selectObject(getObjectAt(x, y));
        }

        /**
         * Selects the given object
         *
         * @param object The object to select
         */
        public void selectObject(final WorldObject object)
        {
                selectedObject = object;
                repaint();
        }

        /**
         * Sets the color to paint the selected object
         *
         * @param selectedObjectColor The color to paint the selected object
         */
        public void setSelectedObjectColor(final Color selectedObjectColor)
        {
                this.selectedObjectColor = selectedObjectColor;
        }

        /**
         * Sets the color with which to paint the selected object's "sight circle"
         *
         * @param selectedSight The color with which to paint the selected object's
         *                      "sight circle"
         */
        public void setSelectedSight(final Color selectedSight)
        {
                this.selectedSight = selectedSight;
        }

        /**
         * Drops an item from a CarrierAgent
         *
         * @param agent The agent dropping the item
         * @param item  The object beind dropped
         * @throws CollisionException Thrown if the item cannot be placed within the "pickup distance"
         */
        public void dropItem(final CarrierAgent agent, final CarriableObject item) throws CollisionException
        {
                int collisions = 0;
                final WorldObjectData agentData = getData(agent);
                Vector dropVector = agentData.getVelocity();
                dropVector = dropVector.setLength(agent.getSize() + item.getSize());
                synchronized (objectsTable)
                {
                        while (true)
                        {
                                final Point dropPoint = agentData.getLocation().add(dropVector);
                                boolean collided = false;
                                for (Iterator iterator = objectsTable.keySet().iterator(); iterator.hasNext();)
                                {
                                        final WorldObject otherObject = (WorldObject) iterator.next();
                                        final WorldObjectData otherObjectData = getData(otherObject);
                                        final double distance = dropPoint.distance(otherObjectData.getLocation());
                                        if (distance < item.getSize() + otherObject.getSize() || !inWorld(dropPoint, item.getSize()))
                                        {
                                                collisions++;
                                                collided = true;
                                                if (collisions > MAX_ADD_OBJECT_ATTEMPTS)
                                                        throw new CollisionException(item, otherObject);
                                        }
                                }
                                if (!collided)
                                {
                                        final WorldObjectData itemData = getData(item);
                                        itemData.setLocation(dropPoint);
                                        itemData.setVelocity(agentData.getVelocity());
                                        return;
                                }
                                else
                                        dropVector = Vector.getRandom(agent.getSize() + item.getSize());
                        }
                }
        }

        /**
         * Registers a listener for this world
         */
        public void addListener(final WorldListener listener)
        {
                listeners.add(listener);
        }


        /**
         * Returns the closest object of the given type to the given agent that
         * is seen by the agent
         *
         * @param agent The agent to get an object near
         * @param type  The type of objects to search for
         * @return The closest seen object of the given type to the given agent
         */
        public WorldObject getClosestObjectOfType(final Agent agent, final Class type)
        {
                final List objectsOfCorrectType = new ArrayList();
                for (Iterator iterator = objectsTable.keySet().iterator(); iterator.hasNext();)
                {
                        final WorldObject object = (WorldObject) iterator.next();
                        if (type.isInstance(object) && getDistanceBetweenObjects(agent, object) <= agent.getSight())
                                objectsOfCorrectType.add(object);
                }
                if (objectsOfCorrectType.isEmpty())
                        return null;
                else
                {
                        Collections.sort(objectsOfCorrectType, objectDistanceComparator(agent));
                        return (WorldObject) objectsOfCorrectType.iterator().next();
                }
        }

        /**
         * Returns a comparator to sort other objects by their distance to the given object
         *
         * @param object The object to compare distances to
         * @return A comparator to sort other objects by their distance to the given object
         */
        public Comparator objectDistanceComparator(final WorldObject object)
        {
                return new Comparator()
                {
                        public int compare(final Object o1, final Object o2)
                        {
                                final Vector v1 = getVectorToObject(object, (WorldObject) o1);
                                final Vector v2 = getVectorToObject(object, (WorldObject) o2);
                                return v1.compareTo(v2);
                        }
                };
        }
}