This weekend, I started to work on a program that will take any shape and fill it with the largest possible inscribed circles. Something like this:

One of the reasons I am interested in doing this is to create a music visualizer. If similar shapes produce similar sets of circles, I can manipulate the shape using sound and get smoothly shifting circles. But to test the algorithm, I started with a random shape generator.

Each point is based on a random radius and angle, but the angle is always increased to avoid looping the shape over itself.

The algorithm I’ve drafted on paper has changed a lot, but it always has these components:

• A spline which provides information about the nearest points to a location.
• A seed method, which chooses a starting point for a seed circle of radius 0. It selects the center of the spline if there are no circles yet. Later it will select from known open spaces in a “fit bin” – if no such spaces are stored, it will choose a tangent point on the largest circle.
• An expansion method, which repeats certain steps until the seed fills its surroundings and has 3 tangent points with the spline or other circles.
• A resolution method, which uses the expansion method to expand the seed, but then attempts to fit this seed into other spaces to see if it can get any bigger. If there is a larger space for the seed, the current seed location and size are saved as an entry to the fit bin, the seed is placed in the larger space, and the method starts over.

I also hope to develop a system for limiting the portions of the spline and circle set that need to be checked continuously during the expansion method. This could take the form of data stored by circles about the places they touch the spline. (If a seed next to a large circle is between two of the large circle’s tangent points to the spline, a and b, then only points in the spline between the indexes a and b need to be checked)

This range could be limited further, to within the outer tangent points of any connected circles around the seed. In the ideal program, the spline will be ignored completely for a seed surrounded on all sides by circles.

The first basic step to my expansion function is to find the 3 nearest points of either circles or the spline, and to set the seed’s radius to the average of their distances.

Using the basic seed method with only a spline present, the seed often looks perfect after the first step. However, it is guaranteed to overlap at least one point. The next step is to move it directly away from the closest/most overlapped point until it is tangent to that point, and start over. It will be closer to the other two points after moving away from the first, usually…

…unless they’re all bunched together. (I caused this problem by smoothing a spline with many points.) In this case, the seed will still expand and move away from the spline until it touches other points, but it may do so very slowly. Luckily, the seed will never have this problem when interacting with placed circles, because a circle will only provide one point as the nearest to a location.

The greatest challenge of this project? speed. I want to save enough frames to render a 30fps music video, with at least 64 circles in each frame. It could easily take days if I approach this the wrong way.

This was inspired by the physics of the game Sugar, Sugar. It’s a neat flash game I remember from my childhood (7 years ago). At the top of each level, there are the words “Sugar, Sugar.” Sugar pours out of the comma, and you must direct it to the various coffee mugs by drawing ramps with the mouse pointer

It’s interesting because it simulates particles only by manipulating pixels – there is no gravitational acceleration, and this allows quite a lot of sugar to be simulated.

so I decided to create a sorting-based physics engine in python. This isn’t about to be implemented into a similar game, mainly because I got sidetracked. Bob Ross says there are no mistakes, just happy accidents. Instead of pulling sugar straight down, this one sorts in random directions to create an interesting pattern. This is a 2-dimensional bubble sort with a twist – it swaps only within single pairs of values, preventing a value from traveling farther than 1 square per frame.

I wanted a much better image of the curve I produced before I posted a question, so I re-made my algorithm in Python. It has a simple Pygame visualizer.

Python is plenty fast for these tests, and it allows me to quickly complete simulations with decent settings.

I represent the derivative of the curve in yellow. Usually this is a rather messy line, because of the large amount of randomness that still exists in the sorted samples. (I also waned the odds of randomization too quickly in the above image, resulting in a misshapen curve with a steeper drop on one side.)

To get a smoother curve, I run many simulations in parallel, then draw the average.

I posted this question on Quora. Lev Kyuglyak responded that it may be a logistic function that produces a sigmoid curve, and that it could be can be represented in the form:

I am skeptical that my program can create a real sigmoid curve, because those graphs have an infinite domain, while the results of my simulations always have a domain of exactly [0,1]. perhaps my program compresses that infinite distance into a very small space as it approaches the left or right of the array. I’m currently thinking of ways to modify my program to have a much larger domain around the point of inflection.

The first change I’ve tried is to modify the probability of randomization with the difference between a traveling sample and its surroundings. samples that are closer in value to their surroundings have a lower chance of randomization and thus travel farther, perhaps forming larger flat areas at the start and end of the curve.

They kinda do, but not in the way I expected.

Weirdness!

Yesterday I wanted to remake my Gravo project using Pygame. It’s Christmas break, so I was actually able to do that.

Here I represent each particle with a line of a length proportional to its speed:

The white lines represent each force acting on a particle at any given time. When two particles pass near each other, the forces grow larger and the lines reach farther.

The twinkling effect is rather cool, but I was more interested in the movement of the ends of those force lines. Further experimentation led me to create this:

Here, lines are drawn following each particle, but floating away from it at a distance determined by a force. Each particle has a line corresponding to each other particle. these lines create a figure 8 or an hourglass when two particles slingshot around each other. the color of the line is also determined by the forces acting on a particle (bright green represents a strong horizontal force, bright blue represents a strong vertical force)

I found that I could add at least 64 particles without significant lag:

Finally, I began to experiment with zooming effects. previously, I have been dimming  the screen and painting over it again to produce the echo. Now I store the current frame to be painted in the background of the next frame.

Here’s my code:

import random as rand
import pygame
import pygame.event
import math

size = [720,720]
screen = pygame.display.set_mode([1280,720])
pygame.display.set_caption("gravo2d")

back = pygame.Surface([1280,720])

class particle:
	
	def __init__(self, groupSize):
		self.pos = (rand.uniform(0.0,1.77777777), rand.uniform(0.0,1.0)) #start anywhere
		self.vel = (rand.uniform(-0.01,0.01), rand.uniform(-0.01,0.01)) #start with a random velocity
		self.charge = rand.uniform(0.5,1.5)*(rand.randint(0,1)-0.5) #charge varies but is never nearly 0
		self.mass = rand.uniform(0.95, 1.05) #mass affects response to forces
		self.color = [int(128+self.charge*128),0,int(128-self.charge*128)] #particle color is based on charge
		self.forces = [] #all forces between this particle and particles of higher index (longest for the first particles)
		self.forceIndex = 0 #the force currently being edited by the simulation
		self.sharedForce = (0.0,0.0) #the equal and opposite force that the simulator uses for the other particle in the pair
		for i in range(groupSize+1):
			self.forces.append((0.0,0.0))
		self.netForce = (0.0,0.0) #modified many times before being acted upon and reset to 0
		
	def addForce(self, drawOnto, f): #used to inform a particle of the force from another particle.
		#add force to net forces
		self.netForce = (self.netForce[0]+f[0],self.netForce[1]+f[1])
		#color with velocity influencing red component, horizontal force for green and verticle force for blue.
		color = [int(511*abs(self.vel[0]+self.vel[1])),(160*math.atan(10000.0*abs(f[0]))),(160*math.atan(10000.0*abs(f[1])))]
		#represent increase in force with a line who's distance from the particle increases.
		self.drawLine(drawOnto, color, [self.pos[0]-self.vel[0]+self.forces[self.forceIndex][0]*64,self.pos[1]-self.vel[1]+self.forces[self.forceIndex][1]*64], [self.pos[0]+f[0]*64,self.pos[1]+f[1]*64], 4)
		#forces[forceIndex] stores this force until next tick  to start the next line segment at the end of this one. sharedForce holds the last force when recording this force, so that the subseuent simulation of the other particle in this pair can use it later in the tick.
		self.sharedForce = self.forces[self.forceIndex]
		self.forces[self.forceIndex] = (f[0],f[1])
		#next time, dealing with a force from a different particle, remember a different last force.
		self.forceIndex += 1
		return color
		
	def acceptForce(self, drawOnto, f, previous, color): #used when an unknown particle of lower index forces this one.
		self.netForce = (self.netForce[0]-f[0],self.netForce[1]-f[1])
		self.drawLine(drawOnto, color, [self.pos[0]-self.vel[0]-previous[0]*64,self.pos[1]-self.vel[1]-previous[1]*64], [self.pos[0]-f[0]*64,self.pos[1]-f[1]*64], 4)
		
	def move(self): #move based on velocity
		self.pos = (self.pos[0]+self.vel[0],self.pos[1]+self.vel[1])
		
	def react(self): #accelerate based on net force
		self.vel = (self.vel[0]+self.netForce[0]*0.1*self.mass,self.vel[1]+self.netForce[1]*0.1*self.mass)
		self.netForce = (0.0,0.0)
		self.forceIndex = 0
		
	def bounce(self): #bounce off the walls
		if (abs(self.pos[0]-0.88888888)>0.88888889): #left and right sides
			self.vel = (self.vel[0]*-0.9,self.vel[1]*0.9) #reverse direction
			#find new position by mirroring over the edge once past it:
			self.pos = (abs(self.pos[0]) if self.pos[0]0.5): #top and bottom sides
			self.vel = (self.vel[0]*0.9,self.vel[1]*-0.9)
			self.pos = (self.pos[0], abs(self.pos[1]) if self.pos[1]

Recently, I saw a fascinating imgur post that visually demonstrates how various sorting algorithms work. I wanted to invent some of my own sorting algorithms with visuals, so I started a new scratch project.

The first two algorithms I added to the project were Bubble Sort and another which I don’t know the name of. it traverses the array to find the minimum after this item, then swaps that minimum with the current item and moves to the next item. Simpler and faster than Bubble Sort, but Bubble Sort has more interesting visuals in my opinion.

I really enjoy jumping into projects without doing any research at all, and I actually mirrored some concepts found in FLAC with my blind draft of a lossless audio codec. passes of increasing sample rate, each only storing the inaccuracies of the previous one – this is what I understand bit peeling to be. I’m sure that leaping without looking has a lasting effect on how I understand these things, even after I read the Wikipedia article on them. It also probably delays my exposure to new concepts, but it’s a very fun way to learn…

The visuals of these algorithms are mesmerizing, and I think they would make good screen savers. That’s what led me to modify the Bubble Sort algorithm to never finish. Each time two array items are switched, each has a very low chance of being set to a random value. I expected it to look like a normal Bubble Sort, with just a bit of noise to make the odds of it finishing very low.

But I did not get chaos.

This uses only random values.

I’ve modified my program so that the chances of an item being randomized decrease over time, so this program will eventually halt with a nearly perfect curve.

Here’s what I notice:

• samples with extreme values often travel the farthest.
• samples that come to rest near the edges hardly ever change
• samples near the middle, being more random, are swapped and randomized most often.
• Samples that travel farther have a greater chance of being randomized again before coming to rest.
• samples approaching the edges can only randomize samples with less extreme values.
• samples near the edges, when randomized, often become less extreme and move towards the center.

so what is the curve? it looks like part of a sine wave, or perhaps an arctangent.

But since everything about the process is linear – the increasing probability of randomization with increasing number of swaps – or increasing exponentially, e.g. the increasing probability of randomization in the wake of a traveling sample as it randomly creates more samples that will travel… It might be the integral of a parabola. I’m not sure how, but I won’t rule it out.

This is a Quora question if I’ve ever seen one. I’m just waiting to get a better screenshot. the odds of randomization are now 162:1 and increasing.

…finished!

It doesn’t look like a sine wave to me – but maybe that’s because the odds against getting extreme samples were so high that the crest and trough couldn’t be built before I terminated it. There’s a small chance that I’ve discovered a new way to calculate some constant like π or e. but I still don’t know what kind of curve it is.

To the internet!