call function on all combinations of a list

[hewih]

i'm creating a little physics engine which manages a list a of collidable objects. in order to calculate all occurring collisions i need to combine every item in the list with each other and check for the collision. 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?

simple sample source

Code: Select all

(defun combine-if (test func list)
   ; 1. combines every item with the rest
   ; 2. check if test is true on current item and rest item
   ; 3. if so, call func and add the result to the result list
   ...)

(combine-if #'= #'cons '(1 2 3 2 1))
; in my little physics engine i would use collidep and cons
; on a list of collidable objects here!

take 1
   check against (2 3 2 1)
      (= 1 2)? => NIL
      (= 1 3)? => NIL
      (= 1 2)? => NIL
      (= 1 1)? => T
      (cons 1 2) => (1 . 2) added to result list
take 2
   check against 3 2 1
      (= 2 3)? => NIL
      (= 2 2)? => T
      (cons 2 2) => (2 . 2) added to result list
      (= 2 1)? => NIL

and so on until there is only 1 item left which cannot be checked against another item

result ((1. 1) (2 . 2))

[ramarren]

is there a existing function or idiom which handles these combinations?

There is MAP-COMBINATIONS in Alexandria which does most of that, you have to accumulate the values yourself but that is sufficiently trivial, it doesn't eliminate duplicates from input list, but why would they be there in the first place?

Code: Select all

CL-USER> (alexandria:map-combinations #'print '(1 2 3 4 5) :length 2)
(1 2) 
(1 3) 
(1 4) 
(1 5) 
(2 3) 
(2 4) 
(2 5) 
(3 4) 
(3 5) 
(4 5) 

in order to calculate all occurring collisions i need to combine every item in the list with each other and check for the collision

This might be obvious, but remember to limit the list of objects using a spatially aware data structure, like spatial-trees. I was always confused by the interface of that library, but it should work since McClim uses it.

[JamesF]

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. 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.

[Destruct1]

I think this easy enough so you dont need an extern library. If you really want to
I would search for a math permutation library, because the problem looks like "choose 2 out of x".

Anyway here is untested code:

Code: Select all

(defun is-it-a-collision (argx argy)
  ;check wheter x and y collide
  ;put them in a global list)

(defun recursive-all-with-all-objects-function (inlist)
  (when (>= (length inlist) 2) 
     ;if length of inlist greater than 2 check collision for first element with all rest elements
     (mapcar #'(lambda (take-argument-b-from-list-by-lambda_mapcar) (is-it-a-collision (first inlist) take-argument-b-from-list-by-lambda_mapcar)) (rest inlist))
     (recursive-first-with-rest-object-function (rest inlist))

Without a good editor the parens are hard to see but I hope you get the concept.

[hewih]

oh how unfair! i WAS checking http://www.cliki.net/Library first for: iteration, mapping and combination utilities but Alexandria isn't listed. thanks Ramarren!

> Ramarren: remember to limit the list of objects using a spatially aware data structure

thanks for the hint, but i just need a small but working physics engine i rather need it for a proof of concept for my architecture and Common Lisp

> JamesF: This is something Lisp is naturally good at...
> Destruct1: I think this easy enough so you dont need an extern library...

i tried implementing it myself at first but then i fell into this popular "don't invent here!" syndrome and thought someone else might have implemented it already thanks for the help though JamesF and Destruct1!