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

[Sean Charles (emacstheviking)]

Some good points there Zoltan!

All the missiles move constantly, the enemies move constantly, the attacking shots from the enemeies move constantly so, in the worst case on the highest difficulty game level I've planned, there could be up to approx. 300 moving objects, of which no more than 20 would be missiles from the player and the player ship, the rests being the attacking entities, their missiles, falling objects, power ups.

I don't regard even that number being particularly high really. 

Taking on board Juliens comment, I have decided to uncomment my initial version that actually updates the hit objects in-place, I love experimenting and trying out different approaches for things just to see where it leads. I wish I had found Mercury years ago... I am trying to find a way to get it into my day job, currently python+django setup, I will try...

I have already read up on k-d trees, one of my favourite YT channels has quite a good video, in case anybody else wants to see it:
https://www.youtube.com/watch?v=BK5x7IUTIyU
K-d Trees - Computerphile
youtube.com


I know about oct-trees but my game is strictly 2D which is a much simpler problem
As I say, this is partly for fun, more learning about anything and everything but mostly to generate a graphics wrapper around raylib, which is approaching stable now in terms of the API calls I need from it, and a set of higher level functions

I am right now figuring out how to integrate HarfBuzz as well, purely to see it render text as the core raylib text rendering is ok, but leaves a lot to be desired and the ultimate goal for my 2D wrapper/engine is for an IDE for my mercury powered transpiler.

Many thanks,
Sean.



> On 10 Oct 2023, at 14:26, Zoltan Somogyi <zoltan.somogyi at runbox.com> wrote:
> 
> 
> On 2023-10-10 21:02 +11:00 AEDT, "Julien Fischer" <jfischer at opturion.com> wrote:
>> A big part of the difference would be that the nondet version sorts
>> the elements and (redundantly) attempt to remove duplicates, whereas the
>> det version just constructs the elements in reverse order directly.
> 
> Another source of difference is that its lowest level operations
> are tail recursive, while the lowest level operations in the nondet version
> can't be tail recursive, because you can't recover a nondet stack frame
> while the values of the variables it contains may be needed to find
> another solution.
> 
> You should note that even the det version in cproduct.m is not
> as fast as it could be, because it adds each new item to the cross product
> using a higher order call. Converting the sets to sorted lists and iterating
> over the lists directly could replace those higher order calls with simple
> unifications, which would make that version even faster.
> 
> But there is another question: do you actually want a cartesian product?
> What percentage of the objects you are dealing with actually move?
> If that percentage is high, then the cartesian product approach is
> probably appropriate. If it is low, then another approach is probably
> better, because any time spent checking whether two stationary objects
> have collided is wasted. (I don't think the Eiffel tower will collide with
> the Burj Khalifa anytime soon.) Approaches based on data structures
> such as oct-trees, k-d-trees or region trees (rtrees) would let you check
> for collisions between (a) just the moved objects and (b) just the objects,
> moving and stationary, near the moved object being examined.
> This approach has a higher constant factor than the cartesion product
> approach due to the need to maintain a tree, but its asymptotic
> complexity would be lower, so for large enough data sets, it should be
> faster.
> 
> The Mercury standard library contains an implementation of one of the
> data structures I mentioned above; you may want to check out rtree.m.
> I have never used it myself, so I can't vouch for it, but it may be
> worth a try.
> 
> Zoltan.
> _______________________________________________
> users mailing list
> users at lists.mercurylang.org
> https://lists.mercurylang.org/listinfo/users

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mercurylang.org/archives/users/attachments/20231010/66204f7b/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: maxresdefault.jpg
Type: image/jpeg
Size: 111563 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/users/attachments/20231010/66204f7b/attachment-0001.jpg>