Algorithm Design: Optimising the Marbles

The previous post showed 3000 ball bearings being squeezed together. The app wasn't that efficient beyond 5000 particles, so needed optimising.

Good news: I've designed (reinvented!) a way of scaling this with linear complexity: space partitioning. Assuming a hex layout in a 2D space, about 15% of the collision tests will be positive, regardless of the number of particles.

e.g. for 10m particles, we'd use about 400m tests for 60m hits. This compares favourably against nested loop approach of complexity O(n^2), with 5Ã—10^13 tests, with 0.00012% of them being hits.
Post has attachment
Following on from the "3000 ball bearings" video [1, ] that illustrates faults in physical sphere packing and crystal structures, I modified my "Spot 2" sim to use particles of identical size. Here are 3000 of them [2, pic]

[2] http://johnvalentine.co.uk/spot3.html
Post has attachment
Phase Solver pt4: more interactive exploration, image export

New:
* Click to re-center
* Zoom in and out
* Export as PNG.
* Resolutions: 1/8 for speedy navigation, 8 for high-quality renders.

I started this session thinking I'd implement multi-threaded processing and async workers, but instead I improved the UI. I think that made a bigger difference to usability, but it still ties up the main thread.

There's a slight error on the vertical axis when re-centering.

http://johnvalentine.co.uk/app/phase/phase.html
Post has attachment
Phase Solver pt3: Have a play

I have a huge todo list for this HTML+JavaScript app.

http://johnvalentine.co.uk/phase2a.html
Post has attachment
Phase Solver, pt2: An imperfect implementation of a 'continued fraction'

I say "imperfect" because I haven't included the zero-th term, and I've limited 'n' to a small odd number. I also think I did it wrong, which is giving me the interesting result here.

Complex phase is mapped to greyscale, but is shifted. Again, imperfect.

I'll work again on this soon.
Post has attachment
Phase Solver

It's nowhere near ready yet, but I thought I'd make a start on the UI. Maybe I was a teensy bit distracted by making it pretty, and forgot about doing the mathsy bit, where that big black space is?
Post has attachment
Slotted Polygons

I rediscovered a render script I made in 2008, so just had to make some images from it!

It recreates the educational toy, whose name I forget, which let you slot octagons together. This script generalizes the shape, so that you can use any regular polygon, and slots many of them together into a large tree.

The pictured example uses pentagons in six hues, to a maximum recursion depth of 13, and a maximum count of 380 (200 were used). I really like the yellow piece at the bottom.

What were the challenges?

1. Rotations, relative to the previous piece. I seem to recall using quaternions for that.

2. Avoiding collisions, for which I used a very approximate occupancy test.

3. Computationally-efficient lighting.

4. Transparency properties, especially colour, saturation and transmission. I spent a bit of time on the micro-surfaces too, which blur distant objects seen behind a piece.

Parameters

Camera setup, soft lighting (Y/N), use caustics (Y/N), piece thickness, edge roundness, select random polygon (Y/N), polygon sides (min, max), hue points for piece colours, structure recursion depth, max piece count, collision proximity, placement attempts bailout, (and others)
Post has attachment
Inner Products ...or simple CSG

Here's a quick demo of a script I wrote in 2004. It creates a solid that, when viewed from different angles, shows a different letter. In this case, I have coloured lights so you can see the shadows from the object.

It should work reasonably well for any letter that has continuous content from left to right, and top to bottom. (I should also allow for typographical features to prevent loss of features that extend beyond guide lines)
Post has attachment
How do we know what math research is worthwhile? [tessellations]

Every so often, I take a peek at what's happening in mathematics or physics. I'm probably not alone when I think, "someone wrote a paper on that?". After a while, usually while cooking food for the family, I think a bit, around what I imagine to be the abstract and practical problems, and it's pleasantly interesting, but I wouldn't want to formally cover every nuance of the problem. A little while later, I might remember that I did something similar that was part of the wider category of associated problems, and wonder whether I could or should have explored it in more detail.

One of my feeds regularly reports on shape-packing: how to pack polygons into planes or surfaces, how to fit regular solids into each other, the polynomial solution that maximally crosses its own path, and so on.

This leads me on to an example: Minesweeper. It's not the P-NP problem that people think of; rather I was briefly interested in the way that differently-shaped minesweeper cells affected game balance. The case of a square is reasonably trivial: each square (not on the edge of the board) has 8 neighbours, and when you count the distribution of the squares that have 0, 1, 2, 3, â€¦ neighbouring mines, you can predict approximately how playable the game will be.

However, I didn't just write Minesweeper. I introduced variations: holes (inactive parts of the grid), linked cells (which tied two non-adjacent cells together for counting neighbouring mines), and shaped cells (which grouped contiguous cells into bigger areas).

Shaped cells proved most interesting, because using areas composed of squares, you could simulate other shapes of cell. For example, using 1Ã—2 areas, you could create a pattern that matches a hexagonal game board by offsetting every second column of areas downwards one cell. A hexagonal board gives you a possible mine count in the range 0..6, so although the board construction seems less trivial, the gaming possibilities are more constrained.

We could also create shapes that have more neighbours, like the one pictured. Rather than the 8 neighbours of a square grid, this "Scroll Lock 2" variant has up to 9 neighbours. Other variants go further, or introduce patterns where there are easy and difficult cells. Large cells can make the smaller cells more difficult to solve, and so on.

Here's the question: is there potential for interesting mathematical exploration here? What would the intrinsic and derived properties be? Can this be applied usefully to anything else, or can other studies be applied here?

Refs:

[1] Here's the app, made for Windows 95â€“10 Desktop:
http://johnvalentine.co.uk/crossmines.php

Note that there's a bug, where, is you choose a 'pattern' game, you have to go in and choose the pattern each time.

[2] "How does one choose which bits of maths will be the ones to make the huge impact down the track?" https://plus.google.com/+DavidRoberts/posts/duMz4SU32ST