algorithm

Streaming descriptive statistics

I recently ran into the problem of getting sample statistics from potentially infinite population or very large sample sizes. The problem is that most algorithms scale linearly with this problem domain. Especially when looking at quartiles. I am going to detail below firstly how I was doing things and secondly …

Urquhart Graph

In computational geometry, the Urquhart graph of a set of points in the plane, named after Roderick B. Urquhart, is obtained by removing the longest edge from each triangle in the Delaunay triangulation. Using the as3delaunay library to generate the triangulation, I then proceeded to remove the longest edge from each triangle to create the Urquhart graph. I …

Voronoi Dungeon Generator

Continuing from the previous post on irregular shaped room generation. The idea is to make use of multiple rooms to create a dungeon. A room’s connectedness is determined by calculating a minimum spanning tree on a delaunay triangulation using a voronoi diagram from the as3-delaunay library. This ensures that all rooms are …

Irregular Shaped Rooms / Caves

I was looking at procedural dungeon generation and found a link on how to generate irregular shaped rooms which can be included in dungeon generation. The idea is to reduce the repetition of square rooms and give a more natural look to the dungeon. I decided to implement the algorithm …

Making a cave-like structure with worms

Growing on the idea from a previous post on making a cave-like structure, this is a different algorithm which makes use of worms / miners to dig out the initial level layout from the rock layer. Thereafter fun things are done to the level to make it look nicer. For example: …

Making a cave-like structure

There are a lot of tutorials on the net that make use of cellular automata to generate cave-like structures. Cellular automata are easy to program and I found a C & C# implementation which I used as a base for this method. The relevant method to generate the cave is …

FNV32 hash in Actionscript

I am converting a library from C++ and some parts C to Actionscript. I am really learning a lot of things whilst doing this. One of them, which I cannot wait till the end to talk about, is the C FNV hashing that I converted. It might not be completely …

Sum to Fifteen (All About Perspective)

I got the idea for this game from a lecture I was watching, given by Scott E. Page. He gave the online course Model Thinking over at Coursera. He is a lecturer in Complex Systems at the University of Michigan.  He presents the idea of how perspectives have such a large influence …