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.)