Archive for 'Game Development' Category

Sudoku Solver with recursive method

Sudoku Solver

Sudoku is a puzzle that uses numbers from 1 to 9 to match row, column, and 3×3 box with unique numbers.

I assume you are here because you want to learn how to find solutions to a Sudoku puzzle. I will show you how you can solve a Sudoku using recursive method. I will first explain what you have to do in English using pictures and then talk about codes in Java. This solution also works if you have cells preset as long as it’s valid.

You can download the demo program here and the whole project including source code here from github. For simplicity, the methods listed on bottom of this page are the ones used for “solving a Sudoku”.

Idea explained in plain English

1. Start from top left cell [0][0]. We will traverse from left-to-right and top-to-bottom.

2. If this cell passed the end [8][8], we will be at [9][0] . If current row is 9, return true indicating it is done as we have gone through all of the cells. This is the first thing to check in the method.

3. Generate 9 randomly ordered unique numbers 1-9, so we can test them one by one.


[Continue reading…]

Circle and Rotated Rectangle Collision Detection

Circle and Rotated Rectangle

I’m going to explain how to implement collision detection for circle and rotated rectangle. Collision detection is determining if object A is hitting object B. A circle has center x y position with a radius. A rectangle contains left top x y position, width, height, and the angle to be rotated with. We assume a rectangle rotates around its center point.

I will use applet, pictures, and code to show this. I read this article as a reference to understanding collision detection between a circle and a rectangle not rotated.

[Continue reading…]

Depth-First Search, Maze Algorithm

What is Depth-First Search?

Depth-first search is an algorithm that can be used to generate a maze. The idea is really simple and easy to implement using recursive method or stack.

Basically, you start from a random point and keep digging paths in one of 4 directions(up, right, down, left) until you can’t go any further. Once you are stuck, you take a step back until you find an open path. You would continue digging from there. It’s just the repetition of these.

First of all, I would like to explain the general idea a little deeper which you can apply using your choice of programming language. After you have the picture in your mind, you can take a look at the sample code and applet in java.

Explanation

Create a 2-dimensional int array with odd row and column size. 0 represents paths(orange cell) and 1 would be walls(black cell).

Explanation 1

Set all cells to 1(wall). There are no paths right now.

[Continue reading…]

Categories