Dev.Mag
You are currently browsing articles tagged Dev.Mag.
(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.
Read the rest of this entry »
Tags: AI, algorithm, C++, compression, Dev.Mag, image partitioning, Image Processing, quadtree, quadtrees, spatial partitioning, sum
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!
24 October 2009 |
I wrote an article for Dev.Mag covering some techniques for working with seamless tile sets such as making blend tiles, getting more variety with procedural colour manipulation, tile placement strategies, and so on.
Check it out!
The Python Image Code has also been updated with some of the algorithms explained in the article.
28 May 2009 |
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.
Read the rest of this entry »
Tags: 2D, AI, algorithm, blending, cellular automata, Conway's game of life, Dev.Mag, diffusion, discrete dynamics, disease simulation, fire simulation, force, Game Maker, grids, optimisation, probability, random, sampling, Simulation, social dynamics, sum, tiles
I studied computer engineering at the University of Pretoria. I worked in game development for almost three years, before I joined InnovationLab to help them create interactive simulations and serious games. After two years, I got back into game development, working for I-Imagine. In 2010 I completed my honors degree, and I have recently taken up the reigns of the South African game development magazine Dev.Mag.
Some projects that I have worked on:
More music: http://www.youtube.com/user/hermantulleken2
Articles for Dev.Mag:
Email: herman.tulleken@gmail.com
Tags: AI, Dev.Mag, Game Development, Perlin noise, poisson disk, sampling, Simulation, tiles, tool development
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).
Tags: 2D, AI, compression, computer graphics, Dev.Mag, image partitioning, Image Processing, Python, quadtree, quadtrees, random, spatial partitioning
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.
Tags: 2D, AI, blending, Dev.Mag, Perlin noise, Python, quadtree, quadtrees, random, sampling, tiles
The quadtree is an important 2D data structure and forms the core of many spatial algorithms, including compression, collision detection, and stitching algorithms. Below you can download general purpose quadtree implementations in Java and Python.
The code accompanies the Quadtrees article in Dev.Mag. The tutorial explains how the implement a quadtree that can be use to store 2D data efficiently, lists what considerations there are in real-world applications, and gives some debugging tips.
Channels Compressed Simultaneously
 |
 |
| The original image (by smcgee). |
The image after being loaded into a quadtree. |
Read the rest of this entry »
Tags: 2D, AI, compression, computer graphics, Dev.Mag, Game Development, image partitioning, Image Processing, Python, quadtree, quadtrees, spatial partitioning
Google App Engine has many properties that makes it suitable for indie development. Two articles in Dev.Mag look at GAE for game development (Issue 24 and Issue 25). The first is an overview of Google App Engine, with some focus on games. The second is a tutorial that explains the implementation of “Guess a Number” on Google App Engine, for which you can download the code. For the tutorial you will need:
Read the rest of this entry »
Tags: AI, Dev.Mag, Django, editor, Game Development, Google App Engine, Python, Web Development
Recent Comments