<div dir="ltr"><div><div><div><div><div>Apologies if this is completely wrong, but:<br><br></div>Wouldn't one process for each particle, given thousands of particles, pose a potential overhead problem given the extra scheduling required between processes?<br>
<br></div>I would be inclined to try one process for each 3d cube, as you mentioned, and also let that process keep track of all particles within its cube (maybe in a ETS table). Then, if a particle crosses over to another cube, the particle would be migrated from one process to another (via a message sent between the two cube processes).<br>
<br></div>To answer your other points of debate:<br><br></div>1. This is a very interesting problem which for graphics from a first person point of view is well researched, but since this is for some backend serving a game/simulation it (I suppose) involves multiple players/entities, so we wouldn't want the 3D space to be asymmetrically partitioned if we could avoid it (atleast to start with).<br>
<br></div><div>If it makes sense given the properties of the 3D space, particles and other objects/players you have, one way to reduce the maximum shapes overlapping with the sphere of influence to 4 is to partition the space into a set of symmetrical cuboids where the Z-axis of each cuboid goes from the minimum to the maximum of the space, and the X and Y sizes of the cuboids remain strictly larger than the diameter of the sphere (as you mentioned for the cube partitioning).<br>
<br></div><div>2. I guess the particles, whether they have their own process or are handled inside a cube (or cuboid!) process are in memory anyway, so I'd wait with caching anything until its time to optimize a working implementation.<br>
<br></div><div>3. The general advice is to save tweaking the BEAM schedulers and which scheduler a process runs in for the later stages of optimization. But for reference, you can bind a process to a specific scheduler [1] and also bind a scheduler to a specific CPU thread (logical processor) [2].<br>
<br>Cheers,<br>Gustav<br><br>[1] Use the {scheduler, N} option (undocumented) to<br>erlang:spawn_opt/2,3,4,5. The number of schedulers can be found with<br>erlang:system_info(schedulers)<br>, and the scheduler for the calling process with<br>
erlang:system_info(scheduler_id).<br><br>[2] Look at the +sbt options at<br><a href="http://www.erlang.org/doc/man/erl.html#emu_flags">http://www.erlang.org/doc/man/erl.html#emu_flags</a><br><br><br></div></div><div class="gmail_extra">
<br><br><div class="gmail_quote">On Wed, Feb 12, 2014 at 9:48 PM, kraythe . <span dir="ltr"><<a href="mailto:kraythe@gmail.com" target="_blank">kraythe@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">Joe, <div><br></div><div>The problems of gaming are similar for sure but the scale here is much larger. But I can throw another monkey wrench into the mix. The motion of the particles are non-deterministic and can be acted upon by an external force. So each particle needs to have its own life and own process. What I had thought of doing is the following and i would be appreciative of the experience of you and the other erlang gurus in commenting on my proposals: </div>
<div><br></div><div>I essentially thought to have each particle be its own process. Furthermore, the world would be divided up into 3d cubes, each of which is at least larger than the maximum radius of the sphere of influence. Each 3d cube would be a process as well and the. The particle process would track which cube it is in and the cubes would track which particles are in them. Then when the motion happens at each frame if the particle leaves a cube, it will send a message to that cube indicating it left and it will also send a message to the new cube that it entered. When determining the particles in the field, the particle would determine whether its sphere spanned multiple cubes and ask each cube which it overlaps to send it a message with the list of particles in the cube. Then it would apply our "in_sphere" test to determine the actual candidates to interact with and then execute those interractions.</div>
<div><br></div><div>Points of debate for me are: </div><div>1) Should they be cubes dividing the space or another shape. If we use cubes, the maximum number of cubes a sphere could overlap would be 8 if the cubes are arranged in a regular pattern. Alternatively we could use an irregular pattern like a brick layer and then the max number of cubes to check is 5. Are there any other configurations that don't have any overlap of spatial partitioning and could reduce the number of candidate cells further without complicating the math badly. </div>
<div>2) is it worth it to cache, in some manner, the particles in the sphere of influence. I am leaning towards "no" because all will have to be checked to see if they moved out anyway and then the other candidates will have to be checked if they moved in. So there seems little reason to cache anything.</div>
<div>3) Is it worth it to manually move processes around cores as they transition to other areas of geometry (i.e. if the particle is on core 8 of machine 5 but its bounding cube is on core 2 of node 1 there could be inefficiency.) This question is largely a result of my newbieness to OTP and erlang I suppose. If we do move the actor around we will have to reconnect the "client" governing the particle motion to the new actor.</div>
<div><br></div><div>Interesting problem huh? </div><div class="gmail_extra"><br clear="all"><div><div dir="ltr"><div style="font-family:arial;font-size:small"><b>Robert Simmons Jr. MSc. <br></b></div></div></div><div><div class="h5">
<br><br><div class="gmail_quote">On Wed, Feb 12, 2014 at 1:42 PM, Joe Armstrong <span dir="ltr"><<a href="mailto:erlang@gmail.com" target="_blank">erlang@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">Interesting problem.<div><br></div><div>How to you map your problem onto a process structure?</div><div><br></div><div>Method 1 - let the process manage regions of space</div><div><br></div><div>How about starting with 1000 parallel processes. Each one managing a point in a 10x10x10 grid in 3-d space.</div>
<div><br></div><div>In pass one you compute which process "owns" each particle. Thereafter each process only manages the</div><div>particles that it owns. Once it knows the velocity and position of each particle it can compute if the particle</div>
<div>will leave the zone in the next time tick. In the case when a particle leaves a zone, you just send a message</div><div>to the next zone controller process that you predict it will move to.</div><div><br></div><div>
I know that some games companies use this technique for large multi-user games written in Erlang. They use a 2D map of squares and each square is controlled by an Erlang processes. This scales nicely on a cluster, since moving off a map square just moves the computation to a new processes and possible a</div>
<div>new node.</div><div><br></div><div>Method 2 - let the processes manage a limited set of processes</div><div><br></div><div>I guess if you didn't have too many particles you could have one process per particle. Each process<br>
</div><div>could have a "gossip" set (the set of "nearby in space" processes) which send messages to it's neighbours as things happen. Or you could let one process handle 10 particles ...</div><div>
<br></div><div>I guess it al depends on the numbers - I don't think you said how many particles there were etc.</div><div>I always like to know some numbers - are we talking millions or thousands of particles? How many</div>
<div>interactions/sec take place etc.</div><div><br></div><div>In any case you'll have to model the problem in different ways and measure.</div><div><br></div><div>Cheers</div><span><font color="#888888"><div>
<br></div><div>/Joe</div><div><br></div>
<div><br></div><div><br></div></font></span></div><div><div><div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Feb 12, 2014 at 6:56 PM, kraythe . <span dir="ltr"><<a href="mailto:kraythe@gmail.com" target="_blank">kraythe@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Ahh octtree is good if the objects are static and if your goal is to find an object in a large space. It is a reductive search algorithm. In this case all of the objects are in motion and I want to know my neigbors, not find object X in the space. Therefore a different approach is called for. <div>
<br></div><div> Imagine thousands of particles flowing around in a medium and needing to determine their interactions based on vicinity, momentum, etc. From frame to frame the state of your tree would change and the cost would make the simulation impossible to render in realtime. Instead if the world is divided up into cubes that are larger than the sphere of influence and each cube knows about its neighbors then I can easily get a candidate list as long as the particles update the cube entity that they are in. As they move into a cube, they inform the cube that they have entered and as they leave the cube, they inform it of their exit. If I know the cube I am in, and I know my sphere of influence overlaps into another cube, I can immediately exclude all candidate not in either cube. If the cube has references to its neigbors, the solution is easy. <div>
<br></div><div>1) Determine if I overlap sphere into neighbors (simple math problem of the radius of my sphere and the boinds of the cube. </div><div>2) For all cubes I overlap, get members. </div><div>3) For all members determine which are inside my sphere. </div>
<div>4) Interract with elements in my sphere. </div></div><div><br></div><div>Incidentally my current version of the code, Thanks to Richard's input, is: </div><div><br></div><div><div><div>%% Subtract the second vector from the first</div>
<div>subtract({X1, Y1, Z1}, {X2, Y2, Z2}) -> {(X1 - X2), (Y1 - Y2), (Z1 - Z2)}.</div><div><br></div></div><div>%% Compute if the vector T is in the sphere with center at vector C and with radius R.<br></div><div>in_sphere(C, R, T) -> </div>
<div> {Dx, Dy, Dz} = subtract(C, T),</div><div> Dx * Dx + Dy * Dy + Dz * Dz =< R * R. </div><div><br></div><div>%% Calculate all entities in the sphere defined at center vector C with radius R and using Fpos which will extract the location to check from</div>
<div>%% each entity in the list. The method Fpos must return a three tuple vector and take the entity as an argument.</div><div>entities_in_sphere(C ,R, Entities, Fpos) -></div><div> [E || E <- Entities, in_sphere(C, R, Fpos(E))].</div>
</div><div><br></div><div>It also appears to run quite fast according to preliminary timer:tc tests but of course there is need for more massive testing of load. I may still have to use the type optimization richard pointed out. I am debating staying with integer arithmetic also. </div>
<div class="gmail_extra"><br clear="all"><div><div dir="ltr"><div style="font-family:arial;font-size:small"><b>Robert Simmons Jr. MSc. <br></b></div></div></div><div><div>
<br><br><div class="gmail_quote">On Wed, Feb 12, 2014 at 8:04 AM, Joe Armstrong <span dir="ltr"><<a href="mailto:erlang@gmail.com" target="_blank">erlang@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote"><div>On Tue, Feb 11, 2014 at 11:17 PM, kraythe . <span dir="ltr"><<a href="mailto:kraythe@gmail.com" target="_blank">kraythe@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">Richard, <div><br></div><div>I appreciate your response and the effort you put into it. And I learned a lot from it. In this case I am learning the thinking mode of Erlang as it is different a bit from what I do to pay the bills. I have yet to get into list comprehensions in Erlang so that is on my ... well ... list. :) You have provided valuable insight. </div>
<div><br></div><div>The main focus of the method is if I have a number of objects with a vector position in a simulation and I want to exclude considerations of interactions with objects outside the sphere of influence, I have to quickly discard the candidates that are not inside the sphere of influence. I originally thought to write a method that did just the vector math because I was wondering if that kind of math would have to ultimately be turned into something native. Even a delay of 1 second would be fatal to the simulation. </div>
</div></blockquote><div><br></div></div><div>Isn't this what octrees are for? - You'd have to use a "cube of influence" - but as far as I know octrees</div><div>can be used to rapidly partition objects in a 3-d space</div>
<div><br></div><div>Take a look at this <a href="http://en.wikipedia.org/wiki/Octree" target="_blank">http://en.wikipedia.org/wiki/Octree</a></div><span><font color="#888888"><div><br></div><div>/Joe </div>
<div> </div>
</font></span><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div><div><div dir="ltr">
<div><br></div><div>The algorithm, however, shouldnt have to consider all candidates as the world is broken into spacial segments (cubes) such that the sphere could intersect with at maximum 8 neighboring cubes so I would only need to consider simulation objects within those 8 cube spaces when determining which elements were actually within the sphere of influence. I have been trying to devise a method of reducing the candidate set even further and am still working on that. Perhaps edge detection and cube boundary calculations but I don't want to spend more math doing that then I would simply excluding objects vector by vector. </div>
<div><br></div><div>Anyway thanks for the reply, definitely some information that I can use in there. </div><div class="gmail_extra"><br clear="all"><div><div dir="ltr"><div style="font-family:arial;font-size:small"><b>Robert Simmons Jr. MSc.</b></div>
</div></div><div><div><br><div class="gmail_quote">On Sun, Feb 9, 2014 at 10:59 PM, Richard A. O'Keefe <span dir="ltr"><<a href="mailto:ok@cs.otago.ac.nz" target="_blank">ok@cs.otago.ac.nz</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div><br>
On 8/02/2014, at 4:53 AM, kraythe . wrote:<br>
> Anyway back to the subject at hand. The algorithm is set but now I am at another quandary Lets say these vectors represent a position in space of particular objects in a simulation. The process of culling the vectors based on the sphere is entirely a vector problem but what the user calling cull/3 really needs to know is which objects are not culled from the list, not just which vectors are not culled. Now in Java I could do a number of things if I wanted to keep the cull algorithm as it is. I could return the list of integers containing the original indexes of the vectors in the list that were culled and use that to filter out which objects need to be considered for the simulation step.<br>
<br>
</div>The word "cull" really grates.<br>
<br>
And all those negations *really* confused me *all over again*.<br>
I wrote a lengthy and helpful description of how to get the<br>
points that were accepted and the points that were rejected<br>
as two lists, because that was the only way I could interpret<br>
your question to make sense in Erlang. But on repeated re-reading<br>
it became clear that you were asking for something else.<br>
<br>
There is no such thing in Erlang as object identity.<br>
The distinction you are drawing between the "points" and the<br>
"objects" simply doesn't exist.<br>
<br>
It so happens that if you use a list comprehension like<br>
[P || P <- Points, some_predicate(P)]<br>
the elements of the result *will* be (references to) the same<br>
implementation-level webs of chunks of memory that were in the<br>
original list, not copies. But nothing other than performance<br>
depends on this.<br>
<br>
A list of integers such as you ask for could be obtained, but it<br>
would be very little use to you, because Erlang lists are *LINKED<br>
LISTS*, not *INDEXED ARRAYS*. Finding the nth element of a list<br>
takes O(n) time, and that could not be changed without making<br>
lists much less useful.<br>
<br>
<br>
</blockquote></div><br></div></div></div></div>
<br></div></div><div>_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
<br></div></blockquote></div><br></div></div>
</blockquote></div><br></div></div></div></div>
<br>_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
<br></blockquote></div><br></div>
</div></div></blockquote></div><br></div></div></div></div>
<br>_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
<br></blockquote></div><br></div>