hewih wrote:to avoid NxN checks i want to take the first element and check it against the rest, take the next and check it against the rest and so on. the result should be a "collision list" of collision pairs: ((box1 circle3) (circle7 circle3) (box2 circle7)). is there a existing function or idiom which handles these combinations?
This is something Lisp is naturally good at.
On first glance, I'd write something that takes a list as a required argument (I'll call it inlist
here), plus an optional argument that defaults to NIL, which I'll call acc
is an accumulator for the result.
If the cdr of the list is null, it'd return acc
Otherwise, it'd take the car of inlist
and iteratively check it for collisions against each element of inlist
's cdr, probably using mapcar or one of its immediate relatives - this may or may not be best accomplished via a helper function that takes an atom and a list and simply returns a list of collisions, possibly using delete-if. Either way, it would call itself on the cdr of inlist
and, if it found any collisions, it would append the list of collisions to acc
(using either nconc or append) and pass that as the second argument.
That should at least get you something that'll work, and that can be optimised later. It's also a generally useful idiom, which can be implemented either as a function accepting other functions as arguments, or as a macro. Paul Graham covered this patch of ground pretty well in On Lisp
, if you want to pursue it a bit further.