Michael Fogleman

Projects AboutResumeMore

Projects tagged "c"

This page highlights several of my personal software projects.

Table of Contents

Heightmap Meshing August 2019

558 C++ 3D Meshing

Convert any grayscale heightmap into a 3D triangle mesh.

This is a modern implementation of a nice algorithm from the 1995 paper Fast Polygonal Approximation of Terrains and Height Fields by Garland and Heckbert. The meshes produced by hmm satisfy the Delaunay condition and can satisfy a specified maximal error or maximal number of triangles or vertices. It's also very fast!


Cellular Forms June 2019

153 C++ Generative 3D

An implementation of Andy Lomas' Cellular Forms.

This is an implementation of a generative algorithm by Andy Lomas, described in his paper Cellular Forms: an Artistic Exploration of Morphogenesis.

While Andy implemented his algorithm on the GPU, my implementation is CPU-based. It includes a real-time viewer where you can watch the forms grow. It can also export STLs, which I used to then ray-trace the results. I found it interesting to "chop" the models in half, revealing their intricate inner structure as shown in the image here.

DLA February 2019

183 C++ Generative 2D 3D

Fast diffusion-limited aggregation in both 2D and 3D.

This is a small program that generates diffusion-limited aggregations in either 2D or 3D. The output is a CSV file containing the coordinates of the particles and their relationship to one another. Rendering is out of scope, but I have produced several example renders. The code is very configurable - there are a few parameters that you can tweak and there are also several code hooks that allow you to alter the algorithm's behavior.

Rush Hour June 2018

283 Go C++ Game AI

I solved the Rush Hour puzzle game and created a database of every interesting starting position.

Rush Hour is a 6x6 sliding block puzzle invented by Nob Yoshigahara in the 1970s. It was first sold in the United States in 1996.

I played a clone of this game on my first iPhone several years ago. Recently, I stumbled on the physical incarnation of it and instantly bought it on Amazon for my kids to play. We've been having fun with it, but naturally I was most interested in writing some code to solve the puzzles.

I did more than write a simple puzzle solver. I ended up computing every possible puzzle and built a complete database of every "interesting" starting position. It was quite challenging (and exciting!) so I wrote a whole article about it. Check it out!

Mister Queen October 2014

146 C Game AI

Mr. Queen is a nice little chess engine written in C.

I wrote my first chess engine back in college. It didn't play very well because I never really figured out the advanced search techniques. More recently, after a long hiatus, I tried my hand at writing a chess engine again, and Mister Queen is the result. It's pretty weak among computer chess engines, but it can beat me handily. Features include:

  • Bitboards and "magic" bitboards for board representation and super-fast move generation.
  • Custom, hash-based opening book based on over three million games from the FICS database.
  • Zobrist hashing and a transposition table storing exact values and the best move.
  • Null move pruning, aspiration windows, iterative deepening, quiescence search.
  • Supports the Universal Chess Interface (UCI).
  • Passes all perft tests.

David Kopec used Mister Queen in a chess app for the Apple TV! Read what he wrote about that here.

AllRGB March 2014

61 Python C 2D Graphics

Generate images that use all 16,777,216 RGB colors exactly once.

Efficiently create AllRGB images that target an input image. The input must be 4096x4096px. The output will also be 4096x4096px and will contain all 16,777,216 distinct RGB values once and only once.

See allrgb.com for details on the concept.


Graph Layout February 2014

112 Python C Graphs Optimization

Experimenting with graph visualization using simulated annealing for layout.

Graphviz is the main player when it comes to graph visualization. But its output isn't very appealing, at least not by default. With this in mind, and being a fan of simulated annealing, I experimented with using annealing for graph layout. The results are pretty good, but it probably doesn't scale very well. The algorithm basically tries to minimize the following metrics, with different weights applied to each:

  • Node-Node Intersections
  • Node-Edge Intersections
  • Edge-Edge Intersections
  • Edge Lengths
  • Total Graph Area
  • Node Rank Violations

Craft April 2013

10,212 C Python Game OpenGL

Minecraft clone for Windows, Mac and Linux.

A very performant Minecraft clone written in just a few thousand lines of C using modern OpenGL (shaders). Online multiplayer support is included using a Python-based server. Many people have used this as a base upon which a more complex game was built.



DCPU-16 April 2012

70 Python C Emulator

An assembler, disassembler and emulator for the virtual DCPU-16 written in Python and C.

The DCPU-16 was intended to form the basis of a video game by Mojang called 0x10c. Work on the game has since discontinued, but at the time there was a lot of excitement around this virtual hardware.

Implemented Specifications

  • DCPU-16 1.7
  • LEM1802
  • Generic Keyboard
  • Generic Clock

Ricochet Robot February 2012

54 Python C Game AI

Implementation of a board game called Ricochet Robot including a GUI and a very fast solver.

My friend introduced me to a board game called Ricochet Robot (or Rasende Roboter in its original German form). It's a fun game, but I found it even more fun as a programming problem. I implemented the game in Python, including a user interface and a solver. After that, I sped up the solver tremendously by porting it to C. My solver includes several "tricks" that make it quite fast. See these slides for more details.