# Kollisionsabfrage - inspiriert durch "pixelgenaue Kolli



## masta // thomas (18. Jun 2007)

Hey Leute 

ich wollte endlich auch mal den Anfang starten, und mich bisschen mit Zeichnen in Java befassen, und da war mir der Thread pixelgenaue Kollisionsabfrage der Kreise ziemlich gelegen, weil ich das Spiel ganz lustig finde.

Ich würd mich freuen, wenn ihr zunächst mal den Code querlesen würdet, und mir evtl. Stellen nennt, an den ich an die ganze Sache falsch rangehe. Damit meine ich z.B. grundlegende Designfehler u.ä. Wie gesagt, das ist das erste Mal, dass ich mich in einer Programmiersprache mit Zeichnen beschäftige - finde es aber ziemlich interessant. 

Tja, scheinbar hab ich irgendwo auch einen logischen Fehler. Das ganze ist ein (großes)KSKB  startet es doch einmal und wartet einen Augenblick, dann merkt ihr, wo mein Problem ist - es wird eine Kollision entdeckt, obwohl sich um den jeweiligen Ball herum kein anderer befindet.

Ich freue mich über Hilfe 

Hier der Code (nicht erschrecken, es sieht nach mehr aus, als es wirklich ist):


```
package de.mcs.test.graphics;

import java.awt.AlphaComposite;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.RenderingHints;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import javax.swing.JComponent;
import javax.swing.JFrame;

public class Balls extends JComponent implements Runnable {

	private static final long serialVersionUID = 3224830373101405104L;

	private int width;
	private int height;
	private List<Ball> balls;
	private int ballsAmount = 10;
	private boolean clicked;
	private int explodingSize = 40;

	public Balls(int width, int height) {
		super();
		setPreferredSize(new Dimension(width, height));
		addMouseListener(new MouseAdapter()
		{
			public void mousePressed(MouseEvent e)
			{
				if(!clicked)
				{
					Ball clickedBall = new Ball(0, new Point(0,0), new Point(e.getX(), e.getY()), Color.WHITE);
					clickedBall.setExploding(true);
					balls.add(clickedBall);
					clicked = true;
				}
			}
		});
		
		this.width = width;
		this.height = height;
		
		initBalls(ballsAmount, 8);
		startAnimation();
	}

	private void initBalls(int amount, int radius)
	{
		this.balls = new ArrayList<Ball>();
		Random rand = new Random();
		for(int i = 0; i < amount; i++)
		{
			this.balls.add(	new Ball(radius, 
									 new Point(rand.nextInt(1)+1, rand.nextInt(1)+1), 
									 new Point(rand.nextInt(width-radius*2), rand.nextInt(height-radius*2)),
									 new Color(rand.nextInt(255), rand.nextInt(255), rand.nextInt(255)))
							);
		}
	}
	
	private void startAnimation() {
		new Thread(this).start();
	}

	public void run() {
		try {
			while (!Thread.currentThread().isInterrupted()) {
				repaint();
				for(Ball ball : balls)
				{
					ball.move();
					ball.checkExploding();
					if(ball.isExploding())
					{
						for(int i = 0; i < balls.size(); i++)
						{
							Ball tmp = balls.get(i);
							if(ball == tmp)
								continue;
							if(ball.checkCollision(tmp))
								tmp.setExploding(true);
						}
					}
				}
				
				Thread.sleep(20);
			}
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
	}
	
	protected void paintComponent(Graphics g) {
		Graphics2D g2d = (Graphics2D) g;
		g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
		g2d.setColor(new Color(0, 51, 51));
		g2d.fillRect(0, 0, width, height);
		for(Ball ball : balls)
			ball.paint(g2d);
	}

	class Ball {
		private int radius;
		private Point speed;
		private Point position;
		private Color color;
		private boolean exploding;
		private int explodingCounter;

		public boolean isExploding() {
			return exploding;
		}

		public void setExploding(boolean exploding) {
			this.exploding = exploding;
			if(exploding)
			{
				this.speed.x = 0;
				this.speed.y = 0;
			}
		}

		public Ball(int radius, Point speed, Point position, Color color) {
			this.radius = radius;
			this.speed = speed;
			this.position = position;
			this.color = color;
		}

		public void move() {
			if (position.x < 0 || (position.x + radius * 2) > width)
				speed.x = -speed.x;

			if (position.y < 0 || (position.y + radius * 2) > height)
				speed.y = -speed.y;

			position.x += speed.x;
			position.y += speed.y;
		}
		
		public void checkExploding()
		{
			if(!exploding)
				return;
			
			if(explodingCounter++ < 100)
			{
				if(radius < explodingSize) 
					radius++;
			}
			else if(radius-- >= 1);
		}

		public boolean checkCollision(Ball ball)
		{
			double dx = Math.abs((position.x - radius/2) - (ball.position.x - ball.radius/2));
			double dy = Math.abs((position.y - radius/2) - (ball.position.y - ball.radius/2));
			
			double  d = radius + ball.radius;           

            return d*d >= dx*dx+dy*dy;
		}
		
		public void paint(Graphics2D g2d) {
			AlphaComposite ac = AlphaComposite.getInstance(AlphaComposite.SRC_OVER, 0.5f);
			g2d.setComposite(ac);

			g2d.setColor(color);
			g2d.fillOval(position.x-(exploding ? radius/2 : 0), position.y-(exploding ? radius/2 : 0), radius * 2, radius * 2);
		}

		public void setRadius(int radius) {
			this.radius = radius;
		}

	}
	
	public static void main(String[] args) {
		JFrame frame = new JFrame("Balls");
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		frame.getContentPane().add(new Balls(500, 350));
		frame.pack();
		frame.setVisible(true);
	}

}
```


----------



## Evolver (18. Jun 2007)

Was mir auffällt ist, dass die Bälle die feritg explodiert sind in der Menge der Bälle bleiben. Die solten entfernt werden, denn auch mit einem Radius<1 können sie sonst noch nicht explodierte Bälle zum explodieren bringen. Ich weiß nicht, ob das das primäre Problem ist, aber das ist mir aufgefallen.


----------



## masta // thomas (18. Jun 2007)

Das ist mir bewusst - daran liegt es aber denke ich nicht, weil die Bälle an Stellen explodieren, wo noch kein anderer Ball liegt :-/


----------



## Evolver (18. Jun 2007)

Das liegt daran, weil der Rdius expolidierender Bälle in den negativen Bereich kommt (nach der Explosion). Der explodierte Ball wird zwar nichtmehr angezeigt, kann aber weitere Explosionen auslösen.

Zu bemerken ist das an einem ganz einfachen Test:
Füge in checkCollision am Anfang mal folgende Zeile ein: _if (radius<0) return false;_

Das gröbste Problem ist damit gelöst, aber die Kollision erolgt immernoch nicht perfekt.


----------



## Marco13 (18. Jun 2007)

BTW: In Point gibt es eine distance/distanceSq-Methode, die macht die Abfrage an sich etwas einfacher.


----------



## masta // thomas (18. Jun 2007)

Oh ja, du hast Recht Evolver, hab ich total verschlampt mit dem Radius & negativer Bereich! Danke!

Und stimmt, danke auch für den Tipp mit Point#distance(), Marco 

Ich kann mir allerdings nicht erklären, warum die Abfrage trotzdem noch so "schlecht" bzw. ungenau ist?
Und, ist euch evtl. etwas an meinem Code aufgefallen, was ihr hättet anders gemacht? Was ich vielleicht unsauber / unschön gelöst habe?


----------



## Evolver (19. Jun 2007)

Wieder ist mir eine Kleinigkeit zur Ungenauigkeit aufgefallen.

Du zeichnes so:
_g2d.fillOval(position.x-(exploding ? radius/2 : 0), position.y-(exploding ? radius/ : 0), radius * 2, radius * 2);_

Richtig wäre aber, bei den ersten beiden Parametern nicht radius/2 sonder einfach nur radius abzuziehen. Schließlich handelt es sich um den Radius und nicht um den Durchmesser. Es gab deshalb auch einen unterschied zwischen dem was gezeichnet wurde und dem, was in derLogik passiert ist. Also besser:
_g2d.fillOval(position.x-(exploding ? radius : 0), position.y-(exploding ? radius : 0), radius * 2, radius * 2);_


----------



## masta // thomas (19. Jun 2007)

Oh, super, danke! Der Fehler ist dadurch entstanden, dass ich zuerst mit dem Durchmesser gearbeitet habe, und dann auf Radius umgestellt habe.
Das macht die Sache schon auf jeden Fall bisschen besser - und richtiger 

Aber so richtig gut läuft es noch nicht. Macht es evtl. einen Unterschied, Bälle, welche explodieren, in eine andere Collection zu packen und so evtl. ein paar Schleifendurchläufe zu sparen? Obwohl die Laufzeit n^2 das doch so extrem nicht beeinflussen dürfte... mhh..


----------



## Evolver (19. Jun 2007)

Eigentlich dürfte es keinen Unterschied machen, denn das Zeichnen und das Berechnen laufen in deinem Programm nicht unabhängig voneinander. Soll heißen: Da du immer erst zeichnest, nachdem die Berechnungen durchgeführt wurden, kann zwischen dem Zeichnen und dem Rechnen eigentlich keine "Asynchonität" entstehen. Das sollte also nicht der Grund für die Ungenauigkeit sein.

Der Grund ist der Unterschiedliche Umgang mit den Radien .... blubb .... probiers wie folgt:
Die Funktion move sollte wie folgt aussehen:
	
	
	
	





```
public void move() {
         if((position.x-radius) < 0 || (position.x+radius) > width)
            speed.x = -speed.x;

         if((position.y-radius) < 0 || (position.y+radius) > height)
            speed.y = -speed.y;

         position.x += speed.x;
         position.y += speed.y;
      }
```

Gezeichnet werden sollten die Bälle einfach durch
_g2d.fillOval(position.x-radius, position.y-radius, radius * 2, radius * 2);_


Dann funktioniert das prima bei mir.


----------



## masta // thomas (19. Jun 2007)

Bei mir nicht so prima  hat sich leider kaum was getan.
Mich ärgert es, dass ich es alleine nicht schaffe :-/


----------



## Evolver (19. Jun 2007)

> Bei mir nicht so prima



Das ist komisch. Hast du auch das Zeichnen der Bälle angepasst?


----------



## masta // thomas (19. Jun 2007)

Schon - schau, hier der ganze Code, explodierte Bälle werden jetzt auch gelöscht
Bei dem veränderten Teil den du geschrieben hast tritt zusätzlich noch der Fehler auf, dass die Bälle manchmal an einer der Achsen "titschen" - hängt denke ich mit der Position der Bälle zusammen.


```
package de.mcs.test.graphics;

import java.awt.AlphaComposite;

public class Balls extends JComponent implements Runnable {

	private static final long serialVersionUID = 3224830373101405104L;

	private int width;
	private int height;
	private List<Ball> balls;
	private int ballsAmount = 10;
	private boolean clicked;
	private int explodingSize = 40;

	public Balls(int width, int height) {
		super();
		setPreferredSize(new Dimension(width, height));
		addMouseListener(new MouseAdapter()
		{
			public void mousePressed(MouseEvent e)
			{
				if(!clicked)
				{
					Ball clickedBall = new Ball(0, new Point(0,0), new Point(e.getX(), e.getY()), Color.WHITE);
					clickedBall.setExploding(true);
					balls.add(clickedBall);
					clicked = true;
				}
			}
		});
		
		this.width = width;
		this.height = height;
		
		initBalls(ballsAmount, 8);
		startAnimation();
	}

	private void initBalls(int amount, int radius)
	{
		this.balls = new ArrayList<Ball>();
		Random rand = new Random();
		for(int i = 0; i < amount; i++)
		{
			this.balls.add(	new Ball(radius, 
									 new Point(rand.nextInt(2)+1, rand.nextInt(2)+1), 
									 new Point(rand.nextInt(width-radius*2), rand.nextInt(height-radius*2)),
									 new Color(rand.nextInt(255), rand.nextInt(255), rand.nextInt(255)))
							);
		}
	}
	
	private void startAnimation() {
		new Thread(this).start();
	}

	public void run() {
		try {
			while (!Thread.currentThread().isInterrupted()) {
				repaint();
				for(int j = 0; j < balls.size(); j++)
				{
					Ball ball = balls.get(j);
					ball.move();
					ball.checkExploding();
					if(ball.isExploding())
					{
						if(ball.radius == 0)
						{
							balls.remove(j);
							System.out.println(balls.size());
							continue;
						}
						for(int i = 0; i < balls.size(); i++)
						{
							Ball tmp = balls.get(i);
							if(ball == tmp)
								continue;
							if(ball.checkCollision(tmp))
								tmp.setExploding(true);
						}
					}
				}
				
				Thread.sleep(20);
			}
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
	}
	
	protected void paintComponent(Graphics g) {
		Graphics2D g2d = (Graphics2D) g;
		g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
		g2d.setColor(new Color(0, 51, 51));
		g2d.fillRect(0, 0, width, height);
		for(Ball ball : balls)
			ball.paint(g2d);
	}

	class Ball {
		private int radius;
		private Point speed;
		private Point position;
		private Color color;
		private boolean exploding;
		private int explodingCounter;

		public boolean isExploding() {
			return exploding;
		}

		public void setExploding(boolean exploding) {
			this.exploding = exploding;
			if(exploding)
			{
				this.speed.x = 0;
				this.speed.y = 0;
			}
		}

		public Ball(int radius, Point speed, Point position, Color color) {
			this.radius = radius;
			this.speed = speed;
			this.position = position;
			this.color = color;
		}

		public void move() {
			
			/*
			if (position.x < 0 || (position.x + radius * 2) > width)
				speed.x = -speed.x;

			if (position.y < 0 || (position.y + radius * 2) > height)
				speed.y = -speed.y;

			position.x += speed.x;
			position.y += speed.y;
			*/
			if((position.x-radius) < 0 || (position.x+radius) > width)
	            speed.x = -speed.x;

	        if((position.y-radius) < 0 || (position.y+radius) > height)
	            speed.y = -speed.y;

	        position.x += speed.x;
	        position.y += speed.y; 
		}
		
		public void checkExploding()
		{
			if(!exploding)
				return;
			
			if(explodingCounter++ < 200)
			{
				if(radius < explodingSize) 
					radius++;
			}
			else if(radius-- >= 1);
		}

		public boolean checkCollision(Ball ball)
		{
			double dx = Math.abs((position.x - radius/2) - (ball.position.x - ball.radius/2));
			double dy = Math.abs((position.y - radius/2) - (ball.position.y - ball.radius/2));
			
			double  d = radius + ball.radius;           

            return d*d >= dx*dx+dy*dy;
		}
		
		public void paint(Graphics2D g2d) {
			AlphaComposite ac = AlphaComposite.getInstance(AlphaComposite.SRC_OVER, 0.5f);
			g2d.setComposite(ac);

			g2d.setColor(color);
			//g2d.fillOval(position.x-(exploding ? radius : 0), position.y-(exploding ? radius : 0), radius * 2, radius * 2);
			g2d.fillOval(position.x-radius, position.y-radius, radius * 2, radius * 2);
		}

		public void setRadius(int radius) {
			this.radius = radius;
		}

	}
	
	public static void main(String[] args) {
		JFrame frame = new JFrame("Balls");
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		frame.getContentPane().add(new Balls(500, 350));
		frame.pack();
		frame.setVisible(true);
	}

}
```


----------



## Evolver (19. Jun 2007)

Upps, ich dachte nach der Antwort von Marco13 hättest du die checkCollision()-Methode selbst angeglichen. So habe ich sie umgeschrieben, wahrscheinlich hat es deshalb bei mir funktioniert, bei dir nicht:


```
public boolean checkCollision(Ball ball)
      {
    	 if (radius<0) return false;
         
         if(position.distance(ball.position) < (radius+ball.radius)) return true;
         return false;
      }
```


----------



## masta // thomas (19. Jun 2007)

Das scheints gewesen zu sein 
Ich habe mir gerade auch nochmal die Kollisionsprüfung genauer angeschaut und es mir dann nochmal durch den Kopf gehen lassen und als Hilfe dazu habe mir eine Linie gezeichnet zwischen zwei Bällen


```
Point b1 = new Point(20, 20);
		int r1 = 30;
		Point b1middle = new Point(b1.x+r1, b1.y+r1);
		g2d.fillOval(b1.x, b1.y, r1*2, r1*2);
		
		Point b2 = new Point(40, 85);
		int r2 = 20;
		Point b2middle = new Point(b2.x+r2, b2.y+r2);
		g2d.fillOval(b2.x, b2.y, r2*2, r2*2);
		
		int distance = (b2middle.x-b1middle.x)*(b2middle.x-b1middle.x) + (b2middle.y-b1middle.y)*(b2middle.y-b1middle.y);
		int rad = (r1+r2)*(r1+r2);
		
		g2d.setColor(new Color(0xffffff));
		g2d.drawLine(b1middle.x, b1middle.y, b2middle.x, b2middle.y);
				
		System.out.println("abstand: " + distance);
		System.out.println("rad: " + rad);
```

Vermutlich, wenn ich das so anpassen würde, könnte es auch mit dieser Methode funktionieren - die natürlich wesentlich umständlicher ist 

Vielen Dank für deine Hilfe und dass du dir soviel Zeit genommen hast!
Jetzt bin ich erstmal glücklich


----------

