[m-users.] Cartesian product of two sets of things.

My video game experiment with Mercury is proving very interesting.

Collision detection: given the low number of objects on the screen, I have been experimenting with various ways of performing collision detection given the nature of Mercury and not using in-place destructive updates etc, which so far, to be honest, has not been a problem, I am still hitting 59FPS on a 60FPS rate limited event loop.

I have one player ship, and I have a list of attacking things, a list of falling things, the attacking things and the falling things (rocks, power ups etc) all have a common type class interface:

:- typeclass hittable(T) where
[
   func id(T)        = int,
   func as_point(T)  = pointf,
   func as_circle(T) = vector3f,
   func as_rect(T)   = rectangle,
   func is_hit(T)    = bool
%   pred set_hit(T::in, T::out) is det
].

Currently, I pass in two lists of things, typically the first list is the current round of missiles from the player, the second list is the list of things that I want to see have collided with anything in the first list. My current implementation is pretty simple, and probably naive:

:- pred collisions_between(
    coll_type::in, list(S)::in, list(T)::in, list(int)::out, list(int)::out
) is det <= ( hittable(S), hittable(T) ).

collisions_between(Check, Shots, Targets, Sids, Tids) :-
    Outer = (pred(Shot::in, !.S::in, !:S::out, !.T::in, !:T::out) is det :-
        Inner = (pred(Target::in, !.S::in, !:S::out, !.T::in, !:T::out) is det :-
            ( if did_collide(Check, Shot, Target) then
                set.insert(id(Shot), !S),
                set.insert(id(Target), !T)
                % set_hit(), Target is not mutable here...have another think!
            else
                true
            )
        ),
        list.foldl2(Inner, Targets, !S, !T)
    ),
    list.foldl2(Outer,
        Shots,
        set.init:coll_set, Sids0,
        set.init:coll_set, Tids0
    ),
    Sids = set.to_sorted_list(Sids0),
    Tids = set.to_sorted_list(Tids0).


The output is two lists, the object IDs of those things involved in collisions.

My question then is, given the two loops are basically generating a cartesian product, is there a module function somewhere that would do that for me, generate a single list of all pairs? Then I could list.chunk and maybe produce a cleaner bit of code. I am currently also considering on uncommenting out the set_hit() typeclass predicate so that I can modify the objects in place, so instead of returning two sets of objects ID,s I'd be returning a new set of objects with their respective hit flags set.

I am also contemplating a simple 'even system' so that the output of the collision MIGHT be a list of actions eg. explode(item), power_up(100), etc etc, like I say, it's a minefield of possibilities!


Thanks.
Sean

_______________________________________________
users mailing list
[email protected]
https://lists.mercurylang.org/listinfo/users