# pixelgenaue Kollisionsabfrage der Kreise



## gieser (15. Jun 2007)

Hallo Leute,
ich möchte ein Flashspiel gerne in Java nachprogrammieren. www.hornoxe.com/flashgame-boomshine/#more-1632 <- das ist es.
Die frage die ich mir stelle, da ja offensichtlich eine pixelgenaue überprüfung drin sein soll, wie ich die am besten implementiere. Soll ich dafür den Bresenham-Algorithmus verwenden? und wenn ja, wie am besten? den kompletten kreis rendern oder irgendwie schon vorher rausfinden, welchen Oktant ich benötige? Ist das überhaupt praktikabel und ich sehe hier ne intelligente Lösung nicht?


----------



## Evolver (15. Jun 2007)

Ein Kreis ist doch definiert durch seinen Mittelpunkt und seinen Radius. Die Kreise "kollidieren" genau dann miteinander, wenn der Abstand ihrere Mittelpunkte kleiner oder gleich der Summe der beiden Radien ist. Also ganz einfaches Rechnen.


----------



## 0xdeadbeef (15. Jun 2007)

Das ist jetzt vermutlich 'ne blöde Frage, aber warum nimmst Du nicht einfach Mittelpunkt und Radius?
Wenn der Betrag des Abstands der beiden Punkte kleiner gleich der Summe der Radien ist, dann gab es eine Kollision.

[EDIT: zu lahm]


----------



## gieser (15. Jun 2007)

also es ist schon seeeehr schlimm, wenn man den wald vor lauter bäumen nicht sieht ^^ und sowas wie ich schimpft sich gymnasiale Oberstufe -.-


----------



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

Das Spiel ist auf jeden Fall eine Seuche, gestern Abend nebenbei ~1h gespielt


----------



## Gast (20. Jun 2007)

ich befürchte vom mittelpunkt auszugehen funktioniert nicht. hat es zumindest damals bei mir nicht. java fängt irgendwie links oben an einen kreis zu zeichnen und nicht in der kreismitte.
deswegen haben wir damals unser spiel, in dem man objekte abschießen muss mit rechtecken realisiert.


----------



## merlin2 (20. Jun 2007)

Dann berechnet man den Mittelpunkt aus der linken oberen Ecke und der Höhe/Breite des Umrechtecks.


----------



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

Richtig - hab ich zwar schon in meinem eigenen Thread gepostet, aber hier ein Grundgerüst des Vorhabens von #1  (ich fand die Idee auch ganz lustig)


```
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 int reloadTime = 30;
	private boolean clicked;
	private int explodingSize = 40;
	private int explodingTime = 3000;

	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++)
		{
			Point speed = new Point(rand.nextInt(2)+1, rand.nextInt(2)+1);
			Point position = new Point(rand.nextInt(width-radius*2), rand.nextInt(height-radius*2));
			Color color = new Color(rand.nextInt(255), rand.nextInt(255), rand.nextInt(255));
			this.balls.add(new Ball(radius, speed, position, color));
		}
	}
	
	private void startAnimation() {
		new Thread(this).start();
	}

	public void run() {
		try {
			while (!Thread.currentThread().isInterrupted()) {
				for(int j = 0; j < balls.size(); j++)
				{
					Ball ball = balls.get(j);
					ball.move();
					ball.explosion();
					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);
						}
					}
				}
				repaint();
				Thread.sleep(reloadTime);
			}
		} 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 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(exploding)
				return;
			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 explosion()
		{
			if(!exploding)
				return;
			
			if(explodingCounter++ < explodingTime/reloadTime)
			{
				if(radius < explodingSize) 
					radius++;
			}
			else if(radius-- >= 1);
		}

		public boolean checkCollision(Ball ball)
		{
	        return position.distance(ball.position) < (radius+ball.radius);
		}
		
		public void paint(Graphics2D g2d) {
			AlphaComposite ac = AlphaComposite.getInstance(AlphaComposite.SRC_OVER, 0.5f);
			g2d.setComposite(ac);

			g2d.setColor(color);
			g2d.fillOval(position.x-radius, position.y-radius, radius * 2, radius * 2);
		}

		public boolean isExploding() {
			return exploding;
		}

		public void setExploding(boolean exploding) {
			this.exploding = exploding;
			if(exploding)
			{
				this.speed.x = 0;
				this.speed.y = 0;
			}
		}
		
		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);
	}

}
```


----------



## Comp-Freak (22. Jun 2007)

fals die distance zwischen kreis und kreis < als radius vom kreis dan ist eine kollision.
oder?


----------



## moormaster (22. Jun 2007)

Das kannst du doch durch einfaches aufzeichnen auch selbst sehen. Wenn du zwei Kreise direkt nebeneinander zeichnest, so dass sich ihre Ränder berühren, dann siehst du auch, dass der Abstand des einen Mittelpunkts genauso weit zum Rand entfernt ist, wie der Radius des Kreises. Vom Rand ist der Abstand der Berührungsstelle bis zum anderen Mittelpunkt wieder identisch mit dem Radius des anderen Kreises.

D.h. sobald ||z1 - z2|| <= r1 + r2 gibt es mindestens einen Berührungspunkt der beiden Kreisränder.

Wobei z1, z2 jeweils Mittelpunkte und r1, r2 jeweils Radien sind.

|| . || ist eine Norm, um die Vektorlänge von z2 - z1 zu messen... meist verwendet man dort die euklidische Norm, d.h.
|| x || = sqrt(x1*x1 + x2*x2 + ... + xn*xn), wobei x ein Vektor ist mit x = (x1, x2, ..., xn)

http://de.wikipedia.org/wiki/Normierter_Raum#p.C2.A0.3D.C2.A02:_Euklidische_Norm


----------

