indexing

	description: "[

		This (2D) collision detector checks the added objects for collisions and generates a
		list of all collisions (collisions: DS_LINKED_LIST[EM_COLLISION [G]]).
		this is void, if no collision was found.
		
		usage:
		first specify, how many sets of collidables you would like to have added
		A set of collidables is a list of collidable objects, that should not be checked for collisions with each
		other, this may be useful, if for example there are objects, that do not move, compared to
		each other, like compositions of collidables, or non-moving objects.
		The number of sets may be increased and decreased later on.

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

class EM_COLLISION_DETECTOR [G->EM_COLLIDABLE]

create

	make

feature -- Creation

	make (nr_of_sets_of_collidables: INTEGER) is
			-- creates an array of sets of collidables
			-- note: arrays start from index 1
		require
			nr_valid: nr_of_sets_of_collidables >= 0
		local
			i: INTEGER
		do
			count := nr_of_sets_of_collidables
			create sets_of_collidables.make (1, nr_of_sets_of_collidables)
			create last_collisions.make

			from i := 1
			variant nr_of_sets_of_collidables + 1 - i
			until i > nr_of_sets_of_collidables
			loop
				-- add an empty set for each index
				sets_of_collidables.put (create {DS_LINKED_LIST[G]}.make, i)
				i := i + 1
			end

			create clipping.make (0,0)
			zoom_factor := 1

			-- set default colors
			create draw_circumcircle_color.make_white
			filled := True
		ensure
			count_correct: count = nr_of_sets_of_collidables
		end

feature -- Element Change

	add (a_collidable: G; add_to_set: INTEGER) is
			-- Add `a_collidable' to a certain set (takes the collidable and index as arguments)
		require
			a_collidable_not_void: a_collidable /= void
			add_to_set_not_void: add_to_set <= count and add_to_set > 0
		do
			sets_of_collidables.item (add_to_set).put_last (a_collidable)
		ensure
			collidable_added: sets_of_collidables.item (add_to_set).last = a_collidable
		end

	add_list (collidable_list: DS_LINKED_LIST [G]; add_to_set: INTEGER) is
			-- adds all elements of `collidable_list' to the set
		require
			collidable_list_not_void: collidable_list /= void
			add_to_set_not_void: add_to_set <= count and add_to_set > 0
		do
			sets_of_collidables.item (add_to_set).extend_last (collidable_list)
		end

	remove (a_collidable: G) is
			-- Removes `a_collidable' from any set containing it
		require
			a_collidable_not_void: a_collidable /= void
		local
			i: INTEGER
		do
			from i := 1
			variant count + 1 - i
			until i > count
			loop
				-- remove from current list
				sets_of_collidables.item (i).delete (a_collidable)
				i := i + 1
			end
		end

	remove_from_set (a_collidable: G; set_index: INTEGER) is
			-- removes `a_collidable' from a certain set
		do
			sets_of_collidables.item (set_index).delete (a_collidable)
		end

	empty_set (set_index: INTEGER) is
			-- empties the set with index `set_index'
		do
			sets_of_collidables.put (create {DS_LINKED_LIST[G]}.make, set_index)
		end

	set_search_depth (depth: INTEGER) is
			-- sets `search_depth', see `search_depth' for more detail
		require
			depth_valid: depth >= 0
		do
			search_depth := depth
		ensure
			search_depth_set: search_depth = depth
		end

	set_movement_check (v: INTEGER) is
			-- sets `movement_check', see `movement_check' for more details
			-- Performance for movement check: O(2^n)
		do
			movement_check := v
		ensure
			movement_check_set: movement_check = v
		end

	set_draw_color (a_color: EM_COLOR) is
			-- sets the color of all collidables, drawn in `draw'
		require
			a_color_not_void: a_color /= Void
		local
			i: INTEGER
			cursor: DS_LINKED_LIST_CURSOR [G]
		do
			from i := 1
			until i > count
			loop
				cursor := create {DS_LINKED_LIST_CURSOR [G]}.make (sets_of_collidables.item (i))
				from cursor.start
				until cursor.off
				loop
					cursor.item.set_draw_color (a_color)
					cursor.forth
				end
				i := i + 1
			end
		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_filled (v: BOOLEAN) is
			-- sets the draw mode saved in `filled'
		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

	check_for_collision is
			-- Checks if any element collides with an other from another set
			-- Saves the resulting collisions in the variable `collisions'
			-- worst-case performance: O(n^2)
			-- resets the cursors on `sets_of_collidables'
		local
			i, j: INTEGER
			pair: EM_PAIR [BOOLEAN, DOUBLE]
			path1, path2: EM_POLYGON_CONVEX_COLLIDABLE
			list1, list2: DS_LINKED_LIST [EM_VECTOR_2D]
			t: DOUBLE
			cursor1, cursor2: DS_LINKED_LIST_CURSOR [G]
		do
			-- empty collision list
			last_collisions.wipe_out

			-- loop through the array of sets
			from i := 1
			variant count - i + 1
			until i > count
			loop
				create cursor1.make (sets_of_collidables.item (i))
				-- loop through all sets with the other elements
				from cursor1.start
				until cursor1.off
				loop
					-- only check if not ignored
					if not cursor1.item.ignore then
						-- loop through the rest of arrays of sets
						from j := i + 1
						until j > count
						loop
							create cursor2.make (sets_of_collidables.item (j))
							-- loop through all sets with the other elements
							from cursor2.start
							until cursor2.off
							loop
								pair := cursor1.item.collides_with_depth (cursor2.item, search_depth)
								if pair.first = True then
									-- `cursor1.item_for_iteration' collided with `cursor2.item'
									add_collision (cursor1.item, cursor2.item, pair.second)
								elseif movement_check > 0 then
									-- no collision was found, but possibly there was one in between the steps

									-- create paths
									create list1.make
									list1.force_last (cursor1.item.last_center)
									list1.force_last (cursor1.item.center)
									list1.force_last (cursor1.item.center)
									create path1.make_from_absolute_list ((cursor1.item.last_center+cursor1.item.center)/2, list1)
									create list2.make
									list2.force_last (cursor2.item.last_center)
									list2.force_last (cursor2.item.center)
									list2.force_last (cursor2.item.center)
									create path2.make_from_absolute_list ((cursor2.item.last_center+cursor2.item.center)/2, list2)

									if path1.collides_with (path2) or else path1.collides_with (cursor2.item) or else path2.collides_with (cursor1.item) then
										-- either the pathes cross, or a path intersects eith the other object
										-- there might be a collision in between the steps
										t := cursor1.item.collides_between_step (cursor2.item, movement_check, search_depth)
										if t > 0 and t <= 1 then
											add_collision (cursor1.item, cursor2.item, t)
										end
									end
								end
								cursor2.forth
							end
							j := j + 1
						end
					end
					cursor1.forth
				end
				i := i + 1
			end
		end

feature -- Access

	count: INTEGER
			-- counts the number of sets

	last_collisions: DS_LINKED_LIST [EM_COLLISION_COMPOSITION [G]]
			-- a list of the collisions generated by `check_for_collisions'

	search_depth: INTEGER
			-- the depth of bisection for search of intersection points of two collidable objects.
			-- default is 0 (meaning just the final position of the collidables)
			-- `search_depth' has to be greater than 0 in order to do movement_checks

	movement_check: INTEGER
			-- if this is enabled (>0), the whole path from `last_position' to the current position
			-- will be checked for a collision. This computations takes a lot of time, so if it
			-- is not really necessary (if there are no such quick movements for example), don't
			-- use it. An example of its usage is, that it prevents objects from flying through
			-- walls or other thin items.
			-- Performance: O(2^n)

	sets_of_collidables: ARRAY[DS_LINKED_LIST[G]]
			-- all sets of collidables in the scene

	collides_with_position (pos: EM_VECTOR_2D): G is
			-- returns a collidable that collides with a certain position.
			-- this can be useful, for getting a single collision with the mouse
			-- the last in the list will be returned
		local
			cursor: DS_LINKED_LIST_CURSOR [G]
			i: INTEGER
			position: EM_CIRCLE_COLLIDABLE
		do
			create position.make (pos, 0)

			from i := 1
			until i > count
			loop
				cursor := create {DS_LINKED_LIST_CURSOR [G]}.make (sets_of_collidables.item (i))
				from cursor.start
				until cursor.off
				loop
					if position.collides_with (cursor.item) = True then
						Result := cursor.item
					end
					cursor.forth
				end
				i := i + 1
			end
		end

feature -- Status Report

	has (a_collidable: G): BOOLEAN is
			-- returns true, if the collidable is in the detector
			-- Performance: O(n)
		require
			a_collidable_not_void: a_collidable /= Void
		do
			Result := not for_all (agent collidables_not_equivalent (a_collidable, ?))
		end

feature -- Iteration

	do_all (action: PROCEDURE [ANY, TUPLE [G]]) is
			-- Apply `action' to every item in the collision detector.
			-- Semantics not guaranteed if `action' changes the structure;
			-- in such a case, apply iterator to clone of structure instead.
		local
			cursor: DS_LINKED_LIST_CURSOR [G]
			t: TUPLE [G]
			i: INTEGER
		do
			create t
			from i := 1
			until i > count
			loop
				cursor := create {DS_LINKED_LIST_CURSOR [G]}.make (sets_of_collidables.item (i))
				from cursor.start
				until cursor.off
				loop
					t.put (cursor.item, 1)
					action.call (t)
					cursor.forth
				end
				i := i + 1
			end
		end

	for_all (test: FUNCTION [ANY, TUPLE [G], BOOLEAN]): BOOLEAN is
			-- Is `test' true for all items?
		local
			cursor: DS_LINKED_LIST_CURSOR [G]
			t: TUPLE [G]
			i: INTEGER
		do
			Result := True
			create t
			from i := 1
			until i > count or not Result
			loop
				cursor := create {DS_LINKED_LIST_CURSOR [G]}.make (sets_of_collidables.item (i))
				from cursor.start
				until cursor.off or not Result
				loop
					t.put (cursor.item, 1)
					Result := test.item (t)
					cursor.forth
				end
				i := i + 1
			end
		end

feature -- Drawing

	draw (a_surface: EM_SURFACE) is
			-- draws all contained collidables on the screen, with clipping and zoom_factor
		local
			i: INTEGER
			cursor: DS_LINKED_LIST_CURSOR [G]
		do
			from i := 1
			until i > count
			loop
				cursor := create {DS_LINKED_LIST_CURSOR [G]}.make (sets_of_collidables.item (i))
				from cursor.start
				until cursor.off
				loop
					cursor.item.set_draw_clipping (clipping, zoom_factor)
					cursor.item.set_draw_filled (filled)
					if draw_circumcircle then
						cursor.item.set_draw_circumcircle (draw_circumcircle)
						cursor.item.set_draw_circumcircle_color (draw_circumcircle_color)
					end
					cursor.item.draw (a_surface)
					cursor.forth
				end
				i := i + 1
			end
		end

feature {NONE} -- Implementation

	add_collision (a_collidable, b_collidable: G; time: DOUBLE) is
			-- adds a found collision to `last_collisions'
		require
			a_collidable_not_void: a_collidable /= Void
			b_collidable_not_void: b_collidable /= Void
			time_valid: time >= 0 and time <= 1
		local
			a_collision_composition, b_collision_composition: EM_COLLISION_COMPOSITION [G]
			cursor: DS_LINKED_LIST_CURSOR [EM_COLLISION_COMPOSITION [G]]
			collision_points: DS_LINKED_LIST [EM_PAIR [EM_VECTOR_2D, EM_DIRECTION_2D]]
			collisions: DS_LINKED_LIST [EM_COLLISION [G]]
			c_collidable, d_collidable: G
			movement: EM_VECTOR_2D
		do
			-- get intersection points and directions
			if time = 1 then
				collision_points := a_collidable.intersection_points (b_collidable)
			else
				c_collidable := a_collidable.duplicate
				movement := (a_collidable.last_center - c_collidable.center) * (1-time)
				c_collidable.move_by (movement.x, movement.y)
				d_collidable := b_collidable.duplicate
				movement := (b_collidable.last_center - d_collidable.center) * (1-time)
				d_collidable.move_by (movement.x, movement.y)
				collision_points := c_collidable.intersection_points (d_collidable)
			end

			create collisions.make
			from collision_points.start
			until collision_points.off
			loop
				collisions.force_last (create {EM_COLLISION [G]}.make (a_collidable, b_collidable, collision_points.item_for_iteration.first, collision_points.item_for_iteration.second, time))
				collision_points.forth
			end

			-- loop through sets of sets of collisions
			create cursor.make (last_collisions)
			from cursor.start
			until cursor.off
			loop
				-- check if the collision composition has one of the collidables
				if a_collision_composition = void and then cursor.item.has_collidable (a_collidable) then
					a_collision_composition := cursor.item
				end
				if b_collision_composition = void and then cursor.item.has_collidable (b_collidable) then
					b_collision_composition := cursor.item
				end
				cursor.forth
			end

			from collisions.start
			until collisions.off
			loop
				-- add collidables or if needed, merge compositions
				if a_collision_composition = Void and b_collision_composition = Void then
					-- the collidables were not in a composition -> make a new composition
					a_collision_composition := create {EM_COLLISION_COMPOSITION [G]}.make
					a_collision_composition.force_last (collisions.item_for_iteration)
					last_collisions.force_last (a_collision_composition)
				elseif a_collision_composition = Void and b_collision_composition /= Void then
					-- one of the collidables is in b_collision_composition
					b_collision_composition.force_last (collisions.item_for_iteration)
				elseif b_collision_composition = Void and a_collision_composition /= Void then
					-- one of the collidables is in a_collision_composition
					a_collision_composition.force_last (collisions.item_for_iteration)
				elseif a_collision_composition /= Void and b_collision_composition /= Void and a_collision_composition = b_collision_composition then
					-- both collidables are already in the same composition
					a_collision_composition.force_last (collisions.item_for_iteration)
				else
					-- both collidables are already in different compositions -> merge compositions
					a_collision_composition.force_last (collisions.item_for_iteration)
					a_collision_composition.append_right (b_collision_composition)
					-- remove `b_collision_composition' from last_collisions
					last_collisions.delete (b_collision_composition)
				end
				collisions.forth
			end
		end

	collidables_not_equivalent (a_collidable, b_collidable: G): BOOLEAN is
			-- returns true if the 2 arguments reference the same object
			-- used by `has'
		do
			Result := a_collidable /= b_collidable
		ensure
			result_correct: Result = (a_collidable /= b_collidable)
		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

	filled: BOOLEAN
			-- true, if the collidables should be drawn filled, otherwise only the outline will be drawn

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

	draw_circumcircle_color: EM_COLOR
			-- color of the circumcircle

invariant

	count_non_negative: count >= 0

end