indexing

	description: "[

		Objects that should be detected by the collision detector EM_COLLISION_DETECTOR
		have to inherit from EM_COLLIDABLE
		
		The implemented collidables are
		EM_CIRCLE_COLLIDABLE
		EM_RECTANGLE_COLLIDABLE
		EM_POLYGON_COLLIDABLE
		EM_COLLIDABLE_COMPOSITION

	]"
	date: "$Date$"
	revision: "$Revision$"

deferred class

	EM_COLLIDABLE

inherit

	EM_COLLISION_IMPLEMENTATION
		export
			{NONE} all
		end

	EM_LOGGING

feature -- Initialization

	initialize is
			-- should be called upon creation, after the center was set
		require
			center_set: center /= Void
		do
			create logger.make
			create last_center.make (center.x,center.y)
			create clipping.make (0,0)
			zoom_factor := 1
			color := create {EM_COLOR}.make_white
		ensure
			color_set: color.red = 255 and color.green = 255 and color.blue = 255
		end

	make_from_other (a_collidable: EM_COLLIDABLE) is
			-- copies a collidable
		require
			a_collidable_not_void: a_collidable /= Void
		deferred
		end

feature -- Access

	center: EM_VECTOR_2D
			-- Center of the collidable objects circumcircle, also known as the circumcenter

	radius: DOUBLE
			-- Circumcircle radius of the collidable object, used for rough collision detection.
			-- This is the maximal distance of any part of the object to `center'

	ignore: BOOLEAN
			-- true, if the object should be ignored from collision detection.
			-- Please note, that this should only be used temporarily, if you don't want
			-- to remove the object from the detector. If you wish not to use this
			-- object anymore, please remove it from the detector.

	holder: ANY
			-- This option may be used, in order to know, who holds the collidable primitive

	rotatable: BOOLEAN
			-- a orthogan rectangle for example is not rotatable

	angle: DOUBLE
			-- angle in radian, in which the bounding volume is rotated (0 is default), in [0 2pi]

	color: EM_COLOR
			-- the color of the collidable, if drawn

feature -- Access

	last_center: EM_VECTOR_2D
			-- the center position since the last movement

feature -- Status Report

	collides_with (a_collidable: EM_COLLIDABLE): BOOLEAN is
			-- Rough collision detection of circumcircle
		require
			a_collidable_void: a_collidable /= Void
		local
			collision: BOOLEAN
			dx, dy: DOUBLE
		do
			dx := a_collidable.center.x - center.x
			dy := a_collidable.center.y - center.y
			if dx*dx + dy*dy <= (radius + a_collidable.radius)*(radius + a_collidable.radius) then
				-- a rough collision was detected
				collision := true
			end
			Result := collision
		end

	collides_with_depth (a_collidable: EM_COLLIDABLE; d: INTEGER): EM_PAIR [BOOLEAN, DOUBLE] is
			-- searches the first collision point of 2 collidables with search depth d.
			-- returns a pair, if no collision was found, returns [false, 0]
			-- otherwise true and the time at which the first collision happened, between 0 and 1
		require
			a_collidable_not_void: a_collidable /= Void
			depth_valid: d >= 0
		do
			if d = 0 then
				Result := create {EM_PAIR [BOOLEAN, DOUBLE]}.make (collides_with (a_collidable), 1)
			else
				if not collides_with (a_collidable) then
					-- if it does not collide
					if collides_with_at_time (a_collidable, 0) then
						Result := create {EM_PAIR [BOOLEAN, DOUBLE]}.make (True, 0)
					else
						Result := create {EM_PAIR [BOOLEAN, DOUBLE]}.make (False, 0)
					end
				else
					-- check if it collided at the last position
					if collides_with_at_time (a_collidable, 0) then
						-- if they already collided at the last position
						Result := create {EM_PAIR [BOOLEAN, DOUBLE]}.make (True, 1)
					else
						Result := create {EM_PAIR [BOOLEAN, DOUBLE]}.make (True, collides_with_depth_implementation (a_collidable, d, 0, 1))
					end
				end
			end
		end

	collides_between_step (a_collidable: EM_COLLIDABLE; depth, search_depth: INTEGER): DOUBLE is
			-- search of collisions in between steps.
			-- Performance: O (2^d * collision_check_time)
			-- returns if they ever collide and the first time of collision found.
		require
			doesnt_collide_at_last_step: not collides_with_at_time (a_collidable, 0)
			doesnt_collide: not collides_with (a_collidable)
		local
			collision_found_at_time, t: DOUBLE
			i, d: INTEGER
		do
			-- breadth-first search for a collision point to depth d
			-- if a collision was found, search will be continued to depth `search_depth' which is O(n)
			-- worstcase performance is O(2^d)

			from i := 1
			until collision_found_at_time > 0 or i > depth
			loop
				from t := 1/(2^(i))
				until collision_found_at_time > 0 or t >= 1
				loop
					if collides_with_at_time (a_collidable, t) then
						collision_found_at_time := t
					end
					t := t + 1/(2^(i-1))
				end
				i := i + 1
			end

			if collision_found_at_time > 0 then
				-- a collision was found, procede with depth search

				if search_depth > depth then
					d := search_depth - i + 1
				else
					d := depth - i + 1
				end

				if d <= 0 then
					Result := collision_found_at_time
				else
					Result := collides_with_depth_implementation (a_collidable, d, 0, collision_found_at_time)
				end
			end
		ensure
			result_in_range: Result >= 0 and Result < 1
		end

	intersection_points (a_collidable: EM_COLLIDABLE): DS_LINKED_LIST [EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]] is
			-- returns the average collision point and tangential direction of the 2 collidable objects `current' and `a_collidable'
			-- in case of concave objects (compositions of convex objects) a collision may be returned for each element of the
			-- composition. The same 2 collidables can have multiple collision points.
		require
			a_collidable_void: a_collidable /= Void
		deferred
		end

	max_distance_to_position (a_position: EM_VECTOR_2D): DOUBLE is
			-- computes the maximal distance to a certain position.
			-- this is used to compute the radius of compositions of collidables
		require
			a_position_not_void: a_position /= Void
		deferred
		end

feature -- Element Change

	process_changes is
			-- Process all changes to the collidable.
			-- recomputes the `radius' and resets the value
		do
		end

	set_ignore (v: BOOLEAN) is
			-- sets if an item should be temporarily ignored for collision detection
		do
			ignore := v
		ensure
			ignore = v
		end

	set_holder (v: ANY) is
			-- assigns the holder to a certain reference
		do
			holder := v
		ensure
			holder = v
		end

	set_rotatable (v: BOOLEAN) is
			-- sets if the object is rotatable
		deferred
		end

	rotate_by (an_angle_in_radian: DOUBLE) is
			-- Rotates an object by a certain angle. positive means clockwise, because the y-axis of the screen is inverted!
			-- rotates around `center'
		do
			if rotatable then
				turn (an_angle_in_radian)
				angle := normalized_angle (angle + an_angle_in_radian)
			end
		end

	rotate_by_around_center (an_angle_in_radian: DOUBLE; a_center: EM_VECTOR_2D) is
			-- Rotates an object by a certain angle. positive means clockwise, because the y-axis of the screen is inverted!
			-- rotates around `a_center'
		do
			if rotatable then
				turn_around_center (an_angle_in_radian, a_center)
				angle := normalized_angle (angle + an_angle_in_radian)
			end
		end

	rotate_to (an_angle_in_radian: DOUBLE) is
			-- Rotates an object to a certain angle around the center.
			-- the angle 0 is the angle in which the bounding volume was created and backed up
			-- the backed up coordinates will always be used to generate the new ones, to
			-- prevent deformation after a lot of rotations.
		do
			if rotatable then
				turn (an_angle_in_radian - angle)
				angle := normalized_angle (an_angle_in_radian)
			end
		end

	rotate_to_around_center (an_angle_in_radian: DOUBLE; a_center: EM_VECTOR_2D) is
			-- Rotates an object to a certain angle around `a_center'.
			-- the angle 0 is the angle in which the bounding volume was created and backed up
			-- the backed up coordinates will always be used to generate the new ones, to
			-- prevent deformation after a lot of rotations.
		do
			if rotatable then
				turn_around_center (an_angle_in_radian - angle, a_center)
				angle := normalized_angle (an_angle_in_radian)
			end
		end

	set_center (a_center: EM_VECTOR_2D) is
			-- sets `center', which also moves the whole object surrounding it
		require
			a_center_not_void: a_center /= void
		do
			last_center.set_x (center.x)
			last_center.set_y (center.y)
			center := create {EM_VECTOR_2D}.make_from_other (a_center)
		ensure
			center_set: center.x = a_center.x and center.y = a_center.y
		end

	reset_center (a_center: EM_VECTOR_2D) is
			-- sets `center', which also moves the whole object surrounding it
			-- also set 'last_center'
		require
			a_center_not_void: a_center /= void
		do
			last_center := create {EM_VECTOR_2D}.make_from_other (a_center)
			center := create {EM_VECTOR_2D}.make_from_other (a_center)
		ensure
			center_set: center.x = a_center.x and center.y = a_center.y
			last_center_set: last_center.x = a_center.x and last_center.y = a_center.y
		end

	set_x_y (x_position, y_position: DOUBLE) is
			-- sets the center to (x,y)
		do
			last_center.set_x (center.x)
			last_center.set_y (center.y)
			center.set_x (x_position)
			center.set_y (y_position)
		ensure
			last_center_set: last_center.x = old center.x and last_center.y = old center.y
			center_set: center.x = x_position and center.y = y_position
		end

	move_by (an_x, a_y: DOUBLE) is
			-- moves the center by an_x, a_y
		do
			last_center.set_x (center.x)
			last_center.set_y (center.y)
			center.set_x (center.x + an_x)
			center.set_y (center.y + a_y)
		end

	set_draw_clipping (top_left_corner: EM_VECTOR_2D; a_zoom_factor: DOUBLE) is
			-- This sets the clipping for the part to draw
			-- The first argument is the top left corner of the screen.
			-- for example if we want an object, that is situated at (5000, 1000), the
			-- clipping should be moved to an appropriate position e.g. (4800, 800)
			-- All objects outside of the clipping will not be displayed
		require
			corner_not_void: top_left_corner /= void
			factor_valid: a_zoom_factor > 0
		do
			clipping := top_left_corner
			zoom_factor := a_zoom_factor
		end

	set_draw_color (a_color: EM_COLOR) is
			-- sets the color of the collidable, if `draw' is used
		require
			a_color_not_void: a_color /= Void
		do
			color := a_color
		ensure
			color_set: a_color = color
		end

	set_draw_filled (v: BOOLEAN) is
			-- sets to filled draw mode
		do
			filled := v
		ensure
			filled_set: filled = v
		end

	set_draw_circumcircle (v: BOOLEAN) is
			-- also draws the circumcircle of the collidable
		do
			draw_circumcircle := v
		ensure
			draw_circumcircle_set: draw_circumcircle = v
		end

	set_draw_circumcircle_color (c: EM_COLOR) is
			-- sets the circumcircle color
		require
			color_not_void: c /= Void
		do
			draw_circumcircle_color := c
		ensure
			circumcircle_color_set: draw_circumcircle_color = c
		end

feature -- Computation

	center_of_mass: EM_VECTOR_2D is
			-- computes and returns the center of mass
		deferred
		end

	area: DOUBLE is
			-- area of the collidable in pixel^2
		deferred
		end

	duplicate: like Current is
			-- returns an equivalent copy of the collidable (just the position and borders)
		deferred
		end

	collides_with_at_time (a_collidable: EM_COLLIDABLE; t: DOUBLE): BOOLEAN is
			-- checks if 2 collidables collided at time t
		require
			a_collidable_not_void: a_collidable /= Void
			t_valid: t >= 0 and t <= 1
		local
			b_collidable, c_collidable: EM_COLLIDABLE
		do
			b_collidable := a_collidable.duplicate
			c_collidable := current.duplicate
			b_collidable.set_center (a_collidable.last_center + (a_collidable.center - a_collidable.last_center) * t)
			c_collidable.set_center (current.last_center + (current.center - current.last_center) * t)
			Result := b_collidable.collides_with (c_collidable)
		end

feature -- Drawing

	draw (a_surface: EM_SURFACE) is
			-- Draw `Current' to `a_surface'
			-- The screen clipping is set with `set_draw_clipping'
		require
			a_surface_not_void: a_surface /= Void
		deferred
		end

feature {EM_COLLIDABLE} -- Implementation

	collides_with_depth_implementation (a_collidable: EM_COLLIDABLE; d: INTEGER; a, b: DOUBLE): DOUBLE is
			-- recursive search of collision points. This function is called by `collides_with_depth'
			-- requires the collidables to collide at the end (b=1) as a precondition (not tested)
		require
			a_collidable_not_void: a_collidable /= Void
			a_and_b_valid: b > a and a >= 0 and b <= 1
			d_non_negative: d >= 0
		local
			b_collidable, c_collidable: EM_COLLIDABLE
			movement: EM_VECTOR_2D
			m: DOUBLE
		do
			if d = 0 then
				Result := b
			else
				Result := 1
				b_collidable := a_collidable.duplicate
				c_collidable := current.duplicate
				m := (a+b)/2
				-- move the collidable
				create movement.make_from_other (a_collidable.last_center - b_collidable.center)
				movement := movement * (1-m)
				b_collidable.move_by (movement.x, movement.y)
				movement := (current.last_center - c_collidable.center)
				movement := movement * (1-m)
				c_collidable.move_by (movement.x, movement.y)

				if b_collidable.collides_with (c_collidable) then
					-- there is a collision in the middle of a and b
					Result := collides_with_depth_implementation (a_collidable, d-1, a, m)
				else
					-- there is no collision in the middle of a and b
					Result := collides_with_depth_implementation (a_collidable, d-1, m, b)
				end
			end
		end

	collides_between_step_implementation (a_collidable: EM_COLLIDABLE; d: INTEGER; a,b: DOUBLE): DOUBLE is
			-- recursive search for the first collision point (if any)
			-- returns the time of the first collision (0 < time < 1)
			-- returns 0, if no collision was found
		require
			doesnt_collide_at_last_step: not collides_with_at_time (a_collidable, 0)
			doesnt_collide: not collides_with (a_collidable)
		do
			if d = 0 then
				Result := 0
			else
				-- no collision was found between a and b yet.
				-- the middle is checked for collisions now

			end
		end

	clipping: EM_VECTOR_2D
			-- the top left corner. for more details see `set_draw_clipping'

	zoom_factor: DOUBLE
			-- the zoom factor from the clipping point

	turn (an_angle: DOUBLE) is
			-- turns a bounding area TO a certain angle. this will be called from rotate_to or rotate_by
		do
			turn_around_center (an_angle, center)
		end

	turn_around_center (an_angle: DOUBLE; a_center: EM_VECTOR_2D) is
			-- turns a bounding area TO a certain angle around a given center. this will be called from rotate_to or rotate_by
		require
			a_center_not_void: a_center /= Void
		deferred
		end

	filled: BOOLEAN
			-- true, if the collidable should be drawn filled

	draw_circumcircle: BOOLEAN
			-- true, if the circumcircle should be drawn

	draw_circumcircle_color: EM_COLOR
			-- color of the circumcircle

invariant

	radius_positive: radius >= 0
	angle_is_normalized: angle = normalized_angle (angle)
	logger_not_void: logger /= Void
	clipping_set: clipping.x = 0 and clipping.y = 0
	zoom_factor_set: zoom_factor = 1
	last_center_not_void: last_center /= Void

end