edit:
At Tom LaGatta's request, here are a few more very rough graphs relating to the number of components. For $n=3,\dots,15$, I ran just 10 instances of each (took about 15-20 minutes). Hopefully that's enough to give a little bit of the idea of the spread.
Here are the total number of components (with size>1) versus $n$. I noticed that it appeared parabolic, so I plotted it on a log-log scale with the function $n^2/3$ (the factor of 1/3 just happened to be close). Each data point corresponds to a different instance.
Here on semi-log scales are the distributions of numbers of components (with size>1) for the various grid sizes I considered. The different colors correspond to distributions observed in different instances. They look much better on semi-log as opposed to log-log, though that's fairly meaningless with not even a decade of data and small number effects.
Code for this section (run with the functions in the notebook linked to below):
(* code to generate data, change parameters as needed *)
minn = 3;maxn = 15;numruns = 10;
data = Table[test = Flatten[makegrid[n, n], 1];Truncate[test], {j, numruns}, {n, minn, maxn}];
(* code to process and plot data *)
averagecomponents = Table[{n, Length[data[[i, n - minn + 1, 2]]]}, {n, minn, maxn}, {i,
numruns}];
plot1 = ListLogLogPlot[averagecomponents, AxesLabel -> {"n", "total number of components"}];plot2 = LogLogPlot[x^2/3, {x, 1, maxn}];Show[plot1, plot2]
compdist = Table[Table[Tally[Table[Length[data[[j, n, 2, i]]], {i, averagecomponents[[n, j, 2]]}]], {j, numruns}], {n, maxn-minn+1}];
ListLogPlot[compdist[[12]], PlotStyle -> PointSize[Large]]
ListLogPlot[compdist[[13]], PlotStyle -> PointSize[Large]]
GraphicsGrid[Partition[Table[ListLogPlot[compdist[[j]], PlotStyle -> PointSize[Medium], PlotLabel -> "n=" <> ToString[j + minn - 1], AxesLabel -> {"size of component", "frequency"}], {j, maxn - minn + 1}], 3, 3, {1, 1}, {}]]
(* not shown: number of infinite rays *)
numinfinities = Table[{n, Count[data[[i, n - minn + 1, 1]], Infinity]}, {n, minn, maxn}, {i, numruns}]
original answer:
I wrote a bit of Mathematica code to try to simulate your process (link here). I only partially commented things, so let me know if you have trouble understanding how to use it. More on this after some pictures and graphs.
I apologize in advance, I don't have the time now to do a real systematic study or gather any real statistics on my computer. I'll have to leave it to you or other interested readers...
I didn't bother to add boundary conditions to cut off the rays leaving the grid. Below, components of size 1 are just rays that don't terminate.
5x5:
8x8:
15x15 grids:
(1)
(2)
Number of components of a given size for 15x15:
(1)
(2)
Stopping time distribution for 15x15 (excluding infinite rays, of which there are 6 in #1 and 7 in #2):
(1)
(2)
Note: I didn't see any cycles at all, but I had to check this by eye, since I didn't write a routine to extract the graph structure of the connected components. What I have now just records their size.
There is what looks like a cycle in the upper left quadrant of 15x15 #1, but you can easily convince yourself by comparing the lengths of the edges that the rays couldn't actually touch.
I used pretty much the most naïve algorithm I could think of:
- Generate a pseudorandom angle at each grid point, and thus get a set of lines.
- Find the intersection times of all pairs of lines. (Lines are naturally parametrized as $x(t)=x_0+t(\cos\theta,\sin\theta)$, where $x_0$ is the starting point and $\theta$ is the angle.)
- From this set of pairs, select pairs of rays that intersect in positive time rather than negative, and sort from smallest time to largest.
- Choose the intersection that occurs at the smallest time, mark the two rays involved as truncated, and record the connected component formed by this as a new one, and record the time of intersection as the "ending time" for the two rays.
- Check the intersection occurring at the next smallest time to see whether it's been preempted by existing rays (by comparing the intersection times with ending times), and if the intersection passes the test, mark these rays as truncated, and record the connected component and any new ending times as in 4.
- Repeat 5. until all intersections or all rays have been eliminated.
What are smarter ways of doing this?
Because of 2., the code runs rather slowly, probably $O(n^4)$ for an $n$ by $n$ grid ($n^2$ grid points, thus $(n^2)^2$ possible intersections). An instance at $n=15$ takes about 40 seconds on my machine to run.