problem on a DFS-algorithm optimization
Hey guys, i've been working on a program that find the solution for the "Evil in Trouble" game.
You can find the game here on google play:
https://play.google.com/store/apps/details?id=com.ursinepaw.evilintrouble
This game is basicly like mario, so the problem is like the classic maze problem, and the algorithm i select is DFS, a very naive DFS search.
Since most of you have not played the game, the situation is, the maze problem has 4 kinds of movement: up, right, down, and left, and obviously the game maker would like to make it more funny by adding more kinds of "movements". There are 3 kinds of tools you could use: Hoe, Spade, Ladder, and to make things worse, in many levels the Evil will need to collect all keys to open the door.
So in this game i summarized 8 kinds of movments:
1.Go up
2.Go right
3.Go down
4.Go left
5.Use Hoe left side
6.Use Hoe right side
7.Use Spade
8.Use Ladder
For the algorithm, you won't need to know how exactly the hoe, spade, ladder does, so forgive me not explaining it.
This algorithm actually works, and by "works" i mean for most of levels it could give out the solution, though it's an O(8^n) algorithm. But for the last one or two level, the running-time will go crazy, once i ran it for 2 hours the program is still running!
So the problem is Optimization.
I did some work and noticed that in the recursion tree, many sub-trees are the same. So there should be a cut-off right? But how to cut them off? I mean there are so many situations, because for each tree node, the node will have:
1. the evil's attributes includes the hoe, spade, ladder, keys he's got.
2. the whole map, if a single block of the map is different then it's a whole new node!
Because of these, saving the sub-tree will take so many memory, can't afford thatr.
Can you help me please?
(If you need to see the source code just let me know and i'll up load it.)
You can find the game here on google play:
https://play.google.com/store/apps/details?id=com.ursinepaw.evilintrouble
This game is basicly like mario, so the problem is like the classic maze problem, and the algorithm i select is DFS, a very naive DFS search.
Since most of you have not played the game, the situation is, the maze problem has 4 kinds of movement: up, right, down, and left, and obviously the game maker would like to make it more funny by adding more kinds of "movements". There are 3 kinds of tools you could use: Hoe, Spade, Ladder, and to make things worse, in many levels the Evil will need to collect all keys to open the door.
So in this game i summarized 8 kinds of movments:
1.Go up
2.Go right
3.Go down
4.Go left
5.Use Hoe left side
6.Use Hoe right side
7.Use Spade
8.Use Ladder
For the algorithm, you won't need to know how exactly the hoe, spade, ladder does, so forgive me not explaining it.
This algorithm actually works, and by "works" i mean for most of levels it could give out the solution, though it's an O(8^n) algorithm. But for the last one or two level, the running-time will go crazy, once i ran it for 2 hours the program is still running!
So the problem is Optimization.
I did some work and noticed that in the recursion tree, many sub-trees are the same. So there should be a cut-off right? But how to cut them off? I mean there are so many situations, because for each tree node, the node will have:
1. the evil's attributes includes the hoe, spade, ladder, keys he's got.
2. the whole map, if a single block of the map is different then it's a whole new node!
Because of these, saving the sub-tree will take so many memory, can't afford thatr.
Can you help me please?
(If you need to see the source code just let me know and i'll up load it.)
Last edited on
so do you want to find algorithm to collect all keys, play the game, or shortest route to the door?
Yes i want to find a solution for each level, and in some levels you need to collect ALL KEYS to open the door so you can solve this level.
The program will print a step by step solution, follow the steps I'll be able to solve the level.
Am i making myself clear? Sorry for not making that clear at the beginning.
The program will print a step by step solution, follow the steps I'll be able to solve the level.
Am i making myself clear? Sorry for not making that clear at the beginning.
what you are asking is not efficient because you will have to get to each level before you can make an algorithm to solve the level, whereas you could have solved the level and more if you don't concentrate on writing code to do it for you.
What you need is a way of grabbing the data from each level, translating it into a readable form so that when fed to some piece of code will always find a route to get all keys at all times.
What you need is a way of grabbing the data from each level, translating it into a readable form so that when fed to some piece of code will always find a route to get all keys at all times.
@Smac89
First of all thanks for your reply.
And sorry i didn't mention that "data" part, I currently use the most naive way: I open the game on my phone, and input the data into the program according to the display on screen ( i've got a function that works like a map-editor, the function will store the data in a readable form), then I run the search to find the solution. Yes, for each level i have to input the map all by hands.
First of all thanks for your reply.
And sorry i didn't mention that "data" part, I currently use the most naive way: I open the game on my phone, and input the data into the program according to the display on screen ( i've got a function that works like a map-editor, the function will store the data in a readable form), then I run the search to find the solution. Yes, for each level i have to input the map all by hands.
Topic archived. No new replies allowed.