Just a little fun one because I've finished my exams and I haven't had time to start any big projects yet. A bit of very simple inverse square law gravitational physics to simulate the sombrero galaxy. All orbiting stars are attracted to the centre of the galaxy by an amount proportional to 1 over the square root of the distance between them.

Just click the two images below to launch the 2D and 3D simulations! Enjoy.

The three examples below show that with slightly different initial conditions, the shapes we find in a simple galactic simulation like this one, are actually surprisingly similar to those we see in real galaxies, for example in the first you can almost see the emergence of the spiral arms of our own galaxy the Milky Way.

## Monday, 31 May 2010

## Thursday, 27 May 2010

### Self Painting Images in Flash

Leading on from the previous post I decided to automate the painting process. The brush moves around the screen randomly creating a stipple like effect by increasing and decreasing pressure. Take a look, its really quite hypnotic. Just click on the image below to launch it.

Labels:
AS3,
Paint,
procedural generation

## Wednesday, 26 May 2010

### Wet Paint Mixing in Flash

One of my favourite features on Photoshop CS5, is the wet mixer brush, which is almost like a real paintbrush to use. I decided that if photoshop could do it, so could I, and a started to work on writing some actionscript that would handle the job.

The basic idea is that a brush is made up of bristles. When you press down on the screen each bristle picks up a certain amount of paint from the pixel it is currently over, and then as you drag your brush around, each bristle drags paint around underneath it.

To do this I wrote some actionscript that found the colour under each bristle, mixed the paint that was already on the bristle with the new paint underneath it, and then moved that new colour to the new location of the bristle. The program draws the paint stroke onto a new layer, a kind of buffer, which it then blurs (for added realism) and copies back onto the original painting.

Here are a few initial results:

Original Image

Painted version:

And here are a few more examples of another image created with it. I'm actually getting similar results as with the photoshop brushes which I'm quite pleased about. To launch the application simply click here and give it a go for yourself. Let me know what you think!

The basic idea is that a brush is made up of bristles. When you press down on the screen each bristle picks up a certain amount of paint from the pixel it is currently over, and then as you drag your brush around, each bristle drags paint around underneath it.

To do this I wrote some actionscript that found the colour under each bristle, mixed the paint that was already on the bristle with the new paint underneath it, and then moved that new colour to the new location of the bristle. The program draws the paint stroke onto a new layer, a kind of buffer, which it then blurs (for added realism) and copies back onto the original painting.

Here are a few initial results:

Original Image

Painted version:

And here are a few more examples of another image created with it. I'm actually getting similar results as with the photoshop brushes which I'm quite pleased about. To launch the application simply click here and give it a go for yourself. Let me know what you think!

Labels:
AS3,
Paint,
Photoshop,
procedural generation

## Saturday, 15 May 2010

### Attempt at "fast" solution to the N-Body Problem

The N-Body problem is a very interesting problem both mathematically and in real world applications such as in observational cosmology. The basic idea of the N-Body Problem is, given N gravitationally interacting bodies, what is the most efficient way to solve the subsequent motions of all of the bodies given some initial conditions? I will be looking at the problem in 2 dimensions.

Lets first take a look at the example in its simplest form, with just two bodies. The two bodies pull on each other by the gravitational force, which causes both to accelerate along a vector pointed along the line joining them. This is a very simple problem to solve and any university level physicist should find solving it trivial. In the case of more bodies however, an analytical solution becomes extremely complicated and far beyond the reach of my mathematical understanding; but what I do understand is computers and iterative techniques. The simplest way therefore to solve a problem with more than two bodies would be simply to summate the forces of all the bodies acting on one body at a given moment in time and update its velocity, then repeat this for each of the other bodies in your system.

Obviously for a number of bodies N, the number of force checks that would have to be done would increase very quickly, in fact at a rate N*N, which means for 1000 bodies, 1 million checks would have to be carried out, remember this is per instant in time.

I propose a solution that uses the bitmap functionality in flash, along with the blur filter. I am sure that it won't stand up to rigorous mathematical scrutiny, but from an aesthetic standpoint, it does the job near enough ok.

The idea is that each body is represented by a pixel, with a colour related to its mass. By applying a blur filter on the bitmap, the gravitational field of the pixel is extended into the surrounding region. A brighter region means more gravitational force, and a darker region less. To solve the problem particles simply need to be accelerated along the line of highest gradient towards brighter regions. This way only N checks have to be carried out massively decreasing computing time.

For example carrying out the test with 10,000 particles, which would otherwise kill my computer (at 24 frames per second that would be 2,400,000,000 force checks per second!) it actual runs reasonably well!

Anyway take a look and feel free to make suggestions to improve the model. Just click the first image to launch the simulation!

Note: Limitations of the simulation include -

Lets first take a look at the example in its simplest form, with just two bodies. The two bodies pull on each other by the gravitational force, which causes both to accelerate along a vector pointed along the line joining them. This is a very simple problem to solve and any university level physicist should find solving it trivial. In the case of more bodies however, an analytical solution becomes extremely complicated and far beyond the reach of my mathematical understanding; but what I do understand is computers and iterative techniques. The simplest way therefore to solve a problem with more than two bodies would be simply to summate the forces of all the bodies acting on one body at a given moment in time and update its velocity, then repeat this for each of the other bodies in your system.

Obviously for a number of bodies N, the number of force checks that would have to be done would increase very quickly, in fact at a rate N*N, which means for 1000 bodies, 1 million checks would have to be carried out, remember this is per instant in time.

I propose a solution that uses the bitmap functionality in flash, along with the blur filter. I am sure that it won't stand up to rigorous mathematical scrutiny, but from an aesthetic standpoint, it does the job near enough ok.

The idea is that each body is represented by a pixel, with a colour related to its mass. By applying a blur filter on the bitmap, the gravitational field of the pixel is extended into the surrounding region. A brighter region means more gravitational force, and a darker region less. To solve the problem particles simply need to be accelerated along the line of highest gradient towards brighter regions. This way only N checks have to be carried out massively decreasing computing time.

For example carrying out the test with 10,000 particles, which would otherwise kill my computer (at 24 frames per second that would be 2,400,000,000 force checks per second!) it actual runs reasonably well!

Anyway take a look and feel free to make suggestions to improve the model. Just click the first image to launch the simulation!

Note: Limitations of the simulation include -

- Blur is not complete, i.e gravity has a limited range - this may be analogous to simulations of the large scale universe where distances are two large for information to pass between.
- Blur takes multiple steps to update (slow information rate)
- Singularities such as collisions cause erratic behaviour (sudden velocity boosts)

Further Note: "Universe" has periodic boundary conditions, i.e X = X + Width & Y = Y + Height

Update: Running the simulation with more particles (100,000) without periodic boundary conditions yields interesting results. As expected the "universe" collapses in on its centre of mass. In this simulation I increased the blur distance, i.e the range of gravity, producing less local effects. The second image shows the simulation after it reaches a stable state with a large central mass.

## Friday, 14 May 2010

### Pedestrian Playground

Looking through one of my favourite books, Critical Mass, I came across a page I had been meaning to do some research into. The section of the book was on cellular automata, and the creation of complexity from simple rules. I mentioned a few posts ago about a paper I had read about solving the Travelling Salesman problem using ants. The travelling salesman solves the problem of getting between a number of towns using the shortest route possible. This is all well and good but the travelling salesman has an absolute answer, and in my opinion that immediately makes the problem slightly less interesting. The randomness of the human psyche is far more exciting, and the pedestrian motion created when you bring large groups of people together are often quite surprising. Take a look at the image below for example; the trails connect 3 points of interest

around a park. None of the paths join any of the 3 target locations in the most efficient way, yet after years of trampling down grass, and the slow fading of former trails, the most desired route (on average) is the one seen here.

Obviously park planners would have a much easier job keeping their lawns meticulous if they could somehow predetermine where people were most likely to walk, thus keeping pedestrians on the paths, and not trampling their grass. This problem is slightly more subtle than the travelling salesman, there are in fact many solutions and they depend on a huge number of factors: how many people want to go to each destination, how fast does grass regrow, how fast does a path form, how many people commute along the paths each day, do people have to walk uphill, is there a fence...? Obviously the list goes on for quite a while, after all humans are not predictable, but we can still create a simple model.

The screenshots below show the main interface of my application, just click the first image to launch it. The number of target towns, and the number of people can be changed, as can the size of random fluctuations in direction, the effect of the destination on the direction walked, and the effect of the route on the direction walked. Two factors called visibility, and distance factor also affect the likelyhood that a pedestrian will take the most direct route to their destination. Have a play around with the factors and see if you can reproduce the pattern seen above.

In the below examples you can see paths merging, even though this is not the most efficient route for anyone. The first image still has some "visibility", the second has absolutely none, people just tend to congregate randomly, but it does make a nice pattern, and the third shows path splitting, where two similar but separate routes form spontaneously.

around a park. None of the paths join any of the 3 target locations in the most efficient way, yet after years of trampling down grass, and the slow fading of former trails, the most desired route (on average) is the one seen here.

Obviously park planners would have a much easier job keeping their lawns meticulous if they could somehow predetermine where people were most likely to walk, thus keeping pedestrians on the paths, and not trampling their grass. This problem is slightly more subtle than the travelling salesman, there are in fact many solutions and they depend on a huge number of factors: how many people want to go to each destination, how fast does grass regrow, how fast does a path form, how many people commute along the paths each day, do people have to walk uphill, is there a fence...? Obviously the list goes on for quite a while, after all humans are not predictable, but we can still create a simple model.

The screenshots below show the main interface of my application, just click the first image to launch it. The number of target towns, and the number of people can be changed, as can the size of random fluctuations in direction, the effect of the destination on the direction walked, and the effect of the route on the direction walked. Two factors called visibility, and distance factor also affect the likelyhood that a pedestrian will take the most direct route to their destination. Have a play around with the factors and see if you can reproduce the pattern seen above.

In the below examples you can see paths merging, even though this is not the most efficient route for anyone. The first image still has some "visibility", the second has absolutely none, people just tend to congregate randomly, but it does make a nice pattern, and the third shows path splitting, where two similar but separate routes form spontaneously.

Subscribe to:
Posts (Atom)