Create a experiment with dots appearing random on a screen

[David McFarlane]

Well, as an inveterate pedant I could not let the matter rest 
there...  I prefer deterministic and efficient algorithms, so I 
skipped over a couple other approaches that might work just as well 
for some folks.  I may as well lay those out for comparison and instruction.

To randomly scatter dots across the screen without overlap, most 
programmers (including me) would first think of a "dart throwing" 
approach.  In essence, this means throwing a dart at the board, and 
if it hits or lands too near another dart, just pull it out and throw 
it again until you are satisfied.  Keep doing this until all darts 
are on the board.  In more programmatic detail, you would first 
create a structure or array or list to keep track of all the dot 
locations.  For each dot, you would pick a location at random from 
the entire field and loop through the array of dots looking for any 
conflict.  If you found a conflict, you would try another random 
location for that dot and retest until you got a good one (some of 
you will see a similarity between this and the 
"NoRepeatOnConsectiveTrials" example from PST).

I do not like this approach for two reasons.  (1) This method is 
nondeterministic, and in theory (where "theory" includes the use of 
true random numbers instead of pseudo-random) it has no guaranteed 
upper limit to how long it will take to succeed.  In practice, of 
course, it would succeed handily, so this may not bother those who 
are not such fussbudgets as I am.  (2) This approach requires at 
least (nDots - 1) loops through the dot array, with the dot array 
growing as each dot gets added.  I prefer doing things in one or a 
small known number of passes whenever possible.  However, this 
approach does allow for enforcing a buffer zone around each dot.

Another approach would be a "full-field shuffle".  For this you would 
first create an array that contains every coordinate location on the 
screen.  You would shuffle that array, then simply pick the first 
nDots locations from that array.  This approach has the advantage of 
conceptual simplicity, and does everything in a single 
pass.  However, it wastes a *lot* of RAM, as it requires an array 
with over 300,000 elements to place just, say, 10 dots, and that 
number grows quickly as you go to higher resolution screens.  But RAM 
is cheap and plentiful now, so why not?  Also, although it does 
guarantee no overlapping dots, it does not provide a means for 
enforcing a buffer zone around each dot.  (You might notice that the 
"full-field" shuffle is just a special case of the "zoning" approach, 
where nZones = nPixels.)

So in short, the "zoning" approach described in earlier posts is 
conceptually complex, but could work efficiently and allow a lot of 
flexibility in how things get scattered; the "dart throwing" approach 
is conceptually simpler and allows some flexibility in how things get 
scattered, but is nondeterministic and inefficient; the "full-field 
shuffle" is conceptually simplest but wasteful of RAM and not very 
flexible in how things get scattered.  In practice, given modern 
resources any of them might do a fine job.

So there you go, three broad approaches to scatter your dots.  I 
leave you to ponder these, pick one, or perhaps come up with 
something even better, and then work out the programming 
details.  And please write back when you get something to work.

-- David McFarlane, Professional Faultfinder


--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "E-Prime" group.
To post to this group, send email to e-prime at googlegroups.com
To unsubscribe from this group, send email to e-prime+unsubscribe at googlegroups.com
For more options, visit this group at http://groups.google.com/group/e-prime?hl=en
-~----------~----~----~----~------~----~------~--~---