Pentagons

A while back I developed a mild obsession with pentagons (mathematical ones, not symbolistic!) It started when I discovered some beautiful (simple and to me, unknown) theorems of quadrangles, such as  Varignon’s theorem. I already came across Miquel’s pentagon theorem, and wondered what other gems I could find.

Here is what I found: Pentagons (2.4 MB PDF).

My search was on the surface a bit disappointing: pentagons as such are not widely studied. I guess it is because some more general theorems (that apply to general polygons) contain the theory, and the specifics as applied to pentagons are not so interesting.

Nevertheless, I did discover a few theorems, and the journey took me into some very interesting corners of geometry; a very rewarding experience. I started to collect these into a document, which is shared below. It’s not comprehensive or complete; there are a few gaps.

(At some stage I may return to look at this again. In particular, there are many theorems of the type “if there is n, there is n+1”, which seems to me to hint at a very general theorem which can be used to prove a bunch of specifics.)

Also, when I started, I did not realise how many of the theorems will generalise to general polygons, so the collection looks a bit silly in retrospect (kind of like listing all the properties of the number 8 that equally apply to even numbers).

Even so, what’s done is done, and can perhaps satisfy someone else’s curiosity.

Continue reading “Pentagons”

Region Quadtrees in C++

quadtree

(Original image by GoAwayStupidAI).

Below are four C++ implementations of the region quadtree (the kind used for image compression, for example). The different implementations were made in an attempt to optimise construction of quadtrees. (For a tutorial on implementing region quadtrees, see Issue 26 [6.39 MB zip] of Dev.Mag).

  • NaiveQuadtree is the straightforward implementation.
  • AreaSumTableQuadtree uses a summed area table to perform fast calculations of the mean and variance of regions in the data grid.
  • AugmentedAreaSumTableQuadtree is the same, except that the area sum table has an extra row and column of zeros to prevents if-then logic that slows it down and makes it tricky to understand.
  • SimpleQuadtree is the same as AugmentedAreaSumTableQuadtree , except that no distinction is made (at a class level) between different node types.

Continue reading “Region Quadtrees in C++”

Tips for Designing and Implementing a Stimulus Response Agent

brain
(Original Image by everyone’s idle.)

This post was a originally published on Luma Labs, now dead.

As old as stimulus-response techniques are, they still form an important part of many AI systems, even if it is a thin layer underneath a sophisticated decision, planning, or learning system. In this tutorial I give some advice to their design and implementation, mostly out of experience gained from implementing the AI for some racing games.

A stimulus response agent (or a reactive agent) is an agent that takes inputs from its world through sensors, and then takes action based on those inputs through actuators. Between the stimulus and response, there is a processing unit that can be arbitrarily complex. An example of such an agent is one that controls a vehicle in a racing game: the agent “looks” at the road and nearby vehicles, and then decides how much to turn and break.

Continue reading “Tips for Designing and Implementing a Stimulus Response Agent”

Guerrilla Tool Development

guerrilla_tools Tools for editing game levels and AI for your own games are nice to have, but it is not always practical to implement these for small projects, nor is it affordable to buy them off-the-shelf or bundled with expensive middleware.

In the Dev.Mag article Guerrilla Tool Development, I give some ideas for getting some useful tools on a tight budget. Check it out!

15 Steps to Implement a Neural Net

neuron

(Original image by Hljod.HuskonaCC BY-SA 2.0).

I used to hate neural nets. Mostly, I realise now, because I struggled to implement them correctly. Texts explaining the working of neural nets focus heavily on the mathematical mechanics, and this is good for theoretical understanding and correct usage. However, this approach is terrible for the poor implementer, neglecting many of the details that concern him or her.

This tutorial is an implementation guide. It is not an explanation of how or why neural nets work, or when they should or should not be used. This tutorial will tell you step by step how to implement a very basic neural network. It comes with a simple example problem, and I include several results that you can compare with those that you find.

Continue reading “15 Steps to Implement a Neural Net”

Cellular Automata for Simulation in Games

header

A cellular automata system is one of the best demonstrations of emergence. If you do not know what cellular automata (CA) is, then you should go download Conway’s Game of Life immediately:

Conway’s Game of Life

Essentially, CA is a collection of state machines, updated in discrete time intervals. The next state of one of these depends on the current state as well as the states of neighbours. Usually, the state machines correspond to cells in a grid, and the neighbours of a cell are the cells connected to that cell. For a more detailed explanation, see the Wikipedia article.

Even simple update rules can lead to interesting behaviour: patterns that cannot be predicted from the rules except by running them. With suitable rules, CA can simulate many systems:

  • Natural phenomena: weather, fire, plant growth, migration patterns, spread of disease.
  • Socio-economic phenomena: urbanisation, segregation, construction and property development, traffic, spread of news.

Continue reading “Cellular Automata for Simulation in Games”

About Me

ht1_smallI am Herman Tulleken.

I have an honors degree in computer engineering, and I have been making games professionally since 2006, working for Luma Arcade, InnovationLab, I-Imagine and ICE and for many others as a freelancer. In 2013 I partnered with friend / colleague Jonathan Bailey to start a new game-tools business Gamelogic. In 2015 we started a community of game developers in Chile, which became GameDev Planet in 2016.

I have written on many game development and related topics (on Gamasutra and others). You can get a full list on my Writing page.

On occasion I also compose the odd piece of music, mostly for piano.

Email: herman.tulleken@gmail.com

View Herman Tulleken's profile on LinkedIn

 

 

Random Steering – 7 Components for a Toolkit

Random steering is often a useful for simulating interesting steering motion. In this post we look at components that make up a random steering toolkit. These can be combined in various ways to get agents to move in interesting ways.

You might want to have a look at Craig Reynolds’ Steering Behaviour for Autonomous Characters — the wander behaviour is what is essentially covered in this tutorial. The main difference is that we control the angle of movement directly, while Reynolds produce a steering force. This post only look at steering — we assume the forward speed is constant. All references to velocity or acceleration refers to angular velocity and angular acceleration.

Whenever I say “a random number”, I mean a uniformly distributed random floating point value between 0 and 1.

Continue reading “Random Steering – 7 Components for a Toolkit”

Quadtrees

The code below implements some quadtree extensions, as discussed in another Dev.Mag tutorial about quadtrees (see Issue 27). The tutorial covers the following topics:

  • what to consider in choosing whether to use a quadtree or not;
  • tests to help you choose an appropriate threshold;
  • how to handle discrete data; and
  • some modifications to the basic algorithm.

Handling Discrete Data

When it comes to discrete data, the “average” of a number of pixels doesn’t make sense. However, we can give it meaning and still use it to get good approximations of the original data, as illustrated in the images below.

The original grid of discrete data. The grid contains integers from 0 to 4. Every integer is mapped to a colour in this image. (If this grid represented a tile map, every integer would be mapped to a different tile).
Here we allowed floating point numbers in the quadtree. Results of queries into the quadtree are rounded before mapping them to colours.
Here we used the floating point part of queries to bias a randomly selected integer. For example, a result of 1.25 will result in a 75% chance of yielding 2.
Here we use a quadtree with interpolation. The result is rounded before it is mapped.
Here we use a quadtree with interpolation, and use the floating point part of the number to bias a randomly selected tile, as above.

Download

Python Implementation

Download from: http://code-spot.co.za/python-image-code/ (See quadtree.py, quadtree_image.py, and quadtree_demo.py).

Python Image Code

I use this code to illustrate many of the tutorials on this site, and the articles I write for Dev.Mag. Ideally, I would like to package the code so that it is the minimal necessary for the particular tutorial; however, a lot of the code is reused, so that it becomes difficult to maintain. Instead, I distribute it all together. That way, new updates and extensions can be found in one place.

The current version includes classes and functions for:

  • easy-syntax 2D and 3D arrays (for example, you can use grid[1:20:2, 2:3:20] to access the pixels in every second column (starting with column 1 and ending before column 20) and every third row (starting from row 2 and ending before row 20) (docs);
  • general image utility function (docs);
  • perlin noise (docs, tutorial);
  • poisson-disk sampling (docs, tutorial);
  • texture generation algorithms (docs, tutorial);
  • quadtrees (docs, tutorial part1 and part 2);
  • classes for generating random points (1D and 2D) from arbitrary distributions (docs, tutorial);
  • functions for blending between images (for smooth transitions between regions in seamless tile sets) [see blend_demo.py, tutorial];  and
  • functions for image quilting (under construction).
A few notes:
  • The code is not optimised, and in general convenience and clarity takes precedence over speed. This code is not suitable for many applications where speed is important.
  • The code will change often. At this stage I do not try to make it backwards compatible.

Download

Python Image Code v0.6

python_image_code_v0_6.zip (593 KB)

Requires PIL (Python Image Library).

This version includes some of the dependencies that accidentally got left behind in the previous version.