Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 2 down vote favorite
1

I am programming the game that named Lights Out. The purpose of this game is turning all the lights out. There's a flash version of the game here. I want to develop a way of solving the game. How can I do this?

share|improve this question
I think what he wants is an AI algorithm that solves the game. I would suggest looking into backtracking. – jSepia Jul 15 '12 at 23:55
@jSepia : How to use backtracking on this game ? :-/ – Hossein Mobasher Jul 15 '12 at 23:59
Backtracking doesn't really work here because there's no notion of a 'maximum depth' - you'd want to explore the tree in breadth-first order, not depth-first (which is what backtracking does), but there are much better answers. – Steven Stadnicki Jul 16 '12 at 2:06
Have a look at math.stackexchange.com/questions/11091/… - while the specific question isn't germane to your problem, the lead answer there gives an excellent description of a mathematical approach to solving these problems that's probably what you want. – Steven Stadnicki Jul 16 '12 at 2:09
@StevenStadnicki: I found some perfect document to solve this game. I had restricted my view to just the programming algorithms, but the Math works better in this one. Thanks for your brilliant comment :) – Hossein Mobasher Jul 16 '12 at 14:03
show 1 more comment

1 Answer

up vote 2 down vote

You can use a tree. There are lots of ways to employ these and you will need to think carefully about which method will work best for your particular game - so some research should be done first.

To give a basic overview.

Start with the root node which will be your level's starting state. Create a branch for every possible action that can be performed at that point and have the node be the new game state after that action is performed. Repeat this for each node that's created.

Then what you need to do is find a node (which you can be looking for while building the tree) in which the game state is the level completed. Then walk back up the tree to the root node to get a list of actions that need to be performed to get to this "complete" state.

This may not be the best solution to your particular problem but it might steer you towards a solution. You might want to look into decision trees and path finding techniques for general interest, but also the reading might give you some ideas.

share|improve this answer
Hum, seems to be a good solution, but i am working on linear algebra now that explained in this link http://www.math.niu.edu/~rusin/uses-math/games/other/lights. Thanks for your solution :) – Hossein Mobasher Jul 16 '12 at 14:00
I think about your solution, but in this game, using tree of states surely has expensive cost on time. Because the time complexity is about 25^25 (because we should turn one light out in each state) – Hossein Mobasher Jul 16 '12 at 17:48
While it can be expensive it does depend on your implementation. You can always evaluate each state node and determine how likely it is to lead to a solution, then expand it before any others. You can also stop when the first solution is reached. Even if you do create every possible scenario, you can always pre-compute the solution for each level (if your levels are random, have them randomly generated and put the solvable ones in a grab bag it a solution). – OriginalDaemon Jul 17 '12 at 9:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.