## Posts tagged “algorithms”

### Discrete physics on a 2D grid: back to basics

Last week, I talked about a fairly sophisticated attempt at solving my 2D discrete physics problem, which ultimately turned out to have unfixable flaws. But I need this problem solved for my game, so I decided to relax my requirements for the time being. This is just to get something... Continue reading

### Discrete physics on a 2D grid: a dissatisfying solution

In last week’s post, I discussed my first two failed attempts at creating something like physics on a 2D grid. It gathered a good deal of attention on Reddit, with several replies from people claiming to have solved it, only to introduce new problems. As I already knew, this problem... Continue reading

### Discrete physics on a 2D grid: how hard can it be?

In the last post, I described my requirements for a 2D discrete physics system I’m working on. Now that I’ve laid out what the system should do, let’s turn to the implementation. Given a space with some walls, a set of objects, and some forces being applied to the objects,... Continue reading

### Discrete physics on a 2D grid: setting the stage

For a new game I’m working on, I need some 2D “physics” that work in discrete time and discrete space. In other words: every object consists of one or more blocks aligned to a square grid, and time advances in turn-based steps. If you’re thinking of Sokoban, you’ve got the... Continue reading

### A little puzzle experiment

Here’s a thing I’m working on: The aim is simply to classify each square on the grid as either land or water. Your clues consist of the following: A list of all islands in the grid. Islands are four-connected: two squares that touch only on their corners do not connect.... Continue reading

### Twistago AI, part 3: Hard

This is the third and final part of a series in which I explain how the artificial intelligence works in my latest game, Twistago. In case you missed the first or second part, you can catch up on them here and here. With the Normal AI able to hold its... Continue reading

### Twistago AI, part 2: Normal

This is the second part of a three-part series in which I explain how the artificial intelligence works in my latest game, Twistago. In case you missed the first part, you can catch up on it here. As you may recall, the Easy AI works by applying a value function... Continue reading

### Twistago AI, part 1: Easy

This is the first part of a three-part series in which I explain how the artificial intelligence works in my latest game, Twistago. The AI has three different levels: easy, normal and hard. This is also the order in which I developed them, each level building upon the lessons and... Continue reading

### Terrain variations in Dragon Attack

Earlier this week, I added some variations to the procedural terrain in Dragon Attack. Previously, the landscape was generated one segment at a time, forming a “chain” of rotated sprites. Each segment would have the same slope as the previous one, plus or minus a random number. To avoid going... Continue reading

### Listing cities for Orbital Express

For my game Orbital Express, I need a list of cities that can serve as targets for the player to aim at. We’re trying to select cities that… … are somewhat uniformly spread across the globe. That way, you won’t end up always having to aim for the same densely... Continue reading

### How to win at the game Pickomino

Pickomino (known as Regenwormen in Dutch, Heckmeck in German) is a dice game in which players try to get as many worms as possible. It is largely a game of chance, but there are some tactics involved, which always leaves me wondering: did I make the optimal choice? Only one... Continue reading

### A height map shader with only two texture lookups

Setup: suppose you have a monochrome texture that contains a height map. A value of 1 is highest, and 0 is lowest. You want to use this texture as a ‘bump map’ to shade a 2D polygon via GLSL, computing light and shadow from the gradient of the height map... Continue reading

### Getting a word list from WordNet

A good selection of words is essential for a fun drawing-and-guessing game; they must neither be too easy nor too difficult. However, I’m thoroughly lazy, so I was not going to compile a word list by hand. Instead, I used Princeton WordNet, which is essentially a graph linking English words... Continue reading

### The manager

The manager is the third and final part of the game’s AI. He is responsible for the high-level strategic decisions. The core of the manager is very simple. He searches the surroundings for potential objectives, divides the benefit of each objective by the cost, then instructs the Navigator to head... Continue reading

### The navigator

The Navigator is the part of the AI that is responsible for pathfinding. Actually, his algorithm is fairly straightforward. Given an objective by the Manager, the Navigator determines the shortest path through a series of waypoints that are defined in the level file, then hands each waypoint in turn to... Continue reading

### The driver, the navigator and the manager

The new AI is making good progress; I’d say it’s about 90% finished. (The other 90% remains to be done.) After writing the code, it cleanly fell apart into three largely independent modules. I like to name my classes after corresponding real-world things, so these are called the Driver, the... Continue reading

### Driver code

There are a handful of racing games that let you race purely against your own best time, but the majority of them let you race against others. It adds an element of competition that you don’t get when racing alone. The solitary racer is someone who spends hours trying to... Continue reading

### Free surface problems solved

Last week, I wrote to my fluid dynamics professor for advice on the free surface fluid simulation. It was a positive surprise to see that I had run into exactly the same problems as he had in his research. I must have been doing something right then! You might recall... Continue reading

### Fluid still failing

It’s been a busy week with little to show for it. As I wrote last time, I more or less gave up on the SPH particle-based method, and opted to fix my grid method instead. That turned out to be harder than I expected. As a first attempt, I tried... Continue reading

### Smoothed Particle Hydrodynamics

I realized that the problems I was having with the tracking of the water volume were not as easy to fix as I thought. It seemed that grid-based (Eulerian) methods are very suitable for a continuous fluid, but not so good when a sharp boundary between water and air is... Continue reading

### Lid driven cavity

Since no existing code fit my requirements, I started working on my own fluid simulator a few weeks ago. The idea was to try both a grid-based and a particle-based method, and see which worked better for my situation. I started with the grid-based version. My code was not based... Continue reading

### Previous work

I looked around for existing code or libraries to do the fluid simulation for me. There are some, but most are either GPL-licensed or too expensive, so they are out of the question for a small-time independent developer like me. Some publications exist on the topic, most notably Jos Stam’s... Continue reading